I entered the Google Code Jam yesterday. I was pleased with my effort when after 50 minutes (of allocated 60) I had completed to two assigned problems. I was working on problem set #1 (room 7). I had a score or 502.75 point (out of 1000) and at 13 hours into the 24 hours period, I was ranked 46th for my problem set.
But my 750 point problem failed system testing, so my final score was 178.59, this put me in 266th (of 939 people, but 482= was the last place) position for the problem set. But my Google rank was 1359 which is better than my best Top Coder ranking.
Which reminds me that the night before I entered the Top Coder SRM 259, I was in division II after my poor Top Coder Open results. The three problems where easy to-do so I’m now back in division I (but only by 2 points), so I need to pull finger and do better in the next SRM. I got top score in the room I was in (#16) and I placed 11th (out of 273) for the division. So even though it was 11pm when I started and 1:30am when I went to bed, I was feeling good.
Well I’m not going to get into the Elimination Rounds.
I was assigned VideoEncode and GridGame.
I spent ~30 minutes of my 60 solving a problem that was really just a bit of algebra. I solved it using binary search, when I just need to rearrange the variables to get a single line piece of code. I had the feeling this was the case, but the stress of the situation I was not trusting myself to solve the algebra faster than getting the binary search working. Net time I’ll have a better indicator. The binary search was required in the AutoLoan problem due to the value been search for had a compounding affect on the result. Whereas here there was no complex relationship.
The second problem was a simple min/max tree problem. Given a 4×4 board how many of the available moves will “win” if I only play perfectly. I had missed the guarantee you win and assuming you play perfectly bits. Not that I know how to solve this. But I went down the path of how many of the moves could I win.
So now I’ll stop trying the path of logic I had been working on after the event, and workout how to solve the problem correctly.
[Some time later]
Oh my, it really was quite simple once I stopped and thought about that at each turn the two players are trying to achieve different things. For our turn we just need to find one move that we win. For the opposition move they win if they find a path we don’t win. So simple now I understand what I was trying to achieve. Other the feeling silly for not know how to program this I now feel relax I worked out how to-do it.
I’ll be ready for next time.
[Just before publishing]
Well the results are in. I came 300th out of 374 in my problem set. Most those people came 317th equal for no score. This hammered my ranking, and I’m now down to 1050. Oh well, I surely can’t get much worse than this.
Here’s the list the 21 problems I’ve solved on the Programming Challenges site.
If any ATR people have solved more I’ll have to start solving them again…
110101 The 3n+1 problem
110103 The Trip
110107 Check The Check
110108 Australian Voting
110201 Jolly Jumpers
110202 Poker Hands
110207 Contest Scoreboard
110306 File Fragmentation
110404 Longest Nap
110405 Shoemaker’s Problem
110805 Tug of War
110903 The Tourist Guide
111302 Rope Crisis in Ropeland !
111308 How Big Is It?
The problems I can’t/haven’t solved and would love to hear of solutions for are
110104 LC-Display (edit 2008: now solved)
110206 Erdos Numbers (edit 2010: now solved)
110208 Yahtzee (edit 2010: now solved)
110801 Little Bishops
110804 Servicing Stations
111002 The Necklace
[Edit 2010] I have a newer, complete list here
The art of know all the required tricks, and just “getting” the problem, and writing the solution. I have so much to learn.
I entered TopCoder SRM 258, and end with a zero score for the second time. But this time at least I submitted a problem that I thought worked. My score is was not too affect this time and I’m still in Division I. I plan to turn the slope of this graph around.
The first problem was calculating the interest rate given the start price, monthly payment and number of months. I’ve done a lot of self discovery in the finance area driving by our (Michaela and me) desire to purchasing a house. The problem reminded me of my book of formula’s so much I couldn’t get over it and just write a program to solve this problem. So after the event was over last night I worked on it. I almost had it solved correctly, but the way I was generating the correct interest rate was ugly (it just required a binary search due to the limit of 0% to 100% stated in the problem) and the exit conditions. The latter was a bigger issue. The problem stated 1e-9 precision, so I comparing the money owning at the end of the term to 1e-9 not the interest rate. So using the binary search also solves that problem.
The second problem was a compression problem. The problem that got my code rejected was a challenge of “ASD”. Although the problem stated the input was from 1 to 50, I had thought that the two compression keys needed to be unique, thus my inner loop would not use the same key as the outer loop. There was also a problem where my inner loop was from 0 to n-1 not n as it should have been. But looking at other peoples solutions I worked out that one correct way was to use Dynamic Programming, which I had been reading about that morning. So failing to spot the change to use it make me feel a little silly, but boy, from now on, DP is going to be on my check list.
The third problem was a really hard DP problem. Work out the probability of each play (1-4) winning a game of snakes and ladders (though they used a different name). That just messed with my head. But the people that did get it had very compressed but elegant solutions. Another learning opportunity.
Anyway the first two problems were opened, read, coded, tested in 5 minutes by the best people, so I’m just thinking they really grok there comp sci algorithm courses.
Well, I just completed the TopCoder SRM 257, and I didn’t even get one problem solved.
The first problem was find the minimum error ( difference ) for a weighted average.
You used 5 weights, with a sum 1.0, that last bit (sum of 1.0) I forgot, so spent the whole time trying to workout why my result was different from the example. Also the run time was too long for the bigger dataset. Not till coding phase was over and I started reading other people solutions did I see my error. GRRRR. So I’m not sure how badly it will affect my ranking, but I’m think its going to hurt. Maybe I’ll get put into the second division, which will be easier, but not as much fun as playing with the big boys in Div I.
So tonight instead of doing game development, I’m going to solve the other two problems that I didn’t even start.