### Nickolas's blog

By Nickolas, 4 years ago, translation,

This turned out to be the hardest April Fools Day Contest to date — the winner solved only 5 problems out of 7!

## 1145A - Thanos Sort

The easiest problem of the contest, with a statement and without any caveats — I just likes the idea of sorting the array by destroying elements you dislike :-) Since the array has at most 16 elements, it's enough to implement the described algorithm precisely: check if the array is sorted, if it is, return its length, otherwise return the maximum of the answers for its left and right halves.

## 1145B - Kanban Numbers

YES or NO answer implies that you need to figure out whether the given number is a kanban number; but first you need to figure out what kind of a number is kanban? OEIS does not have this sequence, but it has several similar ones, such as urban numbers and turban numbers. These sequences are defined as numbers which "ban" certain letters, i.e., don't use them in their English spelling. Thus, kanban numbers "ban" letters "k", "a" and "n"; in practice the numbers from 1 to 99 never contain letters "k" or "a" so you only need to watch for "n".

## 1145C - Mystery Circuit

This problem was a little Easter egg for the people who follow my recent activity on Codeforces :-) The image contained a (relatively) simple quantum circuit for an operation which 1) represents the number in 4-bit binary notation, 2) reverses it, 3) decrements the resulting number, 4) reverses it again and 5) outputs the resulting number in decimal notation again. You could figure this out without doing the math yourself by building this circuit in any tool for quantum circuit modeling, such as Quirk.

## 1145D - Pigeon d'Or

Pigeon d'Or is an actually existing project (well, an existing project concept). But for the purposes of this problem you don't need this knowledge, I just needed a sufficiently long text to hide the real statement. Но для целей этой задачи это знание излишне, мне просто нужен был достаточно длинный текст, в котором можно было бы спрятать настоящее условие. "We did not proofread this statement at all" hints that the typos are not accidental, and you need to pay attention to them. All typos replace correct letters with incorrect ones; if you collect all incorrect letters they will spell the real statement: "two plus xor of third and min elements".

## 1145E - Fourier Doodles

This problem was written by kit1980.

The word Fourier hints at using Fourier transform for images (you can also notice that the training data set files are a lot larger than the rest of the files, so they probably hide some extra information). Fortunately, you didn't have to implement it manually, there are plenty of existing tools to do that, including online ones (I used http://www.ejectamenta.com/Imaging-Experiments/fourierimagefiltering.html). If you look at the transforms of the first 20 files, each of them has one or two characters, which together spell the formula: "((min(id, 25) + id) % (2 + id % 3)) > 0".

## 1145F - Neat Words

Again, YES or NO answer implies that you need to figure out whether the given word is neat. It can be tricky, especially since WORD itself is not neat... Long story short, in this problem you had to group all letters of English alphabet in two types — "linear", consisting only of straight lines, and "curved", including curved elements (you had to take the letters the way they are spelled in the statement, i.e., uppercase). Now, obviously, neat words are words in which all letters belong to the same type, and their opposite (disorderly?) are words which mix letters from both types.

## 1145G - AI Takeover

The hardest part of this problem is identifying the strategies used by the agent. Once you're done with that, the rest of the solution becomes easy: find a sequence of 10 or less moves which produces a different sequence of outcomes for each strategy, play it, deduce the strategy based on the outcomes you've received, and play the counter-strategy for it.

The AI strategies were:

• always play R, P or S,
• loop through a sequence R-P-S,
• start with R, then always play the human player's last move,
• start with R, then always play the move that beats the human player's last move.

You can check that, for example, a sequence of moves RRPPSS allows to distinguish these strategies and to win the next 10 rounds.

As for how to identify the strategies used, majk described one reasonable strategy. If you don't like relying on guesswork, you could try some kind of brute force to figure out the AI's responses to your strategy by encoding them in memory allocation or sleep time, like people frequently do for easier problems.

Oh well, I guess AI takeover is a more serious threat to humanity than I expected...

• +38

| Write comment?
 » 4 years ago, # |   +19 Will editorial for problem C be under mystery too??
•  » » 4 years ago, # ^ |   0 It will be posted soon https://codeforces.com/blog/entry/66260?#comment-503458
•  » » 4 years ago, # ^ | ← Rev. 2 →   +6 Seemed to me that it was a problem on Controlled NOT gate
•  » » 4 years ago, # ^ |   0 Well, it was perhaps the most serious problem though... The answer is the output of the quantum gate with given input (the lowest bit is in the first row).
 » 4 years ago, # |   +6 Solution to G doesn't make any sense at all to me. How was I supposed to solve this? There are many other solutions coming to my mind that make more sense to me. How did anybody solve it in first attempt? majk maybe you could shed some light on it?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 My first attempt was to essentially get all 9 possible permutations of my last move and my current move and note which ones I win. Then I use this table to select a winning move using my last move, which wins for constant strategy and strategy where the AI looks at my last move; but it failed on strategy 4 alas and I didn't imagine there would be strategies as such. But then strategies like that only require 1 test to win somehow, and perhaps depending on the string you're using you may get lucky...
