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

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)$ $O (2^{N})$ such partitions to consider, and it takes $\mathcal O(N)$ $O (N)$ time to find the difference between the sum of the two partitions.

Time Complexity: $\mathcal O(N 2^N)$ $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}$ $F [i] [j] = {\begin{cases} 1 & if i = j = 0 \\ F [i - 1] [j - A [i]] & 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)$ $O (700 N)$ .

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

Comments

There are no comments at the moment.