LeeMobile

Well, this weekend was round 1 of the Google Code Jam, and unfortunately I did not advance to the second round.  I’m actually really disappointed in myself.  Not because I had high hopes of making it far, but that I *could have* advanced if I had just paid more attention and focused.

I wouldn’t be disappointed if I felt that I had my ass handed to me, but I slipped up on fairly rookie and stupid mistakes.

In all fairness though,  I was beat squarely in my inability to recognize where I went wrong within the two hour time limit.  Given that I had two chances to redeem myself (you’re allowed to compete twice out of the three time slots), I should have made it passed this round.

At any rate, I learned a lot of lessons which will be hard to forget for next time :-).  I still enjoyed the experience, and I’ll probably sign up for Top Coder, a programming competition league which holds frequent competitions.  I could see myself doing this every few months or so just for shits and giggles.

For those interested, here are the questions I attempted to solve, and where I went wrong:

The format is that you are presented with 3 questions.  To solve the question, you write a program which takes in the input data set, and you submit the output for verification.   There are two input data sets, a small one and a large one, with the large one worth more points.  Each question is worth different points (depending on level of difficulty), and those with the most points advance.  If there’s a tie in points, then those who submit earliest advance.

Had I solved any one of these problems I would have advanced to the next round.

The three questions I attempted to solve in both slots this round were:

First attempt:

Question 1:

Problem

You are given two vectors v₁=(x₁,x₂,…,x_n) and v₂=(y₁,y₂,…,y_n). The scalar product of these vectors is a single number, calculated as x₁y₁+x₂y₂+…+x_ny_n.

Suppose you are allowed to permute the coordinates of each vector as you wish. Choose two permutations such that the scalar product of your two new vectors is the smallest possible, and output that minimum scalar product.

I chose this question because it was obviously easy.  You just have to sort one vector from largest to smallest, and the other vector oppositely.  Fast and easy problem to code, so I submitted a solution pretty quickly and was already ahead of the pack. Someone was able to read the problem, solve it, code a solution, download the data set, and submit the data set in 3 minutes time… now that is FAST.  I wasn’t that fast, but I was quite ahead.

The large data sets are verified after the competition is over, so you have no way of knowing if it’s valid until the end.  You also get only one shot at it too. In all my hubris, I ran the large data set and submitted.

I found out that my large set was incorrect, and I quickly realized the costly mistake.  The large data set contains values in the vector that are between -1000000 and 1000000.  And in my solution I used a 32 bit integer to calculate the values, which would lead to an overflow since it can’t represent a number like 1000000 x 1000000 (those tricky bastards at Google!).  Had I simply just used a 64 bit integer it would’ve worked out, and I would’ve scored enough points to advance.

Lesson learned… read the bounds more carefully.

Question 2:

 Problem

In this problem, you have to find the last three digits before the decimal point for the number (3 + √5)ⁿ.

For example, when n = 5, (3 + √5)⁵ = 3935.73982… The answer is 935.

For n = 2, (3 + √5)² = 27.4164079… The answer is 027.

This question was weighted heavily enough that if I got just the small data set to work correctly, I would have had enough to pass.  But no, I didn’t solve it correctly either.

My naive solution, because my math skills suck, was to just compute the value and parse the value for the answer.  For the small dataset, the maximum bound on n is 30… so computation should be enough for a correct answer.  There was no way that I would attempt the large, as n had a max of 2000000000 (that’s a shitload of zeroes).  Sounds simple enough, but how do you compute such a huge number with enough precision.  Precision is at the heart of the problem.  So I used Java’s BigDecimal data type, which is really accurate.

However, to get the square root of 5, I initially calculated it using the Math.sqrt() Java function before wrapping it in BigDecimal…. and there was my big mistake.  Math.sqrt returns a double precision float… and when n starts to get large that’s simply not precise enough.

What I should’ve done was use the Newton-Raphson method to calculate the square root of 5 with enough precision to solve the question.  Just solving the small data set alone would’ve been enough to push me through.

My mistake again was another data type error.  That and not remembering a few years back into my numerical methods class about the Newton-Raphson method…. because every person should know it off by heart.  How could you not?!

I won’t bore you with more details about the third problem which I failed at… but it was one where I screwed up by not reading thoroughly enough (I missed a vital constraint).  *Had I* solved it, it would’ve pushed me into the top 100 and I would’ve made it to Round 2 (sigh).

–

So all in all I felt like a newb this weekend.  Shitty in that I could have moved on if I just paid a little more attention to detail and read the questions more thoroughly.  I also felt really rushed and under the gun, so that really clouded my judgment.  All I had to do was take a deep breath and chill out… the answers would have come right to me.

I learned a few lessons though.  Mainly that my math skills suck and that I should maybe re-read some of my old numerical methods and calculus text books.  Also, I should just pay more attention to details. I think that’s more important than anything.

Oh well, there’s always next year.

This entry was posted on Sunday, July 27th, 2008 at 12:45 pm and is filed under Uncategorized. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.