SRM 565: Huge little differences

Ouch, now with 16XX. My new strategy of not opening div1 easy until 10 minutes before the end of the match is really killing my rating.

Div1 250: The one with trees

This one seems very tough. I am very worried because I will have to write the editorial and explain this problem. Seems I will be working hard these two days :(

Div1 500: The one with the division game

Two players play a game with a list initially consisting of all numbers in a interval [A, B]. A turn consists of picking one of the numbers in the list, find a divisor != 1, and divide the number by that divisor. The player who does not have a valid move loses the game.

You are given L and R, count the number of intervals [A,B] such that L <= A < B < R in which the first player wins (both players play optimally.

All right, I just recently solved a problem that used nimbers (Grundy numbers); and it was actually the first time I learned about them and had to write the editorial. So they were in my mind today. The game is a two player, symmetric, turn based game, so a state of the game should have a nimber.

First let us find the nimber of a single game consisting of a number x. I had no ideas so I just did this for the first 40 numbers looking for a pattern: I define a function nimber(x) that calculates the number. Each divisor of x will give us a number y with a nimber of its own. The minimum number that is not in the set of nimber(y)s is the result (minimum excluded ordinal).

In fact, after doing all of that and printing the results from 1 to 40, it was clear that nimber(x) = number of prime factors of x (0 for x=1, 1 for prime x). Now it is clear why this happens. Imagine a number as a set of stones, each labeled with one of the prime factors. So 12 is equal to two stones labeled 2 and one stone labeled 3. Dividing by a divisor of the number is the same as taking some of the stones. For example 12/4 = 3, it is the same as if we took the two stones labeled 2. At the end, what matters all the time is the number of stones, not their labels. This becomes exactly a nim game in which the number of stones in the stack is equal to the number of prime factors.

Let us say that we have found the number of prime factors, the nimbers for all n numbers between L and R, inclusive. The problem becomes: Given n numbers, where n is up to 1000001. Count the number of intervals of consecutive numbers in that list such that the xor of the numbers in the interval is not 0. (Each number is a nim game, the combination of a set of nim games, has a nimber equal to the xor of all those games).

This new sub-problem can be solved with dynamic programming. Let us define a function f(x,i) that returns the number of intervals that start with number i and with a total xor equal to x. (The final result will then be the sum of all f(x,i) such that x is not 0). After placing number i in the interval, you have two choices: Finish the interval with this number, in which case x = number[i]. And not finish the interval, in which case it has to continue (and include number[i+1]) and there are f( x ^ number[i], i+1) intervals that work like that.

The slight inconvenient with that dynamic programming approach is that an array [32][1000001] (The maximum xor will be 31, because the maximum number of prime factors by the constraints is 29). Will not fit in the memory. But fear not, we can approach this complication by using an array [32][2], because each i, only needs to remember the results for i+1.

THE REAL problem (at least to me) was to actually calculate all the nimbers from L to R. This means calculating the number of prime factors for up to 1000001 numbers. In the worst case, each of those numbers is greater than 999999999. Straight forward approaches are too slow. And I could not think of anything during the match.

In my frustration, I decided to just submit a solution with the dynamic programming and all the logic already made, but using a slow approach for the nimber calculation. I knew it would fail. But at least it shows I solved the rest ^^.

At the end of the match, I read Petr's code and the trick to calculate the numbers became clear. It is similar to a Sieve of Erathostenes, but only caring about the numbers from L to R. Given a prime p (up to sqrt(R)), we can just iterate through all numbers between L and R that are multiples of it. And increase the counts of prime factors. This saves a lot of time.

typedef long long int64; 
#define long int64 
 
int current[1000001]; 
int nimber [1000001]; 
 
long dp[32][2]; 
 
struct TheDivisionGame 
{ 
 
    long countWinningIntervals(int L, int R) 
    { 
        int n = R - L + 1; 
        // Cleverly calculate nimber[i] for each 
        // number between L and R (The number of prime factors) 
        for (int i=L ; i<=R; i++) { 
            nimber[i - L] = 0; 
            current[i - L] = i; 
        } 
        for (int p=2; p <= R/p; p++) { 
            int s = L; 
            if (L % p != 0) { 
                s += p - (L % p); 
            } 
            //cout << L << ", "<<s<<", "<<p<<endl; 
            while (s <= R) { 
                while( current[s - L] % p == 0) { 
                    current[s - L] /= p; 
                    nimber[s - L] ++; 
                } 
                s += p; 
            } 
        } 
        // some numbers might still have current[i] > 1, they are primes. 
        for (int i=L ; i<=R; i++) { 
            if (current[i - L] != 1) { 
                nimber[i - L]++; 
            } 
        }  
         
        // Now the dynamic programming part: 
        long s = 0; 
        // dp[x][i] : Number of intervals that start with nimber[i] 
        //            such that the total xor of the interval is x. 
        for (int i=n-1; i>=0; i--) { 
            for (int x=0; x<32; x++) { 
                dp[x][i&1] = 0; 
                // Use nimber[i] and nimber[i+1] 
                // then we need to know the number of intervals 
                // starting with nimber[i+1] that give x ^ nimber[i] 
                if (i+1 < n) { 
                    dp[x][i&1] += dp[x ^ nimber[i]][ (i&1)^1]; 
                } 
                // Use only nimber[i] then x must be == nimber[i] 
                if (x == nimber[i]) { 
                    dp[x][i&1]++; 
                } 
                // Count the intervals with x!=0 
                if (x!=0) { 
                    s+= dp[x][ i& 1]; 
                } 
 
            } 
        } 
        return s; 
    } 
}; 
#undef long 

Div1 250: The one with monsters

I exceeded my time with div1 500 and actually had 8 minutes to solve this problem. I think I should have been able to solve it though. At first it seems like an innocent dynamic programming problem. Then you notice that the scary ness of monsters can be very high.

The trick is to notice that prices are 1 or 2. You can change the problem to calculating f(i, p) : The maximum scaryness you can buy using the first i monsters and spending at most p. This allows a recursive solution. Let us say you want to solve f(i,p), then you have to decide whether or not to bribe monster (i-1), then your available money becomes p - something, but the scaryness is scaryness[i-1] + f(i-1, p - something). If you decide not to bribe the monster, then the maximum scaryness f(i-1,p) you can find must be greater than scaryness[i-1].

See? It is easy!. But it took me far more than 8 minutes to think of this reversal. Ouch. The result is that I am back to 16XX rating. That is a record low, I think. Probably the lowest rating I reeached in years :(.

But this was deserved. I think I should have known how to do the fast prime factorization already. That would have given me a score in div1 500 and more time for div1 easy. Which I should have been able to solve in less than 8 minutes anyway.

Comments?

Any comments?