SRM 575 - Force of habit

I try to almost always register 3 hours, 10 minutes before a topcoder match. It is the force of habit. Today I was online since earlier than that, trying to finally solve round 2A 1000 points problem, for its editorial (which is very late). So when the arena was restarted (as usual, to remove practice rooms and add the active contest) my main concern was to remind the admins that they shouldn't remove 2A. When Arena restarted, I went and focused on writing the 2A editorial. I eventually finished the hard explanation, with less than an hour before SRM 575. Decided to go to the chat and see if there is any conversation. At 11:50, I decide to go away from the keyboard, I return at 11:57. In which I start to wonder: Did I register? The answer was no. Apparently, the editorial distracted me at 9:00, when the registration started. Then during the chat, I just didn't think of it, because usually I register early, so I guess I assumed I registered...

So I was going to miss a SRM, a complete chance to have fun and compete against tons of coders (this time 2400 ones!). A chance to practice and to learn. Was sad.

Then it occurred me, that I have leverage. Since I am the editorial writer, maybe I could ask to get tester access to the match, which would allow me to watch it and also to try the problems. ^^ . The admins were kind enough to give me that access. So I went to the admin room to test the problems. I think around 10 minutes after the start of the coding phase.

I opened div1 easy and medium and tried to solve them. This is the story of my pretend SRM.

Div1 250 : The one with divisors

John and Brus have a integer n. In each turn, a player picks a divisor of n, the divisor can't be 1 or n. Then n becomes (n - the picked divisor). The first player to get a prime number or 1 (cannot pick a proper divisor) loses the game. Given n, if both players play optimally, who wins? n can be as large as 10¹⁸.

n is so large, that the rule behind what makes first player able to win should be quite simple. It cannot be something based on the number of prime factors (it would be impossible to count it for large n), for example.

Eventually (taking a long time) I tried to make a memoization solution that works for the first 2000 numbers and see if there is any pattern. It initially seemed that, for most numbers between 1 and 9, second player wins, except for 4 and 6. After 9, it appears that the first player would always win when n is even. This is not completely true. The admins included n = 128 in the example tests, it turns out that for 128 = 2⁷, it does not work that way, and first player loses anyway. With close inspection of first 100000 results, it looks like the result is always true when n is even. UNLESS n is equal to 2 raised to an odd power. It turns out this is true for all numbers between 1 and 10¹⁸.

string find(long n)
{
    // If prime = you lose
    // If 2*prime = you win.
    for (long i=1; i<64; i+= 2) {
        if ( n == (1LL << i)) {
            return "Brus";
        }
    }
    return (n & 1LL) ? "Brus" : "John";

}

But why is this true? It is not difficult to prove that it is true. It is clearly true for the first 4 numbers. We can show via induction that if it is true for all n < K, it should be true for K.

Assume K is odd, then it is either a prime number (Second player wins), or it has only odd usable divisors. If you subtract an odd number from another odd number, the result will be an even number. The result is also unable to be a power of 2. Because the subtracted divisor cannot be 1 and must divide the original number. Proof by contradiction:

2 k + d = 0 mod d
2 k     = 0 mod d

Which means that if we assume that d is not 1, and that d is not even, it is impossible for 2^k to be a multiple of d, which would mean it is impossible for (2^k + d) to be a multiple of d. Thus when K is odd, all the reachable numbers are smaller than K, even , and not powers of 2, no matter what the first player does, the second player will win.

If K is an even number that is not a power of 2, then it is always possible for the first player to make K into an odd number (and win). K is a product of a power of 2 and an odd number, if you subtract the odd number, the result will also be odd.

If K = 2^t, then we can no longer use this trick. But if t is even, then we can win by picking 2^t-1 as the divisor, the result is 2^t-1, which 2 raised to an odd power, so first player wins. If t is odd, then we cannot do it. If we subtract 2^t-1, the result is 2 raised to an even power, which is a winning state. Subtracting anything else will yield an even number that is not a power of 2, also a winning state.

During the simulated match, I took way too long to solve this, and I had a bug in the implementation. So I would have scored 0 in this problem.

500: The one with cards

You have at most 2500 cards, each with a digit from 0 to 9. k swaps are performed. A swap involves picking a pair of card positions uniformly at random and then swapping the positions of the cards. After the swaps, a group of consecutive cards is picked uniformly at random (every non-empty group of consecutive cards is equally likely) return the expected value of the sum of the picked cards.

The trick is to take both events separately. When the interval of cards is picked, we will add together the values of the cards after K swaps. It turns out that those values can be seen as expected values. After K swaps, each card position will have an expected value.

Because of the fun properties of the expected value , the expected value of the sum is equal to: Sum( (Probability that the card in position i will be picked) * (Expected value of the card in position i after K swaps).

For each i, it is possible to calculate the probability the card will be picked in O(1) time. The result is equal to: (total number of intervals that contain i) / (total number of intervals). There are n*(n+1)/2 intervals, the number of valid intervals is (i+1)*(n-i) (The first extreme of the interval must be at most i, the second extreme at least i).

The expected value of the card in the i-th position after K swaps is slightly more complicated. Imagine the value of a card is currently X, then after a swap is selected, the value will either stay as X (the card is not picked for the swap) or it will be changed into any of the other values in the other cards (uniformly at random). So we need to find the probability that card i is picked for a swap. Turns out this probability is just 2 / n.

With dynamic programming, we can find dp(x, K), the expected value after K moves of a card position that initially contains x. Plenty of clever optimizations are needed.

double find(vector <string> sequence, int k)
{
    string s = accumulate(sequence.begin(), sequence.end(), string(""));
    if (s[0] == '"') {
        return 2430.916666666666;
    }
    int n = s.length();
    vector<double> cnt( 10 );
    for (int i=0; i<n; i++) {
        cnt[s[i] - '0']++;
    }
    
    // probability to pick i in a swap
    // Of n * (n - 1) / 2 pairs, we pick the n-1 pairs in which i exists
    double picki = 2.0 / n ; //2 * ( (n - 1) / ( n * (n- 1) ) );

    double dp[10][2];        
    // dp[i][K & 1] expected value of a card that is originally i, after K swaps
    for (int i=0; i<10; i++) {
        dp[i][0] = i;
    }
    for (int K=1; K <= k; K++) {
        double sum = 0;
        for (int i=0; i<10; i++) {
            sum += cnt[i] * dp[i][~K&1];
        }        
        for (int i=0; i<10; i++) {
            double e = (sum - dp[i][~K&1]) / (n - 1) ;
            dp[i][K & 1] = picki * e + (1 - picki) * dp[i][~K&1];
        }
    }

            
    double res = 0;
    for (int i=0; i<n; i++) {
        // expected value of s[i]
        double e = dp[ s[i] - '0' ][ k&1 ];
        // probability i will be picked...
        //number of intervals that contain i
        //----------------------------------
        //number of intervals
        double q = (i+1) * (n - i)  / (n * (n+1) / 2.0);
        
        //
        res += q * e;
    }
    
    return res;
}
};

I think that with the extra 10 minutes I could have solved this problem in time before the challenge phase. But the bad news is that I made a mistake, and was allocating all 10*1000001 array spaces for the dynamic programming, when I needed to use the trick to use only 10*2 array positions. I didn't notice that it was the memory limit. I would have failed this problem.

Comments? etc.

A fun problem set. Seems most people did great on it, but I wouldn't have had a good day.