KALARRY's blog

TEST CASES BOI 2023
By KALARRY, history, 13 months ago, In English

Hello everyone, I participated in BOI 2023 and I am very disappointed about the competition. In day one's first problem(Car Race) some N*log(N)*log(N) solutions with small memory optimizations passed for 100%, while others got only 58% despite the fact that N could reach 10^6. The second task of day 1(Weights) had a subtask for O(Q*depth) with depth smaller than 30 that was supposed to get someone 24 points (for the other subtasks a faster solution was needed and someone had to adjust the way he stored numbers as they could reach values up to 2^depth which could turn out to be really large). However, naive solutions for ONLY the third subtask with __int128 could earn 91 points. Moreover, many solutions for the problem passed the last subtask(the no further constraints one) but they lost points from the first one. How is this even possible? Last but not least, in the last task of day 2 (Aliens), O(N^2) solutions that required N^2 memory passed K=1 and N <= 10^5. How were all these problems not prevented from the Scientific Committee and from those who tested the problems? Were the testcases never checked and solutions for subtask never tested? All these problems are the ones that make students refrain from participating in Olympiads and I hope that Problem Seters will be more careful in the future.

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

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

I am the author of Car Race and Super tree. Ask me anything.

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

    When will you publish the tasks, together with the test cases and the solutions?

    I know you're not the only one responsible for this, but maybe you have an answer to this question.

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
        Vote: I like it +14 Vote: I do not like it

      Hi, I personally have plans on hosting the mirror on eolymp in the following days. After the mirror I think everything will be published

      → Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it -7 Vote: I do not like it

    Why

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

      I tried to do my best with these problems...

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

    What is the model solution for Car Race?

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

      Initially, model solution for Car Race was small-to-large in O(Nlog^2N). However, I saw that this problem could be solved in linear time. I used an idea of compressing the tree.

      1. Let's look at vertexes on the same depth, obviously other cars will not bother us
      2. Let's consider these vertexes important. Any other vertex could be important if it has more than one important son.
      3. It could be seen, that we do not really need non-important vertexes — let's remove them.
      4. Let's run the dfs simulation of the game. How many vertexes would it travers? Let $$$|D_i|$$$ be the number of the vertexes on the level $$$i$$$. Thus, we can say that on the next level there are at most $$$\frac{|D_i|}{2}$$$ vertexes. Thus, we can upper bound the number of vertexes we traverse by $$$|D_i| + \frac{|D_i|}{2} + \frac{|D_i|}{4} + ... = 2 \cdot |D_i|$$$.

      As we can see, this is linear time from the number of vertexes. Thus, the total time complexity would be $$$\mathcal{O}(N)$$$, to be more precise it is somewhat $$$3 \cdot N$$$.

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

Hello. The Nlog^2 solution you described is not Nlog^2, but Nlog if you would calculate complexity correctly. Maybe this should relieve some of the pain :)

→ Reply
  • »
    »
    13 months ago, # ^ |
      Vote: I like it +7 Vote: I do not like it

    Yes, I thought the same when I could not find a countertest for the small-to-large solution some days before the contets. I found out that here the size of the set in the subtree depends not on the size, but on the depth. I am not really sure how to calculate this complexity now, but I am sure that it is much less than $$$\mathcal{O}(N\log^2)$$$. Thus, the only thing I could do is find the test where it gives ML...

    Although, I would agree that there were some dependencies problems during the contest as the last subtask passed and pre-last did not. I had a talk with organisers some days before the contest and got informed that it is impossible to set dependencies on cms. Thus, I saw no other way than adding similar tests to different subtasks, but it would significantly slow down the system during the contest, as it would have to test more tests for a single submission.

    → Reply
    • »
      »
      »
      13 months ago, # ^ |
      ← Rev. 2   Vote: I like it +23 Vote: I do not like it
      Brief appendix on the complexity of small to large when dealing with depths
      → Reply
    • »
      »
      »
      12 months ago, # ^ |
      ← Rev. 4   Vote: I like it +23 Vote: I do not like it

      Don't know the exact version of CMS that's been used during the Olympiad, but in general CMS supports sort of subtask dependency. It is possible to include same test in any subtask using regex in the scoring section based on the codenames of the tests. You don't need to create the same test several times. But I'm not sure whether Now I am pretty sure it runs a particular test only once if it's included in many subtasks this way. Just checked the evaluation of one such task.

      → Reply
