Codeforces Round 1070 (Div. 2) C. Odd Process.
The problem statement
Given \(n\) integers, for each \(k\) between \(1\) and \(n\) inclusive, the problem asks to form a \(k\)-length sequence of the integers with the maximum sum with the following rule: each time the sum becomes even, the sum obtained so far is discarded.
Initial observations
For smaller \(k\)s, the following strategy looks promising: starting with the largest odd number, keep adding even numbers in descending order with it.
- We have to choose at least one odd because choosing only evens gives an even sum and is discarded.
- Choosing only one odd and the maximum odd is optimal because choosing one more gives an even sum, and the sum is discarded.
Therefore, in this strategy, the sum increases while remaining odd at the same time.
Now, what to do for larger \(k\)s, when there are not sufficient evens—there is a deficit in evens? We have no other choice than to compensate for the deficit from the odds.
How to choose odds compensating the deficit
Let \(x\) be the length of the sequence consisting of the largest odd and all the evens. Let the deficit be \(d = \max(0, k - x)\). For the first \(x\) integers of the desired sequence, the strategy and the sum remain the same. After that, depending on the parity of \(d\), there are two possibilities for compensating:
- If \(d\) is even, we choose the deficit from the odds. Regardless of their values, the chosen odds eliminate each other, without affecting the sum obtained from the first \(x\) integers.
- Otherwise, we choose \(d +1\) odds so that the pairs eliminate each other, sacrificing the smallest even from the sum. We have to make sure that \(d + 1\) odds are available; otherwise, the sum is \(0\).
Two extreme cases
The following two extreme cases, where all the \(n\) integers are either odd or even, need additional care:
- If all the \(n\) integers are odd and \(k\) is even, the sum is \(0\), because an even number of odds gives an even sum. The odd \(k\) case, where the sum is the largest odd, is covered by the strategy above.
- If all the \(n\) integers are even, on the other hand, then the sum is \(0\), because any number of evens adds up to even.
Implementation
- Sort odd and even in two separate partitions in descending order. Find out the first or the largest odd number.
- For each \(k\), choose the sum of \(k-1\) evens in descending order. Note: Have the prefix sum precalculated; without it, the solution exceeds the time limit.