Programming algorithm: finding the winner of a competition

Question

I will compete in the OBI (Brazilian Olympiad of Informatics, in English) and I am trying a few exercises from the last years. But I can't find a solution for this exercise (I translated it, so there may be a few errors):

Chocolate Competition

Carlos and Paula just got a bag of chocolate balls. As they would eat everything too quickly, they made a competition:

• They will eat alternately, one after the other (Paula always starts).
• Each time, they can only eat from 1 to M balls, M decided by Paula's mother, so they don't choke.
• If one ate K balls in his/her turn, the next can't eat K balls.
• Whoever can't play according the rules above loses.

In the example below with M = 5 and 20 balls, Carlos has won:

Who plays        How many ate        Balls left

                                     20
Paula            5                   15
Carlos           4                   11
Paula            3                   8
Carlos           4                   4
Paula            2                   2
Carlos           1                   1

Note that in the end, Carlos couldn't eat 2 balls to win, because Paula ate 2 in her last turn. But Paula couldn't eat the last ball, because Carlos ate 1 in his last turn, so Paula can't play and loses.

Both are very smart and play optimally. If there is a sequence of turns that ensures him/her the victory independent of the other's turns, he/she will play these sequences.

Task:

Your task is to find out who will win the competition if both play optimally.

Input:

The input contains only a single test group, which should be read from the standard input (usually the keyboard).

The input has 2 integers N (2 ≤ N ≤ 1000000) and M (2 ≤ M ≤ 1000), being N the number of balls and M the number allowed per turn.

Output:

Your program should print, in the standard output, one line containing the name of the winner.

Examples:

Input:          Output:
5 3             Paula
20 5            Carlos
5 6             Paula

I've been trying to solve the problem, but I have no idea how.

A solution in C can be found here: http://olimpiada.ic.unicamp.br/passadas/OBI2009/res_fase2_prog/programacao_n2/solucoes/chocolate.c.txt But I can't understand the algorithm. Someone posted a question about this problem in another site, but nobody replied.

Could you explain me the algorithm?

Here are the expected outputs of the program: http://olimpiada.ic.unicamp.br/passadas/OBI2009/res_fase2_prog/programacao_n2/gabaritos/chocolate.zip

Answer 1

Let's say we have a boolean function FirstPlayerWin (FPW) that takes two arguments: number of chocolates left (c) and the last move (l) i.e. the number of chocolates taken on the previous round, which is 0 at the first move. The routine returns true if and only if the first player to play at this situation is guaranteed a win.

The base case is that FPW(0, l) = false for any l != 1

Otherwise, to calculate FPW(c, l), FPW(c, l) is true if for any x <= M, x <= c, x != l, FPW(c - x, x) is false. Otherwise it is false. This is where dynamic programming kicks, because now the calculation of FPW is reduced to calculating FPW for smaller values of c.

However, storing the entries for this formulation would require N * M table entries, where as the solution you pointed to uses only 2N table entries.

The reason for this is that if FPW(c, 0) is true (first player wins if any move is available at chocolate count c) but FPW(c, x) is false for x > 0, FPW(c, y) for and y != x must be true. This is because if denying the move x makes the player lose, i.e. the player would win only by playing x, then the move x is available when y is banned instead. Therefore it is enough to store for any count 'c' at most one forbidden move that causes the player to lose there. So you can refactor the dynamic programming problem so that instead of storing the full 2-dimensional array FPW(c, x) you have two arrays, one stores the values FPW(c, 0) and the other stores the single forbidden moves that cause the first player to lose instead of winning, if any.

How you get to the exact text of the quoted C program is left as an exercise to the reader.