mkisic's blog

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

Hi everyone!

Sixth round of COCI will be held today Saturday, March 13th 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, dpaleka, pavkal5, bukefala, stjepanp and me.

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

Hope to see you later today!

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

»
3 years ago, # |
  Vote: I like it +21 Vote: I do not like it

Is there is solution for E, faster than the Mo and fenwick?

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

    Parallel Binary Search

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

    I used persistent segment tree to solve it in $$$O((n + q)\log{MAXP})$$$.

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

      Can you please explain your solution?

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

        Sure, first build the pst over the frequency of the values and store the root of each version.

        After that, we want to know the maximum $$$k$$$ such that there are at least $$$k$$$ values greater than or equal to $$$k$$$ in the range of positions $$$[l, r]$$$.

        Then, we can make a traversal over the persistent segment tree considering the representative node of the first $$$l - 1$$$ values (let it be $$$last$$$) and the representative node of the first $$$r$$$ values (let it be $$$pos$$$).

        Now, the number of elements with value in range $$$[L, R]$$$ and in position range $$$[l, r]$$$ is $$$st[pos] - st[last]$$$ for the associated nodes $$$pos$$$ and $$$last$$$. This will help us to notice that we can use that information without an extra binary search.

        There are two possibilities, given that we have an extra value called $$$add$$$ that stores the number of elements greater than $$$R$$$ in position range $$$[l, r]$$$. Denote $$$mi = \lfloor\frac{L + R}{2}\rfloor$$$:

        1) $$$st[right(pos)] - st[right(last)] + add \leq mi$$$: This means that the number of elements greater than or equal to $$$mi + 1$$$ is less than $$$mi + 1$$$, which means that none of the values in range $$$[mi + 1, R]$$$ is a possible answer. Then, we must go to the left child and update $$$add = st[right(pos)] - st[right(last)] + add$$$.

        2) Otherwise, we can use $$$mi + 1$$$ as a valid $$$k$$$, which means that the maximum one is in the range $$$[mi + 1, R]$$$.

        It will be something like this:

        int query(int last, int pos, int L, int R, int add = 0){
   if(L == R) return L;
   int mi = (L + R) / 2;
   int greater_than_mi = st[right(pos)] - st[right(last)] + add;
   if(greater_than_mi <= mi){
      return query(left(last), left(pos), L, mi, greater_than_mi);
   }
   else{
      return query(right(last), right(pos), mi + 1, R, add);
   }
}

        Thus, it's just $$$O(\log{MAXP})$$$ per query.

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

Short summaries of my solutions to the harder problems:

Anagramistica
Geometrija
Index
→ Reply
»
3 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Solutions are published here.

→ Reply