## Friday, September 07, 2012

### SRM 555: 5555555555555555555555

Yeah, I posted it in the TCO blog: http://community.topcoder.com/tco12/srm-555/. Let me talk of what was going on to me:

### Waking up at 6:30

I had it all planned up, and set things up to wake up at 6:30, so I could register (Really did not expect it to get any close to the registrants limit).

Unfortunately, I spent just about the whole period from 05:00 to 06:00 waking up to the same lame dream: that I missed the SRM. Only to find out that it was 5:00 and was way early. Arrg, I think it happened at least three times.

### Div1 255

Meh, it seems that my brain was not awake when I first tried to solve this problem. At first I thought it was about splitting in multiples of 5 instead of powers of 5. My first code even had funny tricks to avoid considering a single "0" as a number that begins with leading zeros... The whole plan was to simply get the results modulo 5 when translating bits to integer. It was so clever...

But it failed examples. So, it needed powers of five... I had to fix stuff, but had some lame bugs and it delayed me. At the end , 215 points. Is way too slow. My only hope was the div1 555...

### Div1 555

I actually saw the correct solution (although overcomplicated by dp for the sub-problem instead of even more binomials.) instantly. Of course, after coding everything here were bugs and bugs. I reached a state in which I was passing all examples but the second-last and third-last. Which was very puzzling, because the example that was seemingly the most complicated (last one) was correct. Surely, with 32 minutes left, I would eventually find the mistake, right? ... right?

I tried many things. I noticed the main difference between the examples I was passing and those I was not was that they were the only cases in which Rcount != Ccount, so I was trying to find any bugs related to it. Then I tried other things, and many others. But I effectively had 31 minutes with the same wrong code and no idea what to do. I even doubted the approach, but it really seemed right.

During the challenge phase, I checked out the other solutions and they were using the same logic. After some time off I opened it in the practice room, and could finally see the mistake right away. It is such a stupid mistake that it makes the drop to 18XX rating even more sad. You can see the code I had during the contest. The bug is with subProblem(er/2, Rcount) (and its column analogous), it should be: subProblem(er/2, H), of course, because the first expression makes no sense. I think I quickly replaced a different bug with Rcount and Ccount without putting a lot of thought and then completely missed it. I did not notice that it was also a main trait of the test cases I was failing, that W!=Rcount and H!=Ccount.

Anyway, this whole thing of SRMs made with mixed problem setters that turn out to have very easy div1 250 and div1 500 that everyone solves except for me that take too long or have bugs is really getting old. It is a perfect rating killing storm.

### Codes!

div 2 easy, is really easy:

