29.04.2013  # 1 
Problem 300
This was, by some, the most difficult problem of the round. There are many possible approaches some faster than others. Lets call the number of characters in the input string N. In the problem N <= 100. This means that a bruteforce where you try every possible combination of cuts will timeout for sure. Complexity O( C(K,N) ). The approach that everyone who solved the problem used is dynamic programming. The state is dp[N][K] where dp<span>[j] denotes the best result we can get if we have processed digits [0,i) and have j cuts left. The easiest way to implement this is by recursion and memoization. Complexity O( N^2*K). This problem was initially intended to be worth 400 or 500 points with N <=100.000. Then, the solution would be the following. We binary search the space [0,MaxInt]. Say we are at some value X. It's easy to check if the original string can be cut K times so that the largest piece is less than or equal to X(greedy, add digits while they are less than X, otherwise make a cut). </span> In order to use a binary search on a function it must be monotonic(strictly increasing or strictly decreasing). Well it's easy to see that if there is a solution for some value X, than there is a solution for every value Y > X as well and if there is no solution for X then there is also no solution for every Y < X. (see? monotonic ) This solution has complexity O(N*log(MaxInt)) = O(32*N) = O(N) (almost linear )

