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.

Authors: 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][1], F[i][2], F[i][3], F[i][4], \ldots is dependent on only F[i - 1][1], F[i - 1][2], F[i - 1][3], F[i - 1][4], \ldots. 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.