The contest is over; I hope you've enjoyed it. 1465 participants submitted at least one problem correctly. Unfortunately, nobody managed to solve all 6 problems; congratulations to ShadowSong who won the contest by solving 5 first problems with the lowest penalty time!

290A - Mysterious strings

Last year we've verified that a lack of problem statement doesn't prevent participants from solving and submitting the problem successfully and at the same time saves the problem setter some writing effort. This year we've ascertained this again. Well, I could've invented a long and knotty legend about you, a young but very promising software developer, were summoned to White House and given a task of utmost importance: to deliver an interactive list of USA presidents from founding fathers to our days. It could have featured a dramatic time-consuming search for necessary info, pursuits, firefights, a wounded teammate whose dying words were "Eight is Van Buren, don't forget... print Van, just Buren... doesn't pass". But what for? Three samples and a favorite search engine (I won't name it for the sake of political correctness) are all you need to figure out the dependency between input and output: index number N — surname of N-th USA president, as well as to find all necessary data.

290B - QR code

A statement consisting of a single image looks a bit funnier. One can invent countless functions which convert a pair of integers into a third integers and fit the set of samples from the statement, starting with "0 if numbers have the same parity and 1 otherwise". To avoid trying them all (since that would take much longer than the contest duration) one has to look for a clue in the image. Any online QR-code decoder will give you a link hidden in the code, which will point you to a text file consisting of 0 and 1. If you take a closer look at the file, you'll recognize the same QR-code in it, written block-by-block — 1 for black blocks and 0 for white ones. A hint which points to itself... Maybe that is the statement? Input ranges from 0 to 32, and what are the dimensions of the image, 33 x 33?

Indeed, the problem asked to return the color of the image block in the given row (first number) and column (second number). The text file is given mostly to save people who have already figured out the task the trouble of generating this array.

290C - WTF?

Finally, a real problem statement in plain text! Reading... WTF?

To decode this statement, one has either to recall who the problemsetter is and how much I love weird programming languages, or to extract a couple of keywords from the statement and look for them online. HAI and KTHXBYE are enough of a pointer to Lolcode esoteric language; all you have to do is to figure out what this program does, and to replicate this in any regular language. Once again, there are two ways to do this: find a list of language commands and read through the code, or find an online interpreter and try to run the program on various inputs.

If this problem was to have a proper legend, it would be as follows. You are given a sequence of duels a game character had; there were no ties, so every duel ended in a victory or defeat. Character's rating is defined as a ratio "victories number" / "total duels number". Find the highest rating the character ever had.

290D - Orange

Here goes another picture instead of a statement, this time in lovely shades of orange. A person with some experience of contests written by me might reasonably guess that this is another programming language, but even less known than usual: Baltie. Baltie interpreter exists for Windows only, and doesn't really allow copying this program into it, so it might be easier to make a guess about the meaning of individual command icons. Boxes are variables, arrow certainly looks like assignment, loop and if-then-else are inscribed, but the rest of them will require an effort...

One might also choose another way (which, I suspect, most people did) and figure out the task from the single sample. The contents of the string evidently doesn't change, only the case of certain letters... A bit of magic — and we realize that one has to convert first N letters of English alphabet to uppercase and the rest of them — to lowercase.

290E - HQ

This problem made you think twice: before understanding the statement and after that. A quick glance at HQ9+ reveals that H and Q are commands which print "Hello, World!" and the source code of the program being executed, respectively. One can reasonably guess that HQ language consists of the same two commands which do more-or-less the same thing. To advance further, one has to put in quite some thought: theories like "given program source, return Yes if the output has even length" turn out to be very wrong. Actually things are the other way around: you are given program output instead of its source (H command prints just H, no extra letters), and you have to figure out whether there exists a program which can generate this output. Alas, only a few people managed to guess this and appreciate the beauty of the problem. Once again congratulations to ShadowSong who was first to submit the problem only after one hour of the contest!

How to solve this? First of all, make several useful observations. If the original program has nH characters H and nQ characters Q, each H will print one H, and each Q will print nH Hs and nQ Qs. So the number of Qs in the output must be an exact square of nQ (possibly 0), and you can either immediately conclude that the output is impossible to generate or get to know nQ. Similarly the number of Hs in output equals nH * (nQ + 1), and either the output is impossible or you get to know nH.

With smaller constraint this would be enough to solve the problem by trying all possible permutations of known quantities of H and Q and comparing the output of each permutation with the given one. But having output up to 10^6 rules this approach out, and one has to keep thinking. Find the first Q in the output; evidently, it appeared there as a result of executing the first Q command. Half of preceding Hs will appear as a result of executing this very Q, the other half — as a result of executing individual H commands. So again, we can either mark the output as impossible (if the number of Hs before first Q is odd) or get to know the number of H before first Q in the original program. Exactly the same logic allows to figure out the number of H after last Q in the program.

And finally one last step. First nQ Qs appear in the output as a result of executing the same Q command. So if we take first and nQ-th Q characters of the output, the piece of output between them and prefix and suffix of Hs of known lengths, we'll get the original program! You just have to verify that this program really generates necessary output (the difference can creep in after first nQ Qs).

290F - Greedy Petya

This problem was contributed by Gerald and reveals a different aspect of problemsetters' sense of humor. We spent most of the second hour of the contest feeling more and more disappointed about underestimating the complexity of the task, but Deamon saved us by submitting the only solution barely three minutes before the contest end.

The task was to guess and reproduce the exact wrong solution written by Petya for finding Hamiltonian path (the third sample showed quite clearly that his solution is in fact wrong). Petya turned out to use a well-known greedy approach:

1. Store the graph as adjacency lists.
2. Remove all multiple edges and self-edges.
3. Sort vertices in lists in increasing order of vertex degrees (vertices with equal degrees get sorted by index).
4. Try all possible candidates for the starting vertex of the path and try to move from current vertex to a yet unvisited vertex in order of corresponding adjacency list.

If the algorithm doesn't find a loop, output "No".