Games (1)

Here is a simple game.

We have 2 boxes.

A position in the game is (n,m) which means the first box contains n coins, the second box contains m coins.

A move is for one player to empty one of the boxes, and then distribute the remaining coins in the non-empty box among the 2 boxes, such that each box ends up with aleast one coin.

The winner is the player who makes the last move, ie the player who makes (1,1). Cause the next player won't have a way to distribute 1 among 2 boxes where each box ends up with >=1 coins.

If you have (1,X) that is not terminal position. If we have anything > 1, we can always make a move to (1, (X-1)). Thereforce, the only "terminal position" (or P-position) is (1,1).

Another observation is that (2,x) or (x,2) is a winning position for the player who gets it.

If you're given (odd, odd) you lose no matter what if the second player is playing perfectly.

Why ?

You'll be forced to return to the second player (odd, even).

The second player can always remove one of the odd boxes, and distribute it to be (odd-1, 1)

Now when it is your turn, you can either remove the (odd-1) [so you lose], or remove the 1.

If you remove the one, you'll be back to giving the second player (odd, even).

Now what he has to do is the same. This process will keep repeating, and ultimatly the even number you're returning to the second player will be as small as 2, where he can win by emptying the box which does not have 2 and distributing the 2 so he gives you (1,1).

So how can you win if you want to ? Give your opponent (odd, odd). How to do that ?

if you're given (odd, odd) you have no hope. If you have atleast one even, give your opponent (1, even-1) and so you'll win because you'll enforce that cycle of (1,odd) => (even, odd) [to you], until the even you get is 2 and so you win.

CodeForces 7D - Palindrome Degree

Link: http://codeforces.com/contest/7/problem/D

The main challenge is to determine whether a prefix is a palindrome or not.

This can be solved using the Z algorithm in O(n).

We concatenate the string with its reverse.

The idea is that if a prefix ending at position i is a palindrome, then (z[2*n-i-1]>=(i+1)).

For each such prefix we set dp[i]=1, and then increase it with the dp value of the prefix ending in its middle (differs whether its length is even or odd).

Few Lessons About Rabin Karp after 73 Wrong Answers

Link: http://codeforces.com/contest/113/problem/B

It is indeed quite easy to produce collisions, ie make more than one string map to the same hash value.

However, it is VERY difficult to produce collisions of strings with the SAME SIZE.

Yet, even if this was possible, it is way harder to produce collisions with the same size AND same middle character.

So, instead of storing the hash, concatenate it (bitwise) with the length of the string and the middle character.

That would be a good enough way for handling collisions.

Also, for some reason this pair of base and modulus is the only one that worked to pass test case #29:

int B=29;
int M=(1ll<<31)-1;

Also, instead of using set.insert, just use vector.push_back then at the very end sort and count the unique elments. This reduced the time from 1716 ms to 404 ms !

Adding two numbers in base -2

Base -2 numbers have unique representation like other bases.

The rules: (digit 1, digit 2, carry) => digit, carry next digit, carry follow digit

(0,0,0) => (0,0,0)
(1,0,0) == (0,1,0) => (1,0,0)
(1,1,0) => (0,1,1)
(1,1,1) => (1,1,1)

The idea is that for each 2 ones in position i we can get them by having 1 from next and 1 from next->next

Attached proof for the 3rd case

Note: The value of the carry for each digit can be > 1.

for each i:
   n=num1[i]+num2[i]+carry[i]
   res[i]=n%2
   carry[i+1]+=n/2
   carry[i+2]+=n/2

Note: n/2 is integer floor division (floor(n/2.0))

Sample problem: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=24&page=show_problem&problem=2062

Codility Hydrogenium 2013

I am trying to post exciting problems, together with as complete and convincing proofs as I can, and this is my first attempt.This is my first blog post. I apologize in advance if my explanation is not clear as it should be. I'll try to get back and clarify whenever I can.

Link: http://codility.com/cert/start/helium2013/

You are given a string. The problem is to find the length of the longest possible substring which satisfies the following conditions:

Is prefix (starts from the first character of the string)
Is suffix (finishes at the last character of the string)
Occurs atleast once in the middle of the string (neither a suffix nor a prefix)
None of the 3 occurances mentioned above overlap

The intended solution is to have a linear time complexity O(n), where n is the length of the provided string.

A prerequisite to the solution is to know the Z-Algorithm. The Z-Algorithm constructs a linear array (size n, where n is the size of the original string). Such that:

z[i] = length of longest prefix that equals a substring starting from position i

Note that, however, this does not guarantee non-overlapping. Which means in this case for example:
a  a  a  a  a  a
1 2  4  3  2  1

This issue can be easily solved by modifying the z value, so after calculating it, we modify each z[i] to be:

z[i]=min(z[i],i)

Which means the length of the largest non-overlapping prefix that equals a substring starting from position i.

Now that we have this, we immediately realise that the problem becomes quite easily solvable if it was only for prefix\suffix without needing another reptition in between.

If a substring starting at position i is a suffix that equals a prefix, it will have to satisfy the equality:
i+z[i]== n (where n is the length of the string)

So, this begins the idea of the basic algorithm:
For each suffix that is a prefix AND is repeated somewhere in between, pick the max of those

The question now becomes: How to know if I have a suffix that I know occurs as prefix as well, whether or not its repeated somewhere in the middle.

To solve this issue, we would construct an auxillary array to the z[] array.

This array would have the following property:
dp[i]==length of longest possible prefix that equals a substring starting from i AND does not overlap with a potential suffix that covers all or part of it.

To calculate dp[i] for each i, we first note the following:
Suppose f ==length of longest possible prefix that equals a substring starting from position i == min(z[i],i)

Number of characters after this substring will be: (n-1)-(i+f-1)

Now, this is the crux of the algorithm:
if number of characters after the longest non-overlapping prefix from it is >= length of that prefix:
dp[i]=f
Why ?
First, we can not make it > f
But how about < f ? Do we lose anything by making it equal to exactly f ?
Well, the idea is that if there exists a suffix after me, it MUST be within the characters after me. And if there are more characters after me than my length, it must be there. Otherwise its length will be > f (proof by contradiction).
Otherwise:
dp[i]=floor((n-i)/2.0)
Why ? Well, there are less characters after me than my length. This means I occupy > half the remaining characters from my start position till the end of the string.

The maximum suffix that can co-exist with me is one that occupies half whats left and not anymore.

What we have to do after that is a simple iteration from backwards. For each valid suffix (that occurs as a prefix as well), we check the maximum value of dp[] BEFORE i (can be easily calulated in O(1) using an auxillary array). If its >= current suffix length, then res=max(res,n-i). Then we return res in the end.

Similar problem (overlap allowed): http://codeforces.com/contest/126/problem/B