GAMSTICK - Editorial

editorial
, , , ,
1

PROBLEM LINK:

Practice
Contest

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

DIFFICULTY:

Medium

PREREQUISITES:

Nothing.

PROBLEM:

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.

QUICK EXPLANATION:

Consider all the cases.

EXPLANATION:

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 AND TESTER’S SOLUTIONS:

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

2

Can someone suggest some corner cases for this problem

Here me WA solution

3

@sonu_628

Input:
1
4 1 2 2 4

Expected Output:
Draw

Your Output:
Miron

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

My WA solution.

1 Like
4

@rathi_22

6 1 6 2 3

Expected : Draw

Yours : Slava

1 Like
5

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 ?!

@hloya_ygrt

1 Like
6

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) ???

7

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.

8

@admin

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

9

I think it’s a typo.

10

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

2 Likes