Post 29.04.2013   # 1
Subject 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 brute-force where you try every possible combination of cuts will time-out 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 )

#include <vector>

#include <string>

using namespace std;

#define MAXINT 2147483647

class Cuts



///try to make k cuts on the string s where the largest part will be at most x

    bool ok(string s,int x,int k) {

        long long current = 0;

        for(int i=0; i

            if(current*10 + s-48 <= x) {

                current = current * 10 + s-48;

            } else {

                if(s-48 > x) return false;


                current = s-48;



        return k>=0;


    int getMax(string s, int k) {

        int l = 0,r=MAXINT,m,result = MAXINT;

///binary search the result

        while(l<=r) {

            m = (l+r)/2;

            if( ok(s,m,k) ) {

                result = m;

                r = m-1;

            } else l = m+1;


        return result;



vasja is offline Reply
Post 29.04.2013   # 2

I think you should just leave the complexity O(N*log(MaxInt)). It is not linear complexity. You cannot map log(MaxInt) into a constant. The variables should be left as they are.

Best regards

igorkulev is offline Reply
Post 29.04.2013   # 3

Yeah, thats why i wrote almost linear and put a smiley over there.

But hey, thanks for the feedback

vasja is offline Reply

Please login to post reply.