Editorial for COCI '07 Regional #4 Jednakost

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.

We solve the problem with dynamic programming. Consider the digits in left to right order, deciding where to place addition operators, keeping track of how much of the sum we still need to account for. The state is an ordered pair $(position, remaining\ sum)$ ~(position, remaining\ sum)~.

The smallest number of addition operations can be calculated as follows:

For $sum < 0$ ~sum < 0~, $opt(position, remaining\ sum) = \infty$ ;
For $position = N$ ~position = N~ and $remaining\ sum > 0$ ~remaining\ sum > 0~, $opt(position, remaining\ sum) = \infty$ ;
For $position = N$ ~position = N~ and $remaining\ sum = 0$ ~remaining\ sum = 0~, $opt(position, remaining\ sum) = 0$ ~opt(position, remaining\ sum) = 0~;
Otherwise, $\displaystyle opt(position, remaining\ sum) = \min_{position \le i \le N} opt(i+1, (remaining\ sum)-number(position \dots i))$ where $number(A \dots B)$ ~number(A \dots B)~ is the number represented by digits $A$ ~A~ through $B$ ~B~ (inclusive).

After calculating and storing the values, the above relation can be used to reconstruct the solution.

Comments

There are no comments at the moment.