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

×

TABGAME - Editorial

0
5

PROBLEM LINK:

Div1
Div2
Practice

Setter- Oleksandr Kulkov
Tester- Teja Vardhan Reddy
Editorialist- Abhishek Pandey

DIFFICULTY:

EASY

PRE-REQUISITES:

Observations, Strings, 2-D arrays, Game Theory.

PROBLEM:

Given $2$ strings which tell if a player bringing coin to that cell wins or loses, we need to tell $Q$ queries asking "Who wins the game if game starts at $(x,y)$ and alice goes first?"

QUICK-EXPLANATION:

Key to AC- Observing winning and losing positions diagonally!!

We have data to tell who wins if stone comes at $(0,i)$ or $(i,0)$. Use that to derive data of first $2$ rows. Use the observation that, winning positions dont change diagonally after row 2. (There are corner cases where they can change from row 1 to row 2 going diagonally, but they are guaranteed to remain constant thereafter). Now, store the states (whether player starting at that cell wins or loses) for first $2$ rows and first $2$ columns. After this, all thats left is to do this to make cases. If $(x,y)$ does not lie in first $2$ rows or first $2$ columns, find the corresponding cell in row/column $2$ diagonal to $(x,y)$ (if cell is not in row 1 or row 2 or column 1 or column 2) to find the answer, as states remain constant diagonally. If cell is in first $2$ rows or columns whose state we calculated above, we simply refer to it to answer the query.

EXPLANATION:

This editorial will have $2$ sections. We will be referring to first the brute force, and then deal with what we observed and how we used it to get full solution.

First Subtask-

There was a lot of confusion in this question related to what does $0$ represent and what does $1$ represent, mostly because the question followed a different convention. Hence, to avoid any such confusion, let me denote $W$ as winning position, i.e. player starting from this cell wins, and $L$ by losing position, i.e. player starting from this cell loses.

Lets first get how the games are played by the players. The only thing you need to remember is, for impartial games, usually the starting position itself determines the winner if players play optimally. If "playing optimally" is something that confused you in this question, read the paragraphs below in tab-

View Content

What does above mean (especially if you read the paragraphs in hidden tabs)? The starting position will determine the winner, and if we know states of previous cells then we can find states ($W$ or $L$) of current cell. All thats left is, finding a base case to start with so we can start finding if the position is $W$ or $L$.

How do we do that....HMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMMM. The setter gave us $2$ strings, can we use them for this? Turns out we can :D

I will denote the string also by $WLWLWWWL...$ to avoid any confusion regarding $0$ and $1's$. $W$ means player bringing stone at that position wins, and $L$ means he loses.

We can move vertically up, or horizontally left. Hence, the states ($W$ or $L$) of only these 2 cells matter. For cell $(1,1)$ , we know the states of $(0,1)$ and $(1,0)$ in input. Once we get $(1,1)$, then along the row we can derive state of $(1,2)$ , and hence $(1,3)$ and hence $(1,4)$...and so on. Doing this for every row gives us states of all the cells. Now for every query, we see the state of given cell and accordingly append to the string.

You know the base case, and also the recurrence (when and how to assign a state $W$ or $L$). Can you come up with a pseudo code to assign current state $W$ or $L$?

alt text

Please let me make it clear. $W/L$ in matrix means player who starts his turn at that cell wins/loses, while $W/L$ in string means player who brings stone at that cell wins/loses.

Answer is in tab below-

View Content

Full Solution-

Surprisingly, this section wont be long at all!

The only difference between brute force and full solution is that, full solution observes (or proves) that diagonal elements after row 2 remain constant. Hence, while brute force tries to find the entire matrix, full solution derives the state of cell $(x,y)$ using cells in first $2-3$ rows and columns. (We only need cell which is lying "Diagonally backward" from $(x,y)$ in these rows.)

alt text

Images and all those are fine, but how can one actually get the intuition?

The most basic and commonly used method, of course, is observation. But proofs are needed to be done, so that we can verify and also better ourselves at such questions. I will first state the lemma's or rules, and then move on to prove them one by one. Proofs are in tabs, so that you can first attempt to derive them.

  1. If $A_{ij}=L \implies A_{i+1,j+1}=L$ as well. Meaning, if cell $(i,j)$ is losing state, then cell $(i+1,j+1)$ is losing state as well.
  2. Can we sketch a similar proof for $A_{ij}=W$? Why/Why not? What significance does it have?
  3. Prove that there cannot be more than $3$ consecutive $W's$ in matrix after row 1. After this, explore that when a $W$ changes to $L$. (You'll see it happens in case of $3$ or more consecutive $Ws$.

Proof of Lemma 1-

