Nickolas's blog

By Nickolas, 6 years ago, translation, In English

952A - Quirky Quantifiers

JAPE riddle generator is a program which can produce question-answer puns. This problem has been inspired by one of the witticisms produced by it:

What do you call a quirky quantifier? An odd number.

All you had to do was to check whether the given "quantifier" was "quirky".

952B - A Map of the Cat

This problem was inspired by the awesome book "Surely You're Joking, Mr. Feynman!" In one of his stories Feynman asks a librarian to fetch him a map of a cat, having a zoological chart in mind. Of course, such a serious interpretation was unsuitable for my purposes :-)

This was a perfectly straightforward problem: just pet the cat! If the reaction you get is "no", try a different spot, otherwise you can figure out what kind of a cat this is right away. Just make sure you're not carried away: both kinds of cats get bored after 7th attempt to pet them and send you away without letting you guess their kind.

One thing I didn't take into account was that interactive problems are very rare on Codeforces, so this problem turned out to be much harder than the next one.

952C - Ravioli Sort

Let's call the row of stacks "stable" if each adjacent pair of stacks in it differs in height by at most one (so no ravioli are going to slide to a different stack). It is easy to show that if a row is stable, then after removal of the tallest stack the resulting row is also stable. Indeed, after removing stack ai the only new pair of adjacent stacks is ai - 1 and ai + 1. The row was stable, so |ai - ai - 1| ≤ 1 and |ai - ai + 1| ≤ 1. But ai was the tallest stack, so ai - 1 ≤ ai - 1, ai + 1 ≤ ai. Thus the difference in height between ai - 1 and ai + 1 is at most 1, and the resulting row is also stable.

This means that the output will be correct if and only if the original array was stable (obviously, if the original array was not stable, at least one of the stacks would change even before the first tallest stack is chosen, and once some stacks change it's impossible to fix all of them).

952D - I'm Feeling Lucky!

Do you know how an actual roulette works? Each time you play, the winning number is different (even if you bet on the same number). It was exactly the same in this problem: each time the solution runs, it needs to guess a different winning number. There were two tests, so you have to make a winning bet twice.

This problem required a little exploration and out-of-the-box thinking. It is really hard to win betting on a number or even on two numbers (although I've seen a submission which got 26 on both tests). But you don't need to win big, you need just to win — so why not try bets with higher probability of winning, like "red" or "even"? The checker supported a variety of bets as was shown on the picture, so you just had to explore a little.

952E - Cheese Board

This problem was inspired by the first line of Wikipedia article Chessboard: "Not to be confused with cheese board". Indeed, cheese board, chess board, what's the difference really? :-)

The image in the statement showed a bunch of cheeses (from the first example) arranged in a chessboard pattern, with soft cheeses representing one "color" of the squares and hard cheeses representing the other. The task was to find out the smallest size of a square "chessboard" on which the given cheeses could be arranged in such a way that soft and hard cheeses would alternate, and cheeses of the same type would never occupy adjacent squares.

Once you've figured out the task, the solution is very straightforward. First, count the numbers of soft and hard cheeses. Iterate through the sizes of the chessboard, starting with 1, and for each size count the number of black and white cells on it. If the number of black cells is greater than or equal to the number of hard cheeses and the number of white cells is greater than or equal to the number of soft cheeses or vice versa, return this size of the board.

952F - 2 + 2 != 4

This problem is based on a real bug in the checker for problem 784G - BF Calculator. Fortunately, we caught it before the contest, which is why I can laugh about it today :-)

The checker successfully iterated through the characters of the expression and accumulated them into a "current number" variable to add it to the result or to subtract it from the result. But due to a missing check in current number accumulation plus and minus characters were also counted as digits of the number. In "2+2" example, the first number was correctly interpreted as 2, but for the second one the first digit was ('+'-'0') = -5, and so the second number was interpreted as (-5)*10 + 2 = -48. Minus sign would be interpreted as an extra leading ('-'-'0') = -3 "digit".

The solution follows:

long long result = 0, cur = 0;
expr += "+";
int sign = +1;
for (char c : expr) {
    if (c == '+' || c == '-') {
        result += sign * cur;
        cur = 0;
    }
    if (c == '-')
        sign = -1;
    if (c == '+')
        sign = +1;
    // bug: + and - signs are accumulated into the number
    cur = cur * 10 + (c - '0');
}

952G - Puzzling Language

"Puzzling language" featured in this problem is Orthogonal Puzzlang (a less studied variant of Puzzlang).

There are multiple ways to approach code generation in this language.

The method shown in the example was not the easiest possible, and was chosen quite deliberately :-) But it is possible to develop it further — use triangular blocks of Xs to increment value in a cell and then carefully navigate to the right cell and print its contents. This requires a lot of care when dealing with multiple symbols, increments which are not square numbers (a triangular block of Xs corresponds to an increment by a square number, and yes, \$ sign in the example with ASCII code 36 was not a random choice) and so on.

