Nickolas's blog

By Nickolas, 10 years ago, translation, In English

Unfortunately, the most anybody could solve was 7 problems out of 9 total. 1289 participants solved at least one problem — this is less than the last year's numbers, but not bad either. Anyways, the key point is the total quantity of fun the people had!

409A - The Great Game

The Most Intellectually Challenging Game In The World turned out to be the famous rock-paper-scissors. One could deduce this from the examples — ok, the rock () didn't look itself, but paper [] and especially scissors 8< looked really lifelike!

Team competition is organized like this: players are split into pairs, with one player of each team in each pair, and pairs play against each other (the first line of input has "moves" of first team's players, the second line — of second team's players). The team which scores more individual victories wins.

By the way, the game is not so trivial as it looks — there are big tomes written about the strategies, game ethics and organizing clubs and competitions, the tournaments run in many countries, and the largest tournament had over 6500 participants!

409B - Mysterious Language

Attempting to run nearly any code in Mysterious Language resulted in a pack of compilation errors, among them — "Unclassifiable statement at (1)". This pointed to Fortran language immediately, but then the doubts began. There are quite a few Fortrans out there, and even more compilers, so what exactly needs to be printed out? My idea was that the compiler should have been configured to accept only fixed format of Fortran programs, which points to FORTRAN 77 (Fortran 90 and later supported free format, without uppercasing commands and indentation). Judging from the questions and the comments, something went wrong here, and some programs in free format compiled fine... Anyways, the answer is "FORTRAN 77".

409C - Magnum Opus

Magnum Opus is an alchemy name for the process of philosophical stone creation. This (and also the signature "Nicolas Flammel") hints that the problem describes a recipe of the philosophical stone, and our task is to create it. If we recognize the statement as a text in Latin (although there were attempts to interpret is as Italian) and go to Google Translate for help, we can enjoy the literary beauty and deep irony of the letter, in which a mature alchemist shares the secrets of trade with his younger colleague. Or you can neglect the twists and fast forward to solving the problem, if you notice that the input has 5 numbers, and the recipe contains 5 ingredients in given proportion (proportions are given with easily recognizable Roman numbers before the names of ingredients).

Overall the problem asked how much of philosophical stone we can create, if we have given quantities of ingredients and a smoothly running manufacturing procedure. The answer is min(a[0],a[1],a[2]/2,a[3]/7,a[4]/4).

409D - Big Data

A lot of facts with big numbers is not yet big data. Especially if half of them are wrong! The biggest board games tournament had 43 thousand chess players, the math competition — over a million participants, and Colonel Meow, while a gorgeous cat (you can enjoy the photos at Guinness World Records site ), still doesn't feature a meter-long fur!

The problem asked you to figure out the truth of the given facts, and print 1 or 0 depending on whether i-th fact is true or not-so-true.

409E - Dome

This geometry problem (a joke itself :-) ) was described with a single picture: a hemisphere inscribed in a pyramid. An extra kick is that the problem is kind of inverse problem — you are not given the pyramid and asked to find the radius of a hemisphere, but rather given the hemisphere and asked to build a pyramid around it. Fortunately, pyramid parameters height h and base side length a took only integer values from 1 to 10. The easiest way to tackle this was to try all possible pairs of a and h, calculate all radii (as height in a right-angled triangle with sides h and a/2) and check whether the resulting radius is close to the given one. Note that some radii can be obtained from several pyramids.

409F - 000001

Imagine, initially I wanted to put this problem first, and less than 30 people solved it :-) This is a problem writer's dream — a problem without a statement. Given 4 examples, it's rather tricky to guess an int -> int function for 64 input values. More or less evident theories like "the smallest power of 2 greater than or equal to a" turn out to be wrong (the contest discussion has several more elegant but totally wrong ideas).

Two heuristics* help: 1) even if a problem has no statement, it has a name, and 2) any strange function int -> int can be looked for in Online Encyclopedia of Integer Sequences. Combine them, and you'll get a sequence http://oeis.org/A000001. To solve the problem you don't even have to figure out what "groups of order n" are — the first 64 elements of the sequence are given in the article about it.

  • Note that using a third heuristic (even if a problem has no statement, it has the constraints) is misleading in this case.

409G - On a plane

