Virtual_Contestant's blog

By Virtual_Contestant, history, 4 years ago, In English

Hello everyone can you please tell my why we divide elements as n/m and n/m + 1 in order to minimize the pair of friends. Please help i have my exam tomorrow https://codeforces.com/contest/478/submission/77214745

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

Hello there. I cannot understand what you don't really understand so I will just explain the solution of this problem. If we want to minimize the number of total friends, we will uniformly distribute players along the teams. So, answer will be equal to n/m. Now after we distributed the players, we want to calculate number of friends in each team. Because the whole team is friends with each other, we need to find the number of pairs. For example, if the team has 5 members, the first is friend with the other four. The second is friend with the other three(notice that, we will not count his friend with the first as we already counted their friendship before). With that, we want an equation to calculate for us 4+3+2+1 efficiently. We can easily use $$$(n*(n-1)/2)$$$ which calculates $$$\sum_{x=1}^{n} x$$$ in O(1). Notice that there is something missing. What if we could not fully distribute the players that all the teams have the same amount of players? We should check how many players will remain. So first, we will calculate the number of teams that have n/m players separately, and calculate that will have n/m+1 using the summation formula rule. We can know the remaining players by using n%m Now, after we got the minimum number of pairs of friends, let me explain the maximum. The maximum is a lot easier. A team must consist of at least a player. So we are going to make a new variable called result and that variable will be equal to: n-m+1. We will subtract the number of teams from n and then add 1 as we will use only 1 team to make the maximum number of pairs of friends. We will use that result and the actual maximum answer will be equal to: $$$result*(result-1)/2$$$. I hope this explanation helped! If you have any questions, ask me.