View Content

Answer for 2.-

View Content

Proof for 3.

View Content

Now, with this idea clear, how do we implement it? One of the neat implementations used by @um_nik ought to be discussed here :D.

  • Create a matrix. Find Row 1 and Row 2, along with Column 1 and Column 2 as we discussed above.
  • If Query is in row 1 or row 2, we already have the answer
  • Else, diagonally move backward until you come at row or column 2. The answer is stored in your table.

Code for reference is in tab below-

View Content

SOLUTION

Author's solution can be found here.

Tester's solution can be found here.

View Content

Editorialist's solution can be found here.

$Time$ $Complexity=O(N)$
$Space$ $Complexity=O(N)$

CHEF VIJJU'S CORNER :D

1. Is your idea same as editorial? Still got TLE? Make sure you done use $s=s+'1'$ for making the output string, as this method creates a completely new string and then adds '1' to end, making it $O(N^2)$! Use $s+=1;$ for better performance. Just like creating a new vector to add an element at last v/s adding an element at back of vector.

2. At the end of the day, I'd want you to remember the part of $W$ and $L$ which we discussed. You can apply that to any such game. If starting position determines winner, and you know the state of positions which you can visit from current cell, you can derive for this cell as well. A player wins only if he can force his opponent to lose by making sure opponent plays only at "losing" or $L$ cells. Hopefully this will clear the numerous doubts among div2 guys on what "playing optimally" is :)

3. Often I am asked, what does a coder truly do to ace all the contest's problems?

View Content

4. Setter's Notes (his solution isnt based on observations)-

View Content

5. Related Problems:
- Hackerrank Section for basic problems on game theory.
- Codeforces Section for trickier problems.

asked 13 Sep '18, 01:13

vijju123's gravatar image

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

edited 04 Nov '18, 16:27

Can I somehow get test data for past problems, that my solution failed? It is often very helpful for debugging. For any problem, not for this one.

