Software Engineer

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.