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..

"Double Square"
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...


"Peg 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.

"Studious Students"
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.

Conclusion
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. :)

15 comments:

  1. Seems like you took these problems too complicatedly. Problems 1 and 3 are bruteforcable.

    ReplyDelete
  2. @Sam: Totally right. "Too hard to brute force." I don't think so. :P

    ReplyDelete
  3. actually, the exp() approach is much more efficient if you can derive a proper equation.

    and for the studious student question, simply use the tool that give you the correct result.

    ReplyDelete
  4. Yea, Double Square can be easily bruteforced, and still be fast.

    ReplyDelete
  5. This comment has been removed by the author.

    ReplyDelete
  6. I agreed the approaches I used are not the most efficient one. But they are more flexible to be modified to handle another similar questions.

    ReplyDelete
  7. You're right. And I even still can't solve the other problems. Because I don't think my major will teach me much about this because I take Information systems as my major. Btw I just added you on Facebook Kevin. I'm sorry I'm mistakenly deleted the first comment(Using Excel) because of my cousin, he doesn't know how to use the laptop and he just tried to click what he wants and it's gone.

    ReplyDelete
  8. The exercise 1, with BruteForce is very slow in Java.. a dont know if is the same in ohter languages... but with BruteForce in my experience es very very slow.. 24 hrs is not sufficient.

    ReplyDelete
  9. and it displayed the result at once for Q1 and Q3.
    It takes about 20 sec for Q2.

    ReplyDelete
  10. My time has expired :( but i can do works it. in PHP.

    "Double Square solution"

    function is_perfect_square($value) {
    $sqrt = sqrt($value);
    return $sqrt==intval($sqrt);
    }

    function t($v) {
    $sqrt = intval(sqrt($v));
    $cases = 0;
    for ($j = $sqrt; $j>=0; $j--){
    $num_a = pow($j, 2);
    $num_b = $v-$num_a;

    if (is_perfect_square($num_b)) {
    $cases++;
    }
    }

    return round($cases/2);
    }

    print t(10);
    print "\r\n";
    print t(25);
    print "\r\n";
    print t(64);


    Emmmanuel.

    ReplyDelete
  11. A C implementation of Double Squares takes approx 0.01 seconds on the full input file. My approach was a little better than brute force.

    ReplyDelete
  12. The double square one was easy. Mine took like a second to run. All i have is 2 nested loops. Outer one goes sqrt(n) and the inner one goes sqrt(n - sqrt(i)) where i is the location of the outer loop. if the squared addition of the inner and outer loop was less than n or equal to n i just break out of the loop so it doesn't check so many useless values.

    ReplyDelete
  13. What the hell have you been doing with first task? Here is whole solution:

    $nums=file('input.txt');
    for ($i=1; $i<count($nums); ++$i) {
    $num=(int)$nums[$i];
    $total=0;

    for ($a=0; $a<=sqrt($num/2); ++$a) {
    $b=(int)sqrt($num-$a*$a);
    if ($a*$a+$b*$b==$num) ++$total;
    }

    echo $total."\n";
    }

    ReplyDelete