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. 

Thursday, December 4, 2014

System.Threading.Timer is firing before its supposed to

Problem
I'm using a System.Threading.Timer and specifying a precise time of 10:05 pm, but the timer fires (callback is called) before that time, such as 10:04:59.97 pm.

This causes problems for me because I have to recalculate the next time it should fire based on the current time, and the current time is before the time it was supposed to fire the first time.

Solution
Timers aren't guaranteed to fire exactly when you schedule them to. They will fire a little before or after the time you scheduled. For my situation it's bad when they fire before they're supposed to, because subsequent scheduling is affected by this. Therefore if the timer fires before it's supposed to i sleep the thread until its at or after its expected time. This is achieved by keeping track of the Expected Time in the callback state object.

Code
Here's a stripped down version of my code that's used to handle this situation

        internal class TimerStateObject
        {
            internal System.Threading.Timer refTimer = null;
            internal DateTime expectedTime;

        }

Here's the timer init and callback functions

        private void initTimer()
       {
            TimerStateObject timerStateObject = new TimerStateObject();
         
             timerStateObject.expectedTime = DateTime.Now.Add(ONE_HOUR);
         
             timerStateObject.refTimer = new System.Threading.Timer(new TimerCallback(timerCallBack), timerStateObject, ONE_HOUR , DISABLE_PERIOD);
       }

        private void timerCallBack(Object timerStateObject)
        {
            TimerStateObject state = (TimerStateObject)timerStateObject;
         
            waitUntilExpectedTime(state);

            state.targetTime = DateTime.Now.Add(ONE_HOUR);

            state.refTimer.Change(ONE_HOUR, DISABLE_PERIOD);
        }


        private void waitUntilExpectedTime(TimerStateObject timerStateObj)
        {
            DateTime now = DateTime.Now;
            while (now.CompareTo(timerStateObj.expectedTime) <= 0)
            {
                TimeSpan diff = timerStateObj.expectedTime.Subtract(now).Add(ONE_SECOND));
                Thread.Sleep(diff);
                now = DateTime.Now;
            }
        }
There was an error in this gadget