Editorial for COCI '16 Contest 4 #3 Kas

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.

The entire task comes down to correctly distributing the banknotes as described in the first paragraph of the task. So, we need to distribute some of $N$ ~N~ banknotes into two parts so that the sum of the money in each of the two parts is equal, and the total sum of the money of the unused banknotes is the smallest possible.

Using a naive algorithm, we could have tried out every possible combination and get $50\%$ ~50\%~ of total points. Since each banknote can end up with either Kile or Pogi or nobody, we can conclude that the time complexity of such algorithm is $\mathcal O(3^n)$ ~\mathcal O(3^n)~.

Similar to the previous thought process, let's imagine that we iterate respectively over the banknotes and try assigning them to Kile, Pogi, or nobody. In any step of such an algorithm, we should know which banknote we are currently processing and how much money have Kile and Pogi collected so far. Let $f(k, a, b)$ ~f(k, a, b)~ be a function that returns the largest possible sum of money that Kile and Pogi can collect if after $k-1$ ~k-1~ distributed banknotes Kile has $a$ ~a~ kn, and Pogi has $b$ ~b~ kn.

Evidently, $f(k, a, b) = \max\{f(k+1, a, b), f(k+1, a+c[k], b), f(k+1, a, b+c[k])\}$ where $c[k]$ ~c[k]~ denotes the value of the $k^\text{th}$ ~k^\text{th}~ banknote. Of course, $f(n+1, a, b) = 0$ ~f(n+1, a, b) = 0~ if $a$ ~a~ is different than $b$ ~b~, or $a$ ~a~ in the contrary. If we implement such a solution using the technique of dynamic programming, we have constructed an algorithm of the complexity $\mathcal O(ns^2)$ ~\mathcal O(ns^2)~, where $s$ ~s~ represents the sum of all banknotes.

To obtain all points, it was necessary to notice that it is sufficient to keep track in the state the absolute value of the difference of the amount of money Kile and Pogi have collected so far. We transition from state $f(k, diff)$ ~f(k, diff)~ to states $f(k+1, diff)$ ~f(k+1, diff)~, $f(k+1, diff+c[k])$ ~f(k+1, diff+c[k])~ and $f(k+1, |diff-c[k]|)$ ~f(k+1, |diff-c[k]|)~ that represent, respectively, skipping of a banknote, assigning a banknote to the person currently having more money, and assigning a banknote to the person currently having less money. Since we have $\mathcal O(ns)$ ~\mathcal O(ns)~ states, and the transition is constant, we can conclude that the algorithm is of the complexity $\mathcal O(ns)$ ~\mathcal O(ns)~, which is sufficient to obtain all points.

Even though this wasn't a requirement in the task, we advise you to think of an algorithm to solve this task with a memory limitation of 32 MB.

Comments

There are no comments at the moment.