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[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 :