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.

Author: 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. This simplifies the problem to choosing between pairs or individual removals. Now the problem is simply to choose between $a$ ~a~ and $b$ ~b~ values so that an even number of $b$ ~b~ values is chosen and the sum is minimized. This can be done using dynamic programming. Specifically, let $dp[i][n]$ ~dp[i][n]~ be the minimum sum where exactly $i$ ~i~ $b$ ~b~ values have been chosen so far, and we are only considering the first $n$ ~n~ electrons (arbitrary ordering). Then $dp[i][n] = \min(dp[i-2][n-1]+b_n, dp[i-1][n-1]+a_n)$ . The final answer is $\min(dp[0][N], dp[2][N], dp[4][N], \dots)$ .

Time Complexity: $\mathcal{O}(N^2)$ ~\mathcal{O}(N^2)~

For the full solution, note that only $i \bmod 2$ ~i \bmod 2~ matters. So we only need to consider $i = 0, 1$ ~i = 0, 1~ and $dp[i][n] = \min(dp[i][n-1]+b_n, dp[1-i][n-1]+a_n)$ . There are now only $\mathcal{O}(N)$ ~\mathcal{O}(N)~ states rather than $\mathcal{O}(N^2)$ ~\mathcal{O}(N^2)~.

Time Complexity: $\mathcal{O}(N)$ ~\mathcal{O}(N)~

Comments

1

johnathan79717 commented on Dec. 16, 2018, 4:50 p.m. ← edit 3 →

In fact, you can sort the electrons by $b_i - a_i$ ~b_i - a_i~, and take two at a time, until it cannot be improved, which is an $\mathcal{O}(N \log N)$ ~\mathcal{O}(N \log N)~ solution.