GCJ Round 1B and Internal selection test 1

Yesterday was like a contest day for me. I've taken part in 2 programming contest, one that spanned 5 hours and another that spanned 2.5 hours. In Google Code Jam's round 1B, I just found out how good is ACrush (Winner of GCJ2008) as he managed to complete all 3 questions in 45mins (and obviously getting all of them correct), while I struggled with the recursive parser question and thankfully managed to squeeze into the top 1000 contestants.

An interesting question appeared in the NUS internal selection test for ACM-ICPC. Given a rooted tree with the child having always a larger score than its parent, find the node that is closest to the ancestor from the starting node and at the same time having a score bigger than the input. The number of queries Q is about 100,000, while the number of nodes is about 200,000. The solution that came into my mind was to binary search but the question is how to binary search? The next fact that appeared before me was to store all the ancestors that is 2^i distance away from each node. With that information I can do binary search. In total my runtime complexity was O(N lg N + Q lg N) which apparently about half the speed of the official solution and resulted in time limit exceeded during the contest. However, after the contest, the problem setter decided that our runtime is almost the same as his (N lg N + Q) except the constant factor and increased the time limit from 1s to 2s and my code ran in 1.2s.

More programming to come my way... One scheduled on Wednesday and another on Saturday. For now, I have to clear my stuff and prepare for my AI assignment due Friday and midterm test on Friday. Wish me luck.