BINTOUR - Editorial

PROBLEM LINK:

Practice
Contest

Author: Constantine Sokol
Tester: Mahbubul Hasan
Editorialist: Jingbo Shang

DIFFICULTY:

Easy

PREREQUISITES:

Combination

PROBLEM:

For each of 2^K players labeled by 1 … 2^K, how many permutations of their initial positions can allow him to advance to the final? The tournament is as following figure. The winner of a match is the one with larger label.

EXPLANATION:

For a given player X, if he advanced to the final, his label should be the greatest among the players in his semi-final part.

Assume he is the winner of semi-final one. His position has 2^(K-1) choices. And, there are X-1 players with smaller label. Therefore, the answer is 2^(K-1) * (X-1) * (X-2) * … (X - 2^(K-1) + 1) * (2^(K-1))!.

With X varying from 1 to 2^K, it is easy to maintain the product (multiply a number and divide a number), because the MOD number is a prime, according to the Euler Theorem.

If we calculate the inverse by the fast power, similar to the fast multiply I mentioned in a previous editorial, we can get a O(2^K * K) algorithm.

AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution can be found here.
Tester’s solution can be found here.

4 Likes

@shangjingbo authors solution link gives’access denied’ error…

1 Like

please wait for the updating. Some solutions are not available now. Sorry for the inconvenience

ans = (fact[i - 1] * bigmod(fact[n/2 - 1], MOD - 2)) MOD; ans = (ans * bigmod(fact[i - n/2], MOD - 2)) MOD;

Can anyone explain what these two statements in tester’s code are doing? Are they calculating C(n,r)?

Something similar to C(n, r). The bigmod(a, b) is to calculate a^b MOD. When calling bigmod(a, MOD - 2), it is same as a^(-1) MOD.

1 Like

how bigmod(a,MOD-2) and a^(-1)%MOD are same?

it is modulo multiplicative inverse property that
a^(-1)%mod=a^(mod-2)%mod when a and mod are coprime…bigmod is just calculating a^(mod-2) in log(mod) time…

1 Like

“…happens a battle between a knight on the 2.jth position and a knight on the 2.j+1th position”.
The above line copied from the problem statement is misleading. Should have been: “…happens a battle between a knight on the 2.jth position and a knight on the 2.j-1th position”. Faulty statements like this should be guarded against in future problem statements.

2 Likes

@admin i am not able to understand the use of the bigmod function. Why are we actually calculating (a^b)%mod?

great question loved solving it… The Permutations n Combinations part was easy but the inverse modulo part and calculations were quite a bit. And there was a problem in the problem statement itself. as @bodmas pointed.
my solution can be viewed: http://www.codechef.com/MARCH14/status/BINTOUR,abcdexter24

can anyone pls explain how does the answer 2^(K-1) * (X-1) * (X-2) * … (X - 2^(K-1) + 1) * (2^(K-1))!.
came more detailwise…thank u