Nickolas's blog

By Nickolas, 2 months ago, translation, ,

This was the most well-attended April Fools Day Contest in the whole history of them: 10343 participants solved at least one problem! It was also fairly well-balanced: while each problem has been solved by at least 200 participants, only 17 of them solved all 8 problems.

1331A - Is it rated?

This was the consolation problem of the contest, and still a lot of participants asked me for hints on this problem — some even before the beginning of the round! If you're still not sure how to solve it, the contest announcement itself promised that the contest is not rated, so the answer is a resolute NO'' (case insensitive, quotes for clarity only) :-)

1331B - Limericks

Unusually for this type of contests, the second problem had an actual problem statement! The real task was hidden in it using Steganography 101 — the first letters of the lines spelled out "TWO FACTORS". A quick look at the examples confirmed that you needed to factor the given number and print its factors (in non-decreasing order, without space between them).

1331C - ...And after happily lived ever they

You are probably familiar with the fairy tale ending "... and they lived happily ever after". The problem title is almost that phrase, but with the words scrambled. If you check the problem statement in the other language, it will be a different 6-word phrase that underwent the same scramble. The constraints on the input say that it is an integer are from 0 to 26-1; these two things together should push you towards thinking about binary. The solution is as follows: read the input, convert it into a 6-bit binary representation and scramble it in the same way as the words in the title are scrambled (swapping the 2nd with the 6th and the 3rd with the 4th) before converting it back to the integer. You didn't need to worry whether you need to apply the permutation or the inverse permutation, since those two were the same.

1331D - Again?

This problem has been written by kit1980.

The answer is just the hexadecimal number given in the input taken modulo 2. The problem is absolutely unrelated to OEIS, same as 656F - Ace It!.

1331E - Jordan Smiley

The problem was inspired by the Jordan curve theorem, more specifically by this blog post. You were given the coordinates of a pixel within the picture, and you had to figure out whether it was inside or outside of the region defined by the closed curve that made up the picture.

Once you figured that out, the problem became mostly image parsing :-) The easiest way was to flood-fill the region inside the curve using an image editor, and then somehow convert pixels of different colors into an array of 0s and 1s.

1331F - Elementary!

YES or NO answer implies that you need to figure out whether the given word is "elementary!". At a glance this seems elementary, my dear Watson! — but the fact that "HOLMES" is a "NO" while "WATSON" is a "YES" suggests that this is not what's going on here. In fact you were supposed to use another meaning of the word "elementary" — the one of the periodic table of chemical elements. The word was "elementary" if it could be spelled using only the abbreviated symbols of elements: Ge-Ni-U-S or W-At-S-O-N.

1331G - Lingua Romana

This problem has been written by kit1980.

