I couldn’t solve it by my algorithm which was calculating the number of possible ways for each player. But it needed calculation for each player which would have made it exceed TL.
In short, how would you explain your solution? I just need a few hints if possible 
I precomputed the factorials up to 2^19 modulo-ed by 1000000009, and used exponentiation by squaring with modular multiplicative inverse.
I’m also wondering, did it need modular multiplactive inverse again?
Could someone please tell me if my algorithm was correct, I did something like the following:
for i = 1 to n/2 - 1:
print 0for i = n/2 to n:
print (2 * n_choose_k(i-1, (n/2)-1) * factorial(n/2)^2) % (10^9 + 9)
Yes it is correct. You can simplify the expression (i-1) C (n/2 - 1) to get two terms ((n/2-1)! and (i - n/2)!) in denominator, and hence two modinvs.
@thespacedude, you said a few hints, I’ll give you one: for each player to go to the finals it has to be on a set (supposing we have two sets) in which he is the strongest one, for example, for the arrangement {1, 2, 3, 4} we have the sets {1, 2} and {3, 4}. 2 and 4 are the strongest on their own set. If you work around this it’s pretty straight forward to calculate the solution for each number but if you still need help refer to @bugkiller’s answer or I can explain the full solution (I don’t see the editorials yet).
Thanks for this
consider d=3 ==> n=8
consider the sequence 1 2 3 4 5 6 7 8
the answers for the players are
1:0
2:0
3:0
4: 24x24x2 (1=3C3)
5: 24x24x2x4 (4=4C3)
6: 24x24x2x10 (10=5C3)
7: 24x24x2x20 (20=6C3)
8: 24x24x2x35 (35=7C3)
which is nothing but (n/2)!x(n/2)!x2x((player_strength-1)C(n/2-1))(simple choosing which players can come in current player’s half and then permuting them)
you can precompute (n/2)!x(n/2)!x2
and further
4C3 can be written as 4x3x2/(3!)
5C3 can be written as 5x4x3/(3!)
6C3 can be written as 6x5x4/(3!)
7C3 can be written as 7x6x5/(3!)
you can observe that at ever step one multiplication and one division is there
eg. 5C3 = (4C3/2)*5, 6C3 = (5C3/3)*4
division can be done by modular multiplicative inverse
you find it here
http://discuss.codechef.com/questions/3433/modular-multiplicative-inverse
http://en.wikipedia.org/wiki/Modular_multiplicative_inverse
thus it can be solved in O(nlogn)
You’re welcome
Let’s divide the array into two halves, H1 and H2 . |H1| ,|H2| are always even as N is a power of 2 ( 4,8… Base case should be treated separately N=2. ) . For simplicity sake, Let’s assume player with strength N is on H1 , Then the player who reaches the final is the player in the other half of the array and with the greatest strength in that other half. Clearly, no one with strength till (N-1)/2 can reach the final .
Ans is sum of 2 * (n/2)! * (n/2)! * (i C n/2-1 ) …… That is , choosing a half side for player with strength N * permuting the two halves with n/2 elements each * selecting n/2-1 smaller elements in the other half as player with strength i+1 is the player with maximum strength in the other half.
ur solution is correct, but u need not hardcode output as 0 for i < n/2. ur formula (the one involving nCr) will produce the right answer for all i. all u need to do is handle nCr = 0 if r>n
my AC solution: 3539280
Exactly what I did on paper!! Just couldn’t code the “nCr” part. Thanks for clearing this out!
You’re welcome !!!
can you please explain, how you arrived at (n/2)!x(n/2)!x 2 ? I’m not able to figure it out.
@prav19
If we devide the group of players into 2 halves of n/2 size each then there will one player from each half in the final.
For any player, place him in any half and then decide which players can be in his half so that he wins which is
((player_strength-1)C(n/2-1))(selecting the players which have lower strength than the current one)
once you have selected the players in each half you can arrange them in their halves which will be (n/2)! for each half.
as they are independent it will become (n/2)!x(n/2)! plus you can also interchange these to halves which is 2!
hence (n/2)!x(n/2)!x2!
The idea was simple, which was The palyer with max strength wins its subtree.