The "minimum" part of this problem was particularly challenging for me. I could see that we need to create m
teams as "uniformly" as possible, but I was having a lot of trouble coming up with how to compute that. Hence this post explains the intuition behind distributing n
participants into m
teams as uniformly as possible.
Note: as a matter of notation, the quantity n / m
denotes integer truncating division throughout.
In hindsight, the reason this problem gave me so much trouble is because it demands an understanding of n % m
that I did not initially possess. My tried and true understanding of n % m
has always been
n = (n/m)*m + n%m.
In english, Equation 1 can be read as "starting with n
participants, we can form n / m
teams, each having m
participants, plus some leftover participants." However, 478B - Random Teams requires a fixed number of teams (i.e. m
), so this interpretation will not do. With this in mind and by a twist of perspective, we can rewrite Equation 1 as
n = m*(n/m) + n%m.
It may look like we've accomplished nothing with this rewrite, but we can now read this in a more useful way! Concretely, Equation 2 can be read as "starting with n
participants, we can form m
teams, each with n / m
participants, plus some leftover participants."
As a result, we now have m
teams which are uniform as can be (they all have an equal number of participants!). All that remains is to distribute the leftover participants as uniformly as possible into the m
teams. It is not hard to see that the way to accomplish this is to add each leftover participant to a different team. As a result of this process, we wind up with
n = (n%m)*(n/m + 1) + (m - n%m)*(n/m).
This can be read as "starting with n
participants, we can form m
teams. n % m
of those teams have n/m + 1
participants in them (because there are n % m
leftover participants). m - n%m
of them (i.e. the rest) have n / m
participants in them."
As an example, consider n = 8
and m = 3
. Beginning with Equation 2, applying the procedure which follows, and arriving at Equation 3, we have
8 = (2 + 2 + 2) + 2
= (2+1 + 2+1 + 2) + 0
= 2*(2+1) + 1*2
= (8%3)*(8/3 + 1) + (3 - 8%3)*(8/3).
If only we had reds explaining their approach to hard problems like this. :(