Cannot get logic in GAMSTICK

Hey guys, I was upsolving a question I was unable to solve during August Cook-Off.

Its Game on Stick (problem 4). I read the editorial and I am not able to digest some points it said. The editorial link is here

It quotes that-

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. 

My confusion is that, lets we have N = any odd number (say 9). I have positioned first player at (1,1) and second player at exacty the middle cell (1,5). Now we get pos as-

pos= (5+1)/2 =3

N-pos = 9-3=6

2*pos=6

2*(N-pos)=12

Following editorial,2*pos<2*(N-pos) \implies First player wins

But this obviously is wrong. So I need help regarding 2 things-

  1. Please help in getting the intuition behind solving the problem. I tried making cases, but they are JUST TOO MANY. When N is odd, N even, when both are on same side, both on different side etc. I think I used over 20 if else statements!
  2. After explaining your intuition (please, that is seriously needed!!), please share your solution on what you did, how you simplified stuff etc. (In case you didnt include that in part 1.) .Basically the implementation details/tricks (if any).
1 Like

I went through the problem and editorial, and about the editorial’s x_1=x_2 case, I think it’s just a typo, and the editorialist meant to write the opposite of who wins. But the editorial’s approach seemed convoluted, so I came up with my own which at least to me seems more intuitive. Here goes.

The important thing in this game is that to win you must capture both the vertical cells at the center of the grid so that the opponent is stuck on a side with lesser number of cells. One can win with a greater difference also but this is the minimum requirement for winning. Odd and even N should be considered separately
ODD: 1 2 3 4 5 +---+---+---+---+---+ | | | X | | | +---+---+---+---+---+ | | | X | | | +---+---+---+---+---+ EVEN: 1 2 3 4 5 6 +---+---+---+---+---+---+ | | | X | Y | | | +---+---+---+---+---+---+ | | | X | Y | | | +---+---+---+---+---+---+

In the odd case if you capture both the cells marked X you win. No matter on which side the opponent lies, he cannot get more than half the cells.
In the even case you must capture the X cells if the opponent is to the left of the center, and the Y cells when the opponent is to the right.
If no player can do either of these, it’s a draw. This occurs when a player ends up directly above/below the other. One player can always mimic the other’s motion and prevent the other from moving vertically. So it will always end in a draw because no one will let the other win.

Let w_1, w_2 be the center coordinates that player 1 and player 2 respectively must capture to win.
If N is odd, then w_1 = w_2 = \frac{N + 1}{2}
If N is even, then w_1 must be one of the two centers that is closer to player 2, and vice versa. That’s because to win a player must trap the other on a side with lesser cells as already discussed. So w_1, w_2 will each end up being \frac{N}{2} or \frac{N}{2}+1.

Let’s consider what each player needs to do to win. If both players cannot win, we decide it’s a draw. The dist(a, b) function used below is just the distance along the row dimension, which is just abs(a - b).

Case 1: x_1=x_2

Both players are on the same row. For player 1 to win, he must reach w_1 and then move vertically. But for that he must reach w_1 before player 2 can reach w_1. Similarly player 2 wants to reach w_2 before player 1.
If dist(w_1, y_1) \le dist(w_1, y_2), player 1 wins.
If dist(w_2, y_2) < dist(w_2, y_1), player 2 wins.
You can easily verify this. Note that for player 1 it is \le but for player 2 it is <. That’s because player 1 has the advantage of starting first.

Case 2: x_1 \ne x_2

As before, for player 1 to win, he must reach w_1 and then move vertically. But now if he reaches w_1, but in the next step player 2 also reaches w_1 in the vertically adjacent cell, he cannot win. So each player must reach his target 1 step in advance of his opponent as compared to before.
If dist(w_1, y_1) < dist(w_1, y_2), player 1 wins.
If dist(w_2, y_2) + 1 < dist(w_2, y_1), player 2 wins.

That’s it. Here is my solution, and a more concise solution.
Let me know if some part is not clear!

5 Likes

I wish I could help you

( ಥـْـِـِـِـْಥ)

1 Like

No worries, I am just waiting for @meooow to have a look at the question. He is the one who usually helps and guides me :slight_smile: :smiley:

Damn! I got 80% of this right. For N= even, I considered your “XX” and “YY” cells as “XXXX” (single grouping) and had to go on and on making conditions. A different perception would have helped me save those 8 hours T_T

And then I made my approach even more complicated by making separate conditions when players are on same side and separate if on different sides (and those were the reason behind WA.)

I loved this approach. Its :heart::heart::heart::heart::heart::heart: :smiley: :slight_smile:

Yes at first I was also thinking separately for when players are on the same side vs when on the opposite sides, but I realized that can be avoided by assigning separate targets w_1 and w_2 to the two players :slight_smile: