So sad, I would have solved C in round 8 since I noticed how to make my memo solution work in time (by making it forcefully consume the first element that is still in the bitmask) but... So what I did was that when I encode the used pairs, I use (x,N) for a "pair" that is just a single element, that's what generated the mistake:

            int x = mem2[mask]/100;
            int y = mem2[mask]%100;
            if(y!=N) {
                cout<< "0 "<<(x+1)<<" "<<(y+1)<<" ";
            } else {
                cout<< "0 "<<(x+1)<<" ";
            }
            mask = mask - (1<<x) - (1<<y);           

Well, I would have solved this easily if I didn't use subtraction for bitmasks or if I actually paid attention .... I am pretty sure I would have reached yellow if it wasn't for this bug, but I dropped to 1500~ instead :(


Edit: wow , so the blog entry gets spammed to everybody in the home page, better change it to something useful.

Problem A:
This one was sort of simple but I don't think it was possible to solve it without knowing KMP, just divide the problem into parts. Eventually, I just used KMP on both the input string and the reversed string to get the minimum area to the left of the string that can hold the first substring and the minimum area to the right of the string that can hold the second one. If the sum of these lengths is <= the length of the string, then the thing is possible. (run KMP four times per case, this is  linear, cool)

Problem B:
This was a nice problem, my first idea was to mark white cells on a 201x201 board that is full of walls (and start simulating the movements from 100,100), if you ever reach a cell that is adjacent to a previously visited cell or if a cyclic is formed then it is not the shortest path.

I am sure that approach works, but before risking it , I noticed the constraints, so I just did the same thing and filled white cells on a 201x201 array of walls starting at (100,100) (and simulating the moves). Then I ran a BFS from (100,100) to the final location. If the distance of the BFS is not the same as the length of the string, it is fine.

Problem C:
O(n * 2^n) runs in time, and O(2^n) memory is short enough.

My first idea was a [2^n] memoization, but I used a n*n loop inside of it, so I hit the time limit. Then I went for lunch where I figured out that you can turn this from O(n*n*2^n) to O(n*2^n) by noticing that every point has to be forcefully visited. So I changed then n* n loop into 2 loops, the first one finds the first element that is in the bitmask and the second loop tries to find pairs that contain this element.