»
13 months ago, # |
  Vote: I like it 0 Vote: I do not like it

I really wonder, why O(NKlogN) doesnt pass bitsize<20 subtask on super trees, I mean isnt it only 4e8 operations?

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

    It is ok if to look on TL, but I think it would give ML, as you support K Segment Trees and each of them has Nodes -> NK memory, which could be a bit too much.

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

      I am sorry, just checked — I have a solution O(NKlog) that passes 6th subtask (bitsize < 20).

      → Reply
      • »
        »
        »
        »
        13 months ago, # ^ |
          Vote: I like it +3 Vote: I do not like it

        Thats little weird then, idk what would be the case for this kind of situtation in olympiads. It would be unfair to other participants to their solutions to be rejudged, idk maybe just unlucky day. But it would be a little better if they give me gold, since I had only 6 points difference on front but 30 on behind. Little unfair contest, I can say maybe,also there were 4 seg tree tasks...

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

          Full solution for super-tree does not require any data structures except of vectors and arrays.

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

            Oh my wrong, but shouldn't I get points on subtask 6? (I didnt, I have only 34)

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

              I think all results should be final after the contest end. If you did not get score for some subtasks it is just your poor implementation skills. That is the sad truth. I had the same experience after CEOI 2023.

              If you think that this is a mistake of the judge — you can somehow appeal the decision of the judge... (never had such an experience)

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

            Also what was the intended, I still dont know, thanks.

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

              Intended solution:

              1. Calculate the array $$$f$$$.
              2. Calculate power and superpower
              3. For each update start a dfs in the vertex $$$v$$$. If you did not update the value in this vertex — do not update the remaining subtree. Otherwise, update value $$$f$$$ in the vertex, update power and superpower and run dfs into sons.

              This works in O(NlogA) and has about 60 lines of code.

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

                Oh, really.....

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

                  If you are interested, I could tell a little story.

                  When I just came up with this statement I came up with segment tree beats solution. I implemented it. That was 350 line cancer that worked in O(NlogAlogN), but it worked. Then I faced a question — can I do it faster? Can I get rid of that logN? At that time I understood that I do not really need segment tree and I could easily access the node instead of accessing it after going down in a seg tree. After that, I increased A to 2^60 and N to 1e6.

                  That is the story.

                  → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 months ago, # ^ |
                    Vote: I like it +6 Vote: I do not like it

                  I think 2^60 was unnecessary.

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

                I had a similar solution used same number of operations with euler tour and DSU's. I was pretty sure that this idea would be faster in practice so I didn't even bother to try your solution, but that idea failed miserably. We had a sweet debate with a guy behind through clarifications on how mean the TLE is, although they were pretty insistent on saying it was irrelevant to the problem. I'm pretty sure my code would pass with +0.5 TLE. Sad thing is, I think same applies for problem C too.

                → Reply
                • »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  »
                  13 months ago, # ^ |
                  ← Rev. 3   Vote: I like it +11 Vote: I do not like it

                  I thinked that organizers would've noticed it with the number of clarifications I've sent, but amount of indifference they've shown to the minuscule amount of swearing I did through my 60 submissions shows that they probably didn't even examined my codes.

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

                That's quite nice. I was wondering how to find the numbers to update in O(1) because first thing I did was Euler tour to make tree into an array. Then I did segment tree beats.

                Your solution is much nicer and easier to implement.

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

    Fun fact: during the competition I coded an $$$O(N\ logA\ logN)$$$ solution that got me 100 points (I believe due to weak testcases)

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

      Oh... I heard that if you submit to some problems in the first 1 hour, it gets -1 second in time LOL. Also if your country is Turkey you get auto +1 second in Supertrees ajsdahsdjksfldsjdklfgfksjl and if your name is Cengiz you get auto +37 seconds in every problem. (I passed NKlog^2N in C, and he got TLE with Nlog^2N.)

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

Well, there are some mistakes and weak test cases but we can’t hide the fact that in general it was an amazing olympiad and we gained a lot from it, hopefully year by year it will get better.

As a participant I really enjoyed trying to solve the problems and meeting with other students that are interested in informatics.

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

    Tbh looking at all onsite olympiads I've been at (including IOI2023) this year's BOI seems the best one, i absolutely loved and enjoyed the event, not as much as the tasks though

    P.s. task were actually pretty decent, it's just my personal skill issue :D

    → Reply