Null Void - Chef And Chess (Help)

Can anyone explain the approach for this problem .

https://www.codechef.com/NUVO2019/problems/CANDC

No of ways of dividing an even number n into pairs is \frac{n!}{2^{n/2}\left ( n/2 \right )!}
Firstly store the factorials of all numbers mod 10^9+7 till 10^7 in an array. Then two cases arise

  • n is even:
    Directly report the answer as product of n!, inverse modulo of 2^n/2 with 10^9+7 and inverse modulo of (n/2)! with 10^9+7.(Take modulo after every product to avoid overflow)
  • n is odd
    Do the above process with n-1 instead of n, and multiply the final answer by n and again take modulo with 10^9+7.
    To find inverse modulo you can use Fermat’s Principle.
1 Like

That above expression is also equal to the product of all odd integers less than n. So instead of storing factorials, we can store the product of all odd integers less than ‘i’, in the 'i’th element of an array. This way we don’t have to find the inverse modulo as well.

1 Like

Didn’t simplify the expression and computed directly. Thanks for sharing though.

@vinayaka05

bro its not clear

What should be answer for n=5 ,n=6, n=7 …???

The theory behind the answer: https://math.stackexchange.com/questions/1234696/number-of-ways-you-can-form-pairs-with-a-group-of-people-when-certain-people-can

Buddy even this helps:


this allows you to calculate n! / (n/2)! relatively easily. You can then divide the answer by 2^(n/2) or take the inverse of the same.

Also, was this rated? If so, then when will these ratings reflect?

This is the first time I used LATEX… I thought that the format will change in output… Can anyone help?

\dfrac{(2N)!}{{2}^{N} N! }

This is the string you need:
{ \dfrac{(2N)!}{{2}^{N} N! }

1 Like

Hey can anybody help here how to approach this problem https://www.codechef.com/NUVO2019/problems/PUBG

I don’t really know why but there was a pattern being formed for values of n:
1 1 3 3 15 15 105 105…
So, I simple precalculated all the values and the code was pretty straightforward.

mod = int(1e9)+7

arr = [1, 1]
mul = 3
lim = (10**7)//2+1
for i in range(1, lim):
	val = (arr[-1]%mod*mul%mod)%mod
	arr.append(val)
	arr.append(val)	
	mul = (mul+2)%mod


for _ in range(int(input().strip())):
	n = int(input().strip())
	print(arr[n-1])

PS: I know there probably exists a formula to calculate the nth value of the pattern but I was too lazy :stuck_out_tongue:

@prayushd bro can you please explain me how you got 15 for n=5 and n=6 and 105 for for 7 and 8 as question was little unclear to me that how its computing magic number

We Can do it using “Recursion”.

@vinayaka05
bro can you please explain me how you got 15 for n=5 and n=6 and 105 for for 7 and 8 as question was little unclear to me that how its computing magic number that’s why i was not able to get right pattern.

Magic number is the number of ways of making all the players play. It there are even number of players, then it is same as the number of possible ways of making pairs…which is given by the previously mentioned formula. If the number is odd, then we can choose one player to play with chef in ‘n’ ways and the remaining n-1 people need to be made again into pairs.
The correct formula for making into pairs (only for even n) is (n!)/(pow(2,n/2)*(n/2)!). On simplifying this, we get it as the product of consecutive odd numbers.I can’t see a way to directly prove it.
Hope this helps.

1 Like