You are given a number of small grayscale images, each exactly 32 × 32 pixels in size. The images have been encrypted. The encryption is diﬀerent for the easy and the hard subproblem. Both encryption types are described below.
There is a cat in the 21st image. There are also exactly ten other images with cats among the ﬁrst 20 images. Find those ten cats!
Problem speciﬁcation – easy subproblem
The pictures are encrypted in the following way: We picked a single random permutation on 32 elements. Then, for each picture we shuﬄed its columns using this permutation. That is, each column of pixels is still in its original order from top to bottom, but the order of columns is now diﬀerent. (Note that we used the same permutation for all pictures.)
Problem speciﬁcation – hard subproblem
The pictures are encrypted in the following way: We picked a single random permutation on 32 × 32 elements. Then, for each picture we shuﬄed its pixels using this permutation. That is, the set of pixels is now the same, they are just in diﬀerent locations. (Again, note that we used the same permutation for all pictures.)
For each subproblem you are given one set of encrypted images. Each set of images is provided in two diﬀerent formats:
The ﬁrst format is a ZIP archive that contains each encrypted image as a separate PGM ﬁle.
The second format is a single ﬁle that is formatted as follows: The ﬁrst line contains a single integer: the number of images. For each image, you are then given 1024 integers, each in range from 0 (black) to 255 (white). The ﬁrst 32 of these integers are the colors of the ﬁrst row (left to right), the next 32 is the second row, and so on.
Print ten whitespace-separated integers – the numbers of ﬁrst ten pictures with cats, in ascending order. Do not use leading zeroes, even though the ﬁlenames in the ZIP archive have them.