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^{3}), 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% :(.

## No comments :

Post a Comment