Kostroma's blog

AIM Tech Poorly Prepared Contest (unrated, funny, div. 1 preferred)
By Kostroma, 5 years ago, In English

Hello!

Traditionally AIM Tech organizes a big party for Petrozavodsk camp participants to have fun and get an opportunity to communicate with each other. Usually it comes along with a funny contest in unusual format. This year we decided to share the fun with all codeforces community!

This year we came up with a format requiring (probably) less time for preparing the contest. It is somewhat similar to an ordinary contest with a 3-hour duration. We already have some problem ideas, so it should be super easy to prepare the problems just one night before the competition. We hope everything will run smoothly!

The contest will start on Feb/03/2020 19:15 (Moscow time). It could be a bit rescheduled due to onsite delays.

It will be an unrated funny competition. Unlike usual ICPC-style contests, you'll be given an archive with several open test cases and answers for each problem. You'll have some sample test cases in the statement too, they'll be included in the archive. However, the solutions will be tested against both open and hidden tests. The open tests will be published as an encrypted zip-archive in this post. The password will be published just before the start of the contest.

The statements will be in English only because we are running out of time in preparation and have to prioritize things.

It's not 100-percent clear at the moment, but it seems the contest will be somewhat hard, so we recommend it for div. 1 participants. However, div. 2 participants are welcome as always, but we can't guarantee the contest will be a perfect match for them.

It's possible to participate both individually and in teams of maximum 3 persons.

Another point to mention is that the order of problems could be not the same as the order of their difficulties. But we'll try to do so. A bit.

The authors to blame are Kostroma, zemen, Golovanov399, mathbunnyru and ArtDitel.

As you may notice, it is just one night before the competition, so we should start preparing the problems. We hope that we'll manage not to do very stupid bugs in the tests. See you at the competition!

UPD It's still more than 4 hours before the contest, but the open tests are already prepared! You can download the archive using one of the two links: one two. The encrypted archive contains another archive containing the actual tests.

The password will be published here shortly before the start of the contest.

UPD2 We have to move contest 10 minutes forward, because we need to prepare the last problem :(

UPD3 Oops, the contest is about to start, but we still don't have correct solutions! Unfortunately, each authors' solution contains a bug (or even several bugs!). However, we decided not to cancel the competition. We give you the outputs of the model solutions on open tests in the archive. Guess all the bugs in our solutions and get OK for the code with exactly same bugs! Good luck and have fun!

The password to the archive will be published as a clarification in the contest interface.

UPD4 The password to the archive is oops_seems_that_nobody_tested_the_solutions

UPD5 The editorial is published, but it still does contain bugs, wait a bit while it is being debugged.

UPD6 Feel free to share your opinion in the comments! Were the solutions enough buggy? Was it enough hard, or we should've added a couple of hard problems? Do you want to solve such contests in future?

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

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

Why the unusual contest format? Are there not going to be problem statements?

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

    We don't want to spoil the fun and tell in advance and tell everything about the contest.

    The statements will be in English only because we are running out of time in preparation and have to prioritize things.

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

      means there will be statements.

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

        Or rather that all statements that will be prepared will be in English

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

    There will be statements, if we have enough time, you know

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

Clashes with topcoder srm 777

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

    Unfortunately, this is the time of big party in Petrozavodsk camp, so we can't change the time of the competition.

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

    Sometimes I don't understand our community. Informing about timing coincidence with TopCoder SRM 777 was quite important. It could possibly encourage the contestmakers to shift the start a little bit. Why solvemproblr's phrase was given so much negative feedback? (Currenly I see -51.) Shouldn't we downvote non-informative bulk, and encourage adequate communication?

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

Awesome!I hope I'll enjoy it

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

A second version of April fool

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

>inb4 angry Um_nik complaining about quality after the contest

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

Any constraint on team size?

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

Note that now you can download the encrypted archive with open tests.

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

It would be funnier if we get the problem statements before the contest ;)

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

    Please don't ask impossible things, let's just hope the statements will be available at the start.

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

    You know, I'm one of the authors, it's my first contest in a long time, and the first time I do actually prepare the contest as an author and we prepared the problems one night before the competition.

    What could go wrong? :)

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

"The authors to blame are: Kostroma, zemen, Golovanov399 and mathbunnyru."

