Hey guys, I was upsolving a question I was unable to solve during August CookOff. 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$ $Npos = 93=6$ $2*pos=6$ $2*(Npos)=12$ Following editorial,$2*pos<2*(Npos) \implies First$ $player$ $wins$ But this obviously is wrong. So I need help regarding $2$ things
asked 12 Sep '17, 19:25

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 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. Let $w_1, w_2$ be the center coordinates that player 1 and player 2 respectively must capture to win. Let's consider what each player needs to do to win. If both players cannot win, we decide it's a draw. The $\DeclareMathOperator{\dist}{dist} \dist(a, b)$ function used below is just the distance along the row dimension, which is just $\DeclareMathOperator{\abs}{abs} \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. 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. That's it. Here is my solution, and a more concise solution. answered 16 Sep '17, 01:20
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 ♥♥♥♥♥♥ :D :)
(16 Sep '17, 02:10)
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 :)
(16 Sep '17, 03:25)

I wish I could help you
( ಥـْـِـِـِـْಥ)
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 :) :D