•  » » 4 years ago, # ^ |   +16 It's obvious that a deterministic strategy is a function of the sequence of all previous moves of the human player. I assumed that the problem is solvable without too many incorrect attempts, so it will probably depend only on the last $k$ moves for some small $k$. I realised that for $k = 1$, I can distinguish all $27$ such strategies. So I just tried that.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   +1 Somehow makes sense, but on the other hand there is nothing holding AI back to just have hardcoded sequence of moves "RPSSPSPSRPRPRSSPRPSP" or even alter it based on what we play and having any hardcoded sequence sounds like a very simple deterministic strategy to me. I thought this problem may be about something entirely different like getting bits about strategies from judge by sleeping for some time and taking some amount of memory (that's basically how mnbvmar solved B, C and F — his code to F https://pastebin.com/18zgjAEx) or looking for some informations in linked problem from 5 years ago and taking 6 strategies from testcases there or something entirely different that I didn't come up with. I see what you did there and see why it can seem promising to some people, but for me it just seemed way too naive and just plain stupid to pose a problem with solution like that. Thanks for explanation anyway.
•  » » 4 years ago, # ^ |   +12 Which strategies come to your mind? For me, it was obviously all strategies independent on user input (and with a small enough period because it's unsolvable otherwise) and always playing the move that beats the last move played by the opponent. Turns out I wasn't very far.It does say 6 simple strategies. You'll have to think about what strategies make it solvable because if there's anything complex enough, you cannot solve the problem other than through blind luck — which most likely isn't the point.
•  » » » 4 years ago, # ^ |   +1 The thing is that unsolvable kinda loses its meaning in such a contest. If I assume that this is a legit problem and it is self-contained then maybe you are right. But this is April Fool contest and everything is possible. I explained some approaches in a comment above that came to my mind and there were possibly many more that might have crossed problemsetter's mind but not mine. If this couldn't be the case that such ides exist then it would mean that I should be able to solve any problem on this contest which definitely wasn't the case :).
•  » » » » 4 years ago, # ^ |   +1 There's a limit to what constitutes an April Fools prank. A shit problem that's only solvable by Google-tier datamining or by pure luck is pretty clearly beyond that line.Anyway, trolling yourself with overthinking is part of what makes these contests fun. As soon as I saw the broken image in C, I started digging through HTML, sending curl requests and trying to dig something out of the filename...
 » 4 years ago, # |   0 I was looking answer for C in title of image(
 » 4 years ago, # | ← Rev. 2 →   +32 After so many years of skipping this contest I finally gave it a shot and was pretty excited about it. I loved last year's roulette and cheese board.A — obviousD — got the right idea immediately, but didn't know that "feces" is an actual world (thought it is misspelled "faces"), so I got stuck after getting "mine element" instead of "min element"E — got the right idea but failed to find in google sites that compute Fourier transform on pictures since I googled "fourier transform online" instead of "fourier transform online picture" which gives many resultsB, C, F, G — solutions to these problems don't make sense to me, I wouldn't have solved them in intended way even when given infinite time. But I managed to bruteforce C.This contest gave me nothing but anger that I still can't get rid of.
•  » » 4 years ago, # ^ |   +36 Maybe you are not foolish enough.BTW, typo: "actual world" ==> "actual word". Hidden Message : "l"
•  » » 4 years ago, # ^ |   +14 I perconally just uploaded D's statement into a google doc and didn't even look at non-red words. It counted "berds" as an ok word tho, so I ended up with "min lement".
•  » » 4 years ago, # ^ |   0 Lol u mad.If you had solved the quantum contest, you probably would've known how to solve C. I've seen these gate schemas plenty of times while trying to find out how to solve something there.Ad E, GIMP has an FFT plugin, but with all the dependencies and low-quality installation instructions, it's probably easier to just find something online.
•  » » » 4 years ago, # ^ |   +5 Ah, yeah. C makes sense if you know something about quantum computing, but no way to solve it if you don't.
•  » » » » 4 years ago, # ^ |   +3 Well, taking the risk of getting further downvoted, IMHO one could (as I did) "google search for image" for a part of the image (isolating maybe just one (+) or two) and you would find the images which are on https://en.wikipedia.org/wiki/Quantum_logic_gate (several here) and https://en.wikipedia.org/wiki/Controlled_NOT_gate and https://en.wikipedia.org/wiki/Toffoli_gate.
•  » » 4 years ago, # ^ |   0 E — If you got the idea you can also write some Python code to solve it. Unfortunately for me I started this problem too late and ran out of time :(B — "Kanban" — weird word which suggest we should find some information from this word. After lots of Googling I found ban numbers.
•  » » » 4 years ago, # ^ |   +6 I also googled and found "Kanban number" (numbers on Kanban cards, some inventory system, cf wikipedia) but I got "trapped" by that irrelevant "information"... :-(. Never mind, I liked the contest in spite of some slightly frustrating exercices.
 » 4 years ago, # | ← Rev. 3 →   +13 I have solved B problem only because I watched Numberphile's I-ban numbers video :)
 » 4 years ago, # |   0 After reading several times still doesn't know what it means. I'm noob
 » 4 years ago, # |   +10 Welp I thought the AI in G would be a complete and you loses no matter what "legit" input you commit.
 » 4 years ago, # |   0 While looking at 1145B - Kanban Numbers solutions by top scorers, I found "magic number lists" by these submissions are similar. Can you guys elaborate on the magic list [5, 46, 2, 3, 4, 12, 30, 31, 35, 36, 39, 43, 52, 64, 86] and similar?
•  » » 4 years ago, # ^ | ← Rev. 2 →   0 They are exactly the Kanban numbers that were used in the test cases. But looks like many of them got some/ all of the numbers without even submitting once. So I'm guessing there was some kind of teamwork involved.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Some additional comments. I was wrong about the numbers being exactly the ones tested, there are some slight differences between the submissions (for example 31 (not kanban), 32(kanban), 36(kanban),39(not kanban)... sometimes being marked as kanban).Still the magic sequences used are not even close to the actual kanban numbers, and in no way should it be possible for such a wrong sequence to be accepted first try. It is pretty clear that the magic sequences were found by reverse engineering by submitting many times, see for example this.
 » 3 years ago, # |   0 In the worst case: the time complexity of A. Thanos Sort is O(nlogn). Am I right?