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:
- Print number (Brainfuck) — http://ideone.com
- of ones in (Malbolge) — http://www.malbolge.doleczek.pl/
- base 8 (Piet) — http://www.rapapaing.com/blog/?page_id=6
- notation of a (Befunge) — http://www.quirkster.com/iano/js/befunge.html
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!
Oh, I was sure, that in D second language was Befunge, but tested interpreters freezed.
A is probably the most frustrating problem I ever seen on Codeforces.
After reading the previous contest's problem statement and tutorial I figured out that only OEIS can save us :D
Except for Problem F.
E is the best problem i have ever seen.... :D
Wait, does G consider C++ and C++11 to be different languages? What about MS C++ and GNU C++?
Please help me. I dont understand an editorial of A.
I think our sense of humor are compatible!
Nice contest!
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.
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.
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 :-)
Some c++ functional-style solution of E: 17101307
You invented for_each(start, end, function), does you?
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).
the most boring problem is A!!!
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:
But I got CE from my compiler...
Click
For D I actually went to google image search to search for that image-language. No luck
E written in C++ with a little bit ASM 17107204
In D, I tried two Malbolge interpreters: this and this, and none of them can execute the second program. Is it really correct?
I know it's a terrible thing for a software developer to say, but it worked for me with http://www.malbolge.doleczek.pl/, and it was the first interpreter in my search results. Next time I'll have to pick a more standardized language — or a different kind of joke altogether :-)
http://www.matthias-ernst.eu/malbolge/malbolge.c works for me. (under x86_64 gcc version 5.3.1 20160307 (Debian 5.3.1-11))
F is such troll.. How did you even find such sequences starting with 21, 22, 23?
In the announcement thread someone wrote that OEIS provides an archive with all sequences. From there — probably a script on local files.
Search for the given string on OEIS. That's how I got fooled.
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 :)
I didn't try this problem, but why we can't simply write Floyd-Warshall by goto loops in C++ ?
Without if statement it's a bit tricky to implement goto loops
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
I figure out that he just needs to write some code to print it, but that guy is really a new phenomena.
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!
Next time you can look at Status and see what others are doing.
My first time attempting such a contest, I really enjoyed it :-). Too bad it only comes once a year...
in problem G , why should we add the word 'kitten' !!
And, the checker didn't take my
-=^o^=-
for one. So sad.In problem D, I used online Malbolge compiler, but I got RE and i gave up this problem. So sad..
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.
E was fun using
iota(v.begin(), v.end(), 0)
andfor_each(v.begin(), v.end(), [](){})
.17115093
What is relation of "@" and eval?
PS: I did it with simple exec: 17101778
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.
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.
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.
how pow(2,35)not same as the what it is to be
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.
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
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.