Codeforces round #114 (div1)

So, there we go. What a month. The amount of contests I participated in seems so large that I can't remember a day of the month in which I wasn't participating in a contest, trying to fix a mistake made in a contest a day before or preparing the problem set for the next day. Saturday 31st is approaching and with it the first round of the TopCoder open and the last cool programming contest this month.

Problem A link
Seems we are back to high school physics once again.

What is the most important thing here is that bus #i cannot reach in a time earlier than bus #(i-1). After that, assume that bus #i 's max speed allowed it to reach the place faster, this bus would have no choice other than reach bus #(i-1) and then go with the same speed. So, the time of bus #i will be equal to the time of bus #(i-1).

In fact, this happens with any bus that is earlier than bus #i. And if any bus smaller than i reaches the end after bus #i's optimal time, bus #i will have no other chance than to slow down.

It all boils down to calculate the optimal time t needed for each bus i. And then, the result is max(t , maxTime). Where maxTime is the maximum time for all the earlier buses.

And to calculate the time, use formulas based on acceleration. To be honest I just opened this page: http://en.wikipedia.org/wiki/Acceleration

int n,a,d; 
int t0[100000]; 
int v[100000]; 
 
void solve() 
{ 
    double minTime = 0; 
    for (int i=0; i<n; i++) { 
        double t = t0[i]; //time bus i needs to reach the station ignoring i-1 
        //t1: min time to reach v[i] 
        double t1 = v[i]/(double)a; 
        //displacement after t1 seconds 
        double s = a*0.5 * t1 * t1; 
        if (s > d) { 
            // won't reach max vel 
            t += sqrt( 2*d / (double)a ); 
        } else { 
            // will reach max vel. 
            double x = d - s; 
            //t2: time it takes the bus to move x distance units at v[i] speed 
            double t2 = x / (double)v[i]; 
            t += t1 + t2; 
        } 
        t = max(minTime, t); 
        minTime = t; 
        cout.precision(10); 
        cout.setf(ios::fixed, ios::fixed); 
        cout << t << endl; 
    } 
     
} 

Problem B link
I really should have solved this problem faster, but spent some time debugging things and getting confused by my correct result for example 1.

Let's try a dp solution with many states [bags][won][prizes][num]. bags is the number of available bag spaces you have. won is the number of won tours, prizes the number of tours that gave you a prize and num, the number of tours you have completed. After each tour, there is a probability to win (which will update bags or prizes and will update won) or not (won't update anything).

The base case is when num = all tours, there are no tours left and now you have to verify that there is enough empty space for all the prizes you got and that you won at least l times.

The overall result will be [K][0][0][0]
This is great, except that it is a little slow. Well, the key optimization is to notice that you do not really need to remember bags AND prizes, you can just remember (bags - prizes). If this difference is non-negative at the end of all tours, then you had enough space.

int n, l, k; 
double p[200]; 
int    a[200]; 
 
 
double dp[2][401][201]; 
 
double solve() 
{ 
    for (int spaces = -200; spaces <= 200; spaces++) { 
        for (int won = 0; won <= 200; won++) { 
            dp[n&1][spaces+200][won] = ( ((spaces >= 0) && (won>=l)) ? 1.0 : 0.0 );  
        } 
    } 
    for (int t=n-1; t>=0; t--) { 
        int tt = (t&1); 
        int nt = (t+1)&1; 
        for (int spaces = -200; spaces <= 200; spaces++) { 
            for (int won = 0; won <= 200; won++) { 
                double & res = dp[tt][spaces+200][won]; 
                res = 0; 
                double prob = p[t]; 
                // win 
                if ( (spaces+a[t] >= -200) && (won+1 <= 200) ) { 
                    res += prob*dp[nt][ min(200, spaces + a[t]) + 200][won+1]; 
                } 
                // lose 
                res += (1-prob)*dp[nt][spaces + 200][won]; 
            } 
        } 
         
    } 
         
    return dp[0][k+200][0]; 
} 

As you can see from my code, I did some rather unnecessary optimizations like doing iterative dp to save up memory. I don't think this was needed.

Problem C link

Let us think of a and b. Whenever you subtract a power of a from b, b' will still be equal to b modulo a. So, in fact the relationship won't change.

Here's a sort of idea. For a<=b, take b%a, find the result for (b%a, a) . Now, if (b%a, a) is a losing state, then you should always do b=b%a. But if (b%a, a) is a winning state, then you have to do something to make sure that you are the one who reaches it.

In fact, it is like setting (c = b / a) and now you have a stack of c elements and some allowed numbers of 1, a^2, a^3, ... . A player can remove any allowed number of elements. The player to get 0 elements in the stack wins.

I am sure that this can be reduced to nim. I have no idea how. I tried something funny during the match mixing up some xors hoping that I get to the correct reductiong. But it got hacked. I expected that to happen, but it was still fun.

Update: editutorial is up (quite quickly this time). I feel lame about not solving problem C. It was easy to notice the property, an odd number raised to any power will stay odd. I over focused on trying to adapt nim to it that I didn't try any simpler stuff.