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\% of points, we can consider each possible partitioning scheme. There are \mathcal O(2^N) such partitions to consider, and it takes \mathcal O(N) time to find the difference between the sum of the two partitions.

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

For the remaining 80\% of points, we can solve this problem with dynamic programming. We let F[i][j] be true if there exists a subset of the first i tasks that sums to 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, F[i][*] is dependent on only F[i-1][*]. Thus we save only the previous row, for a memory complexity of \mathcal O(700N).

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


Comments

There are no comments at the moment.