Editorial for DMOPC '18 Contest 4 P3 - Dr. Henri and Ionization
Submitting an official solution before solving the problem yourself is a bannable offence.
Note that we can always do the individual removals first, then all the pair removals at once. This way, we ignore the entire "opposite" condition. This simplifies the problem to choosing between pairs or individual removals. Now the problem is simply to choose between and values so that an even number of values is chosen and the sum is minimized. This can be done using dynamic programming. Specifically, let be the minimum sum where exactly values have been chosen so far, and we are only considering the first electrons (arbitrary ordering). Then . The final answer is .
For the full solution, note that only matters. So we only need to consider and . There are now only states rather than .