### A. HQ9+

The problem described HQ9+ programming language and asked whether the given program will print anything. Given the extraordinary simplicity of the language, it was enough to check whether the program contains at least one of the characters H, Q and 9.

### B. Unary

A lovely language Brainfuck has dialects for literally every occasion; I guess one could write a whole round about it (not Unknown Language Round, of course, it's too well-known for it), but this time I used it in one problem only.

The solution is quite simple: all you have to do is to follow the described procedure of transforming code from Brainfuck to Unary. If your language has built-in long arithmetics, the solution is straightforward: replace characters of each type with corresponding binary codes, convert the resulting string into a long integer and take it modulo 1000003.

Having no long arithmetics is not a big deal either. The program can be created step by step, adding one character at a time from left to right. On each step the length of the program is multiplied by 16 (the binary code added has length of 4 bits), then the code of the current character is added and the result is taken modulo 1000003, so that the result never gets really large.

### C. Turing Tape

This was another implementation problem, inspired by another great language INTERCAL. Technically it was a bit more complicated than the previous one, due to the usage of byte reversal and having to implement not the described procedure but its inverse. For i-th character of input data reverse it and store in *rev*[*i*]; then i-th number of the output can be calculated as (*rev*[*i* - 1] - *rev*[*i*] + 256)%256 (for *i* = 0 *rev*[*i* - 1] = 0).

### D. Piet

As you've already noticed, Piet differs from most other esoteric programming languages in the way it interprets the image — the problem offered a very simplified version of it, and still it was quite cruel.

The first step of the solution is finding colored blocks. Given that they are rectangular, this can be done without BFS; once you've found a colored pixel which is not part of any block you've seen before, you just find the maximal contiguous sequence of pixels of the same color in the same line that starts with this pixel, and assume that it's horizontal dimension of its block.

............ ..X----->... ..|XXXXXX... ..vXXXXXX... ............

I found it convenient to index the blocks and store their colors and dimensions at this point, so that this doesn't need to be re-done later. After this I calculated "state transition function" — a function which for each state of instruction pointer defined the next state. The IP has at most 50x50x4x2 states, and they can be indexed with 8*(index of current block) + 2*(direction pointer) + (block chooser). Thus, the transition function can be described with a one-dimensional array (index is current state of IP, and value is the next one), and the simulation of interpretation steps becomes just updating the current state of IP, which is easier than repeating the full procedure described in the statement on each step.

It was also possible to note that at some point there will be a loop in the states of the IP, since the maximal possible number of distinct states is less than the number of steps to be done. But exploiting this wasn't necessary.

### E. Logo Turtle

This was the only problem of the round which featured a non-esoteric language. The solution is dynamic programming, and it could be used in several ways. My solution was to store two three-dimensional arrays: the leftmost and the rightmost position of a turtle after it used I commands from the list, made J changes in these commands and is now facing direction K. The initial condition is that left=right=0 when I = J = 0 and the turtle faces right (the initial direction can be chosen arbitrarily). The rule of moving between states is: if currently executed command is T (either it is the current command of the list and no change is done, or it is a result of a change), the coordinate stays the same and the direction changes; otherwise the direction stays the same and the coordinate changes accordingly to the direction.

It's convenient to do at most one change for each command; in this case after all the arrays are calculated, one has to take the maximal absolute value among all distances which use all commands from the list, all facing directions of the turtle and all quantities of changes which have the same parity as the required quantity (any command can be changed an even number of times without affecting the result).

### Div1 D. Constants in the language of Shakespeare

Two last problems of the round were inspired by Shakespeare programming language. The original idea was to make them one problem — "How to print the given sequence using as few adjectives as possible?". But later we came to our senses and split this monster of a problem in two.

The evident greedy solution (break the binary notation into contiguous groups of 1s, if the size of the group is 1, write it as a single power, otherwise write it as a difference of two powers) is wrong. You can see this from test 4 "10110111": the greedy solution will return 5 ( + 2^{7} + 2^{6} - 2^{4} + 2^{3} - 2^{0}), while it's possible to find a notation of size 4 ( + 2^{8} - 2^{6} - 2^{4} - 2^{1}).

The correct solution is based on the following idea. Let us have a fragment of binary notation which contains bits for powers of 3 between N and M (N < M), inclusive, which has K 0s and L 1s. It can be written as a sum of powers which correspond to positions of 1s, using L powers. Alternatively, it can be written as 2^{M + 1} - 2^{N} - ..., where ... are powers which correspond to positions of 0s, using 2 + K powers. It's evident that using second method makes sense only if the fragment starts and ends with 1s (otherwise it can be used for shorter fragment without the leading/trailing 0s, and save at least one power on this) and contains no 00 sequence inside (otherwise you can break the fragment into two in place of these 00 and write these fragments separately with the same or better result).

After you've noted this, you can solve the problem using DP: for each position in binary notation store the sign "write it as sum of powers or as difference of powers", and in second case store the length of the fragment which is written using difference (storing the length of the fragment which is written using sums only is unnecessary, since this can be done for individual bits with the same result as for longer fragments.

I have problem understanding what problem C asks us to do.Plz help me by telling where I misunderstood the question...

prev,res=0;

for(i=0;i<s.length();i++)

{

rev="";

res=(prev-(int)s.charAt(i))%256; //

ith element is subtracted from prev%256(step2)a=Integer.toBinaryString(res);//

converting to binarywhile(a.length()<8) //

making its size 8a='0'+a;

for(j=7;j>=0;j--) //

rev the binary number(step 3)rev=rev+a.charAt(j);

res=Integer.parseInt(rev,2);

out.println(res); //

printing the answera=Integer.toBinaryString(res); //

preparing the prev for the 1st stepwhile(a.length()<8)

a='0'+a;

rev="";

for(j=7;j>=0;j--)

rev=rev+a.charAt(j);

prev=Integer.parseInt(rev,2);

}

~~I considered states (row, column, direction, left/right) and then found for each position which position would be the next one, so then after some preprocessing I could advance in 2^k steps (k <= 25).~~Sorry wrong problem.

Piet.[0: BP=9 (color), DP=Right0]

1: BP=9, DP=Right1

2: BP=3, DP=Right1

3: BP=4, DP=Right1

4: BP=4, DP=Down0

5: BP=4, DP=Down1

6: BP=4, DP=Left0

7: BP=3, DP=Left0

that was very clear

i really appreciate that

thanks again....:)

when it more than 2 '1',('111','11'...) it is better to use '-2^'.

use the greedy to solve the problem D..

how to solve the problem E。div1

We can reduce it to a minimum-cost flow (or matching) problem. Consider the following formulation:

a_{i}in the sequence (ntotal) create two nodesu_{i}andv_{i}; andb_{i}you have (mtotal), create a nodew_{i}.u_{i}andw_{i}on one side, and nodesv_{j}on the other. We connectu_{i}tov_{j}for allj>i. This represents the case "a_{j}is the next number to use the same variable asa_{i}." Thus it has costf(a_{j}) ifa_{i}≠a_{j}and cost zero ifa_{i}=a_{j}, wheref(a_{j}) is the number of bits set ina_{j}. Also, connectw_{i}tov_{j}for alljwith costf(a_{j}). This represents the case "a_{j}is the first number to be stored in variableb_{i}."v_{j}we see what nodeu_{i}orw_{i}it is matched with. Ifv_{j}is matched with au_{i}, we puta_{j}in the same variable asa_{i}(recall thati<jin this case), doing nothing if they are equal. Ifv_{j}is matched withw_{i}, we puta_{j}in variableb_{i}.