LUCKG - Editorial

devuy11 · July 14, 2014, 3:02pm

PROBLEM LINK:

Practice
Contest

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₁ , M ) , (N₂ , M ) , … , ( N_w , M ) , where Ni is the length of the i^th cycle , and w is the total number of cycles and N₁ + N₂ + … + N_w = N.

Let S[i] = ( N₁ + N₂ + … 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₁ : N , N+1 , 2N + 2
f₂ : N-1 , 2N , 2N + 1
f₃ : N-2 , 2N-1, 3N
f₄ : N-3 , 2N-2, 3N-1
… : …
f_N-1 : 2 , N+3 , 2N+4
f_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₁ : N , N+1 , 2N + 2 , 3N+3
f₂ : N-1 , 2N , 2N + 1 , 3N+2
f₃ : N-2 , 2N-1, 3N , 3N+1
f₄ : N-3 , 2N-2, 3N-1 , 4N
… : …
f_N-1 : 2 , N+3 , 2N+4 , 3N+5
f_N : 1 , N + 2 , 2N + 3 , 3*N + 4

f_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₁ : N , N+1 , 2N + 2 , 3N + 3 , 4N + 4
f₂ : N-1 , 2N , 2N + 1 , 3N+2 , 4N + 3
f₃ : N-2 , 2N-1, 3N , 3N+1 , 4N + 2
f₄ : N-3 , 2N-2, 3N-1 , 4N , 4N + 1
… : …
f_N-1 : 2 , N+3 , 2N+4 , 3N+5 , 4N + 6
f_N : 1 , N + 2 , 2N + 3 , 3N + 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 = 3x + 4 OR M = 3x + 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₁ : 3 , 4 , 8
f₂ : 2 , 6 , 7
f₃ : 1 , 5 , 9

UnitB :: N=3 and M=5

f₁ : 3 , 4 , 8 , 12 , 13
f₂ : 2 , 6 , 7 , 11 , 15
f₃ : 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₁ : 3 , 4 , 8 , 12 , 13 , 17 , 21 , 22
f₂ : 2 , 6 , 7 , 11 , 15 , 16 , 20 , 24
f₃ : 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.

praneethiitr · July 14, 2014, 3:36pm

I think n=3,m=4 is the only special case that will not follow the pattern. That alone made me think twice before coding the solution

mohit2104 · July 14, 2014, 3:38pm

Yep exactly .

sousnake · July 14, 2014, 3:41pm

the answer for above case is to be found differently while other cases can be handled with the same pattern. This took me long time to solve this case while i solved the others easily by brute force.

fauzdar65 · July 14, 2014, 4:01pm

When cycle length is 3 and m=4, this was the only case my code failed on.
Got AC in practice now, just by adding a brute solution for this case.
Even i thought there was no solution to this case, how could i ever think of brute solution.But i guess this was what made this somewhat difficult.

gkcs · July 14, 2014, 4:05pm

Please submit your solution on 3 4 using brute force

fauzdar65 · July 14, 2014, 4:08pm

Input:
1
3 4
1 2 0

Output:
1 7 8 9
4 5 6 12
2 3 10 11

http://www.codechef.com/viewsolution/4329384

fauzdar65 · July 14, 2014, 4:14pm

9>4,5,6
8>4,5,6
7>4,5,6

So 9/16.

gkcs · July 14, 2014, 4:16pm

Oh god. I see my error now. Thanks.

mjbpl · July 14, 2014, 6:09pm

I did the same mistake. Missed this case to only to see WA after WA.

ashwin1907 · July 14, 2014, 6:52pm

A very bad problem. A problem whose solution depends solely on pattern inference should be avoided in a contest. One does not learn anything from such problems. I wasted 2 days thinking about it only to find that it was all about a pattern. Pissed off

xellos0 · July 14, 2014, 7:07pm

I found it okay, especially considering such problems (bruteforce small cases and use some general obervation on sufficiently large ones) aren’t really rare in ACM contests.

That you didn’t notice there could be pattern doesn’t mean it’s impossible to do.

devuy11 · July 14, 2014, 7:09pm

Actually, It was not a pattern recognising problem . I will tell you how i solved the problem . I aimed at making minimum loss to each player . If you took this as the aim , you can get the pattern very easily [ which has reasonable enough ].

rahul_nexus · July 14, 2014, 7:45pm

Can somebody explain the proof of the pattern. .I did not get the editorial

sid12 · July 14, 2014, 8:09pm

http://www.codechef.com/viewsolution/4314907

can someone pls tell me the fault in the code. Thanks in advance!

midhul · July 14, 2014, 10:51pm

Why does this post have the “bfs” tag?

yash_15 · July 14, 2014, 10:55pm

I had found a similar pattern. Luckily I ran a tester function to check for all m and n >2. Luckily I found the 3,4 test case. The problem is aptly named Lucky Game, because otherwise you cant solve this problem.

ayushj10 · July 15, 2014, 12:03am

I found this question to be very interesting. Thanks to the problem setter, and a very nice editorial indeed. I just had one doubt, actually I thought of a complete different way to approach this problem. I can be completely wrong so any help will be appreciated

So considering the 2nd test case, all the players have a probability of winning=5/9. I worked upon it:
The probability of selecting a card is 1/3. So, 1/3(2/9+6/9+7/9)=5/9, or (1/3) * (1/9) * (2+6+7)=5/9 and similarly for other players as well. Thus I concluded:

(1/m) * (1/n) * x > 1/2, or x > (m * n)/2
So I basically need to find n different subsets consisting of m elements whose sum (i.e. x) should be > (m * n)/2 and they should have no common elements between them. If such subsets exist, print them else print No Solution.

Is there anything wrong with this approach? Or is this another possible way to work around the problem?

Thanks!

ayushj10 · July 15, 2014, 6:53pm

Anyone? Still awaiting a reply. Thanks

xellos0 · July 15, 2014, 8:51pm

Random tags are random.