Editorial for DMOPC '18 Contest 4 P3 - Dr. Henri and Ionization

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

Authors: r3mark

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 and 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 .

Time Complexity:

For the full solution, note that only matters. So we only need to consider and . There are now only states rather than .

Time Complexity: