About Cinderella

National Round Task 3: About Cinderella

English translation by SOTA – AI Community of the Slovak original, Uloha3_Popoluska.pdf ("CK Úloha 3: O Popoluške"; CK = celoštátne kolo, national round), from the Olympiáda v umelej inteligencii (Slovak Olympiad in Artificial Intelligence), 2025/26. The original task belongs to its authors. Organisers who would like this translation removed can email [email protected].

[Figure: see the original statement.]

When the royal ball was being prepared, the stepmother said:
"Cinderella, I have spilt a tensor of letters into the tensor of handwritten digits. If you sort it out within two minutes, you may come with us."

The girl went out through the back door into the garden and called:
"Little pigeons, turtle doves and all you little birds under the sky, fly to me and help me sort:
the digits you leave in the tensor, the letters go into your little beaks."

Then two doves flew to the window, the turtle doves after them, and finally all the little birds of the sky came flocking down. They sat down around the stepmother's tensor and began to pick out the letters with their little beaks. Because they already had an autoencoder of digits at their disposal, everything was sorted before the two minutes had passed. It was lucky that the stepmother had not mixed into the tensor letters such as O, which would have been indistinguishable from digits such as 0.

Start from the notebook anomaly.ipynb

In it you will find code to download the stepmother's tensor and the model of a convolutional variational autoencoder of digits. Solve the following tasks:

1. Compute the maximum reconstruction error of the given autoencoder applied to the symbols in the stepmother's tensor. For a symbol (in which the pixels have values from 0 to 1), the error is computed as the mean of the squares of the differences between the values of corresponding pixels in the input and in the output of the autoencoder. Print it to at least four decimal places. (10 points)

2. Find (by any means) the list of indices of the letters in the stepmother's tensor, sorted from the smallest to the largest. For each correct index you receive a proportional share of 60 points. However, for each index at which there is not a letter but a digit, you receive -1 point; even in the worst case, though, only to the extent that you have 0 points in total for this whole subtask.

3. Print the number of letters in the tensor. (max. 10 points, depending on the deviation from the true count; some points can be obtained even for an estimate)

4. Print the string of letters in the order in which they follow one another in the stepmother's tensor. (max. 20 points, depending on the length of the longest common subsequence with the correct answer).

   Hint: when Cinderella took a closer look at the letters, she found that this subtask is easier than it seems at first sight.

You submit the notebook with its outputs; mark the answers to questions 1-4 clearly. When scoring the subtasks, the graders may also award points beyond those earned by the result, for example if the result is incorrect but the idea is correct.