Contest Duration: - (local time) (180 minutes) Back to Home

B - Taking the middle Editorial by evima

For each $$1 \leq i \leq N$$, in Aoki’s $$i$$-th turn, there are $$2(N-i)+1$$ cards. The median of the ID numbers of those cards is between $$N-i+1$$ and $$N+i$$ (inclusive). Thus, for each $$1 \leq i \leq N$$, Aoki has $$i$$ or more cards with ID numbers between $$N-i+1$$ and $$N+i$$.

On the other hand, it turns out that every set of cards containing $$i$$ or more cards with ID numbers between $$N-i+1$$ and $$N+i$$ for each $$1 \leq i \leq N$$ can be the set of cards Aoki has in the end, which we can prove by mathematical induction on $$N$$. Thus, we just have to find the minimum possible value of a set of cards satisfying this condition, which we can find by the following algorithm:

• For each $$i = 1, \ldots, N$$ in this order, do the operation below to choose a total of $$N$$ cards. The total value of those cards is the value we seek.
• Among the unchosen cards with ID numbers between $$N-i+1$$ and $$N+i$$, choose the card with the least value.

We can make this algorithm work in $$O(N\log N)$$ time with a priority queue, for example.

posted:
last update: