Nickolas's blog

April Fools Day Contest 2016: editorial
By Nickolas, 9 years ago, In English

I'm happy to see that this year there were 3 people who managed to solve all 7 problems! Unfortunately, only 1097 participants solved at least one problem, which is less than in 2014.

656A - Da Vinci Powers

This problem asked to figure out an integer sequence from two samples and problem title. It turned out to be surprisingly hard, a lot harder than I anticipated. A quick search through OEIS shows that while there are a lot of sequences which have these two numbers in them, only one is related to Leonardo da Vinci (and if you're looking for da Vinci, there are only two sequences overall). http://oeis.org/A221180 is an erroneous series of powers of 2, written down by da Vinci in his diaries and available as part of "Codex Madrid I".

656B - Scrambled

Just one word: typoglycemia. The urban legend (unsupported by any known research) claims that people can easily read text even if letters in each word are scrambled, as long as the first and the last letters stay in place. Looked like a fun thing to verify on a small (and strongly biased) sample of competitive programmers. Judging from the results, it's really not much of an obstacle :-)

When un-scrambled, the lengthy statement becomes a story about two roommates who are trying to figure out a fair way to split dishes washing duty. (Fun fact: this problem idea is actually inspired not by any real-life events but by a theater play.) "You agree on two arrays of integers M and R, number upcoming days (including the current one) with successive integers (the current day is zero), and you wash the dishes on day N if and only if there exists an index i such that N % M[i] = R[i], otherwise your roommate does it... Calculate the percentage of days on which you end up doing the washing."

To find the answer, you can find least common multiple of numbers in array M. The infinite number of days ahead can be split into identical blocks of M days, so the percentage of all days on which you end up with the chore will be the same as the percentage of the first LCM days. Iterate over days 0..LCM-1 and for each day check who gets to do the chore on it (since each element is at most 16, LCM will be at most 720720, and iteration will be sufficiently fast).

A much simpler approach would be just to iterate over a lot of days regardless of LCM and calculate the answer based on them — the absolute error will be small enough for this solution to pass.

656C - Without Text

One more statement-less problem (and one more problem which turned out to be harder than I thought), but at least this one has a picture! By this time anyone with a history of participation in my contests should recognize a program regardless of the language in which it is written. In this case it is Sanscript, a visual dataflow language. The image doesn't represent the whole program, just the body of the main loop, but it contains most of the logic.

Individual elements of the program (functions) are fairly well annotated, so it shouldn't be too hard to figure out the overall purpose of the "code". The whole mess of the blocks and arrows calculates sum of indices of uppercase letters in English alphabet (A is 1, B is 2 etc.) minus sum of indices of lowercase letters in alphabet. Non-letter characters are ignored.

656D - Rosetta Problem

I love so many unusual programming languages that one language per problem just can't cover all of them. The solution is simple: have several languages per problem! Unfortunately, most people on Codeforces don't share my passion for languages, and this problem, while being trivial to implement, turned out to be the hardest in the whole contest.

Each paragraph of the statement is a short program in one of esoteric languages. If you recognize each one, find an interpreter for it and execute the program, you'll get a piece of statement. Put them together to find out what is it that you need to do to solve the actual problem:

656E - Out of Controls

This problem was the first and the last one to tell you clearly and without doubt what you have to do: write a solution to a simple graph problem (likely using a Floyd-Warshall algorithm) without any traditional reserved words for loops and conditional statements.

There is a number of workarounds possible, which strongly depend on the language you use. Three main approaches were:

  • Honestly rewrite the solution in a recursive way.
  • Add some other characters in the middle of each forbidden keyword (/*..*/ in C++ or @ in Python with eval)
  • Use built-in functions like map, each etc.
  • I suspect the few Haskell users were not inconvenienced at all :-)

656F - Ace It!

This problem was contributed by kit1980.

One of the most common tricks in April Fool's day contests is OEIS lookup. Most statement-less problems can be solved by thoroughly searching the website. In this problem, you were given OEIS sequence numbers, and if you checked them on the website, you could notice that the answer is the first element of the given sequence. Now it's just a matter of encoding this lookup process, given that Codeforces doesn't allow solutions to visit external websites...

Ok, it's about time to shout "April Fool!" and burst into laughter. Forget about OEIS. This problem was carefully forged to look very much like what I've described (and I hope it did!), but the actual solution is much, much simpler. The input represents a hand of cards in a game of blackjack, and you have to calculate the sum of points for it. A stands for Ace, worth 1 point (the minimal sum of the 6 digits part of the hand is 12, so if Ace is counted as 11, you're guaranteed to go bust), digits 2..9 correspond to matching cards, and pair of digits 10 represents, well, a ten. The reference to "validity" in the statement meant that 1 or 0 will never appear alone, but will always form a valid card.

656G - You're a Professional

This problem was a kind of tribute to a story called "The Expert" (https://www.youtube.com/watch?v=BKorP55Aqvg). You are given a simple task, but the checker, a.k.a. the customer, keeps throwing new requirements at you. First, you have to rewrite your solution in any other language (that's when you don't want C++ to be the only programming language you know!) regardless of what was your original language. Next, the solution turns out to be too long (again, regardless of its original length). Finally, you have to add a kitten to it (just put a word "kitten" anywhere in the code). Turned out to be much easier than decoding weird programming languages!

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

Comments Comments (46)
| Write comment?
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

Oh, I was sure, that in D second language was Befunge, but tested interpreters freezed.

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it +29 Vote: I do not like it

A is probably the most frustrating problem I ever seen on Codeforces.

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

    After reading the previous contest's problem statement and tutorial I figured out that only OEIS can save us :D

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

E is the best problem i have ever seen.... :D

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Wait, does G consider C++ and C++11 to be different languages? What about MS C++ and GNU C++?

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Please help me. I dont understand an editorial of A.

→ Reply
»
9 years ago, # |
  Vote: I like it +39 Vote: I do not like it

I think our sense of humor are compatible!

Nice contest!

→ Reply
»
9 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Really nice problems, I got fooled by F :)

Was it intentional that the first page in google search for "malbolge interpreter online" gives segmentation fault for the provided code? Only the second result (the one you point to) returns answer. BTW I didn't know what is the last language but this part of statement was unnecessary.

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

    Without the last piece I interruptted "Print number of ones in BASE 8" as print oct(raw_input().count('1'))[1:]

    There are indeed only two possibilities, though.

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

    No.

    The order of search results depends on the person, I think the one I link to from the editorial was the first one for me. I guess Malbolge is not standardized enough to be portable cross-implementations :-)

    → Reply
