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.

last update: