Last Updated: 17 Apr, 2021
Ropes
Moderate
Asked in companies
You are given an integer 'N'. There are 'N' children standing in a circle. They are given 'N' / 2 ropes. They have to choose pairs in such a way that one child holds one end of the rope and the other child holds the other end. Your task is to determine the total number of different possible arrangements such that:
Note:
1. In each arrangement, there is exactly one child at either end of the rope. This means one rope will be held by exactly two children.
2. No rope should cross any other rope.
Input Format:
The first line contains an integer ‘T’, which denotes the number of test cases to be run. Then, the 'T' test cases follow.
The first line of each test case contains a single integer, 'N'.
Output Format:
For each test case, print a single integer, denoting the total number of required arrangements. Since, the answer may be very large, print the answer modulo 10 ^ 9 + 7.
Output for each test case will be printed in 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 <= 10
1 <= N < 2 * 10^3
N is always even.
Where ‘T’ denotes the number of test cases and 'N' represents the total number of children.
Time Limit: 1sec
Approaches
Approach: The approach is to break down the problem into some smaller subproblems. We can observe the fact that if a pair of children is chosen and handed a rope, then all the children to the left of this rope must be able to form pairs, and similarly on the right side.
If the number of children on the left side is ‘X’, then the number of children on the right side will be ‘N - X - 2’. So, our problem breaks down into finding the ways for ‘X’ and for ‘N-2-X’ and multiplying them.
Note that ‘X’ can have multiple values and we need to find all possible arrangements so we need to sum up the number of ways for each value of ‘X’.
Algorithm is as follows:
- If 'N' = 0, return 1. This is because if there are no children, then there is only one way to arrange this, and that is to give no one any rope.
- Now, define 'MOD' = 10^9 + 7.
- Define a variable, say totalArrangements, to store the total number of ways to form pairs.
- Now, run a loop from ‘LEFT’ = 0 to ‘LEFT’ < N, with an increment of 2, after every loop because we are considering only even numbers, and do:
- The number of children on the right side will be ‘N’ - ‘LEFT’ - 2. Store this value in a variable, say ‘RIGHT’.
- Now, add the product, findTotalArrangements(left) * findTotalArrangements(right) to our variable, ‘SUM’. This is because if there are ‘LEFT’ children on the left side, then they can be arranged in findTotalArrangements(left) ways. Similarly, if there are ‘RIGHT’ children, then they can be arranged in findTotalArrangements(right) ways. So, total possible arrangements will be the product of these values.
- Now, take the modulo of ‘TOTALARRAGEMENT’ to avoid any overflow.
- Finally, return this value of ‘TOTALARRAGEMENT’.
Approach: We can observe that we are solving the same subproblems multiple times. This can be avoided if we store the answer for each subproblem somewhere. So, whenever we are asked to find the answer to a subproblem, we can simply look it up, and the answer has been already solved and stored, we do not require to solve it again, and we can simply return this answer. If the answer has not been solved earlier, then we solve the answer and store it for future use.
Algorithm is as follows:
- Define a lookup vector, say ‘MEMO’ of size ‘N’, to store the results of all smaller subproblems. This way, we can avoid solving the same problem multiple times. ‘MEMO[i]' stores the number of arrangements of ‘i’ children
- Now, initialize all values of ‘MEMO’ to -1. Make the value of ‘MEMO[0]' to be 1 as we already know the answer for this value.
- Return the value of findWays(N, MEMO). This function is responsible for returning the total number of arrangements for ‘N’ children.
Int findWays(N, memo) {
- If the value present at ‘MEMO[N]’ is other than -1, that means that problem for ‘N’ has been solved earlier, and thus we can simply return this value. If the value is -1, then we need to solve this problem.
- Now, define ‘MOD’ = 10^9 + 7.
- Define a variable, say totalArrangements, to store the total number of ways to form pairs.
- Now, run a loop from ‘LEFT’ = 0 to ‘LEFT’ < ‘N’, with an increment of 2 after every loop, because we are considering only even numbers, and do:
- The number of children on the right side will be ‘N’ - ‘LEFT’ - 2. Store this value in a variable, say ‘RIGHT’.
- Now, add the product, findWays(LEFT,MEMO) % MOD * findWays(RIGHT,MEMO) % MOD to our variable, ‘TOTALARRANGEMENTS’ .
- Now, take the modulo of sum to avoid any overflow.
- Make ‘MEMO[N]’ = ‘TOTALARRANGEMENTS’.
- Finally, return this value of ‘TOTALARRANGEMENTS’.
Approach: The approach is to use Bottom-Up Dynamic Programming to further optimize our solution. We can use an array and get rid of recursion which will make our solution more efficient. The idea is to use an array and store the values for all subproblems in this array and use the smaller values to find larger values.
Algorithm is as follows:
- Initialize an array, say ‘DP’, of size ‘N’ + 1.
- Make ‘DP[0]’ = 1.
- Now, run a loop from ‘i’ = 2 to ‘i’ = ‘N’ with an increment of 2 after every loop, because we are considering only even numbers, and do:
- Define a variable, say ‘SUM’ = 0.
- Run another loop from ‘LEFT’ = 0 to ‘LEFT’ < ‘i’ , with an increment of 2 after every loop, and do:
- Store the value of ‘i’ - ‘LEFT’ - 2 in a variable, say ‘RIGHT’.
- Now, add the value of ‘DP[LEFT]' * ‘DP[RIGHT]’ to ‘SUM’.
- Make ‘DP[i]’ = ‘SUM’.
- Return the value present at ‘DP[N]’.
Similar problems