Saturday, September 26, 2009

Topcoder | SRM 449 experience

This time the performance was a bit disappointing. The problems were related to mathematics and trigonometry.

I spent some time on 250 ptr and just didn't understand that if I scale its lower parts to upward, it will become a bigger triangle, and I just have to find the lengths of base and perpendicular of that bigger triangle. The formula was sqrt(2)*(max(finish) - min(start)). This is the solution.

Just no idea clicked and I decided to open 500 ptr because I was pretty sure that it would have been a simpler one. It was simple(only problem statement :) ), as you might have seen but wasn't easy. Again it was a mathematical trick, because brute force solution will surely leads to time out. This was the logic behind it. (The following statements are copied from editorial)

-> If we see, the greatest odd divisor that divides N is N if N is odd or if N is even the greatest odd divisor of N is F(N/2).
-> For (1,N) if N is odd we get 1 + 3 + 5 + ...N + F(2) + F(4)+....F(N-1). The greatest even N is F((N-1)/2).
-> That means the sum F(2) + F(4)+...F(N-1) = F(1) + F(2) + F(3) + F((N-1)/2). Now this is our original problem with N as (N-1)/2.
-> In case of N as even our problem is split into 1+3+5+ ....N-1 and F(2)+ F(4) + ......+ F(N), which is again sum(1,N/2).
-> Now the sum of 1+3+5+.....+N= (N+1)*(N+1)/2


Click here for its solution.

After a sad Coding phase, I decided to gain some points in challenge phase, I was sure that many participants will attempt 500 ptr as brute force so I attacked them, I made 3 challenges one of them was wrong and finished at 75.

Next day, I opened the page to see how much rating points I lost, I was amazed that these were not too many.

Friday, September 4, 2009

Google Code JAM

Google Code JAM Qualification round is over. Unfortunately, code JAM's scoreboard doesn't give much statistics about the results

I saw these stats about google code JAM and I would surely like them to share with all of my readers.

Language statistics

Solutions by Language

Regional Statistics

Hope this will help.