TABGAME - Editorial

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

link CodeChef: Practical coding for everyone

1 Like

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…

can someone please explain the setter’s solution?

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

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.

1 Like

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

My Code

Solutions arent accessable?

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

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 :slight_smile:

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. :slight_smile:

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

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

got it . thanks

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

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.

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

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.

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.

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

Row 1-

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

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.

1 Like