Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

saket9450's blog

By saket9450, history, 5 years ago, In English,

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.

 
 
 
 
  • Vote: I like it
  • +4
  • Vote: I do not like it

»
5 years ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

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 be

where x i 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 > 1

Let's see what happens when we change one guy of his team (for instance, from team x 2 to team x 1. All terms will be equal except those of team 1 and 2, and it's gonna be better trade if our sum diminishes:

x 2 > x 1 + 1

this 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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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 :)

  • »
    »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    nice approach dude!

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    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

»
15 months ago, # |
  Vote: I like it +3 Vote: I do not like it

Thanks for the answers