(27 Oct '18, 04:48) batura_dima5★

I was able to get AC using brute force approach implemented with bitwise operations.

Let's say U1 is the bitwise representation of a diagonal (coming from top right to bottom left), then the next diagonal U2 can be calculated as: U2 = ~(U1 & (U1<<1)). Plus the bits corresponding to the boundary conditions need to be overriden when necessary. Using bitset would still cause TLE, so need to manually implement bitset functionality using array of unsigned long long's and apply operations only to the necessary elements.

link

answered 20 Sep '18, 19:29

shoom's gravatar image

6★shoom
3534
accept rate: 30%

can you please explain why l at 1,3.

link

answered 17 Sep '18, 20:20

vaibhav190499's gravatar image

4★vaibhav190499
16
accept rate: 100%

Ouch!! I am sorry, it should be a $W$ :(

(17 Sep '18, 21:52) vijju123 ♦♦5★

why are they trying to prove there cannot exist three consecutive 1's

link

answered 18 Sep '18, 11:50

sasidhar_reddy's gravatar image

4★sasidhar_reddy
0
accept rate: 0%

Think!

How did we prove that there cannot exist $3$ consecutive $1's$? By contradicting that it'd be a $L$ in place of $W$ in middle. Now, try to find conditions when $W$ changes to $L$ diagonally. You'll see that this happens when there are $3$ consecutive $1's$

(18 Sep '18, 11:55) vijju123 ♦♦5★

got it . thanks

(18 Sep '18, 15:42) sasidhar_reddy4★

I have a doubt ....its a mistake but I want to ask why my approach is wrong? my solution

what I tried was every player either wants to win or try another user can lose if he is not winning... so, what I was doing :

user 1 starts the game and checks both the sides if row and column both are 0 moves towards the side having odd distance. if both sides have even distance then he know that he will try his luck in the next chance[if he gets otherwise he will lose]. similarly, checked for (0,1) , (1,0) and (1,1) combination .....

thanks in advance...

link

answered 18 Sep '18, 22:23

gryphon's gravatar image

3★gryphon
112
accept rate: 0%

edited 18 Sep '18, 22:28

Hi,
In my solution I was traversing horizontally for calculating answers for the first two columns, but got stuck in TLE.
Please help
Thanks in advance

link

answered 18 Sep '18, 23:03

tmk23's gravatar image

2★tmk23
1
accept rate: 0%

if someone still needs soln(commented) he can refer mine i had mapped all the diagonal element

link https://www.codechef.com/viewsolution/20233525

link

answered 18 Sep '18, 23:41

gyanendra371's gravatar image

3★gyanendra371
2936
accept rate: 33%

I don't understand why do you say that there cannot be more than 3 consecutive W, there cannot be 3 consecutive W! and the proof is:

  • say there are 3 consecutive W at (i, j-1) (i, j) (i, j+1).
  • (i-1,j) must be also a W, because if it was an L than the next coordinate on its diagonal (i, j+1) would have been L, but we know its a W
  • but this can not be: (i-1, j) is W and (i, j-1) is W so (i, j) must be L - these are the rules...
link

answered 19 Sep '18, 00:27

ihadanny's gravatar image

2★ihadanny
1
accept rate: 0%

The proof clearly says that $3$ $W$ are not allowed, and it makes it very clear. Stop nitpicking on grammar like that :/

(19 Sep '18, 01:22) vijju123 ♦♦5★

can someone please explain the setter's solution?

link

answered 19 Sep '18, 01:20

ihadanny's gravatar image

2★ihadanny
1
accept rate: 0%

I successfully solved this question during the live contest but implementation of my code was getting wrong everytime. Hard luck!

link

answered 20 Sep '18, 00:59

aamir_911's gravatar image

3★aamir_911
11
accept rate: 0%

Any idea as to why am I getting TLE on subtasks 9,10 and 11? @vijju123

My Code

link

answered 22 Sep '18, 18:35

kshitij_07's gravatar image

4★kshitij_07
364
accept rate: 6%

Try to do the 2-D array declaration outisde the while(t--) loop, and replace ll with int. The TL is tight for this question.

(22 Sep '18, 19:49) vijju123 ♦♦5★

Solutions arent accessable?

link

answered 24 Sep '18, 20:00

vamousrafa's gravatar image

2★vamousrafa
311
accept rate: 0%

For now try the tester's solution given under tab. There are some messups with solution link by @admin this time.

(24 Sep '18, 20:56) vijju123 ♦♦5★

why we are subtracting from each character of input strings '0'?? Thanks in advance.

link

answered 15 Oct '18, 01:40

hp98's gravatar image

2★hp98
1
accept rate: 0%

Thats just an implementation step. If I subtract '0' from '1' , I get (49-48) [their ASCII values!!] =1 which I can use as an index in array.

(17 Oct '18, 01:05) vijju123 ♦♦5★

I read this editorial twice but still can't get the intuition behind making two separate cases for filling row1,col1 and row2..n,col2..n. Can someone make me understand this part ?

If(A0,j==W) then Aij=W//I can win by moving to cell (0,i) Not able to understand this line.

Thanks in advance :)

link

answered 18 Oct '18, 11:25

harrypotter0's gravatar image

4★harrypotter0
318110
accept rate: 1%

edited 18 Oct '18, 12:00

Which line made you think that you HAVE to fill ONLY that way? I might help there! You can fill anyway if I recall correctly- there are multiple valid ways out of which any can be chosen.

(18 Oct '18, 11:37) vijju123 ♦♦5★

actually, I am not able to understand this part. Could please provide comments over filling of the table for row 1.

Row 1-

If(A0,j==W) then Aij=W//I can win by moving to cell (0,i) Else if (A1,j−1==L) then Aij=W//I can force my opponent to lose by moving to cell (1,j−1) Else A1j=L

Here, if A[0][j]=='W' then why A[i][j]='W'??

(18 Oct '18, 12:06) harrypotter04★
1

Assume 1 based indexing, where $A[0][j]$ represents the j'th character in string (just like shown in pciture, string character above column). If ending up on that cell is $W$, then I will just move my cell to that and win. Dont assume Row 1 corresponds to 0'th index in array. 0'th index is for string.

(18 Oct '18, 12:57) vijju123 ♦♦5★

@vijju123 could you provide your solution for this problem as above links are not working.

(18 Oct '18, 14:40) harrypotter04★

I have to ask @admin to fix link to setter's codee :/ . There was no code of setter at testing page else Iwould have pasted it. It was with @admin .

There wasnt any editorialist solution, idk which solution he linked lol. You can refer to @um_nik 's code for now - its based on editorial except that it calculates for first 10 rows. I will try to upload my solution by evening.

(18 Oct '18, 15:15) vijju123 ♦♦5★

My solution
I had created two functions for alice and bob. Then I subtracted min(x,y) - 2 from both x and y. Then called alice(x,y ).
Was getting NZEC ( probably Stack Overflow. )
So, for both alice and bob, tried decreasing which is lower between x and y first, then the higher.
Got AC. :)

link

answered 04 Nov '18, 20:15

babangain's gravatar image

3★babangain
434213
accept rate: 4%

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:

×3,820
×643
×323
×267
×241

question asked: 13 Sep '18, 01:13

question was seen: 3,385 times

last updated: 04 Nov '18, 20:15