candypinkmagicholeflipflop

Sort the coins by increasing $X_i$, and let $w_i$ be the weight of the $i$-th coin in this order.

Two unflipped coins are always compatible as neighbors, whereas two flipped coins are never compatible. If exactly one of two neighboring coins is flipped, the condition holds precisely when the flipped coin has the larger $X$.

Let $f_i$ be the number of flipped coins among the first $i$ coins in sorted order. Every flipped coin in such a prefix needs two neighboring, unflipped coins with smaller $X$. Unless the prefix contains the entire circular arrangement, the induced paths must therefore contain at least one more unflipped coin than flipped coins. Consequently every feasible selection satisfies

$$f_i \le \left\lfloor \frac{i-1}{2} \right\rfloor \quad (1 \le i < N), \qquad f_N \le \left\lfloor \frac{N}{2} \right\rfloor.$$

These inequalities are also sufficient. List the unflipped coins as $u_1,u_2,\ldots,u_m$ and the flipped coins as , each in increasing order of . If , arrange them as . If , arrange in a circle. The prefix inequalities ensure that every flipped coin has strictly larger than each adjacent unflipped coin.

It remains to maximize the sum of weights subject to these nested prefix-cardinality limits. Process the coins in increasing order of $X$, inserting each weight into a min-heap. Whenever the heap size exceeds the limit for the current prefix, remove the smallest weight. The retained set is a maximum-weight feasible choice under all processed prefix limits. The final heap sum is the answer.

Sorting and heap operations take $O(N\log N)$ time and $O(N)$ space.

Solution written by GPT6