Can anyone help me with Celestial Voyage?

Hello friends can someone help with the math behind this problem ?? @vijju123 @kaushal101 @mohit_negi @taran_1407 @vivek_1998299

Thanks in advance :slight_smile:

Guys can someone help with the above question ?? What concept of maths is involved here ?? Guys just some hint will also be helpful :slight_smile:


This problem is a copy of Airplane Arrangements on HackerEarth.

1 Like

@meooow could u please explain the solution in a bit detail?

Thanks @meooow How did they arrived to that formula ??

According to the editorial on Hackerearth, the answer is given by

\frac{(2 \cdot (n + 1)) ^ m \cdot (n + 1 - m)}{n + 1}

First assume there is an (n + 1)^{th} seat between first and last so the seating is circular.
Now 2 \cdot (n + 1) is the number of ways each person can be assigned a seat and entry point. So (2 \cdot (n + 1)) ^ m is number of ways to assign seat and entry point to all m people. Here the entry point functions as only the direction in which a person checks for empty seats. Also note that the (n + 1) ^{th} seat cannot actually be assigned to anyone, but this situation will be eliminated from the final answer.
The seating is circular, so each person is guaranteed to find a seat. But if the (n + 1)^{th} is full, that means at some point a person could not find a seat in the original problem and became angry. Now we need to count the number of ways in which this seat remains empty.
For each way exactly n + 1 - m seats remain empty. By intuition I can claim that each of the \binom{n + 1}{n + 1 - m} choices of seats are equally likely to remain empty. What I want to find is the number of ways where a particular seat is always empty, which is \binom{n}{n - m}.
Now \binom{n}{n - m} = \frac{n + 1 - m}{n + 1}\binom{n + 1}{n + 1 - m}, so the answer is

\frac{n + 1 - m}{n + 1} \cdot (2 \cdot (n + 1)) ^ m

Got it know. Thankyou so much for this :slight_smile:

My solution is facing TLE error . Any suggestions ?

Got it now . Python’s pow is too slow . Self made power function in C++ does it in one go :slight_smile:

Actually it is not Python’s fault, you forgot to provide the modulo argument to the power function. You need to call it as pow(2*(n+1),m,mod). Also you cannot directly divide under a modulo, you need to multiply with the modular inverse instead. Or in this case, that can be avoided by cancelling one (n + 1) term from numerator and denominator.

Oh my bad ;0