PROBLEM LINK:
Author: Arkapravo Ghosh
Tester: Arkapravo Ghosh
Editorialist: Arkapravo Ghosh
DIFFICULTY:
EASY
PREREQUISITES:
Game Theory, Game States
PROBLEM:
Chef and Chefu plays a game. Given N balls, one can remove 1, 2, or 3 balls in each move. Chefu makes the first move. If Chefu and Chef play alternately and both of them play optimally, we need to determine the winner of the game.
QUICK EXPLANATION:
We can see that 0 is a losing state, as the player who has his move with 0 balls remaining loses. 1, 2 and 3 are winning states. 4 is a losing state as whatever number of balls he removes, the other player will land with 1, 2, or 3 balls which are winning states. Similarly, 5, 6 and 7 are winning states and 8 is a losing state and so on. We can use an array with A[0] = 0, A[1] = 1, A[2] = 1, A[3] = 1 as base cases and fill up the rest using A[i] = not(A[i-1] and A[i-2] and A[i-3]). Now we can answer each test case in O(1) time. If we watch the pattern that 0, 4, 8, 12, 16 … are losing states and the rest are all winning states. So, if N is a multiple of 4, then Chef will win otherwise Chefu will win.
EXPLANATION:
We can see that when there are 0 balls, the player who has his turn loses. If there are 1, 2 or 3 balls, then the player who has his turn removes all the balls wins the game. Now, if there are 4 balls, then the player who has his move loses, irrespective of how many balls he remove – suppose he removes 1 ball, then there will be 3 left and the other player will win, if he removes 2 balls, then there will be 2 left and the other player will win and similarly, if he removes 3 balls , there will be 1 left and the other player will win. Now, if there are 5 balls, then the player will move 1 ball and make the other player fall in the same situation as in 4 balls, so that the latter loses.
So, if we see carefully, then 0 is a losing state, i.e. the player who has his turn when 0 balls are there loses. 1, 2 and 3 are the winning states, i.e. if 1, 2 or 3 balls are there, then the player who has his turn wins. Similarly, 4 is a losing state, as whatever move the player plays he will lose. 5, 6, 7 are the winning states, as the player who has his turn will remove 1, 2, or 3 balls respectively, and make the other player fall in the situation with 4 balls remaining. 8 again is a losing state as whatever number of balls 1, 2, or 3 he removes, there will 7, 6 or 5 balls remaining and the other player will again be in a winning state. And so on…
We can build an array in a bottom-up fashion to solve the problem. The base cases are: - 0 is a losing state and 1, 2, 3 are winning states. So A[0] = 0, A[1] = 1, A[2] = 1, A[3] = 1. Now, we can fill up the rest of the array, using the formula A[i] = not(A[i-1] and A[i-2] and A[i-3]), i.e. if any of the three previous states is 0, then the current state is a winning state, else if all the three previous states are winning states, then the current state is a losing state. The time complexity for this approach is O(1) with constant pre-processing time to build the array.
We can optimize this code further by a simple observation. If we watch the pattern, we can see that 0, 4, 8, 12, 16 … will be the losing states, though it is mentioned in the constraints that N > 0. So, if N is a multiple of 4, then the player who has his move first i.e. Chefu will lose and Chef will win. Otherwise Chefu will win and Chef will lose. The time complexity of this approach is O(1).
You can find both the approaches below.
AUTHOR’S AND EDITORIALIST’S SOLUTIONS:
Author’s and editorialist’s solution can be found here (array approach) and here (optimized).