Tom and Jerry

Hard
0/120
Average time to solve is 10m
profile
Contributed by
7 upvotes
Asked in company
Flipkart limited

Problem statement

Tom and Jerry are playing a game. In this game, they are given an undirected graph of ‘N’ vertices labelled from 0 to 'N' - 1 and ‘M’ edges. They will take alternate turns starting with Jerry.

At the beginning, Jerry is at node 1, Tom is at node 2 and there is a hole at node 0. In each turn, a player can move to any other node which has a direct edge with the node in which they are currently present, with a condition that Tom cannot move to node 0.

Now the game can end in three ways :

1) If ever Tom occupies the same node as Jerry, Tom wins.

2) If ever Jerry reaches the Hole, Jerry wins.

3) If ever a position is repeated, the game is a draw.

Your task is to find who wins the game or is there a draw between the two if both the players play optimally.

Example:

Example

In the above graph, Tom has only one choice to go to node 3. Jerry also has only one option to go to node 0. And the first turn will be taken by Jerry so it will go to node 0 and hence win the game. So we will return 1.
Detailed explanation ( Input/output format, Notes, Images )

Input format:

The first line of input contains an integer ‘T’ denoting the number of test cases.

The first line of each test case contains two space-separated integers ‘N’ and ‘M’ denoting the number of vertices and the number of edges in the undirected graph.

The next ‘M’ lines each contain two space-separated integers ‘u’ and ‘v’, denoting an edge from vertex ‘u’ to vertex ‘v’.

Output format:

For each test case, return 0 if the game draws, 1 if Jerry wins the game, or 2 if Tom wins the game.

Output for each test case should be in a separate line.
Note: 
You don't need to print anything, it has already been taken care of. Just implement the given function.

Constraints:

1 <= T <= 10
1 <= N <= 50
1 <= M <= 300
1 <= u, v <= N

Time Limit: 1 sec

Sample Input 1 :

1
5 5
0 3
3 2
3 1
4 1 
4 2

Sample Output 1 :

TOM

Explanation for Sample Output 1:

Example

So we can see from the graph, in the first step Jerry has two options, node 4 and 3. But at the same time in the first step, Tom also has two options node 4 and 3, so whatever node Jerry chooses, Tom will always catch him.
Sample Input 2 :
1
6 6
5 3
1 5
5 4
4 2
2 3
3 0
Sample Output 2:
DRAW

Explanation for Sample Output 2:

Example

So we can see from the graph, in the first step Jerry has only one option node 5. Now Tom has two options node 4 and node 3 so playing optimally Tom will choose node 3 because if Tom chooses node 4 then in the next two turns Jerry will reach node 0. So now Tom will keep on walking between node 2 and node 3 and at the same time Jerry will keep on walking between node 5 and node 4. Hence game will result in a draw.
Hint

Can you think about dynamic programming by storing the previously obtained results and saving extra time?

Approaches (1)
Bottom to Top

The basic idea is to do a memory cache search. Here we have 3 dimensions: At time T, the position of Jerry X, and position of Tom Y, so at any time and any position F(T, X, Y) should have a value, either 0 or 1 or 2.

 

Here 0 means draw, 1 means Jerry wins, and 2 means Tom wins.

 

Actually here we are doing colouring of the graph so if it’s Jerry’s turn and any of the child of the current node is 1 we will set current node’s value as 1 which means Jerry can come to this current node without being caught by Tom, but if the value of all children is 2 then the value of current node will also be 2 which implies Tom will catch Jerry at this node in any case. We can also understand this intuition by taking the current turn as Tom’s turn in the same way.

 

  • We will take a 3D array ‘DP[T][X][Y]' initialized to -1.
  • Tom and Jerry will never revisit the visited nodes because if they visit, it will result in a draw so the length of a maximum path by anyone will be of size ‘N’. So making a total of 2 * ‘N’ steps or maximum value of ‘T’ will be 2 * ‘N'.
  • So we know the maximum value of ‘T’ can be 2 * ‘N’ and maximum value of ‘X’ and ‘Y’ can be 'N'. Now the total states of ‘F’ can be 2 * ‘N’ * ‘N’ * ‘N’ = 2 * ‘N’ ^ 3.
  • There are ‘N’ nodes, so after 2 * ‘N’ steps, if we still can't decide who wins, the chase game will continue forever and return 0.
  • So we have a total of 2 * 'N'* ‘N’ * ‘N’ = 2 * ‘N’ ^ 3 status.
  • There is some position for whom we already know who will win:
    • F(*, 0,*) = 1, when Jerry go-to position, Jerry wins.
    • F(*, Y, Y) = 2, when Jerry and Tom get to the same position, then Tom wins.
    • F(2 * 'N',*,*) return 0, because, after this, it will repeat forever.
  • So there can be two cases :
  • If the current turn is of Jerry then, first of all, we will check above three conditions if none of getting satisfied then do:
    • Check the value of ‘DP[T][X][Y]’:
      • If ‘DP[T][X][Y]’ is not equal to -1 then we know we have already calculated the result for the current state so return ‘DP[T][X][Y]’.
      • Else do:
        • Increase ‘T’ by 1 and check the status of all children of the current node which we can also say neighbours of Jerry.
        • If the status of any neighbour is 1 then set 'DP[T][X][Y]'=1 and return 1.
        • If the status of all neighbours is 2 then ‘DP[T][X][Y]’=2 and return 2.
        • Else ‘DP[T][X][Y]’=0 and return 0.
  • We can similarly process for Tom’s turn with just two changes :
    • Increase ‘T’ by 1 and check the status of all children of the current node which we can also say neighbour of Tom.
    • If the status of any neighbour is 2 then set ‘DP[T][X][Y]’=2 and return 2.
    • If the status of all neighbours is 1 then ‘DP[T][X][Y]’=1 and return 1.
Time Complexity

O(N ^ 3 * K), Where 'N' is the number of vertices and 'K' is the maximum degree of a vertex in the given graph.

 

Since one recursive call costs O(K) time because we iterate through all edges of a node. Because of the cache, the number of recursive calls is limited to the number of elements in the cache which is O(N ^ 3). Thus the overall time complexity will be (N ^ 3 * K).

Space Complexity

O(N ^ 3), Where ‘N’ is the number of vertices.

 

Since the space used by the DP array is O(N ^ 3). Thus the space complexity will be O(N ^ 3).

Code Solution
(100% EXP penalty)
Tom and Jerry
Full screen
Console