Programming Algorithm: Finding a Winner

Question

I will compete in OBI (Brazilian Olympiad in Computer Science, in English), and I have been trying a few exercises from past years. But I can’t find a solution for this exercise (I translated it, so there may be a few errors):

Chocolate contest

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

• They will eat one after another (Paula always starts).
• Each time they can eat only from 1 to M balls, M decides the mother of Paula, so they do not suffocate.
• If someone ate K balls in turn, the next one cannot eat K balls.
• One who cannot play according to the above rules loses.

In the example below with M = 5 and 20 balls, Carlos 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 

Please note that in the end, Carlos could not eat 2 balls to win, because Paula ate 2 in her last turn. But Paula could not eat the last ball, because Carlos ate 1 in his last turn, so Paula can not play and loses.

Both are very smart and play optimally. If there is a sequence of turns that guarantees him victory regardless of other turns, he / she will play these sequences.

Task:

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

Input:

Input contains only one test group, which should be read from standard input (usually a keyboard).

The input has 2 integers N (2 ≤ N ≤ 1,000,000) and M (2 ≤ M ≤ 1000), N is the number of balls and M is the number allowed per move.

Output:

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

Examples:

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

I tried to solve the problem, but I have no idea how to do this.

The 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 not understand the algorithm. Someone asked a question about this problem on another site, but no one answered.

Could you explain the algorithm to me?

The following are the expected results 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 logical function FirstPlayerWin (FPW) that takes two arguments: the number of candies on the left (c) and the last move (l), that is, the number of candies accepted in the previous round, which is 0 on the first move. The subroutine returns true if and only if the first player playing in this situation is guaranteed victory.

The main 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, this is not true. This is where dynamic programming takes place, because now FPW calculation is reduced to FPW calculation for lower values ​​of c.

However, for storing records for this wording, records in table N * M will be required, where, since the solution you specified uses only records in table 2N.

The reason for this is that if FPW (c, 0) is true (the first player wins if any move is available in chocolate c), but FPW (c, x) is incorrect for x> 0, FPW (c, y) for and y ! = x must be true. This is because if negating the movement of x makes the player lose, that is, the player will only win by playing x, then moving x is available when y is instead prohibited. Therefore, it is enough to store for any account “c” no more than one forbidden move, which forces the player to lose there. Thus, you can reorganize the dynamic programming problem so that instead of storing the full two-dimensional array FPW (c, x) you have two arrays, one stores the values ​​FPW (c, 0), and the other stores single forbidden movements that cause the first the player will lose, not win, if any.

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

Answer 2

I think this is another weakly disguised exercise in dynamic programming. The state of the game is described by two values: the number of remaining balls and the number of balls eaten in the previous movement. When the number of remaining balls is <= M, the game is either won (if the remaining number is not equal to the amount consumed in the previous move) or lost (if there is one - you cannot eat all the balls, and your opponent can eat the balls that you leave )

If you developed a win / loss situation for all the numbers of balls up to H and all possible numbers of balls eaten by the previous player and wrote this in the table, then you can work out the answers for all the number of balls up to H + 1. A player with balls H + 1 and k balls eaten in the previous step, will consider all possibilities - to eat i balls for i = 1 to M, except for the illegal value of k, leaving the position with balls H + 1-i and the previous move i. They can use the table giving the winning situation for the balls H to try to find the legal k that gives them victory. If they can find such a value, the position H + 1 / k is a victory. If not, it will be a loss, so they can expand the table to hide up to balls H + 1, etc.

I did not process all the code without commenting, but it looks like he could do something like this - using dynamic programming such as recursion to build the table.