https://www.codechef.com/COCA2020/problems/COCA2003

https://www.codechef.com/COCA2020/problems/COCA2003

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 2
nC2 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