Number Split

topCoder: NumberSplit

By Editorial:

The first thing to notice here is that the numbers in every step become smaller. Let's take an example and say we have a five digit number of the form abcde (a, b, c, d and e represent the decimal digits of the number), which we split to produce the successor: ab * c * de. Here it is always c < 10 and de < 100, so for the successor we have: ab * c * de < ab * 10 * 100 = ab000 ≤ abcde. Similar with any other numbers and splittings.

Now we need a way to compute all possible successors, given a given number. For this we can use the following recursive pseudo-code:

generateSuccessors(int multiplier, int n) {
    add (multiplier * n) to the set of successors
    for (i = 10; i <= n; i *= 10) {
       generateSuccessors(multiplier * (n / i), n % i);
    }
}

We initialize the set of successors to an empty set, and call generateSuccessors(1, n) (where n is the number, for which we want to find the successors). Finally, we remove n from the generated set (since this is not a successor of n itself, we need to split the given number to at least two parts for a successor to be valid).

To compute the longest possible sequence, starting with the given start, generate all successors of start as described above, and for each n in the successor set compute recursively longestSequence(n). The return value is the maximum of all computed values + 1 (if start is a single digit number, the successors set will be empty, and we return 1). Note that this would not work if loops in the sequence were possible, but since each successor is smaller then the original number, this can not happen. In order to avoid a timeout, we need to memorize in a buffer all values already computed.

Alternatively, we can use dynamic programming, by initializing longest[i] = 1 for all single digit numbers i, and computing longest[i] from i = 10 up to i = start by adding 1 to the maximum of longest[j] for all j in the successor set of i. This works, since all successors of i are smaller than i. With this solution, we compute the longest sequence for more numbers than actually needed (many numbers between 1 and start can not be reached from start) but with the low constraints this solution was within the time limit.

my dp code with memoization (note: topCoder does not have itoa)

void itoa(int n, char* buff) {
    sprintf(buff, "%d", n);
}
// memoization array
int a[999999];
int solve(string s) {
    int ss = atoi(s.c_str());
    if(a[ss] != -1) return a[ss];
    char buff[10];
    if(s.length() == 1) return 1;
    int res = 0;
    for(int i = 1; i < s.length(); ++i) {
        // single split
        int left  = atoi(s.substr(0,i).c_str());
        int right = atoi(s.substr(i).c_str());
        itoa(left*right, buff);       
        checkmax(res, 1+solve(string(buff)));
        string rights = s.substr(i);
        if(rights.length() <= 1) continue;

        // this part does double split
        for(int j = 1; j < rights.length(); ++j) {
            int lleft  = atoi(rights.substr(0,j).c_str());
            int lright = atoi(rights.substr(j).c_str());
            itoa(left * lleft * lright, buff);
            checkmax(res, 1+solve(string(buff)));
        }           
    }
    return a[ss] = res;
}

int NumberSplit::longestSequence(int start) {
    char buff[10];
    itoa(start,buff);
    memset(a, -1, sizeof(a));
    string s(buff);
    return solve(buff);
}