### saket9450's blog

By saket9450, history, 6 years ago,

Random Team Can any one please help me to find how minimum number of pair friends can be formed in this probem,i got the maximum part ,but not getting how to calculate minimum numbers of pairs of friends.

• +4

 » 6 years ago, # | ← Rev. 4 →   0 If there are x guys in a team, this team will produce friends, so that means the number of friends we will have in the end will bewhere xi is the number of guys in team i. If there's only one possible team (m = 1), we can't do nothing, so let's assume we have m > 1Let's see what happens when we change one guy of his team (for instance, from team x2 to team x1. All terms will be equal except those of team 1 and 2, and it's gonna be better trade if our sum diminishes:x2 > x1 + 1this means we should take a guy from group 2 and put him in group 1 only if the number of guys in group 2 had at least 2 guys more than group 1. Based on that, we should try to keep the size of the groups as close as possible to minimize that sum.
•  » » 6 years ago, # ^ |   0 thanx ivanilos for helping me, i got the point :D .
 » 6 years ago, # |   0 for minimum number you would like to have equal number of people in all groups.so first you give n/m members to each team.now you will be left with n%m members.still what is the best way to ensure equality? you distribute these n%m members 1 per team in each of the arbitrarily selected n%m team . now why did we split in such a manner to ensure equality? we found that the number of friends is proportional to square of the number of people in a team. an intuitive example if we were to find to split 100 onto two parts such that the sum of squares is minimum we would split it in 50-50. ps- i recently did this question therefore got encouraged to share my approach . no disrespect to ivanilos sir :)
•  » » 3 years ago, # ^ |   0 nice approach dude!
•  » » 8 months ago, # ^ |   0 ll a=n/m, b=n%m; ll min = (a*(a-1)/2)*m+ b*a; can't understand what is wrong in my code
•  » » » 2 months ago, # ^ |   0 suppose testcase n = 5 m = 3 then as per your approach distribution would be 1 1 1 2 , which is not optimal solution for minimum answer. Note , this happened because n%m was greater than n/m , thus considering those cases where n%m is greater than n/m : One must distribute (n%m) to m teams(upto which one-one distribution is possible) .Thus your answer 1 1 1 2 will become 1+1 , 1+1 , 1+0 or 1 1 2
 » 22 months ago, # |   +3 Thanks for the answers