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

Автор mkisic, история, 4 года назад, По-английски

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!

  • Проголосовать: нравится
  • +47
  • Проголосовать: не нравится

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

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

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

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

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

Is there any online mirror?

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

Is it possible to add a gym contest on Codeforces?

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

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? :(

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

    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.

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

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

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

    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.

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

      Did you use any other structure like ordered_set?

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

        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.

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

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

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

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

    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.

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

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)

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

    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.

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

    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.

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

      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 ;)

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

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

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

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:)

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

    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?

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

Where can I upsolve this contest?

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

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