ipaljak's blog

By ipaljak, history, 23 months ago, In English

Hi all,

The Central European Olympiad in Informatics (CEOI) 2022 is starting on Sunday and we'd like to invite you to participate in two online mirror contests that will feature the same problems as the two competition days.

The day 1 mirror will take place on Tuesday, July 26th, 10:00 CEST, and day 2 mirror will take place on Thursday, July 28th, 10:00 CEST. Both contests will last for 5 hours, contain 3 IOI-style problems, and have full-feedback.

In order to participate in the CEOI 2022 Online Mirror contests, you'll need an account on evaluator.hsin.hr. After logging in, you can register for the Mirror contests on the "Events" page.

Hope you'll enjoy the contests.

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

| Write comment?
»
23 months ago, # |
  Vote: I like it +35 Vote: I do not like it

Btw, evaluator.hsin.hr is amazing online judge.

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

EDIT: The starting time of the mirror was wrong. The mirror starts at 10 am local time. Sorry for the inconvenience.

Auto comment: topic has been updated by ipaljak (previous revision, new revision, compare).

»
23 months ago, # |
  Vote: I like it +37 Vote: I do not like it

Is there any way to register late for the mirror?

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

    We've increased the registration period. You can register up to 14 CEST.

»
23 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Is Abracadabra just

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

    un/fortunately yes (or maybe not lol)

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

    You can do it using only segment tree

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

      wtf how

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

        You can recover the permutation if you know the prefix maximums.

        I used a segtree,a Sparse Table and a set.

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

          Why are u using register so much?

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

            I found someone else using register when I started learing and I kept using it until now even when I know it is useless, it's hard to change.

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

          Can you explain a bit?

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

    You can do it using only BIT.

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

really liked the part of the contest where i got to implement the problems

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

Is it possible to get a full score with sqrt-decomposition in Abracadabra?

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

Was the mirror same as the real contest in terms of time limits and the judging machines? I struggled a lot with Time Limit in "P3. Prize". My time complexity is $$$O(N + (K + T) \cdot \log N)$$$ and only got 19/100 points.

Could it matter that I answered queries immediately instead of all at once? I didn't flush the output each time so it should be ok, right?

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

    Me the same. I struggled with (19/100) TLE for a really long time!!Then I accidentally changed my way of answering queries and passed!!

    I used to answer queries one by one, flushing my output every time I read a new one.

    Then I changed to reading all the queries at once and it passed. I really don't know why..

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

    I tried out locally (on prize.in.1a) your last submission that scored 19 pts, and it didn't finish under 20 seconds (then I killed it).

    Didn't analyze the code, but it doesn't look like it's due to the way you answer queries.

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

      Was it some special test? I tried chain, star, random tree — each type was below 1s locally.

      EDIT: I've just downloaded that test from the system. I get 0.15s locally, strange. Maybe there is UB, I will try to figure it out.

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

      Where can i upsolve this contest?

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

    the same happened to me in the real contest :( , it’s most probably from the way queries are answered…

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

    Yes, I am 99,9% sure that was the problem. I've spent more than 2 hours optimizing everything in my code, but still got 19/100. I started reading queries first, and only than answering. Got 100 immediately. And yeah,I didn't flush either and was sure it should be fine. Very frustrating...What's worse, there are official contestants who got 19 points on this problem. Likely those were the absolutely correct solutions, cause solving only sub task K<=200 is almost impossible(at least I think so).

»
23 months ago, # |
  Vote: I like it +8 Vote: I do not like it

When will CEOI day1 results be published?

»
23 months ago, # |
  Vote: I like it +8 Vote: I do not like it

I think B is similar to this CF problem.

»
23 months ago, # |
  Vote: I like it +49 Vote: I do not like it

I don't understand the point of such tight limits in an interactive problem.N<=2000 would have been completely fine as well.The only additional thing required for higher N is how find distance between 2 nodes in O(logn) which is well-know and doesn't serve any purpose

  • »
    »
    23 months ago, # ^ |
    Rev. 2   Vote: I like it -18 Vote: I do not like it

    The main point of large N was to differentiate between subtasks 3 and 4 (gauss vs erdos). This also influenced some of the decisions regarding time limits.

    Our solutions and all of the testers that solved the problem fit it comfortably under 3.5 seconds (2-2.5 seconds usually), and we didn't feel it would cause many problems in the contest.

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

      comfortably under 3.5 seconds

      2-2.5 seconds usually

      pick one

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

      maybe the high constraints on N and T wouldn’t have caused any problems if the interactor wasn’t so janky

»
23 months ago, # |
  Vote: I like it +67 Vote: I do not like it

How to upsolve problems?

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

Can someone explain how to solve Abracadabra and Prize?

  • »
    »
    23 months ago, # ^ |
      Vote: I like it +11 Vote: I do not like it
    Abracadabra
  • »
    »
    23 months ago, # ^ |
      Vote: I like it +23 Vote: I do not like it
    Prize
    • »
      »
      »
      23 months ago, # ^ |
        Vote: I like it +68 Vote: I do not like it

      Alternatively:

      Prize
»
23 months ago, # |
Rev. 4   Vote: I like it 0 Vote: I do not like it

Did anyone mange to get $$$O(n^2)$$$ complexity to get the $$$n=10^4$$$ subtask on A? I think calling atan2 $$$10^8$$$ times probably made it TLE. I changed it to dot product but now it WAs for some weird reason

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

I wonder whether making tests for these problems is harder than the problems themselves

»
23 months ago, # |
  Vote: I like it +8 Vote: I do not like it

Is there a way to submit? I'm still struggling with C. I found it difficult to implent, is there a good way to do it?

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

    I lost all my time trying to debug it. on the one hand I want to find the bug now and finally get ac, but on the other hand I don't want to see that problem ever again :'D

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

I have a though about Drawing, but i am not sure that isn't it is the correct solution.Because the node can adjacent to more than three other nodes in this solution.

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

    I may be found a similar solution. Firstly choose the uppermost point and set it as root. Then polar sort all of the points according to root. We'll continue with the leftmost available vertex for the first child of the root, now when we look at the process, we're again at a plane with some points and we rooted it from some convex hull point. Implementation:(dfs2 and the polar sort) Your text to link here..., I really feel like the solution is wrong btw. (Also the checker is corrupted probably, for(int i = 1; i <= n; ++i) gets AC).

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

All accepted solutions of CEOI 2022

(Warning: my solution to drawing is garbage.)

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

    Can you explain how to solve drawing?

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