kevinsogo's blog

By kevinsogo, history, 4 years ago, In English

Link to the mirror! (Please register at the gym)

Hello Codeforces!

I'd like to invite you to the mirror of the 2020 eliminations round of the National Olympiad in Informatics – Philippines. The mirror will be held in the Codeforces gym. The NOI.PH is the Philippines' qualifier for the IOI.

Contest format:

  • There are 17 problems over 9 days.
  • The problems will have subtasks. The maximum score for each problem will be 100 points.
  • The submission that achieves the maximum score is counted towards the final ranking.
  • The problems range from easy to challenging. Everyone from the newbie to the grandmaster will find an interesting problem in the contest.

Editorials will be released after the mirror contest ends.

Acknowledgments: The problem setters were kevinsogo, cjquines, Shisuko, andrewting, jabbawookiees, guissmo, verngutz. Thanks to Benq and ekzhang for additional help in testing. Lastly, thanks to MikeMirzayanov for Codeforces, and Polygon, which was used to prepare the problems.

Edit: Registration is now open! I've added the mirror link. Please register at the gym.

Have fun!

Edit: Thanks for joining the mirror. Congratulations to TLE for winning the mirror!

Congratulations to the top five:

Please wait for a bit until we release the official editorials and solution analyses. Meanwhile, feel free to comment here about the problems.

Edit: The editorials have been released. Click here. Enjoy!

We apologize for the delay. Anyway, once you see the document, I hope you'll understand that it took a long time to prepare given the amount of detail our editorialists usually aim for.

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

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

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

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

Why is the time limit for all problems 30.0 s ? Isn't that too loose?
For example, my naive solution can get many points 69904911

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

    Oh wow, what a misconfiguration! Thanks for pointing this out. I used the "Import from Polygon contest" button to set it up, and I didn't realize that it set all the time limits to 30sec. I have updated everything and am trying to rejudge everything now.

    I'm sorry for the inconvenience.

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

How do you solve L and H?

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

    L: use a segment tree with range operations add to a[i], add to b[i], and swap(a[i], b[i])

    H: dp[i][j][k] = using the elements 1..i, how many permutations have j pairs and have element i at position k. This will be O(n^3) if we use prefix sums.

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

      Thanks!

      For L could you elaborate a little more on what arrays a and b keep track of?

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

    For L, use a segment tree where each node stores the total sum of all open boxes, and total sum of all closed boxes. (These are the a[i] and b[i] in this comment.) Then you just have to be careful in how to propagate these updates (I had 5+ wrong submissions due to this.)

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

      Hm, I considered doing something similar but I concluded that propagation would be impossible because I would be unable to to tell if a particular flip update came before or after an add update. I guess I will think about it more. Thanks!

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

    L can also be solved using treaps.
    Use two treaps, one for open, one for closed boxes. Flip operation is just swapping two ranges in the two treaps.

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

Problem P is pretty cool, thanks!

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

    I'm glad you liked it! It's my favorite in this set too.

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

When will the editorials be released?

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

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

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

How to solve problems J and N?

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

    J: Assume all edges in a query have the same weight $$$w$$$. Then look at the components after doing kruskal for all edges with weight less than $$$w$$$(each component is compressed into 1 node). The answer is the amount of edges in the spanning forest formed by the query edges. You can find the components using a persistent array(or something similar) and merging small to large in DSU, without path compression.

    Group the edges by their weight and sum the answers for each of those groups.

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

      There's a way to do J without persistence: for every edge $$$e$$$, track its vertices's components before all edges with the same weight as $$$e$$$ were added to the DSU, since that will be the only version 'relevant' to this edge.

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

    N: Consider all cigarettes by their number subtracted by one. The condition to be touched by angel $$$i$$$ then becomes $$$A \mod 2^i>=2^{i−1}$$$ which is exactly the bit count because i becomes very large. However, we only need to consider any $$$i$$$ in range $$$[1,31]$$$.

    As the next step, we define a function that $$$F(N,k)$$$ which returns both the sum of the indices and the count of indices less than $$$N$$$ with $$$k$$$ bits set. The sum and number of indices between $$$[L,R]$$$ with $$$k$$$ bits is $$$F(R,k)−F(L−1,k)$$$. My function is a bit clunky and I'm sure there is a simpler way to accomplish it, so I won't explain the inner workings here unless someone asks. The important thing is that the function works in $$$O(\log{}N)$$$ regardless of $$$k$$$.

    Let $$$H(z, L, R)$$$ be the sum of the $$$z$$$ holiest indices within $$$[L, R]$$$. We will find $$$H(r_b, L, R)$$$ and then subtract the $$$H(r_{a−1}, L, R)$$$. Notice also that any number with a bit count of $$$x$$$ will be "holier" than a bit count of $$$x−1$$$. This suggests, that we iterate backwards from $$$31$$$ bits and keep the sum at each step.

    To find $$$H(z, L, R)$$$, iterate $$$k$$$ from $$$[31, 0]$$$. At each step, count the sum and number of indices $$$[L, R]$$$ with k bits set (use $$$F(N, k)$$$ as defined before). If the number of indices with $$$k$$$ bits set is less than or equal to $$$z$$$, decrement $$$z$$$ by the number of indices and add sum of the indices to the final value to be returned.

    However, if $$$z$$$ doesn't nicely approach 0, there is a problem. To solve it requires a final insight. Consider two indices $$$i_1 \gt i_2$$$ both with $$$k$$$ bits set. By the second condition of holy comparisons, "the last that is touched is the holiest", it can be shown that $$$i_1$$$ is always holier.

    Proof

    After the final insight, we can binary search on the lower bound of our interval in order find sum of the final indices. (Binary search for the lower bound $$$l$$$ such that the count of indices from $$$[l, R]$$$ with $$$k$$$ bits set is equal to the remaining number of indices that we need). Then add this number to the counter, and return.

    The final complexity is $$$O(T (\log{} 10^9)^2)$$$. For each query, we iterate through the 31 possible values for $$$k$$$ bits set, and at each step we take $$$O(\log{}10^9)$$$ to count both the sum and the number of indices with $$$k$$$ bits set, except for one iteration when it takes $$$O((\log{}10^9)^2)$$$ for the binary search. But since this can happen at most once, the final complexity is still $$$O((\log{} 10^9)^2)$$$ per query.

    Some care needs to be taken to minimize the constant factor (I'm not sure if it's required to pass), however the main idea there. Hopefully I was of help!

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

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