Saturday, May 08, 2010

Google Code Jam - Qualification Round 2010

Google Codejam 2010 is here! As usual, there are three problems with 33 points each (10 points for the small dataset and 23 points for the big dataset). Here's my overview so far of the tournament.

Problem A : Snapper Chain
So far the problem has 84% correct ratio, so it'd indicate it's an easy problem and it is. The problem statement might seem a bit confusing but break it down to essentials, understand the atomic problem and you'll have your solution in no time. But beware, if you don't use appropriate techniques, you might be in trouble for the bigger dataset, so try out some long inputs on your own before you run it for the actual dataset.

Problem C : Theme Park
94% percent correct ratio! Wow, that's saying something. Looks like most of the people got it right. I think I did too and I hope it stays the same for the big testset too. It's quite a straight-forward problem to give any hint. Just manage your data structures well and you should be able to solve it in no time.

Problem B : Fair Warning
As always is the case with Google Code Jam, there will always be one problem where only your coding skills will not save you. You can't just crunch your numbers with a really huge data-type and get away with it. No sir! And Problem B falls straight into that category. As the problem clearly states, "64 bits will not save you. You have been warned." One of the inputs could be as high as 1050 And that's where I am stuck. Hopefully I can solve it out.

I'll post the solutions and tricks here once the contest is over. Till then, happy coding and stay tuned!

5 comments:

goutham said...

well I got the prob with Theme Park... the small inputs were solving good but the large inputs contained loops for 100,000,000 which are huge and time consuming .... and all my 8 min of submission time went away...

Anonymous said...

It is nice that you have blogged about the GCJ, but please bear in mind that it is against the rules to discuss the problems before the contest round ends.

You are not actually giving away solutions, but even giving subtle hints may not be looked upon kindly by the admins, and might become grounds for disqualification. So please be careful.

Maybe taking this post offline until the round ends in a few hours?

Divye Kapoor said...

Any place where there's a more detailed discussion of the "Fair Warning" problem?

Bendz said...

Hi,
It's my first visit to your blog. I need more time to understand these things :(
If you've got time, visit my insurance blog.
Cool blog and Keep it up.
;)

Me said...

Long time no blog.. we want more..