Блог пользователя Errichto

Автор Errichto, 5 лет назад, По-английски

Hi.

On Wednesday at 9:05 CET / 8:05 UCT you can participate in the GYM version of the finals of 2017-2018 Russian Olympiad in Informatics (ROI), Day 1. And on Thursday there will be day 2, same time.

Links to GYM contets: day1 and day2.

5 hours, 4 problems, IOI-style scoring with subtasks. Statements will be available in three languages: English, Russian, Polish.

We wanted to use those problems in a camp in Warsaw so we had to import the problems to some system anyway. Then why not Polygon+Codeforces and thus allowing everybody to participate? Huge thanks to MikeMirzayanov for helping me with using GYM.

And credits to problem authors: Andreikkaa for Radium, Endagorion for Viruses, pashka for Innophone, Георгий Корнеев and GlebsHP for Quantum Teleportation.

Second day authors: cdkrot for Decryption, "jury" for Quick Sort, GlebsHP for Robomarathon, Endagorion for Addition without carry.

I will post a very short editorial in English here, after the contest.

Extraction of radium
Innophone
Quantum teleportation
Viruses

Second day tomorrow, same time.

Thank you for participation.

Addition without carry
Decryption
Quick sort
Robomarathon
  • Проголосовать: нравится
  • +382
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +25 Проголосовать: не нравится

Wow, thank you very much! So you had translated those problems for the camp?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +39 Проголосовать: не нравится

    I translated from Russian to English, and then a few other guys did from English to Polish.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +34 Проголосовать: не нравится

      So, do you know Russian or just used google translate? If you know Russian, it looks like you would be eligible to participate in old versions of vk cup :) (But they may change rules)

»
5 лет назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

5hours and 4problems!

How hard the problem could be...

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can I ask why it is just a gym? Why didn't you do something like Codeforces Round 545 (Div. 2), some rating round?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +30 Проголосовать: не нравится

    Probably because there are some people who already know the problems and their solutions

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +20 Проголосовать: не нравится

    The best preparation for an olympiad are problems from olympiads. Similar topics, same scoring format (subtasks). And people solve problems from CF anyway, like Junakson said.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Small mistake in Russian name of the contest

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    :D Sorry, the Russian name doesn't appear at all in the English interface of editing the contest. It's ok now. (The name was "Russian name".)

»
5 лет назад, # |
  Проголосовать: нравится +18 Проголосовать: не нравится

