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

358 Missed Again

Just remembered that there is an SRM Today. And I remembered it at 13.05, just couple of minutes after the competition starts :)) damn.

Euler Tour

SRM 185 EulerianRace, given a graph where node degree's are even, construct euler tour, according to some rule. Start from 0, build a cycle, if every edge is visited we're done. Other wise check from start of current cycle, which node has unvisited edge, find again cycle from that node. Insert the new cycle in between.

What to do in this problem is clear, how to do it ? also somewhat clear. I had planned this implementation, but as always, the devil is in the details. The most time I spent when practicing this problem is to realize the mistakes in inserting cycles to existing cycle using list.add(index,element).

I have list 0,4 and I wanted to insert 1,2,3, inserting one by one this 1,2,3 always at the position after element 0, seems like something logical. But it turns out it produces 0,3,2,1,4 instead of 0,1,2,3,4. So next time I wanted to insert a list into a list with this, I should remember to increase the index.

import java.util.*;
public class EulerianRace {
    int n, start, split;
    int[] d;
    boolean[][] b, u;
    LinkedList < Integer > res = new LinkedList < Integer > ();

    public int[] planRoute(String[]bridges) {
        n = bridges.length;
        u = new boolean[n][n];
        b = new boolean[n][n];
        d = new int[n];

        for (int i = 0; i < n; i++)
            for (int j = 0; j < n; j++) {
                b[i][j] = bridges[i].charAt(j) == '1';
                if (b[i][j]) d[i]++;
            }

        res.add(0);
        split = 0;
        while (split != -1) {
            split = -1;
            for (int i = 0; i < res.size(); i++)
                if (d[res.get(i)] > 0) {
                    split = i;
                    start = res.get(i);
                    go(start); break;
                }
        }

        int[] ret = new int[res.size()];
        for (int i = 0; i < res.size(); i++)
            ret[i] = res.get(i);
        return ret;
    }
    void go(int cur) {
        res.add(split++, cur);
        for (int i = 0; i < n; i++)
            if (b[cur][i] && !u[cur][i]) {
                u[i][cur] = u[cur][i] = true;
                d[cur]--; d[i]--;
                if (i != start) go(i);
                break;
            }
    }
}

Missed SRM 355

Register at midnight, for competition at 3.a.m. Then trying to stay awake watching movie. Usually this works, and for the last 2-3 SRM at 3.a.m I managed to stay awake and compete. This time I dozed off, I don't know at what time, and I don't set any alarm. When I woke up, first I feel bad that I slept, when I check the problems, it was not a bad thing I overslept :P.

Petr problems was really hard.

Test Vim TOHtml

Testing VIM TOHtml, this is security bunker from SRM 269, in an effort to get friendly with Mr. Floyd & Mr. Warshall.

import static java.lang.Math.max;
import static java.lang.Math.sqrt;

public class SecurityBunker {

        public double chooseBomb(String[] field) {
                int R = field.length;
                int C = field[0].length();

                int Bomb = 0, Obj = 0;
                int [] rBombs=new int[100], cBombs = new int[100];
                int [] rObj  =new int[100], cObj   = new int[100];

                for(int i=0;i<R;i++)
                for(int j=0;j<C;j++)
                if(field[i].charAt(j) == '*'){
                        rBombs[Bomb] = i;
                        cBombs[Bomb] = j;
                        Bomb ++;
                } else
                if(field[i].charAt(j) == '?'){
                        rObj[Obj] = i;
                        cObj[Obj] = j;
                        Obj ++;
                }

                int [] rOB = new int[Obj+Bomb];
                int [] cOB = new int[Obj+Bomb];
                int nOB = 0;
                for(int i=0;i<Bomb;i++){
                        rOB[nOB] = rBombs[i];
                        cOB[nOB] = cBombs[i];
                        nOB++;
                }
                for(int i=0;i<Obj;i++){
                        rOB[nOB] = rObj[i];
                        cOB[nOB] = cObj[i];
                        nOB++;
                }

                int dist[][] = new int[nOB][nOB];

                for(int i=0;i<nOB;i++)
                        for(int j=0;j<nOB;j++){
                                int dr = rOB[i] - rOB[j];
                                int dc = cOB[i] - cOB[j];
                                dist[i][j] = dr*dr+dc*dc;
                        }

                for(int k=0;k<Bomb;k++)
                for(int i=0;i<nOB;i++)
                for(int j=0;j<Bomb;j++)
                        if(max(dist[i][k],dist[k][j]) < dist[i][j])
                                dist[i][j] = max(dist[i][k],dist[k][j]);

                double res = 0;
                for(int i=Bomb;i<nOB;i++)
                        for(int j=0;j<Bomb;j++)
                                res = max(res,dist[i][j]);

                return sqrt(res);
        }

}