SRM 537

This SRM has cash award so it attracted a lot coders. I have to wake up at 6:00am and register myself.

p275 is easy. Given A, B positive integer, and X positive integer, count number of positive Y != X such that (X,Y) can generate all linear combination of (A,B), and we only accept A*a + B*b for a,b>=0. If there are infinitely many Y, return -1.

First it is easy to see when -1 occur. Only when X divides both A and B, then we do not need Y at all. Easy check, A % X == 0 && B % X ==0. I ended up coding a gcd, which is a bit overkill.

Then we need to enumerate all possible Y's since A, B and X are all small, at most 200. Notice that for Y to be valid, (X,Y) has to be able to generate A and B, and if that is true, then (X,Y) can generate all integers representable by (A,B). For this purpose Y cannot be bigger than max(A,B) so we only try Y=1 to max(A,B). For each Y, we check whether both A and B are representable.

ans=0;
for Y=1 to max(A,B)
aok = bok = false;
for(a=0; a*X <= A; ++a)
if ((A-a*X) % Y == 0) // A is good
aok = true;
for(b=0; b*X <= B; ++b)
if ((B-b*X) % Y == 0) // B is good
bok=true;
if (aok && bok)
ans++;
return ans;

p500 is a DP problem, and everybody knows that. The problem is:
given ducks[N] which are ducks in room 0 to N-1, with N at most 50.
there are two spells, spellOne[i] makes ducks[i] turn into ducks[i] xor spellOne[i]
spellTwo[i] will move ducks[i] into ducks[spellTwo[i]] and it is a permutation.
In each day spellOne and spellTwo occur with prob=0.5. After K days, with K at most 50, what is the expected number of ducks in room[0].

We all know linearity of expectation, but we cannot really apply xor to doubles. Now what?

The trick is to consider each bit of an integer separately, as ducks[i] is at most 10^9, so 30 bits suffices. We know the operation of xor if we have only one bit.

Now we have a DP[k][i][b] means probability of ducks in room[i] being 1 after k days, when only bit b is considered. And the transition is

DP[k][i][b] +=
// spellOne
if spellOne[i] is one at bit[b]
0.5 * (1.0 - DP[k-1][i][b])
else
0.5 * DP[k-1][i][b]
// spellTwo
DP[k][spellTwo[i]][b] += 0.5 * DP[k-1][i][b]

In the end we combine all bits
for b=0 to 30-1
ans += (1<<b) * DP[K][0][b]
return ans;

p1000, asks for longest circular dominos and I did not quite understand the problem, the solution is mincost flow, though.

Got a rating boost by solving p250, boosted from 1332 to 1409.