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.