Contest name:- CodeChamp
Date:- 24/06/2020
Can someone please post the logic??
hey there @glegoo,
consider a string where every character occurs twice -
like “AADDBBNNFF”
Can you count the number of permutations of this string -
Of course, it is = (2*n)! / (2^n)
(where n - number of distinct characters it the string)
the similar intuition is used in arranging the parenthesis that occurs in pairs and each pair is of a different colour. You could resolve it as a string like the one above.
If want to have a look. Here is my solution.
Hope it helps.
Cheers.
You can simply precompute the whole sequence f_n = (2*n)! / (2^n) into a list and then just answer the queries by list look-up. My solution.
Hi. Can you, please, explain how did you deduce the formula?
Don’t follow this technique for solving problems. This is just a shortcut
What I did was just, go to oeis.org and search the sequence i.e. 1,6,90.
You will see results, and the given formula- (2n)!/2^n
Link
Now next just precompute and thats the answer.
The question is a combinatorics problem. Here we can think of it as placing 2n objects in 2n places(since there are N pairs of parenthesis) but here condition would be that each time we have to place a matching pair rather than single objects.
So we have to choose 2 places out of 2n places and put a pair of object(parenthesis).
this can be done in 2nC2 ways…this can be done for the n objects so (2*nC2)n ways but while computing this there will be repetition.so we have to divide it by n…thus it becomes 2nC2.
Now the question changes to as we are having 2n-2 places and n-1 objects so the formula for this will be (2n-2)C2.
similarly we have to calculate this i.e 2nC2 * (2n-2)C2 * (2*n-4)C2…upto 2C2.
for example for n=3 it will be 6C2 * 4C2 * 2C2=90
The formula[(2*n)! / (2^n)] can be easily derived just computing each of the single cases.
Here’s the proof:
1 Like
I’ve explained it you can see my deduction of formula.
Thanks for ur help