Moderator Note: This is a current contest question on codechef.com.

N players sit around a round table. There are $n \cdot m$ cards with unique numbers of range $1\ldots n\cdot m$.

Each player has $m$ cards. In each set of the game each player selects some card and everyone shows his card at the same time. Card of $i^{\text{th}}$ player is compared to card of player $p[i]$. If it’s number is greater than the number on card of player $p[i]$, then $i^{\text{th}}$ gets a point. $P$ is a permutation of sequence $0\ldots n-1$.

But all players when playing want this game want to win. So, we decided to give cards in such way, that each player gets a point with probability larger than $\frac{1}{2}$.

We need to tell all m cards of each of the n players playing the game.

Example : Let $n=3$ and $m=3$ and array $P$ be [2 0 1]. Then here answer is :

Player 0: 2 6 7
Player 1: 3 4 8
Player 2: 1 5 9

Here in this case each player has probability $\frac{5}{9}$. So i need to find the distribution of these cards.

  • $\begingroup$ I don't understand what $P$ is for. Since $P$ is known before the players select their cards, why not just agree that the players are rearranged so that $P[i] = i+1$? $\endgroup$ – MJD Jul 5 '14 at 20:44
  • $\begingroup$ @MJD Itjust shows that ith player card is compared with card of P[i]th player $\endgroup$ – user157452 Jul 5 '14 at 20:45
  • 1
    $\begingroup$ @MJD: (a) it allow smaller cycle; (b) it's there to make the question more complicated. Since in a programming contest, anything that cause more difficulty is a chance for a program to fail, even if such difficulty is trivial mathematically. $\endgroup$ – Gina Jul 5 '14 at 20:54
  • $\begingroup$ @Gina Yeah right $\endgroup$ – user157452 Jul 6 '14 at 4:50
  • 1
    $\begingroup$ This is a problem from an ongoing contest codechef.com/JULY14/problems/LUCKG . Kindly put this question on hold until the contest is over. $\endgroup$ – Mod Jul 6 '14 at 14:07

Now that the contest has ended you can see successful submissions at https://www.codechef.com/JULY14/problems/LUCKG, on the sidebar to the right.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.