vito1036's blog

Croatian Open Competition in Informatics (COCI) 2023/2024 — Round #1
By vito1036, history, 14 months ago, In English

Hi everyone!

The 18th season of COCI is starting soon! The first round will be held this Saturday, November 4th at 13:00 UTC. You can access the judging system here. If you are not familiar with COCI contest format, we encourage you to read the announcement.

The round was prepared by ppavic, ToniB, mlicul, itiamhr and me.

Feel free to discuss the problems in the comment section after the contest ends.

Hope to see you and good luck!

Update: the round has been moved to start 1 hour earlier because of the Meta Hacker Cup.

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

Comments Comments (44)
| Write comment?
»
14 months ago, # |
  Vote: I like it +14 Vote: I do not like it

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

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

I like COCI. Excited :)

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

Will register be here: https://evaluator.hsin.hr/events/? When it will be?

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

    Yes it will be here. Idk when will it be open though

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

    It will appear on late Friday and be available until the contest starts on Saturday.

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

Why the bitset is in the tags of the blog?

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

Hello, I want to register but unfortunately I cannot see the captcha, How can I do?

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

    Maybe try different browser / different device? I really don't know, it should appear.

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

Sadly Meta Hacker Cup will start as soon as this contest is ended.

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

    We'll try to move it earlier by one hour. Perfect warm up for MHC :)

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

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

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

With the 1h moving it overlaps 40 minutes with ABC. So the best time would have been 13.50 UTC, leaving 10 looong minutes between ABC and COCI and between COCI and MHC :D I'm joking, for this only Saturday I will give up ABC in favour of COCI

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

Reminder: the contest starts in one hour.

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

Is there a $$$n*m$$$ solution for the problem C? I have tried 3 different $$$n*m*logn$$$ solutions but they did not pass :D (with RMQ, segment tree, and set)

Anyway, thanks for the nice problem setting!

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

    However, I did not understand why $$$n*m*logn$$$ did not pass in 4 seconds.

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

    Yes, our intent was to force O(n*m) solutions, but if optimized enough even O(n*m*logn) could pass.

    Hint
    → Reply
    • »
      »
      »
      14 months ago, # ^ |
      ← Rev. 2   Vote: I like it +1 Vote: I do not like it

      I strongly believed that it would pass :)

      Anyway, thanks a lot I will look into it.

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

    Problem is in too big constant factor (for set/segment tree)

    For RMQ isn't memory N^2 log N? Then it was clear why it was not working

    I solved it in O(n*m*logn) with Fenwick Tree and binary search on it (bit by bit) (finding last non-zero element in cnt[20000] aray)

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

      It seems you learned reducing constant factor after the accident lol

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

      If you use "short int" you will be fine.

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

      Here is my NMlog^2NM solution that is AC. 2d segtree is fast enough.

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

Problem E is so annoying, where can I upsolve the problems after contest?

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

    It should be available on the tasks page in the HONI category soonish.

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

    You can now upsolve the problems here.

    Go to HONI > 2023./2024. > 1. kolo, and you should be able to see all the tasks.

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

      When, you will add editorials and test cases?

      Thanks for good contest :D

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

        They will be uploaded in a day or two, probably.

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

How E?

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

    Ah yeah, I should write it today. In short, you find a dfs-tree and fix some backedge, then by careful analysis of the other backedges you can figure out if it's good or not.

    Let (u, v) be a backedge, and let u be the node closer to the root (suppose u is not the root). Then you can think of three important components, UP (part with the root), MID (part between u and v) and DOWN (children of v). The other children of u have to be connected to UP and that can be easily checked. There are two important cases:

    1. There is some component in DOWN connected to both UP and MID. Then it is enough to check whether all the components from DOWN are connected to either UP or MID.

    2. There is no such component. Then there has to be a backedge from MID to UP. And again all DOWN components are connected to either UP or MID.

    All of the checks can be preformed with segment trees. A helpful thing to precalculate is for every node, the highest and lowest backedge going out of it. It can be done either with small to large or segment trees.

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

      Great problem btw!

      I immediately thought of DFS trees, but it seemed too complicated to track the cases, so I tried using SQRT decomposition. For nodes with more than SQRT(M) degree, do DnQ over all N nodes excluding the edges coming from that node, and for nodes with less, do a DnQ over time. But it comes out to O(sqrt(M) * log(M) * (M + N)) which sadly doesn't pass all :(

      I will try to solve it with DFS trees some day... Is there some other interesting solution for it?

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

    Delete Two Vertices Again (editorial)

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

Can you share your idea in problem B and problem C,I found problem C very interesting problem,thanks for author of problems

→ Reply
  • »
    »
    14 months ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it
    Problem B
    Problem C
    → Reply
»
14 months ago, # |
  Vote: I like it +1 Vote: I do not like it

how D?

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

Can you please add the results?

→ Reply