Saturday, January 8, 2011
Hacker Cup - 3 Questions solved.
I am not trying to expose how to solve these 3 problems, I just write down my feeling and experience about coding for the 3 Hacker Cups problems since last night. (I slept 5 hours only)
Last night, I was alone in Starbuck and start to solve the Hacker Cup problems.
I just read "Double Square" instruction and then start to work..
I remembered I have met the similar questions in ACM programming contest long time ago. My friend told me to solve this with the help of log() and exp(), but actually they do not help me. Until now, I still dont know how to solve this problem with log() and exp(). But last night, I just consider this as a searching problem for a node in a big binary tree and I solved this.
After 1 hour, I wrote a java program and it can find of the answers if the input is a simple 5-digit interger. However, my laptop hanged if the input is Integer.INT_MAX=2147483647. (I have not waited until it ended.)
Then, I tried to add some tricks to remove some unless nodes in the tree. After 2 hours later, my optimizied code can solve the input of 2147483647.
I was very happy at that time and I tried to submit my answer. However, when I clicked the 'submit button' with my Chrome browser, It replied that 'Time Expired'....
I found that the timer counter will not display in Chrome browser. Why I know this now? Because I had submitted "Peg Game" answer with IE and "Studious Student" with Chrome this afternoon.
Anyhow, that is my bad I have not prepared well for this game...
Then I went back to home have my dinner and then started to work on "Peg Game"...
Honestly, I don't understand what "Peg Game" is actually doing at first few times I read the instruction, especially when I see the probability outcomes in sample output.
Basically, if you tried to use the data structure to construct the peg game board, I thought you go to a wrong direction.
I have spent a lot of my time to figure out how those probabilities are calculated. After you have clarified what it is, you can complete the code quickly.
I solved the problem around 6am this morning, but I have not uploaded the answers at once. Because I also want to solve the last question "Studious Students" first before I submit my answer again.
I don't think this problem can be simply solved by the approach of sorting and appending the strings. Although, this kind of approach can solve 4 out of 5 given sample inputs. Ha ha... This is one of the biggest tricks in this round of Hacker Cup..
The real point of this questions is how you handle the case that if there exists a string which is a prefix of the another strings... I spent most of my time to handle this issue.
Hacker Cup reminded my memory when I still was a Computer Science Student. Hope you have fun in this game.
By the way, if you use Android mobile phone and like game, please try this puzzle game I designed ---> "Harvest Field".
It is available in Android Market now. :)
Posted by Kevin Wong at 2:49 PM