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

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.

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.

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.

Here is my link to the solution

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

Make a 2D matrix as mentioned by @admin5

Try to find the pattern for the following cases :

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