mkisic's blog

Croatian Open Competition in Informatics (COCI) 2020/2021 — Round #4
By mkisic, history, 4 years ago, In English

Hi everyone!

Forth round of COCI will be held this Saturday, January 16th at 14: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 paula, Shtef, dpaleka, pavkal5 and me.

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

Hope to see you on Saturday!

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

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

Can you add these rounds in kattis for upsolving/practicing? I see some COCI rounds are there, some not.

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

Can it be postponed by 10-15 minutes so that there is some gap between arc and coci.

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

Is there any online mirror?

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

Is it possible to add a gym contest on Codeforces?

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

    We were going to add a "COCI season icpc-style contest" to the gym sometime. I think oj.uz has separate contests usually.

    → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it +11 Vote: I do not like it

Is it just me or was this round tougher than usual? An interesting experience still, but I feel like first problem was way too easy as compared to the others.

And why wasn't there a story behind second problem? :(

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

    Yeah, I take responsibility for the lack of storytelling in this round. But I think the story for Patkice compensates for Vepar and Hop.

    The second problem on COCI is usually intended as an educational one in the Croatian version of the contest, so we may keep the stories shorter there.

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

How to solve D? I wrote centroid decomposition with fenwick tree of ordered_set, but this got TL and only 15 points...

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

    It's centroid decomposition. In each subtree count number of pair $$$(v, u)$$$ such that $$$max(high(v), high(u)) - k\ge depth(v) + depth(u)$$$, where $$$high(v)$$$ is the maximum edge from root to $$$v$$$ and $$$depth(v)$$$ is the depth of $$$v$$$. This can be calculated using fenwick tree only.

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

      Did you use any other structure like ordered_set?

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

        No, you can just sort all the nodes by $$$high(v)$$$ increasingly. And enumerate the one as larger $$$high(v)$$$. And this reduces to finding numbers of $$$u$$$ such that $$$high(v) - k - depth(v)\ge depth(u)$$$, which is sufficient to just use fenwick tree.

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

Are the results to be released? Also how to solve p3 Hop?

The rest of the full point sols are on my github: link.

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

    Let $$$B_i = \lfloor \log_2 A_i \rfloor$$$. If there is an edge between $$$x, y$$$, then $$$B_x < B_y$$$. And $$$0 \le B_i \le 59$$$.

    Now take a length-3 base-4 representation of $$$B_i$$$. For all $$$i, j$$$, print the first position where two length-3 numbers differ.

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

      Do you know of problems with a similar trick? I vaguely remember seeing similar stuff before but cannot pinpoint where.

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

Damn I'm rusty. Didn't participate in any contests for quite some time, but I thought COCI was usually on easier side :P

Anyway, was a Dijkstra on 16 million vertices not supposed to pass in the last task? I got time limit, and because the tests are grouped very unpleasantly, I got nothing for the whole 80 points subtask :P Not a fan of grouping tests that aggresively. (Unless my program just hangs on that test or something :P)

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

    mkisic's implementation with Dijkstra runs in 1s (out of 2s TL), but the intended solution is the asymptotically faster 0-1 BFS, if I'm not mistaken.

    The grouping of the tests into clusters is what IOI does, and COCI is primarly intended as a training contest for Croatian high school competitors. Although, I guess we could work on making clusters more granular.

    Digression: we encourage feedback like this, all contestants (both on COCI and the Croatian version) who have feedback on the problems, the best place is these Codeforces threads for COCI.

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

    There were only 4 million vertices though, right? What I did, and I assume it's the intended solution, was 0-1 BFS which probably makes a significant difference.

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

      This was my implementation of 0-1 BFS

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

      Okay, my solution was that the graph's vertices are of the form: (row, column, direction) and it means the shortest path from the start to a given field, assuming we change the arrow on that field to point into a given direction. The cost is 1 when the field you're about to enter has a different arrow than the one we're about to set. ... but yeah now that you mention it, I can see that this third dimension isn't strictly needed, if we assume we modify the arrow from the field we're departing from, instead of the one we're arriving at.

      ... and yeah, I did remember you could get away with a special BFS in this case, but I didn't assume organizers would be that mean ;)

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

Solutions are posted: https://hsin.hr/coci/

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

Hello! I am reading editorial for task B and in Necessary skills I noticed Vp. What is it and where i can find related sources to understand Vp? Please help me:)

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

    Sorry, I should have elaborated a bit more, but writing is hard...

    The notation $$$v_p(x)$$$ denotes the "largest power of $$$p$$$ that divides $$$x$$$". For example, $$$v_2(8) = 3, v_5(100) = 2, v_3(7) = 0$$$. You may have seen the Fundamental Theorem of Arithmetic in this form: $$$n = \prod_{p} p^{v_p(n)}.$$$

    This $$$v_p$$$ comes up in problems that ask for divisibility, because if $$$y$$$ is a multiple of $$$x$$$, then $$$v_p(y) \ge v_p(x)$$$.

    In this task, we use https://en.wikipedia.org/wiki/Legendre%27s_formula to calculate $$$v_p$$$ of an interval -- although you could probably come up with the formula by yourself, the proof is a single line.

    Can anyone well versed in Codeforces problems give an example where a similar approach is used?

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

Where can I upsolve this contest?

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

You can solve all problems here: https://oj.uz/problems/source/540

→ Reply