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(n³), 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[301][301];
    
    int L;
    int dp[301][301][3];

    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[301];
        acum[0] = 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% :(.