You are not logged in. Please login at www.codechef.com to post your questions!

×

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

asked 12 Sep '17, 19:25

vijju123's gravatar image

5★vijju123 ♦♦
15.4k12066
accept rate: 18%

edited 14 Sep '17, 23:45

1

I wish I could help you

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

(15 Sep '17, 19:06) kunnu1202★

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

(15 Sep '17, 20:27) vijju123 ♦♦5★

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 $\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.
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!

link

answered 16 Sep '17, 01:20

meooow's gravatar image

6★meooow ♦
7.1k718
accept rate: 48%

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) vijju123 ♦♦5★

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) meooow ♦6★
toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • image?![alt text](/path/img.jpg "title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported
  • mathemetical formulas in Latex between $ symbol

Question tags:

×2,719
×1,070
×178

question asked: 12 Sep '17, 19:25

question was seen: 406 times

last updated: 16 Sep '17, 03:25