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.

Answer 2

I think this is yet another thinly disguised exercise in dynamic programming. The state of the game is described by two quantities: the number of balls remaining, and the number of balls eaten in the previous move. When the number of balls remaining is <= M, the game is either won (if the number remaining is not equal to the number eaten in the previous move) or lost (if it is - you can't eat all the balls, and your opponent can eat the balls that you leave).

If you have worked out the win/lose situation for all numbers of balls up to H, and all possible numbers of balls eaten by the previous player and written this down in a table, then you can work out the answers for all numbers of balls up to H+1. A player with H+1 balls and k balls eaten in the previous move will consider all possibilities - eat i balls for i = 1 to M except for the illegal value of k, leaving a position with H+1-i balls and a previous move of i. They can use the table giving the win-lose situation for up to H balls left to try and find a legal k that gives them a win. If they can find such a value, the H+1/k position is a win. If not, it is a loss, so they can extend the table to cover up to H+1 balls, and so on.

I haven't worked through all the uncommented example code, but it looks like it could be doing something like this - using a dynamic programming like recursion to build a table.