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