Constructing Matches Qual 1 2007

TCCC Qual 1 yesterday, with 28 minutes left to work on 1000 ptr, I had mentally throw in the towel. I've been saying to myself I could not do this in less than half an hour. This problem looks very complicated at that time. I could not think of a way to approach it, and keep saying to myself it's impossible to do it within time frame, so I decided to roll my tobacco and smoke outside instead of working on it.

When its already too late, somehow I see the DP problem is not too complicated. Just construct the match from left to right, by first putting two vertical matches at the top and the bottom row, to make left wall of current column. Every DP step try all possible 3 horizontal matches to fill the column. Having two left vertical matches on the left wall and 3 horizontal matches, the next 2 vertical matches can be determined based on this 5 choices of matches, and the requirements of the weight of both top and bottom rectangles. Here is a sample code, which might explain better than my words.
What I had in mind when writing that code can (hopefully) be visualized with the diagram. The red ones are the previous Dynamic Programming step, blue ones are the next sub problem we'll deal later. During calculation of each steps, we know somehow the dp algorithm reach a state where matches top & bot are left vertical wall for the current column. We tried all possible horizontal (i,j,k) matches, and continue to check cost of building the next column if possible (possible means the restriction on weights are not violated). We then choose minimum of all these sub problems.

15 minutes before TCCC

I don't think it is a good idea to practice 15 minutes before the match, might waisted some number of neurons better used for the match. Maybe I just write something here. After two canceled match I managed to stay yellow, SRM 362 I suppose to get very big rating drop, -120 or more, since I got a failed challenge + 0 points which is -25. SRM 363 was my best performance so far, gained + 120. All in all both canceled I guess I am even.

I don't know if I should believe this feeling or not, some minutes before SRM 362, I have a bad feeling about the match, and it turn out that it was a bad match for me. And now seems I have the same feeling. Anyway we have 3 chances to qualify, if I did not make it this time, just try another one.


Edit:

After the match, turns out that somehow my feeling was right, the 500 ptr was a greedy problem. Up until now, these kind of problems always made me nervous. I rarely feels confident when submitting solution on greedy problem, that's why it took me long time to work on this problem, left me only with 20 minutes to think about the third problem. Still I am lucky enough in this match to solve both 250 & 500 ptr. Yay ! still qualified, and still yellow, though I lost 23 points :P

Finally Yellow

Two of my best matches in div I happened to be 3.a.m ones, and this is one of them :P. Ranked 131th in division 1, with 103+ additional rating points, finally I become Yellow !.

All thanks to this brute O(n^3) force (but I am not ashamed, Petr's look more or less similar :P):

import java.util.*;
import java.math.*;
import static java.lang.Math.*;
import static java.util.Arrays.*;
import static java.util.Collections.*;

public class WhiteHats
{
    public int whiteNumber(int[] c)
    {    
        sort(c);
        int n = c.length;
        for(int w=0;w<=n;w++){
            int cur[] = new int[n];
            int cnt[] = new int[n];
            for(int i=0;i<w;i++) cur[i] = 1;

            for(int i=0;i<n;i++)
            for(int j=0;j<n;j++) if(j!=i)
                cnt[i] += cur[j];

            sort(cnt);
            boolean ok = true;
            for(int i=0;ok && i<n;i++) ok = (cnt[i] == c[i]);
            if(ok) return w;
        }
        return -1;
    }
}

I hope I could stay yellow or even better increasing :)