GAME THEORY IN COMPETITIVE PROGRAMMING
Game Theory in Competitive Programming Series: Part 5
Part 5 of Game Theory in CP — Circle Game(Codeforces)
Welcome to part 5of this series, in case you have missed part 4, here is the link: https://medium.com/intellectually-yours/game-theory-in-competitive-programming-series-part-4-e102ad86ec6c
PROBLEM STATEMENT:
Utkarsh is forced to play yet another one of Ashish’s games. The game progresses turn by turn and as usual, Ashish moves first.
Consider the 2D plane. There is a token which is initially at (0,0). In one move a player must increase either the x coordinate or the y coordinate of the token by exactly k. In doing so, the player must ensure that the token stays within a (Euclidean) distance d from (0,0).
The game ends when a player is unable to make a move. It can be shown that the game will end in a finite number of moves. If both players play optimally, determine who will win.
PROBLEM LINK:
CONSTRAINTS:
d (1≤d≤10^5), k (1≤k≤d).
INPUT FORMAT:
The 1st line contains the T the number of test cases.
The only line of a test case contains the Euclidean Distance d and k respectively
OUTPUT FORMAT:
For each test case, the output should be the name of the winner that is, Utkarsh or Ashish.
INPUT EXAMPLE:
5
2 1
5 2
10 3
25 4
15441 33
OUTPUT EXAMPLE:
Utkarsh
Ashish
Utkarsh
Utkarsh
Ashish
HINT:
The focus here is not on the subsequent moves that lead to the result, but on the last point inside the area/ the 1st point outside the area, if you can identify that coordinate you can tell which player wins.
SOLUTION/EXPLANATION:
The game is always started by player 1 as given in the problem. Thus the player 2 can keep the token on the line x=y at his turn. Now as the play continues there will arise 2 cases at the end.
1) The 1st coordinate outside the permissible area will be (X1,X1) where X1 belongs to Z*k. Z being any arbitrary integer >= 0.
2) Or it would be (X1,X1+k) or (X1+k,X1) where X1 belongs to Z*k. Z being any arbitrary integer >= 0.
Now if we observe the 1st case scenario it is only possible if that was moved by player 2(coordinate on the line x=y ). Thus player 1 being the victor.
In the second case the coordinate can only be achieved by player 1(Lying outside the line x=y). Thus ensuring player 2’s victory.
If both the payers play optimally this is the result irrespective if the game is prolonged by any player by diverging from the x=y line by more than k units.
CODE IMPLEMENTATION:
That’s all for today! Stay tuned for Part 6 of Game Theory in CP !