Day 1 starts in 10 minutes. Good luck!

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can you extend registration?

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Can we get the actual verdict?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    I can change if for tomorrow to "complete" feedback whatever that means (does it show a test for which a solution fails?). Also, maybe it would be better to show the current leaderboard? I'm not sure.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      I think the leaderboard should stay hidden. But that verdicts are really annoying — I don't know if it's TLE or WA. Anyway, it's not a strict problem.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +9 Проголосовать: не нравится

        Not showing TLE/WA on big subgroups is feature intended by problemsetters of original contest, not a bug. When you can submit without restrictions and penalties, many participants starts staring to submit a lot of different trashy hacks, instead of solving problems.

        So, showing detailed reports on small subtasks, and binary report got score/not got score on big gives you quite a lot of information (most wa's will happen on small subtasks), while not inspiring incorrect and unproven hacks like "oh, lets check first 1000 possibilities, not all".

        Side effect of this solution, is increasing cost of some kinds of errors like integer overflows or out of bounds, but we consider it reasonable. Anyway, if you are testing large timelimit, you probably should generate big test locally, and will see if it crashes or returning negative answers. If you do not, and just submitting random constants for testing — that is not behavior I want to inspire. Hardness of such tests is one more think which considered when desiding which result showing should be used.

        Everything above should be threat as my personal opinion, not a official position of Olympiad jury. But I think reasoning of others are more or less same.

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          As I said before, that's not a big deal. The only think made me to ask this question was IOI rules thing.

          And thanks for a detailed answer. I agree with your opinions.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Not showing proper verdict costed me not-getting-a-AC.

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +28 Проголосовать: не нравится

        Someone can also say "not showing the editorial before a contest costed be not-getting-AC" ;p

        But yeah, it's better to show the verdict if IOI does it.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I solved B with $$$O(N \sqrt{N})$$$ Time, but it turns out to be not enough for getting 100 pts (I submitted with various constants, but 84 was maximum)..

»
5 лет назад, # |
Rev. 4   Проголосовать: нравится +8 Проголосовать: не нравится

In the problems 3, how can we prove that it is always optimal to jump to some nodes(i,j) from the node(x,y) that satisfied x<=i and y<=j, which means we don't have to concern about jumping to a node (i,j) where either i<x or j<y (or both) is satisfied. This claim is intuitively correct, but I couldn't get the exact proof.

By the way, thank you for preparing such a nice problem set.

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It isn't true. You must consider all four directions (plus going to the next/previous cell in the same row/column). The lemma is: if you go from $$$(i, j)$$$ to $$$(i2, j2)$$$ such that $$$i < i2$$$ and $$$j < j2$$$, then it's enough to consider going to the closest such $$$(i2, j2)$$$ (to one of those tied at the minimum distance).

    Yeah, problems are nice. Kudos to the organizers of ROI. I will list them tomorrow in the blog, when I have time.

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      If we have multiple processors having the same minimum distant from the current processor, do we only need to link to any one of them, or we have to consider all?

      • »
        »
        »
        »
        5 лет назад, # ^ |
          Проголосовать: нравится +6 Проголосовать: не нравится

        All. Have you read the editorial in the blog?

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

          Yes, but I am kind of confused about the detail of the L-shape thing. Could you please explain a bit more?

          My questions:

          1. why is it an L-shape? for finding these processors have the same shortest distant I think it should be a diagonal or so.

          2. what do we store and how do we find the vertices in L-shape?

          Thanks a lot!

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            There is a drawing in the editorial. Each cell in the L-shape has the same distance to the current cell $$$(i, j)$$$.

            If you want to find cells in such a shape, you can use sets of positions for each row and for each column. Or just iterate linearly over all $$$k$$$ cells and check which are in the shape.

            • »
              »
              »
              »
              »
              »
              »
              5 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

              Oh I see, I made a mistake.

              I transferred Chebyshev distance to Manhattan Distance, And all I am thinking is with Manhattan Distance. Sorry for that.

              Got it, thanks!

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      Oh, I see! I apologize for my misunderstanding.
      Btw this greedy is very genius and amazing...(easy to understand but super difficult to come up with during the contest)

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Problem B is quite similar to 436F

»
5 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Day 2 starts in 10 minutes. This time with complete feedback.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Will the standings of Day 2 be available?

»
5 лет назад, # |
  Проголосовать: нравится +20 Проголосовать: не нравится

When will the tutorial for second day be published?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    Three of the four problems are done. Robomarathon coming soon. Sorry for the delay.

    • »
      »
      »
      5 лет назад, # ^ |
      Rev. 2   Проголосовать: нравится +13 Проголосовать: не нравится

      Just as a reminder if you have forgotten to add it, but I would like to see the solution to the problem "Robomarathon". I don't intend to hurry you, but I would be grateful if you add some brief editorial about this.

      • »
        »
        »
        »
        5 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится +11 Проголосовать: не нравится

        Or does anyone know the solution? It seems it was a bit relatively easy one in this problem set, but I haven't got to the right answer even though it has passed 3 weeks after the contest ended. I've been distressed by this problem from morning till night for more than a half the month (note: contains some exaggerations). I guess many participants have already forgotten how to solve this problem, but would anyone help me get out of this restive circumstance?

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +20 Проголосовать: не нравится

          For minimum place, only one start neer this robot should be used. For maximum — either everything with distance not less than closest endpoint (1 or n), or only other endpoint (could be proven by removing closest or adding furthest on other cases).

          After that number of persons before us is some sets on (i, a_i) plane, number of points in which can be found using several sweeping lines.

          Also, timelimit in this problem is quite tigh, so good constant is required for 100-point solution. Any nlogn should score 70+.

        • »
          »
          »
          »
          »
          5 лет назад, # ^ |
            Проголосовать: нравится +22 Проголосовать: не нравится

          I've just written a full editorial. Sorry for the delay.

          It's bizarre that Pavel answered while I was writing it. After two months of you waiting...

          Sorry again.

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            Thanks for all who taught me the solution! I really appreciate it.

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            I mentioned post in top (probably, because of your edits), and answered for unseen post. Even didn't saw it was 2 months ago :)

»
5 лет назад, # |
Rev. 4   Проголосовать: нравится -10 Проголосовать: не нравится

Can someone please tell me why this approach doesn't work for B — Decryption of ROI Day 2: Start from the first element in the sequence not already put in a segment, create a new segment and put every subsequent element such that it's larger or equal to the first element in this segment, and the maximum of all of the remaining numbers is greater or equal to the current maximum element.

Here's my code:

I'm really curious why this gives WA, because at first glance it looks like it's optimal.

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Hi Errichto, thank you for the great problem set!

It seems that subtasks in Day1 P4 are not well configured. My full solution with assert(n <= 50) gets only 33 points. Could you please check this?

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +10 Проголосовать: не нравится

    You should thank the original organizers, obviously :D

    Everything is ok with subtasks. Notice the dependencies. Subtask 4 requires subtask 2 to be solved so you need to solve $$$p = 1$$$ for all $$$n$$$ first. This is indeed quite strange but I've just checked in the original Russian statement that it should be like that.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

for the question Viruses, any idea why this passes. It seems to me like clear $$$n^4$$$