Table Game Approach

general
1

Can anyone share their approach(100pts) for the problem TableGame?

2

In order to get 100 points there is a pattern in 2d dp matrix so we dont need to fill whole matrix.

Example:
given string is 1010 and 1101 so matrix will be

  1 0 1 0
1 0 1 0 1
1 1 0 1 0
0 1 1 0 1
1 0 1 1 0

Here all the elements in diagonal from right uppermost corner are same, so we don’t need to fill whole matrix we can just fill 2 rows and 2 colums and can give answers for all queries.

1 Like
3

U can see the pattern and check that it is repeating just solve for n,m = 10 and print the Bruteforce and then u will find that its repeating.

4

From A[2][2],
if A[i][j] = False, then A[i+1][j] along with A[i][j+1] must be True.
That’s because, not(False) + something always True.
As, A[i+1][j] and A[i][j+1] is True, A[i+1][j+1] must be false as not(True) or not(True) is False.
Hence, if an element is False for i greater 2 and j greater 2 then A[i+1][j+1], A[i+2][j+2],… will be False, same is applicable for True.
Now if any i and j is greater than 2, I was reducing the smallest among them two by subtracting some number from both.
I submitted both Top-Down and Bottom up approach this way, They got RE ( Too many recursion, As difference between a and b was probably high) and TLE.
Now for Top-Down approach, I called bob(a-1,b) first if a is lower then bob(a,b-1) and vice-versa if b is lower to reduce no. of pending recursions.
And got AC finally on 30th submission. :slight_smile:
Here is my link to the solution

5

1 2 3 4 5 6 7 8
1 * - * * * * - *
2 * * - * - * * -
3 * - * - * - * *
4 - * - * - * - *
5 * - * - * - * -
6 - * - * - * - *
7 * - * - * - * -
8 * * - * - * - *
above matrix is formed for these two strings

str1 --> 11100011

str2 --> 00011100

* represent a winning position and - represent a loosing position

from position (2,2) and onward values are repeating on the diagonals
you just have to fill row 1&2 and column 1&2

6

Make a 2D matrix as mentioned by @admin5

Try to find the pattern for the following cases :

  1. when all the characters in both the strings are 0 , Example : str1 = 0000… AND str2 = 0000…
  2. when all the characters in any of the string are 0 , Example : str1 = 000000… OR str2 = 00000…
  3. when strings contains both 1s and 0s , Example str1 = 10101011000… , str2 = 10011101…