Tetrahedron

Posted: 6 Dec, 2020
Difficulty: Moderate

PROBLEM STATEMENT

Try Problem

You are given a tetrahedron with vertices A, B, C, and D. An ant is standing at vertex D. The ant won't sit idle. It will keep on moving from one vertex to another along some edge of the tetrahedron. Your task is to count the number of ways in which the ant can go from the initial vertex D to itself in exactly n steps. In other words, you are asked to find out the number of different cyclic paths with the length of n from vertex D to itself. As the number can be quite large, you should print it modulo 1000000007 (10^9 + 7).

For example:

1

For n = 2, there are three cycle D -> A -> D, D -> B -> D and D -> C -> D 
Input Format:
The first line of input contains an integer ‘T’, denoting the number of test cases. Then each test case follows.

The first line and the last line of each test case contain the integer ‘N’ denoting the required length of the cyclic path.
Output Format:
For each test case, print the count the number of ways in which the ant can go from the initial vertex ‘D’ to itself in exactly ‘n’ steps modulo 1000000007 (10^9 + 7).

The output of each test case will be printed on a separate line.
Note:
You do not need to print anything, it has already been taken care of. Just implement the given function.
Constraints:
1 <= T <= 5
1 <= N <= 10 ^ 5

Time Limit: 1 sec.
Approach 1

Let’s call vertex ‘A’ as 3, ‘B’ as 2, ‘C’ as 1 and ‘D’ as 0.

 

The idea is to break the main problem into smaller subproblems and recursively solve the smaller subproblems.

Let P(x, n),  represents the number of ways to move from vertex 0 to vertex x in ‘n’ steps.

Then our main problem is P(0, n).

P(0, n ) = P(1, n - 1) + P(2,n -1) + P( 3, n - 2).

Since vertex 1, 2 and 3 are equivalent to each other so we can write, P(0, n) = 3 * P(1, n -1)

And for x != 0 let's say 1.

P(1, n) = 2 * P(1, n - 1) + P(0, n - 1).
 

Hence we got the optimal substructure property.

Algorithm :

The steps are as follows:

 

Let 'numberOfWays' be the function that count all the possible ways

  • Take a variable  ‘mod’ value equal to 10 ^ 9 +7.
  • Make the helper function ‘count(vertex, steps)’ and call the helper function ‘count(vertex, steps)’ and store the answer in variable  ‘ans’.
  • Return ‘ans’ as final result.

 

Description of ‘count(vertex, steps)’ function

 

This function returns the number of ways to reach vertex ‘0’ from vertex ‘vertex’  in ‘steps’.

  • Check the base condition i.e steps is equal to 0.
    • If ‘vertex’ is equal to 0, return 1 way.
    • Else return 0.
  • Take a variable 'ans', initialize it to 0.
  • If it is 0th vertex:
    • Store the three times of answer of subproblem(1, steps - 1) in 'ans', and take modulo ‘mod’.
  • Else:
    • ‘ans’ is equal to 2 times of count(1, steps - 1)  + count(0, steps - 1).
  • Update the 'dp[vertex][steps]’ with ‘ans’ i.e dp[vertex][steps] = ans.
  • Return 'ans' .
Try Problem