paula's blog

By paula, history, 4 years ago, In English

Hi everyone!

The third round of COCI will be held tomorrow, December 12th 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 Gabrijel, mkisic, pavkal5, dpaleka and me.

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

Hope to see you tomorrow!

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

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

What is the difficulty of problems in COCI?

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

    There's one easy problem and another somewhat easy (algorithmic) problem. The rest are split into multiple subtasks and range from medium to very hard. A nice and really high quality problemset in my opinion, but 4/5 problems is pretty tough for most people to hit, even Masters/Grandmasters.

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

Reminder: the contest starts in less than one hour.

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

Problem Selotejp is direct copy of 1404E - Bricks.

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

    Sorry, we were not aware of this problem. We know that problem is very general and that probably was already on some contest but still we thought that it is quality bitmask dp for Croatian version of competition.

»
4 years ago, # |
Rev. 2   Vote: I like it +8 Vote: I do not like it

Will the problems be available for upsolving?

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

My solutions

Knijge
Vlak
Sateliti
Selotejp
Specijacija
  • »
    »
    4 years ago, # ^ |
    Rev. 3   Vote: I like it +17 Vote: I do not like it

    I overcomplicated problem C. I tried all possible rotation of columns, construct an ordering of row suffixes incrementally (like how we actually implement suffix arrays), and then computed the optimal row rotation which involves real suffix arrays. Then we have $$$M$$$ candidates of length-$$$NM$$$ binary strings to compare. I maintained these carefully with bitset and compared them with _Find_first(), so my code doesn't compile on my machine. Didn't bothered to think too much, since I solved the problems in reverse orders and had plenty of time to do anything.

    D is the second time copy-pasting BOJ 13444 :) Not much to say, but I really loved figuring it out back then. It's quite standard if solved with bitmasks, though.

    I think I have a different motifs for E, and I quite liked the problem. Instead of compressing the tree I have flattened the tree to $$$(N+1) \times (N+1)$$$ square grid. Last row contains numbers $$$1, 2, \ldots, N + 1$$$ denoting the index of nodes it belongs in depth $$$i$$$ (minus $$$i(i-1)/2$$$ or whatsoever). You can observe that the difference of $$$i-1$$$-th row and $$$i$$$-th row is simply an addition to a suffix. Fenwick trees are sufficient to determine what it is.

    Now the problem boils down to:

    • Finding a mapping between nodes in a tree and a cell in a grid
    • Finding a first row $$$r$$$ such that two cell $$$(r, x)$$$ and $$$(r, y)$$$ have same values

    The mapping can be described as follows. Define $$$pos[i]$$$ as a starting position of suffix for row $$$i$$$. Then a mapping for a row $$$r$$$ can be defined as a $$$k$$$-th smallest element, or counting numbers $$$\le c$$$ in a set $$$[pos[0], pos[1], \ldots, pos[r]]$$$. You can use persistent segment trees here.

    To find the first row, notice that two cells in same row have same values iff no suffix additions were done in between. It's a range minimum query over a reverse permutation of $$$pos$$$.

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

      I don't quite follow how your square grid is defined — you've said what to put into the last row but not the other rows. I have a feeling it might be quite closely related to my persistent segment tree but I'm not sure. Maybe you can show what it contains for the first sample case?

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

        Thanks for the comment. I've updated the reply to better illustrate the concept.

        For the sample case:

        [1 1 1 1]
        1 1 [2 2]
        1 [2 3 3]
        1 2 3 [4]
        

        Brackets indicate the range updates. The first range update is not needed, but I used it to simplify the implementation.

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

          Ok, a row in your grid corresponds to a prefix sum of the leaves in my segment tree.

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

    Another way in which you could improve the last problem's complexity to $$$O(n$$$ $$$log$$$ $$$n)$$$ is by noticing that you can find the depth of the LCA of the $$$u$$$-th and $$$v$$$-th node in the bottom row by finding when do all numbers in your presistent segment tree between $$$u+1$$$ and $$$v$$$ become 0. That can easily be solved by remembering when did each element become 0 and using RMQ.

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

The editorial is published: link

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

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