← All solutions

Shortest judge solution: 771 bytes. Shortest team solution (during contest): 686 bytes.

Python solutions by the judges: only Pypy (but for no good reason, should be feasible with CPython as well)

This is a fairly straight-forward dynamic programming problem. Let C (i, j) be the minimum squared error cost of posterizing pixels with intensities r₁, . . . , r_i using j colors. The quantity we are looking for is then C (d, k).

We can formulate the following recurrence for C:

C (i, j) = min_{0 ≤ i < i⁰} C (i⁰, j − 1) + F (i⁰ + 1, i),

where we define F (a, b) to be the minimum cost of posterizing pixels with intensities r_a, . . . , r_b using a single color. Assuming for the moment that we have computed the function F, it is a standard exercise in dynamic programming to turn this recurrence into an algorithm for computing C (i, j) in time O(i² j).

Computing F (a, b) can be done in a few different ways. Note that

F (a, b) = min_{x ∈ Z} ∑_{i = a}^b p_i (x − r_i)².

This is just a quadratic function in x, so the best x can be found by basic calculus (or some form of ternary search for those so inclined).

There are just d² different possible inputs to F and the answer for all these can be precomputed to be used when computing C. The bounds were actually small enough that it was even possible to get away with recomputing F (a, b) every time it was needed, at least if the implementation had good constant factors.