SRM 537: oh my

I am starting to write this as the intermission phase begins. I have submitted solutions for the 275 and the div1 500. I am fairly sure my div1 500 will survive (it is dynamic programming). But I'd say the probability my 275 fails is around 95%. I am currently first in my room, but all I need is somebody in my room to figure out the 250 is a good challenge mine and I will lose the money prize.

Div1 275
Awful stuff, I knew I was going to have issues with this problem the second I read it.

Anyway, note that eventually the distance between every two reachable numbers will be gcd(A,B). And that's really all I could get. I tried to do something that does simulations and does tons of hacks. Let's see if it works.

Div1 500
This was nice. You have some numbers. And there are K random steps. With 0.5 probability, the numbers are permuted using a permutation array. With 0.5, the numbers in each index are xor-ed against numbers with the same index in another array. Return the expected value for the first element after the K moves.

The constraint for K is at most 50, the limit on the number of ducks and the xor values (the elements of the array) is at most 10^9

There is a difference between quickly starting to code the solution and spending a lot of time wondering what to do. Permutation and Xor each can be seen as applying to only a single bit positions on all the numbers. Now, something funny about expected value. The expected value of the number in element 0 can be seen as (Expected value of the first bit) + 2 * (Expected value of the second bit) + .... etc. This is because the expected value is a linear application.

So, if you change the problem to finding the expected value of each of the (At most 30) bits of element 0. It becomes all about finding the probability that it will be 1. To find the probability that the x-th bit of element 0 will be 1, you can do a dynamic programming based on the following recurrence: F(v, bit, pos, K): The probability that the pos-th element will have a bit v (1 or 1) in the bit-th bit after K moves.

struct KingXMagicSpells 
{ 
     
    double dp[2][30][50][51]; 
    bool  seen[2][30][50][51]; 
    vector<int> ducks; 
    vector<int> spellOne; 
    // probability to get a bit in this position after K moves 
    double rec(int v, int bit, int pos, int K) 
    { 
        double & res = dp[v][bit][pos][K]; 
        if (! seen[v][bit][pos][K]) { 
            seen[v][bit][pos][K] = true; 
            res = 0; 
            if (K == 0) { 
                // no moves 
                if ( v == ( (ducks[pos] >> bit) & 1 ) ) { 
                    res = 1.0; 
                } else { 
                    res = 0.0; 
                } 
            } else { 
                // one move... 
                // was there a permutation? 
                res = 0.5 * rec(v, bit, prev[pos], K-1); 
                // was there a xor? 
                res += 0.5 * rec(v ^ ( (spellOne[pos] >> bit) & 1 ), bit, pos, K-1); 
            } 
        } 
        return res; 
    } 
     
    int prev[50]; 
    int n; 
 
    double expectedNumber(vector <int> ducks, vector <int> spellOne, vector <int> spellTwo, int K) 
    { 
        this->ducks = ducks; 
        this->spellOne = spellOne; 
        n = ducks.size(); 
        for (int i=0; i<ducks.size(); i++) { 
            prev[ spellTwo[i] ] = i; 
        } 
        memset(seen, 0, sizeof(seen)); 
        double res = 0; 
        for (int i=0; i<30; i++) { 
            res += ( (1<<i) * rec(1,i,0, K) ); 
        } 
         
        return res; 
    } 
}; 

Outcome
I finished typing this when the challenge phase ended. It seems 275 was not as much of a challenge fest as I thought. Even if I fail 275, I will be first place, and I am very sure that I will pass 500, unless I do something very lame somewhere that causes it to have random bugs.