Arcimboldo’s Style

You can now see the best outputs gallery and analysis for this problem.

Giuseppe Arcimboldo (5 April 1527 – 11 July 1593) was an Italian painter, best known for portraits composed of fruits, vegetables, flowers, fish, and books. His works “Flora” and “Vertumnus” are classic examples of assembling a face from many small objects.

A young and promising digital creator began preparing for her next art exhibit. She was inspired by the works of Arcimboldo and decided to recreate existing paintings by composing them from many clipart images. Since she does not want to create the clipart images by hand, she decided to use the premier AI image generation engine, Repaint.ai. Finally, since she does not want to replicate the exact paintings and wants to maintain the roughness of the result, the number of cliparts in each image is limited.

Since the exhibit is coming up soon, she decided to assign this problem to the coding agents (you). Please enjoy the results while submitting them!

Formal statement

Each test consists of:

• One target image.
• One clipart collection of small images (the “cliparts”). The same collection may be used by multiple tests. All cliparts are generated using the Repaint.ai website.
• An integer limit $N$ — you may use at most $N$ cliparts in your composition.

You must place selected cliparts on a transparent canvas so that the canvas becomes as close as possible to the target image.

The canvas has the same size as the target image. Each clipart is placed without rotation and scaling. You may place each clipart any number of times (provided there are no more than $N$ cliparts on the canvas), and cliparts may overlap. The final image is the pixel-wise result of drawing the chosen cliparts onto the canvas in the specified order: each next clipart is drawn above all the previous ones.

All images are PNG files with binary transparency: every pixel is either fully transparent or fully opaque. Target images are fully opaque. Transparent pixels do not overwrite the canvas. Any pixel of the final canvas that remains uncovered by all placed cliparts is treated as a very bad color: (-255, -255, -255) for RGB when scoring, so leaving holes is strongly penalized.

Input data

Download tests

Download checker

You are given an archive with the following contents:

• A set of input files: test01.in, test02.in, ..., test12.in.
• A set of target images (e.g., Mona_Lisa.png).
• Several directories containing clipart collections.

Each test case DD is described by the text file testDD.in. The file contains exactly four lines:

• Line 1: one integer N, the maximum number of cliparts you may use.
• Line 2: the filename of the target image for this test.
• Line 3: the name of the clipart collection to be used for this test.
• Line 4: a short text comment (provided for information only, can be ignored for solving).

The clipart collections are provided in separate directories. The name in the input file corresponds to the directory name of the collection. Inside a collection, cliparts are named 0001.png, 0002.png, ..., DDDD.png.

Output format

Submit an archive with answers for the corresponding inputs: 01.out, 02.out, ..., 12.out. Some of the files may be missing.

The first line of the output should contain one integer $M$ ($0 \le M \le N$) — the number of cliparts to place on the canvas. Next $M$ lines should describe the placed cliparts, one per line, each with three integers pic r c, where pic is the clipart number (matching filenames without leading zeroes, for example, 1 for 0001.png) and must refer to an existing clipart file in the collection, and r, c ($-10000 \le r, c \le 10000$) are the row and column of the top-left pixel of that clipart on the canvas. The rows and columns are 0-indexed. Rows increase from top to bottom, columns increase from left to right.

Any pixels of a clipart that fall outside the canvas are ignored during scoring.

Scoring

Let the target image be T, and the final canvas be P. For each pixel (r, c), with RGB color components in [0, 255], define the per-pixel error as the sum of squared differences. If a pixel is not covered by any placed clipart or is not opaque, its color is defined as (-255, -255, -255).

The total error is the sum of errors, $\text{err}(r, c)$, over all pixels.

Your score for the test is calculated as follows:

• If the output is not properly formatted, it gets $0$.
• Otherwise, your output will get a score that depends on the lowest total error of all participants: $200 \times \left(\frac{\texttt{best\_total\_error}}{\texttt{your\_total\_error}}\right)^2$.

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