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); 
}