Friday, December 5, 2014

TopCoder SRM 639 500-pt

Approach
This problem can be broken down into finding the last round the player won, and then adding up the numbers before that number until the player's score is reached. The minimum number of additions are desired, so loop backwards and only add numbers


Code

Analysis
This passes all system tests and does so quickly.

There are two loops that loop a maximum of N times, where N = the last round player x won. N is between sqrt(x + 2y) and x. The worst case would be not finding N, and therefore looping all the way to X. This gives us O(x). In practice if N is found it will be close to the lower bound.


Premature optimization temptation
I wasted alot of time with this optimization so i figured i would share it, so that I can remember to avoid the premature optimization trap in the future. I always have to remind myself to get the program working first, and then optimize, but only optimize bottlenecks.

Here's an optimization when looking for the last round won (N)
1. N must <= X
2. sum(1 to N) must be = x + y
3. sum(1 to N) = N(N+1)/2 (http://en.wikipedia.org/wiki/Triangular_number)
4. N(N + 1)/2 = x + y
5. Because of 1. sub N for x, N(N + 1)/2 = N + y
6. Algebra N^2 + N = 2N + 2y
7. Algebra N^2 = N + 2y
8. Algebra N = sqrt(N + 2y)
9. Sub x back in on the right side, giving N = sqrt(x + 2y). And that's the lower bound

Therefore, because of 1. and 9. sqrt(x + 2y) <= N <= X.

In other words start the loop at sqrt(x + 2y) and loop until X

In practice, this saves alot of looping. In case#5 where x=932599670050 and y=67400241741, this is a difference between 1.4 million loops vs 300k loops. However, i'm also outputting the performance times, and this optimization only saves a relatively small amount of time in case #5 and slows down all of the other cases. This is probably because Math.Sqrt() is an expensive operation.

Therefore this is microoptimization, and not worth it at all. I fell into this trap of optimizing before getting the code right. It's a common problem with programming, "premature optimization is the root of all evil," said the quicksort inventor. 

No comments:

Post a Comment

There was an error in this gadget