## Thursday, April 11, 2013

### SRM 576 : If only...

With anxiety-caused symptons getting worse than I ever imagined, I had some distractions during this SRM, but once I began to code the div1 576's solution, I could distract my brain and feel good for a while. Therapy by TopCoder sounds like a promising field of research for whoever wants to investigate how to reduce stress crisis in programmers.

## Div1 576 : The one with sponges

You got up to 300 things that make s[i] drops fall per minute, they are all aligned in a horizontal line and with a distance of 1 between them. You want to place up to M sponges of length L bellow these things that drop, in a way that each sponge receives between A and B drops per minute. If we number drop things from 0 to n-1, then each sponge must be at a horizontal position (left-most border) that matches the position of a drop between 0 and n - L. You can place sponges below other sponges, the sponges above intercept the drops. Count the total number of ways. Two ways are considered the same if for each sponge Q in the first way, there exists a sponge P that absorbs exactly the same set of drops.

With n <= 300, the worst complexity we could have is O(n3), so we need to be clever. I had the most difficulty trying to interpret the main rule. Then it appears to be complicated to optimize...

Let us make an array good[i][j] if it is a good idea to have a sponge that absorbs the drops between i and j. (The total number of drops per minute is between A and B). We can see the problem as assigning sponges in a way that the drops they receive come from a good interval. Of course, doing such an assignment is not always possible.

The trick is to notice that for each set of contiguous intervals that were picked to have a sponge. The necessary and sufficient condition for it to have a solution (and a unique solution) is that at least one of the intervals is of size L.

With that in mind, it is simple to make a dynamic programming with three states: [x][M][state], where x is the number of positions that were already processed. state is 0, if the last position does not contain a sponge, 1 if the last position contains a sponge and such set of contiguous intervals does not ye contain a interval of length L, and 2 otherwise.

const int MOD = 1000000009;struct TheExperiment{    string s;        bool good;        int L;    int dp;    int mem(int x, int m, int didL)    {        int & res = dp[x][m][didL];        if (res == -1) {            if (x == s.size()) {                res = ( (didL != 1) && (m == 0) );            } else {                res = 0;                if (m > 0) {                    for (int y = 1; (y <= L) && (x + y <= s.size()); y++) {                        if (good[x][x + y]) {                            int nd = didL;                            if (y == L) {                                nd = 2;                            } else if ( didL == 0 && y != L ) {                                nd = 1;                            }                            res += mem(x+y, m- 1, nd );                            if (res >= MOD)  res -= MOD;                        }                    }                }                if (didL != 1) {                    res += mem(x + 1, m , 0 );                    if (res >= MOD)  res -= MOD;                }            }        }        return res;    }            int countPlacements(vector <string> intensity, int M, int L, int A, int B)    {        memset(dp, -1, sizeof(dp));        s = accumulate(intensity.begin(), intensity.end(), string(""));        this->L = L;                int acum;        acum = 0;        for (int i=0; i<s.size(); i++) {            acum[i + 1] = acum[i] + s[i] - '0';        }        for (int i=0; i<=s.size(); i++) {            for (int j=i; j<=s.size(); j++) {                int total = acum[j] - acum[i];                good[i][j] = ( A <= total && total <= B);            }        }        return mem(0, M, 0);            }};

I took long to think of the solution. But I was barely able to finish the code and pass examples before the 10 minutes mark. I was thrilled to find that I was going to have 10 minutes to solve div1 easy. Too bad it turned out to be the kind of problem that is complicated to implement. I could implement the code in 10 minutes, but it had mistakes.

I fear my div1 576 may have code mistakes, I am not performing at 100% :(.