GAMSTICK - Editorial



Author: Yuri Shilyaev
Tester: Hasan Jaddouh
Editorialist: Yury Shilyaev






Given a grid 2 \cdot N and two players in positions (x_1, y_1) and (x_2, y_2). Each player can move to adjanced by side cell on his turn, but he can’t visit cells visited by the other player. Predict the result of the game.


Consider all the cases.


It is obvious, that for some time players will move closer to each other and then some different scenarious could happen. After that they would change their x coordinate and move back, but this happens not in each game.

Let’s solve different problems for cases when x_1=x_2 and x_1 \neq x_2. Also let’s make first player to the left of the second, simply reversing the grid.

Solution for x_1 = x_2:

Let the middle between them be pos = \lfloor \frac{y_1 + y_2}{2} \rfloor. Now just compare 2 \cdot pos with 2 \cdot (N - pos). If it is less than 2 \cdot (N - pos), first player wins, if equal the game will end with draw. Second player wins otherwise.

Solution for x_1 \neq x_2:

  1. If y1=y2, the result is draw.

  2. If they stay on one diagonal, i.e y_2 - y_1 = 1, than first player can win by moving by x coordinate, or can make a draw moving to the right by y coordinate. Second player can’t win in this case. So let’s compare 2 \cdot y_1 with 2 \cdot (N - y_1).

  3. In the last case, let’s move them to the middle of the distance between them. Let D = y_2 - y_1 - 2. Now, let’s move the first player to the right on \lceil \frac{D}{2} \rceil. And the second to the left on \lfloor \frac{D}{2} \rfloor. Now, the first player can win if his potential number of visited cells is already enough to win. So the first player wins if 2 \cdot y_1 > 2 \cdot (N - y_1). The same for the second player, he could change his plan to move to the middle and change x coordinate on his last chance. Let’s compare if 2 \cdot (y_1 + 1) < 2 \cdot (N - y_1 - 1). Otherwise, he is ready for draw as the first player.


Author’s solution can be found here.
Tester’s solution can be found here.

Can someone suggest some corner cases for this problem

Here me WA solution


4 1 2 2 4

Expected Output:

Your Output:

It would be really helpful if someone could help me out similarly.

My WA solution.

1 Like


6 1 6 2 3

Expected : Draw

Yours : Slava

1 Like

for the case N=5, {x1,y1} = { 1,2} ; and {x2,y2} = {1,4} .

Pos = 3.

Hence 2⋅pos > 2⋅(N−pos) , which according to the editorial should mean player 2 won, which is not the right answer!! Can some help ?!


1 Like

why do we multiply every time by 2. like here 2⋅y1 > 2⋅(N−y1) .why didn’t we write like this y1> (N−y1) ???

If n = 5, and coordinates of the players are (1,1) and (1,3) -> player 2 should win, but with above equation player 1 is going to win. Please explain.


The author’s solution and tester’s solution links are broken.

I think it’s a typo.

In case it helps anyone, I have written an alternate approach here.