»
9 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Some c++ functional-style solution of E: 17101307

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +16 Vote: I do not like it

    You invented for_each(start, end, function), does you?

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

      I was not sure it's not banned :) Also it's not that trivial to generate start and end (they should be iterators, not numbers).

      → Reply
»
9 years ago, # |
  Vote: I like it +7 Vote: I do not like it

the most boring problem is A!!!

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

E

Add some other characters in the middle of each forbidden keyword (/*..*/ in C++ or @ in Python with eval)

Do you mean sth like this:

f/*..*/or (int i = 0; i < n; i++);

But I got CE from my compiler...

→ Reply
»
9 years ago, # |
  Vote: I like it +8 Vote: I do not like it

For D I actually went to google image search to search for that image-language. No luck

→ Reply
»
9 years ago, # |
  Vote: I like it +5 Vote: I do not like it

E written in C++ with a little bit ASM 17107204

→ Reply
»
9 years ago, # |
  Vote: I like it +39 Vote: I do not like it

In D, I tried two Malbolge interpreters: this and this, and none of them can execute the second program. Is it really correct?

→ Reply
»
9 years ago, # |
  Vote: I like it +18 Vote: I do not like it

F is such troll.. How did you even find such sequences starting with 21, 22, 23?

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it

    In the announcement thread someone wrote that OEIS provides an archive with all sequences. From there — probably a script on local files.

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

    Search for the given string on OEIS. That's how I got fooled.

    → Reply
»
9 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Given small constraint in E, my first thought was to write 1000 if statements (with C++ conditional operator), similar to this: 17104757. Luckily I gave up midway and found the recursive solution :)

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    I didn't try this problem, but why we can't simply write Floyd-Warshall by goto loops in C++ ?

    → Reply
    • »
      »
      »
      9 years ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      Without if statement it's a bit tricky to implement goto loops

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

    that's what I did E-code just a recursion functions instead of 2 loops for input ,3 for Floyd-Warshall and 2 to find the answer

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

    I figure out that he just needs to write some code to print it, but that guy is really a new phenomena.

    → Reply
»
9 years ago, # |
  Vote: I like it +16 Vote: I do not like it

For me error message in G was misleading. I decided that more modern language is some really modern, and start learning D. But it appears that any other language is appropriate.

In all other respects it was a merry contest!

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

    Next time you can look at Status and see what others are doing.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

My first time attempting such a contest, I really enjoyed it :-). Too bad it only comes once a year...

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

in problem G , why should we add the word 'kitten' !!

→ Reply
»
9 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

In problem D, I used online Malbolge compiler, but I got RE and i gave up this problem. So sad..

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

    Actually, once I've got the other three parts, "Prnt number ??? base 8 notation of a", I was tempted to check whether it's the number of 0s, 1s, or 2s by just submitting such three solutions.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

E was fun using iota(v.begin(), v.end(), 0) and for_each(v.begin(), v.end(), [](){}).

17115093

→ Reply
»
9 years ago, # |
  Vote: I like it +39 Vote: I do not like it

@ in Python with eval

What is relation of "@" and eval?

PS: I did it with simple exec: 17101778

→ Reply
»
9 years ago, # |
  Vote: I like it +9 Vote: I do not like it

Problem F was a good one! I spent half an hour trying to fit the necessary info into 64 KBytes... Feeling foolish :P .

Thank you for the contest! Also, I'm amazed by the flexibility shown by the Codeforces platform in problems E and G.

→ Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anybody plz tell me why in problem G the word kitten is added in solution How come you get to know to add this word only as this is not mentioned in the problem statement.

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

    You will be given the instruction in the verdict if you click on the "Wrong Answer on Test 1". For this task you are not penalized for these incorrect submissions so you can try as many times as you want.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

how pow(2,35)not same as the what it is to be

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    The sequence is not actually powers of 2, it's what da Vinci believed to be powers of 2, but he made an error during calculations.

    → Reply
»
9 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve problem G? I have submit it with C++,C,Pascal,JavaScript,JAVA8,but I always get a Wrong answer on test 1

→ Reply
  • »
    »
    9 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    In the list of your submissions, the "Wrong answer on test 1" outcome should be clickable. Click and read what you are expected to do next.

    → Reply