This problem was written by Skiminok; I'm quite a trickster myself, but I wouldn't have dreamed of giving the statement in samples. And not just giving it; the points from each sample had to be plotted on a 2D plane to get a picture like this

and read from it the statement: 5 + AVG Y (each sample represented one letter).

409H - A + B Strikes Back

This problem caused plenty of emotions and questions "how can it be, I had correct answers for the pretests, and the submission fails the very first test?". See, today is April 1st, and even the checker might feel a bit playful today. For example, it might refuse to accept the solution, and it will require some persuasion for it to stop being naughty. The authors' idea was to reject the first five attempts on the problem right away, and to start actually checking the submissions only starting with the 6th attempt. I do hope that it looked like this from participants' point of view :-)

409I - Feed the Golorp

This problem was contributed by kit1980.

Golorp's name (have anyone noticed that "golorp" is "prolog" spelled backwards?) is an expression in Prolog. The jaws (left part up to ":-") contains the list of variables (possibly with repetitions) separated by arithmetic characters. The characters are just separators and have no deep meaning, they can be replaced with commas. The stomach (right part after ":-") lists the inequalities that must hold for the variables from the jaws.

The task is to find lexicographically smallest set of variable values which satisfy the constraints. In fact, you have to perform topological sorting. The easiest way is to iterate infinitely through the inequalities, find the ones which are not satisfied yet and increase the value of the variable which must be greater than the other one in it. As soon as one of the variables grows to be 10, the answer is false. Otherwise we will stop when all inequalities are satisfied. With the given constraints the solution is fast enough.

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

| Write comment?
»
10 years ago, # |
  Vote: I like it +5 Vote: I do not like it
»
10 years ago, # |
  Vote: I like it +4 Vote: I do not like it

for problem D, i noticed that every fact had a number along with it. i thought that these would somehow be related to the answer, but i was wrong! :D

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

    This was our original intention (to have people output number from i-th correct fact), but this problem was the last to be prepared (less than 10 hours before the contest), and I had only 16 facts total — using only half of them for tests would have left us with only 8 test cases, which seemed too little.

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

Can we declare March 1st as Fool Programmers Day and have a contest like this again... :) we all have got a lot of fun trying to solve those problems...

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

    March 1 is already past, why not make it May 1 instead :)

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

      Sorry I forget which one comes after april.... thats why i am a big fool.. May 1 then... :D

»
10 years ago, # |
  Vote: I like it +4 Vote: I do not like it

For problem B, did you change the grader in the middle of the contest? In the beginning, the filename in the compilation output is "program.f". However, after I solved other problems and then went back to this problem, the filename changed into "program.ext".

That was a (slight) advantage for me that noticed this fact :)

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

    I myself noticed folder named g95 (fortran compiler) and some other great hints too. And similarly some time later the same error wouldn't include the path : ))

»
10 years ago, # |
  Vote: I like it -8 Vote: I do not like it

How to add a friend?

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

    Open this person's profile, there will be a star next to his name, press it, it will turn yellow, which mean you added him. but dont post comments that have nothing to do with the topic.

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

409H - A + B Strikes Back

When solving this I knew the answer will be evaluated on attempt 6 because "Emperor strikes back" was episode 5. I hope that was the rationale to choose number 5 or was it not?

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

    It wasn't :-) 5 was chosen as a reasonable compromise between few attempts which could be done unintentionally, and a lot of attempts which are irritating.

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

    actually, i feel that in such type of contests, problem name should be chosen with something to do with the answer, rather than the other way around. basically, i mean that Strikes Back could have been chosen because of 5 attempts, rather than what u suggested. :)
    for example, i think this was the rationale behind the name of the problem 409F - 000001. am i right Nickolas? ;)

    P.S. i see that the problem 409H - A + B Strikes Back contains the tag 2-sat. any idea why?

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

      In some problems name just has to be strongly related with the solution — for example, if the problem doesn't have a statement. This, of course, is the case with 000001. In other problems name can be anything funny, like in A + B strikes back — I find the idea of A + B taking revenge on humans for treating it without proper respect pretty funny.

      P.S. No clue; either a bug or a joke from a co-author :-)

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

        I find the idea of A + B taking revenge on humans for treating it without proper respect pretty funny.

        seconded! :D