Why can't we blame ArtDitel? :D

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

    Fixed, you are welcome to blame him too now.

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

      Why me? I will just sit and drink beer during contest :(

      But actually you can blame me for not preparing contest at all yesterday night :troll:

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

        You'll be answering questions like "why the problems are so bad??" in the contest interface.

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

Hi Codeforces.

To be well prepared for the contest, together with Fly_37 and w0nsh we decided to make our version of Poorly Prepared Snowman.

Cheers from Petrozavodsk!!! <3

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

    Comparing with our contest, this seems like a truly inspiring work of art.

    → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 3   Vote: I like it +55 Vote: I do not like it

    Comparing with high-frequency trading, this seems like a truly inspiring work of art.

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

"UPD2 We have to move contest 10 minutes forward, because we need to prepare the last problem :("

Why not just start the contest and add the last problem during the contest?

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

    Thank you, that's the path we'll choose.

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

    Maybe they use those 10 minutes to prepare other problems too, who knows

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

GuessTheBugForces

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

5kB/s, 2.0MB now. oh man..

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

"We give you the outputs of the model solutions on open tests in the archive." Sorry, I am not able to find the outputs. I can see only test cases.

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

Imagine reading J's statement on a regular Codeforces/ICPC contest...

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

    Good idea, will add this problem to next rated cf contest

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

    It would be funny to give this problem printed on a piece of paper :)

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

It could be better if difficulty was like A>B>C>D>...

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

    Sorry, we didn't have time to sort problems ¯_(ツ)_/¯

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

I like the format, but the problems are to hard, was not able to solve one.

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

    Sorry about that, it wasn't that easy and fun to prepare the easy problems. We tried to emphasize that we recommend it for div. 1 participants.

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

After 1 hour:

UPD5 The contest was rated.

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

All statements in cf should be like Problem J

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

Why my poorly prepared solutions are not passing?

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

I want more.

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

How to solve B, even without bug? I used bitsets and got MLE. Then I wrote something ugly that reused old bitsets which got AC, was this intended?

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

    gosh, I tried different buffer-size bitset, either TLE or MLE..

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

    You can solve the problem with linear memory usage.

    If you have $$$k$$$-bit words, the time complexity is $$$\mathcal{O}(E \frac{V}{k})$$$. But we can get the same complexity by first calculating for only the first $$$k$$$ vertices which vertices can reach them, then for only the second $$$k$$$ vertices and so on. This again takes $$$\mathcal{O}(E \sum_{i = 1}^{\frac{V}{k}} \frac{k}{k}) = \mathcal{O}(E \frac{V}{k})$$$ time.

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

    You need to use long long instead of bitsets :))

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

      Is this a serious reply or just a joke? If the former, can you explain how? Also, how does it take less memory than bitsets?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 4   Vote: I like it +8 Vote: I do not like it

        Actually you can check out the editorial now. Sometimes it's hard to stop joking, but I meant what is written in the mango_lassi's comment just above.

        UPD I would say it was more like a hint than a joke, but after I posted it I just saw the comment with a solution

        → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 4   Vote: I like it 0 Vote: I do not like it

      I get TLE with Longs... probably due to overhead from recursion (cause I basically just use memoized DFS). I could only pass by using bitsets and experimentally adjusting the bitset size to use per round... my sweet spot is somewhere around $$$2^{13} \sim 2^{14}$$$ bits.

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

        It's true, solutions with recursion are too slow. The intended solution uses DP on the topological sort.

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
          ← Rev. 3   Vote: I like it 0 Vote: I do not like it

          Hm, finding the topological sort beforehand to avoid the looped recursion doesn't seem to improve the performance much to me (still TLE with 64-bit long partitions, bitset partition performance similar). Maybe it's just Kotlin things. Ah well, at least it pushed me to learn topological sort

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

    Actually we thought that this problem is very classical and all div.1 participants know how to solve it. Turns out we did a dramatic mistake.

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

What's the Djikstra bug?

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

    we used std::priority_queue with default comparator instead of std::set

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

      Another thing is that we don't consider vertices that have already been at the top of the heap — the standard trick when you write dijkstra in doubles, for example

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

      Duh, that's so random. I spent more than an hour on this problem writing some MITM to tell me which paths correspond to some different values on 5th test and have not seen any logic there and would have never thought of this.

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

    We gonna publish the editorial next year, stay tuned!

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

    You should submit a wrong solution. This contest has a new codeforces round format, where authors make buggy solutions and you have to guess all the bugs. :)

    Hope this helps, please feel free to ask.

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

