a_journey's blog

By a_journey, history, 9 months ago, In English,

Here is the problem.

And here is one of the AC solution : http://codeforces.com/contest/999/submission/39534469 which is based on how to distribute M cards among N persons optimally such that joy is maximum. But how will we take care of this case : Suppose there are 3 players whose favourite card is say x and it occurs 5 times.

suppose p1 get 2 card , p2 = 2 , p3 = 1 and they want to have 4 cards in total.

Now how to select the remaining cards for them, since suppose if i give number y to player 1 it can be the favourite for some other player which will decrease his joy and may affect total joy.

 
 
 
 
  • Vote: I like it
  • 0
  • Vote: I do not like it

»
9 months ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Actually you can always select some cards which are not favourite of anyone and give it to any player that needs it.

You can consider it like let's say we have total of X cards and out of them Y are fav. for some person. Distribute Y cards to each person in any way(may not be optimal) some person may get k cards some less than k. for these people you still have X-Y cards which are not the fav. of anyone and you can distribute it in anyway.So basically the problems boils down to 0/1 knapsack type for each independent fav. number.

Now try to give each player cards from 0 to min(remcards,k) and do a simple recursive dp.