Editorial for DMOPC '18 Contest 4 P3 - Dr. Henri and Ionization
Submitting an official solution before solving the problem yourself is a bannable offence.
Author:
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
.
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:
Comments
In fact, you can sort the electrons by
, and take two at a time, until it cannot be improved, which is an
solution.