SRM 554

I posted something about SRM 554 TCO blog. Extra comments:

I had quite a silly luck this time. I do not why, but I took very long in the 250 points one. Probably because I went from the general case to the specific case instead of the opposite. So I was just about to solve the problem finding the union of three arithmetic sequences, until I started doing an extra analysis to notice that many of the intersections are not possible.

Pretty code for that problem:

int find(int redCount, int redHeight, int blueCount, int blueHeight) 
{ 
    return  
         + min(redCount, blueCount) 
         + 1 + min(redCount-1, blueCount) 
         + 1 + min(redCount, blueCount-1) 
         - (redHeight == blueHeight) * (min(redCount, blueCount) ); 
} 

For div1 500, I messed up even more spectacularly. I reached the conclusion of the condition that was necessary to reach the optimal result (but I did not think to prove that it is also sufficient, knowing that it was also sufficient would have saved me a lot of problems). The problem is that after that, I used a dynamic programming approach. I took some time to code it, until I found that I was failing the last example (Which does not make sense, because the condition IS necessary). I did a quick fix by adding a dimension to the dp. The quick fix was not necessary, but it passed the examples so I submitted the problem.

Then I noticed that I had too many dimensions and my approach could be too slow (It was n⁶ in theory, but maybe it runs faster). I tried some random test cases, until I found one that was not timing out, but instead breaking an assertion I added while debugging the first bug. It turns out that I was sorting an array after I make the copy that was in use by the dynamic programing algorithm. So, I fixed that bug, which fixed the assertion, but now, as I suspected, was timing out. I figured that maybe that lame bug was the one that caused my initial solution to fail. There was only 1 minute left. Somehow, I managed to get rid of the extra dimension in the dp, pass examples and re-submit before the end of the coding phase.

Challenge phase was more about feeling very nervous. I felt the approach was right, but overcomplicated , so there was plenty of room for failure. At the end I passed. (yay)

Here is pretty code for it:

vector<int> find(vector<int> heights) 
{ 
    int n = heights.size(); 
    vector<int> res(n, 0), used(n, false); 
    used[0] = true;  
    //res[0] = 0 is always possible. 
    // Yes, it is always possible to choose any arbitrary first element and still 
    // follow the condition (non-increasing and then non-decreasing) 
    // 
    for (int i=1; i<n; i++) { 
        for (int j=n-1; j>=0; j--) { 
            if (! used[j]) { 
                if (heights[j] <= heights[ res[i-1] ] ) { 
                    //this is always fine. 
                    // If an element j exists such that: 
                    //   heights[j] < heights[res[i-1]) 
                    // 
                    // It means that the next case was never reached. Thus it is 
                    // still possible to do it. 
                    // 
                    // if heights[j] = heights[res[i-1]], then it can count as 
                    // either of the cases and also fine. 
                    res[i] = j; 
                } else { 
                    // If the new element is greater, then it must forcefully be 
                    // equal to the minimum of the remaining elements so that the 
                    // rest of the elements are placed in non-decreasing order.  
                    bool can = true; 
                    for (int k=0; k<n; k++) { 
                        can &= (used[k] || (heights[k] >= heights[j]) ); 
                    } 
                    if (can) { 
                        res[i] = j; 
                    } 
                } 
            } 
        } 
        used[res[i]] = true; 
    } 
    return res; 
} 
 

As you can see, Figuring out (and proving) that the condition is not only necessary but also sufficient allows a VERY simple approach.

Div2 1000 was cute. Here is code for it too:

const int MOD = 1234567891; 
#define for_each(q, s) for(typeof(s.begin()) q=s.begin(); q!=s.end(); q++) 
struct TheBrickTowerHardDivTwo 
{ 
    int pow5[5]; 
    int mem[8][48][5*5*5*5]; 
     
    // I encode each state as a single number in base 5. 
    // (I added a fifth color that is a wildcard. So that the top-most row 
    // in a dp can add any colors without decreasing K). 
    // 
    // The transition array saves all the possible transitions from a state 
    // of colors to another AND the value we have to decrease from K. 
    // It is sorted non-decreasingly by the value to decrease from K, so that 
    // we can stop when K would get less than 0. 
    vector<pair<int,int> > transition[5*5*5*5]; 
     
     
    int rec(int K, int H, int state) 
    { 
        int &res = mem[K][H][state]; 
        if (res == -1) { 
            if (H==0) { 
                res = 1; //empty 
            } else { 
                long long tem = 0; 
                // Iterate through the list of transitions, try the transition 
                for_each(q, transition[state]) { 
                    int nk = K - q->first; 
                    if (nk >= 0) { 
                        tem += rec(nk, H-1, q->second); 
                    } else { 
                        break; 
                    } 
                } 
                res = (int)( tem % MOD); 
            } 
        } 
        return res; 
    } 
     
    int find(int C, int K, int H) 
    { 
        pow5[0] = 1; 
        for (int i=1; i<=4; i++) { 
            pow5[i] = 5*pow5[i-1]; 
        } 
        memset(mem, -1, sizeof(mem)); 
         
        // make the transitions 
        for (int state=0; state<pow5[4]; state++) { 
            for (int newstate=0; newstate < pow5[4]; newstate++) { 
                bool valid = true; 
                int krem = 0; 
                for (int i=0; i<4; i++) { 
                    int x = (newstate / pow5[i])%5; 
                    // use only C colors... 
                    valid &= ( x < C); 
                    // sharing face with the above brick 
                    if ( (state/pow5[i]) % 5 == x) { 
                        krem++; 
                    } 
                    // We represent the colors in this way. 
                    // [0][1] 
                    // [3][2] 
                    // This means that a cube is adjacent to the next and previouis 
                    // index. Which translates to us needing to check index (i+1)%4 
                    int y = (newstate / pow5[ (i+1) % 4 ]) % 5; 
                    if (y == x) { 
                        krem ++; 
                    } 
                } 
                if (valid && (krem <= K) ) { 
                    transition[state].push_back( make_pair(krem, newstate) ); 
                } 
            } 
            sort(transition[state].begin(), transition[state].end()); 
        } 
        long long res = 0; 
        for (int i=1; i<=H; i++) { 
            res += rec(K, i, pow5[4] - 1 ); 
        } 
        return (int)(res % MOD); 
    } 
};