The problem statement is actual source code of a program written in Perligata. If you manage to run it (or translate it from Latin, though I wouldn't recommend that!), you might recognize TPK algorithm. After that you can implement it yourself or look it up on RosettaCode.

1331H - It's showtime

Both the problem title and the error message you'd get if you try to run some random code like "123" in custom invocation tab point you to an esoteric language ArnoldC — a language based on the one-liners of Arnold Schwarzenegger. You'd have to experiment a bit with finer and less documented points of the language, such as reading input, but modulo function is defined in the documentation, and overall it's a fairly approachable language — as long as you don't try anything fancy like arrays!

• +170

 » 2 months ago, # |   0 What about problem H
•  » » 2 months ago, # ^ |   +1 ArnoldC
•  » » 2 months ago, # ^ |   0 it is still unknown :)
•  » » 2 months ago, # ^ |   +54 IT'S SHOWTIME YOU HAVE BEEN TERMINATED
•  » » 2 months ago, # ^ |   +17 IT HAS BEEN TERMINATED
•  » » 2 months ago, # ^ |   +10 STICK AROUND CHILL
•  » » 7 weeks ago, # ^ |   0 GET YOUR ASS TO MARS
 » 2 months ago, # |   +69 The answer for the first problem should be "YES" since it is April FOOLS Day. Like if you agree.
•  » » 2 months ago, # ^ |   +54 Then it would have been the first time a contestant would have felt a shock after getting an AC xD
•  » » 2 months ago, # ^ | ← Rev. 4 →   +14 Well, if that's the case, they could've taken it even further by updating the ratings and changing it back afterwards.
•  » » » 2 months ago, # ^ |   0 No thank you
 » 2 months ago, # |   0 """You are probably familiar with the fairy tale ending "... and they lived happily ever after". """NOPE
•  » » 2 months ago, # ^ | ← Rev. 2 →   0 I didn't know that too. I figured it out myself.
 » 2 months ago, # |   +11 Forever tourist orz
 » 2 months ago, # |   +86 Are permutation in title in Russian and English statement consistent? and(5) they(4) lived(3) happily(2) ever(1) after(0) and(5) after(0) happily(2) lived(3) ever(1) they(4) и(5) жили(4) они(3) долго(2) и(1) счастливо(0) и(5) счастливо(0) долго(2) жили(4) и(1) они(3) This inconsistency made me recover permutation from samples. I think, something is wrong with Russian statement, because English permutation is same as for samples.
•  » » 2 months ago, # ^ |   +8 I was confused with it aswell, but thought that english version is tested better and I used a permutation of english words.
•  » » 2 months ago, # ^ |   +26 Yeah, and the double “и” threw me off anyway. And the samples actually allow two different permutations. Alright, so the trick this time was to either try both permutations, or look at the statement in English.
•  » » 2 months ago, # ^ |   +9 That awkward moment when you use Google translate for the Russian version, and then realise "wtf am I doing" xD
•  » » 2 months ago, # ^ |   +10 Exactly, russian doesn't work correctly.
•  » » 2 months ago, # ^ |   +33 My bad, sorry about that!
•  » » 2 months ago, # ^ |   +10 I've believed that Toho only attracts East Asian…… But now I know it would attract everyone, just like Vodka would even attract Patchouli!
 » 2 months ago, # |   -12 You are probably familiar with the fairy tale ending "... and they lived happily ever after"...uhhh,not really:)
 » 2 months ago, # |   +22 How to find a solution for D? Is it just a random thing you should notice? I did submit x%2 at 9th minute of the contest, but was absolutely sure it's a wrong solution.
•  » » 2 months ago, # ^ |   0 x should be the last digit here as today's is April fool day
•  » » 2 months ago, # ^ |   0 print the last digit of binary code of given HEX code.
 » 2 months ago, # |   0 Are Problem G and H have the same solution as these are the boundaries of the last solution ->xd
 » 2 months ago, # |   +12 After seeing problem A I was like, why it's not loading completely, but it was something different
•  » » 2 months ago, # ^ |   0 hahaha,I just refresh for many times even though I have saw the complete problem
 » 2 months ago, # |   -79 This contest was a proper waste of time. Had little high hopes from it...
•  » » 2 months ago, # ^ |   -14 but it was totally fun
•  » » » 2 months ago, # ^ |   -48 no idea you're talking about which fun to be honest... -_-
 » 2 months ago, # | ← Rev. 2 →   +2 I think the first question is telling us that my "Plot Twist 2: Contest is rated" will not happen. :)
 » 2 months ago, # |   +84 How it feels to participate in fools day contest
•  » » 2 months ago, # ^ |   0 gg
•  » » 2 months ago, # ^ |   0 Really, wonder what next year will bring :D
 » 2 months ago, # |   0 Can anyone give me the actual code of H?
•  » » 2 months ago, # ^ |   +25 Here you go: 75151340 CodeIT'S SHOWTIME HEY CHRISTMAS TREE t YOU SET US UP 0 HEY CHRISTMAS TREE input YOU SET US UP 0 GET YOUR ASS TO MARS input DO IT NOW I WANT TO ASK YOU A BUNCH OF QUESTIONS AND I WANT TO HAVE THEM ANSWERED IMMEDIATELY HEY CHRISTMAS TREE n YOU SET US UP 0 GET TO THE CHOPPER n HERE IS MY INVITATION input HE HAD TO SPLIT 1000 ENOUGH TALK HEY CHRISTMAS TREE mod YOU SET US UP 0 GET TO THE CHOPPER mod HERE IS MY INVITATION input I LET HIM GO 1000 ENOUGH TALK HEY CHRISTMAS TREE result YOU SET US UP 1 STICK AROUND n GET TO THE CHOPPER result HERE IS MY INVITATION result YOU'RE FIRED n I LET HIM GO mod ENOUGH TALK GET TO THE CHOPPER t HERE IS MY INVITATION n LET OFF SOME STEAM BENNET 1 ENOUGH TALK BECAUSE I'M GOING TO SAY PLEASE t GET TO THE CHOPPER n HERE IS MY INVITATION n GET DOWN 2 ENOUGH TALK BULLSHIT GET TO THE CHOPPER n HERE IS MY INVITATION n GET DOWN 1 ENOUGH TALK YOU HAVE NO RESPECT FOR LOGIC CHILL TALK TO THE HAND result YOU HAVE BEEN TERMINATED 
•  » » » 2 months ago, # ^ |   +23 Ladies and gentlemen, we got her. Bessie the cow herself outside of Farmer John's barn.
•  » » » 2 months ago, # ^ |   0 Thank you!But now i am going to die seeing the solution! -_-
 » 2 months ago, # | ← Rev. 2 →   -10 Cool tasks! thanks!!! Like if you agree.
 » 2 months ago, # |   0 Even though I only got 4 problems, I enjoyed this year's April Fools contest much more than last year's. Great job!
 » 2 months ago, # |   +2 Problem E: "somehow"(https://littlevgl.com/image-to-c-array)
 » 2 months ago, # |   +9 I am quite disappointed that it turned out to be a real language in G :( I was deducing the actions based on the common knowledge of latin words, and THAT was actually very entertaining.
 » 2 months ago, # |   +11 Maripium has made 73 submissions to get an AC to problem F! I am amazed! So much effort. Such Perseverance!!!!
•  » » 2 months ago, # ^ |   +3 meh, it's not interesting to solve like that
 » 2 months ago, # |   0 What a contest cool!!!!
 » 2 months ago, # |   +7 Most people during the first 15 min of the contest: Busy reading questions and submitting solutionsMe: Furiously typing my login details literally every 2 minutes to try to read a question.Seriously though, does anyone know what's going on here?
 » 2 months ago, # |   0 I feel so sad for printing YES or NO instead of 0 or 1 in D :( . Really cool contest, btw I enjoyed it. I guess I was too engaged in searching about limericks, and analyze that mathematical limerick to notice it was also an acrostic. But I guess researching Limericks is a time well spent.
 » 2 months ago, # | ← Rev. 2 →   0 This contest was fun, especially during this Quarantined Lockdown due to Corona.... Many of us were bored at home and this was kinda entertaining.
 » 2 months ago, # |   +24 better than actual rounds :)
 » 2 months ago, # |   +10 This contest made me miss the IPSC, but this contest is way better. Thanks for giving me this interesting experience <3
 » 2 months ago, # | ← Rev. 3 →   0 For D, realizing I've found a pattern, I tried to fetch the given OEIS sequence and print the first element of it. The first submission got me RTE. But I kept trying, until I realized, I was fooled.Submission:
 » 2 months ago, # |   0 can anyone provide me the code for B. how many inputs we have to take??
 » 2 months ago, # |   +10 Unfortunately, the following didn't work for G: 75134077Fortunately, you can add converte parameter to the use statement and run locally. It outputs perl code that is almost valid.
•  » » 2 months ago, # ^ |   0 I had the same idea tooUnfortunately it was the only problem I couldn't solve in the contest as I didn't have the setup to run Perl
•  » » 2 months ago, # ^ |   +13 Yes, we checked that Codeforces doesn't have Perligata installed — that would've defeated the purpose of making you write a little code :-)
 » 2 months ago, # |   0 Can anyone tell me how to convert that image to string in C++/Python ? (in Problem E)
•  » » 2 months ago, # ^ |   0 I used this code to get the answers for E: from PIL import Image import numpy as np image = Image.open('smile.png') data = np.asarray(image) print(data) out_color = (255, 255, 255, 255) in_color = (255, 0, 0, 255) colors = {in_color: 'IN', out_color: 'OUT'} answers = [[None for _ in range(64)] for _ in range(64)] out_answers = set() for i in range(64): for j in range(64): x = i * 15 + 7 # 964 / 64 = 15, 15 // 2 = 7 y = j * 15 + 7 answers[i][j] = colors[tuple(data[x][y])] if answers[i][j] == 'OUT': out_answers.add((i, j)) for i, j in [(0, 0), (27, 0), (0, 27), (27, 27)]: print(i, j, answers[i][j]) with open('out_answers.txt', 'w') as f: f.write(str(out_answers)) 
•  » » » 2 months ago, # ^ |   0 (Here I filled the insides with red)
 » 2 months ago, # |   0 Someone please,explain H number problem...It is still unknown.
•  » » 2 months ago, # ^ | ← Rev. 3 →   +10 I agree. With large numbers like 100, it seems unreasonable to calculate the double factorial of n when n is too large.The solutions that were given seem to be based on the assumption that, for any m > 0 and n > 2:n!! mod m = (n x ((n-2)!! mod m)) mod mand then calculate by recursion.However I am not quite certain about the mathematical truth behind this assumption?Edit: it seems the previously stated assumption is not actually true. However the algorithm still seems valid. Here is a readable version of the solution, courtesy of the winner, tourist: x = input() n = x / 1000 md = x % 1000 flag = 1 res = 1 while n > 0: if flag > 0: res = res * n flag = 1 - flag tmp = (res / md) * md res = res - tmp n = n - 1 print res I'd simplify the algorithm as such: x = input() n = x / 1000 md = x % 1000 res = 1 while n > 0: res = (res * n) % md n = n - 2 print res It seems to work, but I can't figure the mathematical proof behind it. Feel free to comment.
•  » » » 2 months ago, # ^ |   0 Okay I think I have a sort of proof.We'll consider the congruence relation, defined here.The core of the algorithm is the property that, for any positive integers a, b, and k, and an integer m > 1, if a ≡ b (mod m) then ka ≡ kb (mod m) (stated here)We'll consider integers n and m, so that n > 2 and m > 1. The goal of the algorithm is to compute n!! mod m.Let p = n mod m. Therefore, by definition n ≡ p (mod m).So n(n - 2) ≡ p(n - 2) (mod m).This means (n(n - 2)) mod m = (p(n - 2)) mod m = ((n mod m)(n - 2)) mod m.We'll call this number p', so p' = (p(n - 2)) mod m.Therefore n(n - 2) ≡ p(n - 2) (mod m) and n(n - 2) ≡ p' (mod m).So (n(n - 2)(n - 4)) mod m = (p(n - 2)(n - 4)) mod m = (p'(n - 4)) mod m...If we keep iterating like this, we can eventually compute n!! mod m through the aforementioned algorithm, without having to compute the potentially large number, n!!.Feel free to comment.
 » 2 months ago, # |   0 fun contest and my first ac submissions
 » 2 months ago, # |   0 what is wrong with problem B ? for(i=2; i<=n/2; i++) { if(n % i == 0) cout<
•  » » 7 weeks ago, # ^ |   0 your output should be i and (n/i) without space.