**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.

## 5 comments :

Hah, I am the coder with the lowest score that still received a room prize.

I follow your blog frequently, and I found this post very informative. I have always wondered, though, what does "rec" stand for? I see it as the name of many memoization functions.

In my case, it is for recursion, recurrence, or recursive .

So, all your predictions came true: I am (one of) the writer, and if I am a writer, you would be the room leader :)

I'd like to be remembered for my genre savvyness.

Forgot to mention I liked the match. The div1 250 is just such a hard counter against vexorian.

Post a Comment