Out of google codejam 2013

That was a very bad day. At least I redeemed myself during the last few minutes and managed to submit something. Not good enough. If I was faster I could have at least gotten a t-shirt.

I was feeling a bit slow-minded today. So I was nervous about this match, the first hour was all about me trying not to get distracted and focus. I wasted minutes formalizing the cost formula based on a single number of stations. I am not sure why.

One hour later, I gave up and decided to read the other problems. Problem B seemed interesting.

Problem statement

So I got clever, and thought that the second result can be calculated if you find the minimum index of a player that will ALWAYS lose. The second result is equal to that index minus 1. Always win and always lose are very similar problems. So similar, that Always-lose can be seen as the complete reverse of always-win and we can find a relation-ship between an always-lose function and an always-win one...

...That's what I thought at least. But I was having issues, because when I did the example cases in paper, the trick was not consistent.

Things didn't make sense and time was flying. Decided to open the other problems. At first I thought C-small could be done with meet-in-the-middle (and maybe it can), but this problem is probably a bit too theorical for me. D-small seemed like a heavy implementation problem, I didn't even read it.

Less than 40 minutes left, I was about to just call it a day and get out of the codejam site. But then I decide not to give up. B is the one problem that seemed the most solvable, so I decided to finally face it!

It turns out that in my first analysis, I thought that P was the worst rank of the competitor that gets a prize. Whereas it actually is the number of competitors... I am fairly sure I would have solved this problem 1 hour earlier if it wasn't for this stupid mistake.

After correctly reading the statement, there is still the little issue of actually solving the problem (index that is guaranteed to win)... I assumed that it involved some recursion and binary representation, but I didn't know exactly what to do.

I decided to write a bruteforce solution for N=3, (8 players). I wanted to make sure that the larger P, the larger the result. For some reason I had doubts... I made a solution that showed, for each P, all the indexes that win and all that lose. Good news, so my first assumption is true.

In a flash of very lucky intuition, I noticed a pattern. These are the results of my bruteforce:

P = 0 : LLLLLLLL
P = 1 : WLLLLLLL
P = 2 : WLLLLLLL
P = 3 : WLLLLLLL
P = 4 : WLLLLLLL
P = 5 : WWWLLLLL
P = 6 : WWWLLLLL
P = 7 : WWWWWWWL
P = 8 : WWWWWWWW

If the i-th string is W, the i-th player is guaranteed to win.

So note how the first 4 indexes (after 0) have only one W, the next 2 indexes have 3, and the next 1 index has 7...

Time was running short, and I had this strong suspicion that I could use this logic to fill everything. For example, for N=4 (16 players), indexes 1-8 have one W, 9-12 three Ws, 13-14 seven Ws and index 15 has 15 Ws. I tested my fate, and this silly , out of nowhere logic works for B-small, the better news were that it is easy to optimize it for N=50, and I could solve B-large too...

There were 7 minutes left for the match. I tried to open A again, maybe if I could somehow solve A-small I could at least ensure a place in the top 1000. But it wasn't possible. Even if I thought of a solution, coding it would have taken far more than 7 minutes. I spent the last 5 minutes looking at how my rank became worse and worse and further from the top 1000. When the match ended, I was in position 1120-th. The large solutions were evaluated and I was 1057-th. So that's it. Maybe if google penalizes 57 solutions, I can get a t-shirt. Although to be honest, all codejam t-shirts throughout the years look the same. Maybe they changed the design this year.

-------------------

Rant: Too much emphasis in long problems. Most people would have nothing to do. I blame the 30 minutes extension in the coding time. The good thing about the codejam format was that it allowed to have approachable problems as small inputs. But lately the small inputs are tough anyway. Are B and C-small really much easier than the large ones?