Nickolas's blog

By Nickolas, 2 months ago, translation, In English,

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!

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

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What about problem H

»
2 months ago, # |
  Vote: I like it +69 Vote: I do not like it

The answer for the first problem should be "YES" since it is April FOOLS Day. Like if you agree.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +54 Vote: I do not like it

    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   Vote: I like it +14 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

"""You are probably familiar with the fairy tale ending "... and they lived happily ever after". """

NOPE

»
2 months ago, # |
  Vote: I like it +11 Vote: I do not like it

Forever tourist orz

»
2 months ago, # |
  Vote: I like it +86 Vote: I do not like it

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, # ^ |
      Vote: I like it +8 Vote: I do not like it

    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, # ^ |
      Vote: I like it +26 Vote: I do not like it

    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, # ^ |
      Vote: I like it +9 Vote: I do not like it

    That awkward moment when you use Google translate for the Russian version, and then realise "wtf am I doing" xD

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

    Exactly, russian doesn't work correctly.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +33 Vote: I do not like it

    My bad, sorry about that!

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

    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, # |
  Vote: I like it -12 Vote: I do not like it

You are probably familiar with the fairy tale ending "... and they lived happily ever after"...uhhh,not really:)

»
2 months ago, # |
  Vote: I like it +22 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

Are Problem G and H have the same solution as these are the boundaries of the last solution ->xd

»
2 months ago, # |
  Vote: I like it +12 Vote: I do not like it

After seeing problem A I was like, why it's not loading completely, but it was something different

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    hahaha,I just refresh for many times even though I have saw the complete problem

»
2 months ago, # |
  Vote: I like it -79 Vote: I do not like it

This contest was a proper waste of time. Had little high hopes from it...

»
2 months ago, # |
Rev. 2   Vote: I like it +2 Vote: I do not like it

I think the first question is telling us that my "Plot Twist 2: Contest is rated" will not happen. :)

»
2 months ago, # |
  Vote: I like it +84 Vote: I do not like it

How it feels to participate in fools day contest

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone give me the actual code of H?

  • »
    »
    2 months ago, # ^ |
      Vote: I like it +25 Vote: I do not like it

    Here you go: 75151340

    Code
    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it +23 Vote: I do not like it

      Ladies and gentlemen, we got her. Bessie the cow herself outside of Farmer John's barn.

    • »
      »
      »
      2 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Thank you!

      But now i am going to die seeing the solution! -_-

»
2 months ago, # |
Rev. 2   Vote: I like it -10 Vote: I do not like it

Cool tasks! thanks!!! Like if you agree.

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it +2 Vote: I do not like it
»
2 months ago, # |
  Vote: I like it +9 Vote: I do not like it

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, # |
  Vote: I like it +11 Vote: I do not like it

Maripium has made 73 submissions to get an AC to problem F! I am amazed! So much effort. Such Perseverance!!!!

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

What a contest cool!!!!

»
2 months ago, # |
  Vote: I like it +7 Vote: I do not like it

Most people during the first 15 min of the contest: Busy reading questions and submitting solutions

Me: 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, # |
  Vote: I like it 0 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it +24 Vote: I do not like it

better than actual rounds :)

»
2 months ago, # |
  Vote: I like it +10 Vote: I do not like it

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   Vote: I like it 0 Vote: I do not like it

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, # |
  Vote: I like it 0 Vote: I do not like it

can anyone provide me the code for B. how many inputs we have to take??

»
2 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Unfortunately, the following didn't work for G: 75134077

Fortunately, you can add converte parameter to the use statement and run locally. It outputs perl code that is almost valid.

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I had the same idea too

    Unfortunately 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, # ^ |
      Vote: I like it +13 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

Can anyone tell me how to convert that image to string in C++/Python ? (in Problem E)

  • »
    »
    2 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    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, # |
  Vote: I like it 0 Vote: I do not like it

Someone please,explain H number problem...It is still unknown.

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

    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 m

    and 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, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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, # |
  Vote: I like it 0 Vote: I do not like it

fun contest and my first ac submissions

»
2 months ago, # |
  Vote: I like it 0 Vote: I do not like it

what is wrong with problem B ? for(i=2; i<=n/2; i++) { if(n % i == 0) cout<<i; }