int theMax(vector <string> board) {     int h = board.size(), w = board[0].size();     int res = 0;     // pick a row     for (int i=0; i<h; i++) {         // pick a column         for (int j=0; j<w; j++) {             int ones = 0;             // count the ones             for (int a=0; a<h; a++) {                 for (int b=0; b<w; b++) {                     // the xor operation ^, is great to simlate toggling...                     int o = ( (board[a][b]=='1') ^ (a==i) ^ (b==j) );                     ones += o;                 }             }             res = std::max(res, ones);         }     }     return res; }

div2 medium / div1 easy: The lack of a c++ library function to convert a integer to binary is really lame.

int getmin(string s) {     int n = s.size();     int dp[n+1];     dp[0] = 0;     int INF = 100;          // make the powers of 5:     long long p = 1;     string pow5[100];     int q = 1;     pow5[0] = bit(p); // the bit(x) function returns x in binary.     while (p <= (1LL<<62) / 5) {         p *= 5;         pow5[q] = bit(p);         q++;     }          // dp part:     for (int t=1; t<=n; t++) {         dp[t] = INF;         for (int i=0; i<q; i++) {             // does it end with the i-th power of 5?             int len = pow5[i].size();             if ( (t - len >= 0) && ( s.substr(t-len, len) == pow5[i] ) ) {                 //Yes. Yes, it does.                  dp[t] = std::min(dp[t], dp[t - len] + 1);             }         }     }     return ( (dp[n] >= INF) ? (-1) : dp[n] ); }

div2 hard: This guy was completely not standard and not easy (at least not for me.) I think I needed a lot of thought to reach the good method to do a dp program. Like I said in the TCO blog, it is all about what starting point you use for the analysis. I was trying bottom-up dp instead of top-down and it was a true nightmare. (For me, this is the hardest div2 hard in a while).

const int MOD = 555555555; typedef long long int64; #define long int64 long dp[555][554][2][2]; struct MuddyRoad2 {     int theCount(int N, int muddyCount)     {         memset(dp, 0, sizeof(dp) );         dp[0][0][1][1] = 1;         dp[0][0][0][0] = 1;                  //dp[i][m][p1][p2] returns the total number of ways         // to set muddy segments if:         // * We have already assigned segments higher than i         // * p1 is the parity of the number of paths for i+1         // * p2 is the parity of the number of paths for i+2         // * There are m muddy roads left to mark.         //         for (int i=1; i<=N-1; i++) {             for (int p1 = 0; p1 < 2; p1++) {                 for (int p2 = 0; p2 < 2; p2++) {                     for (int m=0; m<=muddyCount; m++) {                         long & res = dp[i][m][p1][p2];                         // do nothing                         res = dp[i-1][m][ (p1 ^ p2)  ][p1];                         // place a 0                         if ( (m > 0) && (i < N-1) ) {                             res += dp[i-1][m-1][0][p1];                             res %= MOD;                         }                     }                 }             }          }         // this way p1^p2 = 1 for i=N-1 :)         return dp[N-1][muddyCount][0][1];     } }; #undef long

Div1 medium: This dreaded problem was easy but that's not a good thing when you do it wrong for a lame reason and everyone else solves it.

 long C[3200][3200]; int count(int H, int W, int Rcount, int Ccount, int S) {     long res = 0;     memset(C, 0, sizeof(C));     // Pascal's triangle is a combinatorics problem coder's best friend     for (int i=0; i<=3199; i++) {         C[i][0] = 1;         for (int j=1; j<=i; j++) {             C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;         }     }     for (int r = (Rcount % 2); r <= Rcount && r <= H; r += 2) {         for (int c = (Ccount % 2); c <= Ccount && c <= W; c += 2) {             int tem = (H - r) * c + (W - c) * r;             if (tem == S) {                 cout << r << ", "<<c<<endl;                 int er = (Rcount - r)/2;  //extra                 int ec = (Ccount - c)/2;                 long prod = 1;                 prod = (prod * C[H][r]) % MOD;                 prod = (prod * C[W][c]) % MOD;                 prod = (prod * C[H-1 + er][H-1]) % MOD;                 prod = (prod * C[W-1 + ec][W-1]) % MOD;                 res += prod;             }         }     }     return (int)(res % MOD); }

Tm3dantes said...

Hi Vexorian,

I still don't understand SRM 555 Div 2 Hard. What does parity have to do with finding the number of ways?
For prob statement N=10 and muddyroads as 4, I counted the VALID number of ways you can have 4 muddy roads and be able to get through to the friend's house as 5. Do we also count the last 1 b/c the other 64 ways are INVALID? Also, I did a quick test with how many ways you can have 4 muddy roads in 8 slots, and came up with 70?

Thanks,
tm3

vexorian said...

The problem statement asks you to count the number of ways to assign the muddy road. So that the NUMBER OF WAYS to move from 0 to N-1 is EVEN.

So when I say parity, I mean the piirty OF the number of ways.

It is the same as saying "Calculate the number of ways" modulo 2.

So in fact f(x) is 0 if the number of ways to move from x to n-1 is even and 1 if it is odd.

When you see it as parity, then you can see that making a certain road muddy will make its number of ways to go from that road to n-1 ZERO and zero is even, so the parity is 0. Thus making a road segment muddy is the same as forcing the parity (the result of f(x) ) to be 0.

Otherwise, if we do not make the road segment muddy, then the parity of the number of ways to go from x to n-1 depends on : f(x+1) and f(x+2). Which takes us to the dp:

dp[x][m][p1][p2]

p1 is f(x+1) and p2 is f(x+2). So they are used to calculate the parity of f(x) in case we do not make the road muddy.

It means we have two choices:
* Make road x muddy: f(x) becomes 0 and m is reduced by 1.
* Do not make road x muddy: f(x) = ( f(x+1) + f(x + 2) ) % 2 = (p1 + p2)%2, m stays the same.

f(x) and p1 will become p1 and p2 for the next case.