Last Updated: 6 Dec, 2020
Tetrahedron
Moderate
Asked in company
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:
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.
Approaches
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' .
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. If we observe carefully the subproblems are repetitive. So we can use memozition to avoid recomputation of repetition subproblems.
Algorithm :
The steps are as follows:
Let 'numberOfWays' be the function that count all the possible ways
- Take a global 2D array of size 2 * n and ‘mod’ value equal to 10 ^ 9 +7.
- Run a loop and initialize the dp of size 2 * n with -1.
- Make the helper function ‘count(vertex, steps)’ and call the helper function ‘count(vertex, steps)’ and store answer in variable ‘ans’
- Return ‘ans’.
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 ways
- Else return 0.
- If we have already computed the subproblem(vertex, steps) then return the answer i.e if dp[vertex][steps] != -1 .
- Return ‘dp[vertex][steps]’.
- 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' as the final answer.
If you observe carefully, you will see that the current state of ‘dp’ is only dependent upon the previous state of ‘dp’.
We will maintain two variable ‘waysZero’, denoting the the number of ways to reach vertex ‘0’ from ‘0’ in ‘n’ steps and second variable ‘waysNonZero’, denoting the the number of ways to reach vertex other than 0’ from ‘0 in ‘n’ steps.
Initialization:
waysZero = 1
waysNonZero = 0
Transition:
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)
waysZero = 3 * waysNonZero
waysNonZero = 2 * waysNonZero + waysZero
We can use a temporary variable to perform above transition.
Algorithm :
Let 'numberOfWays' be the function that counts all the possible ways to reach from vertex 0 to 0 in exactly 'n' steps.
- Take a variable 'waysZero' and initialize it to 1.
- Take the variable 'waysNonZero' and initialize it to 0.
- Run a loop from 1 to 'n':
- Store 'waysZero' in the temporary variable 'temp'.
- Update 'waysZero' with (3 * waysNonZero) % mod.
- Update 'waysNonZero' with ((2 * waysNonZero) % mod + temp) % mod.
- Return 'waysZeros' as the final answer.
Similar problems