Will we be able to submit after contest ended?

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

What is the bug in F?

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

    I think each if/else has been randomly swapped. I just brute-forced which swaps produce correct answers, and there was exactly one "correct" one.

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

Never thought I would ask this, but how to solve A?

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

    We mixed up n and m and < and > :((

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

      Well I got the first part, but the second could not possibly get, tried all 4 combinations of < and > and also cutting the matrix in weird parts. What do you mean mixed < and > ? Take test 3, answer is (6,3), which gives 2923880. That number is neither maximum or minimum in row or column!

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

        If you mix up m and n, you get very different rows and columns :)

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

          Tried that too, flipped it all around, neither 2839457 is maximum or minimum, 3851539 is maximum in current row but not anything in column, and 5796409 is maximum in both row and column and did not fit

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

Me writing correct A solution:Done. Me seeing that authors solution in some given test case outputs column that doesnt exist:Alright,im done with this problem, goodbye. Seriously, how authors "solution" managed to print: 1)nonexistent column in A 2)some random distance in Dijkstra(it was minimal sometimes, but my dijkstra always outputted correct minimum) in D 3)Some weird stuff in C(it looks like they created a segment tree for all cases and didnt create for each case,as was said in statements)

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

    1) swap(n, m) 2) wrong order in priority queue

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

    I think you should read the announcement once again :)

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

      I read it, I knew solutions would be wrong, but not that wrong

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

        What can I say? We tried to be wrong in the best way possible.

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

          J was the best statement ever, make statements like this always

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

Will the solutions of contestants be made public?

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

    Buggy solutions for the problems with buggy author solutions — indeed, very useful to be published :)

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

what's the E bug? Besides, the correct formula is $$$1-p^n-(1-p)^n$$$ right?

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

    We're not sure, but it seems to be called an overflow.

    Wait a bit, we will publish the solutions :) Well, we hope.

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

      But you just said "We gonna publish the editorial next year, stay tuned!"

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

        Nope, that was my colleague Kostroma.

        no jokes: We will publish them in several minutes, stay tuned.

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

        This was a punch.

        However, I don't like to give leaves without figs. The important thing is when the real editorial is published, not this currently buggy thing.

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

      Funnily enough my ModInt implementation had that overflow bug, but not quite the same one. But thanks to this contest I found a way to prevent this issue for the next time some contest somewhere decides to use $$$1234567891$$$ or even $$$2147483647$$$ (INT_MAX) as the modulus

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

Contest is finished but still, authors are writing buggy statements in the comment section.

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

I don't like such contests and guessing what authors intended, but I must say this one was well prepared and problems seem interesting.

Also, why the miniature profile pic of Kostroma has so low quality?

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

    Thanks for the kind words!

    Since the quality of the contest was not that bad, I decided to change the profile picture. Does it look better now?

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

      I don't know if you're selling hugs or protesting global warming in Winter but yeah, it looks better.

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

        I thought you know a bit Russian :) You can check out two links: one two (the second one in Russian, but the text is applicable to Google Translate)

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

          Oh, that's a serious thing, don't mind my previous comment. It was a joke about the quality of your pic again. I know the cyrrilic alphabet but can't see exact characters in your new pic...

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

In our country, there's nothing unusual about preparing contests the night before.

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

    It's cool, because we were offered to write next SEERC, no need to change our workflow.

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

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

I didn't participate, but I read the problems and the editorial afterwards. A bit of unrated riddle-like programming is certainly a breath of fresh air and a fun thing to do once or so a year. Sure, the answers may be arbitrary and biased towards users with particular experiences rather than based on knowledge, but it is after-all unrated, and meant to just blow off some steam stresslessly.

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

I tried solving question D — Dijkstra, but I've failed test 5. It seems the solution that you posted for this test case is 4764268, but if you choose a path through the vertices 1->16->11->20, the cost is 2580639, which is smaller. Did I read the question incorrectly or is this a mistake? Thanks in advance.

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

Why is problem J so long?

→ Reply