Nickolas's blog

Codeforces Beta Round #96: editorial
By Nickolas, 13 years ago, translation, In English

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 ( + 27 + 26 - 24 + 23 - 20), while it's possible to find a notation of size 4 ( + 28 - 26 - 24 - 21).

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 2M + 1 - 2N - ..., 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.

  • Vote: I like it
  • +58
  • Vote: I do not like it

Comments Comments (16)
| Write comment?
13 years ago, # |
← Rev. 2   Vote: I like it -8 Vote: I do not like it

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 binary
                while(a.length()<8)   //making its size 8
                a='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 answer
                a=Integer.toBinaryString(res);  //preparing the prev for the 1st step
                while(a.length()<8)
                a='0'+a;
                rev="";
                for(j=7;j>=0;j--)
                rev=rev+a.charAt(j);
                prev=Integer.parseInt(rev,2);
            }
→ Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Problem E stand up some difficulties for me in finding a solution. Can someone please reply me what's the main idea of the problem ? Thanks in advance.
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    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.

    → Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it
    it's a dynamic programming.The idea is foreach character, try to change it (if possible) or not.My state is (position, changeLeft, direction, value)

     I missed "abs" of the value during the contest. Lost about 1200 point :(
    → Reply
13 years ago, # |
  Vote: I like it 0 Vote: I do not like it
Could anyone explain the following case for Problem Piet.
Input:
3 7
901
922
934
Output:
3
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    [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

    → Reply
13 years ago, # |
  Vote: I like it -6 Vote: I do not like it
can anyone explain the following test case of Piet for me?
3 9
888
456
226
Ans: 4
→ Reply
  • 13 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it
    Log from my accepted solution on this input:
    After step 1: color=8, DP=right, CP=right
    After step 2: color=8, DP=down, CP=left
    After step 3: color=6, DP=down, CP=left
    After step 4: color=6, DP=down, CP=right
    After step 5: color=6, DP=left, CP=left
    After step 6: color=2, DP=left, CP=left
    After step 7: color=2, DP=left, CP=right
    After step 8: color=2, DP=up, CP=left
    After step 9: color=4, DP=up, CP=left
    → Reply
    • 13 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it
      thanks,
      that was very clear
      i really appreciate that
      thanks again....:)
      → Reply
13 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it
Sorry, my mistake.
→ Reply
13 years ago, # |
  Vote: I like it +9 Vote: I do not like it
Where is the editorial of Div1 prob.D and E?
→ Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

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

    use the greedy to solve the problem D..



    → Reply
13 years ago, # |
← Rev. 2   Vote: I like it +3 Vote: I do not like it

how to solve the problem E。div1

→ Reply
  • 13 years ago, # ^ |
    ← Rev. 2   Vote: I like it +22 Vote: I do not like it

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

    • for each number ai in the sequence (n total) create two nodes ui and vi; and
    • for each variable bi you have (m total), create a node wi.
    We will create a weighted bipartite graph with nodes ui and wi on one side, and nodes vj on the other. We connect ui to vj for all j > i. This represents the case "aj is the next number to use the same variable as ai." Thus it has cost f(aj) if ai ≠ aj and cost zero if ai = aj, where f(aj) is the number of bits set in aj. Also, connect wi to vj for all j with cost f(aj). This represents the case "aj is the first number to be stored in variable bi."

    The result is obtained by a minimum-cost matching in this graph. To recover the sequence, for each vj we see what node ui or wi it is matched with. If vj is matched with a ui, we put aj in the same variable as ai (recall that i < j in this case), doing nothing if they are equal. If vj is matched with wi, we put aj in variable bi.

    Hope this helps!
    → Reply