Image Archiver

Ivan has just been appointed as the CEO of Rezipit (a sub-company of a very successful startup). The company aims to develop an image archiver with the best compression efficiency and highest quality in the world. From his university studies, Ivan recalls that the smaller the number of distinct values in the file, the better it can be compressed. And the genius idea strikes his mind!

At the first stage of product development, he wants to design an algorithm that takes an image in an 8-bit RGB color model and produces an image of the same size with at most $k$ same-colored 4-side connected components so that the MSE (mean squared error) difference between the original and the output image will be as small as possible.

Since this is just a raw idea, Ivan asks you to develop the prototype.

Input Data

You are given $20$ tests: 01-k.png, 02-k.png, $\ldots$ , 20-k.png, where k in each filename is replaced with value of $k$ .

Download inputs (problem-i-inputs.zip)

Each PNG image is provided in an 8-bit RGB color model. In this model, each pixel color is represented by three integers $r, g, b \in [0, 255]$ .

Here is a short description of these tests:

Test	$k$	Image Size
`01-128.png`	$128$	$1 \times 4096$
`02-3.png`	$3$	$16 \times 2048$
`03-2.png`	$2$	$1024 \times 1024$
`04-5.png`	$5$	$999 \times 999$
`05-10.png`	$10$	$2000 \times 2000$
`06-32.png`	$32$	$256 \times 256$
`07-512.png`	$512$	$1024 \times 1024$
`08-512.png`	$512$	$512 \times 512$
`09-12.png`	$12$	$1024 \times 1024$
`10-8.png`	$8$	$1024 \times 1024$
`11-3.png`	$3$	$1080 \times 1295$
`12-16.png`	$16$	$1024 \times 1024$
`13-7.png`	$7$	$1024 \times 1024$
`14-64.png`	$64$	$512 \times 512$
`15-64.png`	$64$	$717 \times 512$
`16-32.png`	$32$	$1280 \times 1024$
`17-16.png`	$16$	$1024 \times 1024$
`18-128.png`	$128$	$1024 \times 1024$
`19-256.png`	$256$	$1024 \times 1820$
`20-1024.png`	$1024$	$1536 \times 2040$

Output Data

Submit images 01.png, 02.png, …, 20.png with answers to the corresponding inputs. Some of the files may be missing.

We say that two pixels are connected if their cells share an edge and they have the same colors (tuples $(r, g, b)$ ).

An output image should:

be in an 8-bit RGB color model (without opacity),
have the same size as the input one,
should contain at most $k$ connected components.

Scoring

Suppose a given image has dimensions $w \times h$ .

For two images $U$ and $V$ of size $w \times h$ , let us define their similarity score:

$\text{RMSE}(U, V) = \sqrt{\frac{1}{3 wh} \sum\limits_{x=1}^{w} \sum\limits_{y=1}^{h} \sum\limits_{\texttt{ch} \in {\texttt{R}, \texttt{G}, \texttt{B}}} (U_{\texttt{ch}}[x, y] - V_{\texttt{ch}}[x, y])^2}$

Let us consider one test and suppose that:

$\texttt{input}$ is the input image.
$\texttt{answer}$ is your answer image and $\texttt{your\_points} = \texttt{RMSE}(\texttt{input}, \texttt{answer})$ .
$\texttt{baseline}$ is the baseline image for this test. The baseline image has all pixels of the same color selected optimally (the image has exactly one connected component). We set $\texttt{base\_points}$ as $\texttt{RMSE}(\texttt{input}, \texttt{baseline})$ .

Your final score for the test is calculated as follows:

If the image provided is not properly formatted or the number of same-colored 4-side connected components is bigger than $k$ , your output gets $0$ .
If $\texttt{your\_points} \geq \texttt{base\_points}$ , your output gets $0$ .
Otherwise, your output will get a score that depends on the lowest number of points all participants: $180 \times \min\left( \frac{\texttt{best\_points}}{\texttt{your\_points}}, \frac{\texttt{base\_points} - \texttt{your\_points}}{\texttt{base\_points} - \texttt{best\_points}} \right)^{1.5}$ .

Note that the scoreboard will show your best score for each test among all your submissions.

Image Archiver

Input Data

Output Data

Scoring

Problem by Recraft