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.

# | User | Rating |
---|---|---|

1 | tourist | 3778 |

2 | Benq | 3592 |

3 | ecnerwala | 3521 |

4 | Um_nik | 3423 |

5 | jiangly | 3375 |

6 | Petr | 3342 |

7 | Radewoosh | 3337 |

8 | scott_wu | 3313 |

9 | maroonrk | 3265 |

10 | yosupo | 3259 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 202 |

2 | 1-gon | 200 |

3 | rng_58 | 194 |

4 | SecondThread | 193 |

5 | awoo | 187 |

6 | vovuh | 183 |

7 | Um_nik | 182 |

8 | antontrygubO_o | 177 |

9 | Ashishgup | 175 |

10 | -is-this-fft- | 171 |

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.

↑

↓

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Jan/19/2021 08:02:58 (h3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

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 > 1Let's see what happens when we change one guy of his team (for instance, from team

x_{2}to teamx_{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}+ 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.

thanx ivanilos for helping me, i got the point :D .

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

nice approach dude!

can't understand what is wrong in my code

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

Thanks for the answers