Editorial for DMOPC '18 Contest 4 P2 - Dr. Henri and Responsibility

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: Kirito

For $20\%$ ~20\%~ of points, we can consider each possible partitioning scheme. There are $\mathcal O(2^N)$ ~\mathcal O(2^N)~ such partitions to consider, and it takes $\mathcal O(N)$ ~\mathcal O(N)~ time to find the difference between the sum of the two partitions.

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

For the remaining $80\%$ ~80\%~ of points, we can solve this problem with dynamic programming. We let $F[i][j]$ ~F[i][j]~ be true if there exists a subset of the first $i$ ~i~ tasks that sums to $j$ ~j~. We obtain the recurrence:

$\displaystyle F[i][j] = \begin{cases} 1 & \text{if } i = j = 0 \\ F[i-1][j-A[i]] & \text{otherwise} \end{cases}$

If we directly implement this, saving the result to each visited state, our array will be too big. However, we see that for each $i$ ~i~, $F[i][*]$ ~F[i][*]~ is dependent on only $F[i-1][*]$ ~F[i-1][*]~. Thus we save only the previous row, for a memory complexity of $\mathcal O(700N)$ ~\mathcal O(700N)~.

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

Comments

There are no comments at the moment.