Codeforces Educational Round 18

March 29, 2017, 7:28 am

I haven't participated in many Codeforces rounds lately, but I did do Educational Round 18. Codeforces hosts "Educational Rounds" periodically, which are unrated and usually focus on teaching common techniques and tricks.

Problem C was a simple greedy algorithm with lots of edge cases, and problem D was essentially implementation. Problem E was interesting, but unfortunately I couldn't solve it during the contest. Nonetheless, here are my thoughts on it.

E: Colored Balls

In this problem, we have \(N \leq 500\) colors of balls (with \(x_i \leq 10^9\) balls of color \(i\)), and we want to partition the balls into monochromatic sets such that no two sets differ in size by more than \(1\). Our goal is to minimize the number of sets.

First, it is clear that this is the same as maximizing the number \(k\) such that every set is of size \(k\) or \(k + 1\): after finding this number, we can find the minimum number of sets for a particular color \(i\) by taking \(\lfloor \frac{x_i}{k + 1} \rfloor\) and then adding \(1\) if the remainder is nonzero. (To see why, consider a variant of the division algorithm: \(x_i = q(k + 1) - r\), with \(0 \leq r \leq k\). The above procedure gives us \(q\) in this formulation, and that corresponds to taking \(q - r\) sets of size \(k + 1\) and \(r\) sets of size \(k\).)

Each \(x_i\) has some number of potential valid values of \(k\), and we want to find the maximum \(k\) that is valid for all \(x_i\). Our approach will be as follows: generate the whole set of valid \(k\) values for \(x_1\), and then cull this set for each of \(x_2, x_3, \dots\).

There are a few parts to this solution. First, let's try to characterize the valid values of \(k\) for a particular \(x_i\). We want to know for which values of \(k\) there exist nonnegative integers \(a, b\) such that \(x_i = a(k) + b(k + 1)\). Since \(k\) and \(k + 1\) are always coprime, there are infinitely many (potentially negative) integers \(a\) and \(b\) satisfying this equation. If we can find one solution, then we can characterize all the solutions. The obvious solution is to take \(a = -x_i\) and \(b = x_i\), so all the solutions are of the form \(a = -x_i + (k + 1)z\) and \(b = x_i - kz\), for \(z \in \mathbb{Z}\). If there are any solutions with both \(a \geq 0\) and \(b \geq 0\), then one such solution will be with \(z = \lfloor \frac{x_i}{k} \rfloor\). \(b\) will always be nonnegative with this value of \(z\), so we only need to check if \(a \geq 0\) also: \(a = -x_i + (k + 1)\lfloor \frac{x_i}{k} \rfloor \geq 0\), which is the case when \(\lfloor \frac{x_i}{k} \rfloor \geq x_i \bmod k\) (where \(\bmod\) is taken to mean remainder, as in most programming languages).

This gives an easy way to check if a given value of \(k\) will work for a particular \(x_i\), and so we can use this in the culling step in our algorithm. However, this doesn't help us generate all the valid values for \(x_1\). It's not even clear that there aren't too many values to store in a set!

It turns out that there are never more than \(3\sqrt{x_i}\) values of \(k\) for any \(x_i\). To prove this, we will just describe the procedure to enumerate them; this will also complete our algorithm.

First, note that for \(k \leq \sqrt{x_i}\), the condition (\(\lfloor \frac{x_i}{k} \rfloor \geq x_i \bmod k\)) always holds. This gives us \(\sqrt{x_i}\) values. For the others, we iterate over all possible values of the left-hand side of the inequality (there are only \(\sqrt{x_i}\) to consider), and for each, we identify at most \(2\) values of \(k\) that are valid.

We will denote our guess for the left-hand side of the inequality by \(y\). We will show that only \(\lfloor \frac{x_i}{y} \rfloor\) and \(\lfloor \frac{x_i}{y} \rfloor - 1\) may be valid values of \(k\). It will be easy to check each of these using our condition and add them to our set if they are indeed valid.

So we want to show that only \(k = \lfloor \frac{x_i}{y} \rfloor\) and \(k = \lfloor \frac{x_i}{y} \rfloor - 1\) may satisfy both \(\lfloor \frac{x_i}{k} \rfloor = y\) and \(x_i \bmod k \leq y\). We will show at least one condition must fail whenever \(k > \lfloor \frac{x_i}{y} \rfloor\) or \(k < \lfloor \frac{x_i}{y} \rfloor - 1\).

First, we handle the \(k > \lfloor \frac{x_i}{y} \rfloor\) case. In this case, the first condition (\(\lfloor \frac{x_i}{k} \rfloor = y\)) cannot hold; in fact, \(\lfloor \frac{x_i}{k} \rfloor < y\). It is enough to note that \(k > \frac{x_i}{y}\) whenever \(k > \lfloor \frac{x_i}{y} \rfloor\), since \(k\) is an integer. Then

\[\left\lfloor \frac{x_i}{k} \right\rfloor \leq \frac{x_i}{k} < \frac{x_i}{x_i/y} = y.\]

The \(k < \lfloor \frac{x_i}{y} \rfloor - 1 \) case is more subtle. Without loss of generality, assume the first condition holds (if not, then we are done). We will prove that \(x_i \bmod k > y\). To do so, we again invoke the division algorithm. For convenience, let \(m = \lfloor \frac{x_i}{y} \rfloor - k\).

\begin{align} x_i &= qk + r & (0 \leq r < k) \\ &= yk + r \\ &= y\left(\left\lfloor \frac{x_i}{y} \right\rfloor - m\right) + r \end{align}

But since \(y \lfloor \frac{x_i}{y} \rfloor \leq x_i\), rearranging gives \(r \geq my > y\), as desired.

This completes the proof that there are never more than \(3\sqrt{x_i}\) (in practice, there are usually close to \(2\sqrt{x_i}\)) valid values of \(k\), and so we can start by testing all of these for \(x_1\), adding valid ones to a set, and then iterating over the other \(x_i\) and removing invalid ones. At the end, we can choose the largest element of our set (the set can never be empty because \(k = 1\) is always valid) and calculate the corresponding minimum number of sets as described above.