### PROBLEM LINK:

**Author:** Vitalij Kozhukhivskij

**Tester:** Shang Jingbo and Gerald Agapov

**Editorialist:** Devendra Agarwal

### DIFFICULTY:

Medium

### PREREQUISITES:

Adhoc , bfs

### PROBLEM:

N players are there, each player needs 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^{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^{th} player gets a point. P is a permutation of sequence 0…n-1.Your aim is to give them cards such that the winning probability of each player is greater than 0.5 , if it is not possible output “No Solution”.

### Explanation

We need to realize that each player is in some group. Each group is independent i.e. player of one group does not compete with any player of the other group. We will try to form maximum possible such groups.

How does each group looks like ?

Each group is a cycle.

How to find each group ?

The main condition of the group is that the player of this group does not compete with any other player of the other group, so we keep on finding each players competitor till we end up in a cycle [ i.e. a player from the same group ].

**Pseudo code for finding cycles/groups**

```
Init visit[] to 0
get_cycles is a array of vector to store cycle/group.
for(int i=0;i<n;i++)
if(visit[i]==0)
int j = i
while(!visit[j])
get_cycles[w].push_back(j)
visit[j] = 1
j = a[j]
w++
```

Now , the problem is reduced into subproblem with (N_{1} , M ) , (N_{2} , M ) , … , ( N_{w} , M ) , where Ni is the length of the i^{th} cycle , and w is the total number of cycles and N_{1} + N_{2} + … + N_{w} = N.

Let S[i] = ( N_{1} + N_{2} + … N_{i} ) * M

Now, one of the possible solution is to distribute cards from ( S[i-1]*M + 1, S[i] * M ) for ( N_{i},M ) group. I will solve the problem using this.

Now I will use cards from 1 to N_{i}*M , and will map the numbers as explained above for each group.

**For the rest part of the editorial , i will assume a cycle of length N because each cycle is independent and can be handled using the above fact.**

We need to first realize that there are no solution for M<=2 OR N<=2 where N is the cycle length and not the original N. Simple proof by programming is to code a brute force solution and find out that this is not possible. Mathematically , you can easily proof for each N<=2 OR M<=2.

**Case 1:** Now let us solve for the case when M = 3

If we distribute the number’s like this:

f_{1} : N , N+1 , 2*N + 2
f _{2} : N-1 , 2*N , 2

*N + 1*

fN-1, 3

f

_{3}: N-2 , 2*N*

fN-2, 3

f

_{4}: N-3 , 2*N-1*

… : …

fN+4

… : …

f

_{N-1}: 2 , N+3 , 2f

_{N}: 1 , N+2 , 2*N+3

f_{i} denote i^{th} player in the group.

Minimum Probability of winning of each player is 5/9(for N>=3) which is greater than 0.5

**Case 2:** Now let us solve for the case when M = 4

Now let us solve for the case when N>=4.

If we distribute the number’s like this:

f_{1} : N , N+1 , 2*N + 2 , 3*N+3

f_{2} : N-1 , 2*N , 2*N + 1 , 3*N+2
f _{3} : N-2 , 2*N-1, 3

*N , 3*N+1

f

_{4}: N-3 , 2

*N-2, 3*N-1 , 4

*N*

… : …

fN+4 , 3

… : …

f

_{N-1}: 2 , N+3 , 2*N+5*

fN + 3 , 3*N + 4

f

_{N}: 1 , N + 2 , 2f_{i} denote i^{th} player in the group.

Minimum Probability of winning of each player is 9/16(for N>=4) which is greater than 0.5

For the case of N=3 and M=4 , you can easily brute and find a valid solution . Total possibilities that you need to test is 12! which can be done by bruting.

**Case 3:** Now let us solve for the case when M = 5

If we distribute the number’s like this:

f_{1} : N , N+1 , 2*N + 2 , 3*N + 3 , 4*N + 4
f _{2} : N-1 , 2*N , 2

*N + 1 , 3*N+2 , 4

*N + 3*

fN-1, 3

f

_{3}: N-2 , 2*N , 3*N+1 , 4

*N + 2*

fN-2, 3

f

_{4}: N-3 , 2*N-1 , 4*N , 4

*N + 1*

… : …

fN+4 , 3

… : …

f

_{N-1}: 2 , N+3 , 2*N+5 , 4*N + 6

f

_{N}: 1 , N + 2 , 2

*N + 3 , 3*N + 4 , 4*N + 5

f_{i} denote i^{th} player in the group.

Minimum Probability of winning of each player is 14/25 (for N>=5) which is greater than 0.5

You can calculate the probability of winning for N=3 and N=4 and it will also come out be greater than 0.5

**NOTE**: The pattern of all the sequence are the same . The pseudo code given below generates it.

**Pseudo Code**

```
Generate_Sequence(N,M) //M = 3 OR 4 OR 5 and ( N!=3 if M=4 )
for ( i = 1 ; i<= N ;i = i + 1 )
first_number = N - i + 1
//This loop generates all numbers for f[i] player.
for ( int j = 1;j<=M ; j++)
print first_number
if ( first_number % N == 0 )
first_number = first_number + 1
else
first_number = first_number + N + 1
```

Now that we can solve for any given N ( which is the cycle length ) and M = 3, 4 and 5. Let me explain the solution for any general M.

Let M = 3*x + 4 OR M = 3*x + 5 OR M = 3*x

i.e. each number can be represented in terms of 3,4 and 5.

Find solution for each N and M=3 x times and the remaining portion(which is either 4 or 5) [ Do not forget to increase the value].

**Proof**

We now need to prove that this strategy will indeed lead to a winning probability of greater than 0.5 for each player.

Let i^{th} player be competing with p[i]^{th} player. We have find for each unit of 3/4/5 cards among a group , probability of winning of each player is more than 0.5

We need to proof that there is a probability of 0.5 that i^{th} player wins when he chooses a card from a Unit to compete another card of p[i]^{th} player from other Unit.

Wlog Let us consider 2 units UnitA and UnitB , where numbers used in UnitA is strictly less than the numbers used in UnitB.

So the probability that i^{th} player chooses a card from UnitA and p[i]^{th} player chooses a card from UnitB is the same as the probability that i^{th} player chooses a card from UnitB and p[i]^{th} player chooses a card from UnitA.

So the probability of winning of i^{th} player in inter unit matches is the same whereas in the same unit is more than 0.5 , thus giving an overall probability of more than 0.5

**NOTE** : Unit here means a group of 3/4/5 cards distributed to each player in the fashion described above. As players are allowed to choose cards randomly , a player can choose a card from any unit.

For Example :

Let us suppose M = 8 and N=3 and we have the initial given array as : 1 2 0

So, we have just 1 cycle of N = 3

M = 3 + 5

UnitA :: N=3 and M=3

f_{1} : 3 , 4 , 8

f_{2} : 2 , 6 , 7

f_{3} : 1 , 5 , 9

UnitB :: N=3 and M=5

f_{1} : 3 , 4 , 8 , 12 , 13

f_{2} : 2 , 6 , 7 , 11 , 15

f_{3} : 1 , 5 , 9 , 10 , 14

Increase each card number by 9 to get numbers different from UnitA.

Now let us find the probability of winning of Player 1 (which is competing with player 2):

Player 1 chooses a card from UnitA and Player 2 also chooses a card from UnitA ==> Winning Probability > 0.5

Player 1 chooses a card from UnitB and Player 2 also chooses a card from UnitB ==> Winning Probability > 0.5

Player 1 chooses a card from UnitA and Player 2 also chooses a card from UnitB ==> Winning Probability = 0 , lost 3 * 5 * 8 times

Player 1 chooses a card from UnitB and Player 2 also chooses a card from UnitA ==> Winning Probability = 1 , won 5 * 3 * 8 times

Final probability of winning is more than 0.5 for player 1 , similarly you can calculate for each player.

Final Answer will be :

f_{1} : 3 , 4 , 8 , 12 , 13 , 17 , 21 , 22

f_{2} : 2 , 6 , 7 , 11 , 15 , 16 , 20 , 24

f_{3} : 1 , 5 , 9 , 10 , 14 , 18 , 19 , 23

**Complexity**:

O( N * M )

### AUTHOR’S AND TESTER’S SOLUTIONS:

Author’s solution

Tester’s solution to be uploaded soon.