My reference solution used a much easier approach. The simplest command to generate in Puzzlang is decrement — it is just a standalone 'X'. And due to the fact that memory cells in Brainfuck wrap around, you can get any value in a memory cell starting with any other value and decrementing it the right number of times. The generated program can have only 2 columns, with '-' (decrement) instruction implemented as ".." — newline — "X." and '.' (print) instruction implemented as "X.".

This approach can be optimized further without adding too much complexity: my actual reference solution still generated 2-column programs but encoded both decrement and print instructions as either ".X" or "X." depending on the previous instruction, so that decrement 'X's formed a chessboard pattern, and print 'X's were right below the 'X's of previous instructions. This reduced the size of the program by a factor of 2.

Another solution I implemented didn't use wrap around of memory cells, but instead relied on torus topology of the program. I used a program with 2 columns again, with the same implementation of decrement and print instructions as in the previous approach. A sequence of 2*N increment instructions could be represented as a block of N+1 "XX" lines. The first line of the block would be interpreted as ",,", but the interpreter is permissive enough to just ignore these instructions. Every line of the block after that is interpreted as "++". This approach typically generates shorter programs but requires a bit more care when implementing it — I got it quite right only on the fourth try :-)

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

| Write comment?
»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Why my solution with "don't touch me" without '!' gets OK and with'!' gets WA? Bugs in tests or joke?

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Same happened to me, my solution with "are you serious ? " got WA ;(

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    phew. Submittd so many solutions; all in vain until i found this comment and removed all the exclamation signs from my solution. It should have been mentioned in the question. :(

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it -12 Vote: I do not like it

    dere is no wae

»
6 years ago, # |
  Vote: I like it -24 Vote: I do not like it

Is it rated?

»
6 years ago, # |
  Vote: I like it +52 Vote: I do not like it

Anyone else thought problem B was that normal cats get grumpy when you touch them too much?

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

"This year I tried to make the problems less puzzling and more versatile."

Yes,I think it's more interesting than before because of these versatile problems.

»
6 years ago, # |
  Vote: I like it +16 Vote: I do not like it

Isn't "don't even" mean we can't send even number to the cat?

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Another way to solve G(the way I did it): For every character, make an empty line(250*'.').Then make a line which is ("..."+'X'*asciiCode+('.' until the end)). This line does nothing(interpreted as '>'+','*asciiCode+'<')

Then make a line which is ("X.X"+'X'*asciiCode+"X."+('X' until the end)). This line, combined with the previous one is interpreted as "<>"+'+'*asciiCode+"<>" and then some ','(which are useless).

That way, in memory cell 2 we have the ascii code for the character. Then we print it the same way as in the example. After that we clean up cell 2 with "X."*asciiCode. Output for sample 36847564

»
6 years ago, # |
  Vote: I like it +7 Vote: I do not like it

I printed words "black", "red", "are you feeling lucky?" and nearly all numbers from 1 to 36. But got WA :(

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

"and once some stacks change it's impossible to fix all of them"

I think that's not trivial. One way to prove it is to see that the entropy (sum a_i log(a_i)) strictly decreases when ravioli collapse, but that was actually the "hardest" (well the non-easy) part in my humble opinion.

But I'm interested if you have a simpler proof.

  • »
    »
    6 years ago, # ^ |
    Rev. 4   Vote: I like it +5 Vote: I do not like it

    It's actually trivial. Let x be the tallest stack of ravioli that will ever lose ravioli. Then number of x-stacks will strictly decrease since non of rovioli will collapse from any of the taller stacks.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Ooooohhh.

      I feel so stupid.

      Thank you very much :)

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Why did you choose ? I mean it works with any convex function, it's called Karamata's inequality.

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Yes yes of course, but I found it first by thinking of entropy as it was linked to a loss of information.

»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

You can see that in problem B, the "Grumpy cat" picture shows "NO"(Uppercase) on its tail and two legs. That would be different from the "no"(lowercase) on the picture of "Normal cat".

I didn't participate in the contest because of the time. But i like it very much.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    " For simplicity all responses are written in lowercase." Read tasks more careful, pls

    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      O sorry. Will I get many downvotes? But I don't want to!

      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        I don't think so, but next time just read twice and try to submit your idea before commenting

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    ZXB[user:netszxb]&SJC[user:sjc061031] AKed IOI!They're both dalao!

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I had never seen a roulette before, because it's very rare in China. Luckily I found that I can even guess something other than an integer after googling for half an hour. But those who neither know the rules nor searched it for such a long time would have a hard time with this problem.

  • »
    »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Yes, but as example tasks for using OEIS last years meant that you've to search this sequences

»
6 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Well, If you type "I'm feeling Lucky!" and press I'm feeling lucky button in Google there is a site that comes up with a roulette and the ball is on 13. I was so hyped to submit but I didn't work out xD It was still fun but would be better that way IMO.

»
3 years ago, # |
  Vote: I like it -13 Vote: I do not like it

ok boomer