Um_nik's blog

XXI OpenCup GP of Nizhny Novgorod
By Um_nik, history, 3 years ago, In English

Time: Feb 7, 11:00 UTC+3

Link: Click (OpenCup login needed to participate)

Authors: Um_nik, Merkurev, KAN, WYOCMWYH with help from ashmelev, Ferume, fake123 and dario2994.

The contest was used for Petrozavodsk training camp and ICPC training camp.

Editorial

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

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

How to solve L, E, C?

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

    C: The answer is $$$\phi(n) \cdot \binom{n-1}{k-1}$$$, which you can compute in $$$O(k)$$$ time (note that $$$k \le \frac{n}{4}$$$ so it's barely fast enough.

    E: Compute a maximum matching (of size $$$M$$$) using Edmond's Blossom Algorithm. Basically, you can reduce the problem of whether there is a vertex cover of size $$$M$$$ to 2-SAT (because the vertex cover must contain at least one vertex per edge in the matching), which you can solve in $$$O(m+n)$$$ time. For the case $$$M+1$$$, try all extra unmatched vertex to take into the vertex cover as well as all edges in the matching where both endpoints are taken.

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

How to solve H?

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

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

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

    The contest is still running for Div.2 :) As it was postponed 3 times, and then started, but without problems(!), and so later it restarted again :)

    UPD. It's just finished. How to solve Div.2 Problem H. "Ending by 3"?

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

Thanks for participation! Link to the editorial in the post, it should be clickable, but if it isn't, please write me.

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

How do you solve B?

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

I'm not sure if it's intended, but problem I can also be solved using the observation that to get minimum cost to buy $$$i$$$ souvenirs it always makes sense to keep all the $$$i - 1$$$ souvenirs from before, and buy one extra ( not necessarily at time $$$i$$$ ). So, one can solve it by iteratively picking the next cheapest souvenir and updating the costs. Fast simulation of this procedure can be done with sqrt decomposition and CHT. Complexity is $$$O(N \sqrt{N})$$$. Code

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

    If that holds, then you can also solve the problem in $$$\mathcal{O}(n C^{1/3})$$$ without assuming that all $$$p_i$$$ are distinct, by grouping items with equal $$$p_i$$$, and noticing that if we have a group of elements with equal $$$p_i$$$, and in the optimal solution to $$$dp[i][k]$$$ we take $$$m$$$ of them, then in $$$dp[i][k+1]$$$ we take $$$m$$$ or $$$m+1$$$ of them.

    I didn't notice that all $$$p_i$$$ are distinct during the contest, so this was what I did. I don't know how to prove that that observation holds, though.

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

      You can prove the observation by considering this as a min-cost matching problem. The addition of one new "slot" can only add one new augmenting path, which must consist of taking one new souvenir and shuffling some others around.

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

What could be any unproven algorithm of your choice in problem E? Before, I usually used "many times take any unmatched vertex and match it with the random neighbor", but it let me down this time.

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

In fact, L can be solved much simpler in Python. Extended Stirling formula $$$\ln(n!) = \frac12\ln(2\pi) + (n + \frac12)\ln{n} - n + \frac1{12n} + O(n^{-2})$$$ works like a charm even for $$$n = 10^4$$$, as the coefficient in $$$O(n^{-2})$$$ is really small (I believe it is something like $$$\frac{1}{144}$$$). The only problem is that we can't calculate $$$\ln$$$ precise enough in C++, so we need to use Bigdecimal type

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

    Or use a "better formula" (courtesy of Wikipedia):

    Of course, with a brute force when $$$k$$$ is small.

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

    The issue is not in calculation of $$$\ln$$$ itself, the issue is in taking difference of them, which creates awful relative error.

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

      But it's good enough if you use Python and tell its Bigdecimal to have, say, 50 decimal digits of accuracy.

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

How to solve G,I,J?I don't know why so many people solve the problem G.

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

The editorial for problem L says that while multiplying by the factor $$$\frac{2(R+1)}{B+R+1}$$$ "If we skip first $$$\sqrt{B}$$$ operations, each next $$$\sqrt{B}$$$ operations will multiple the answer by at least 2". Why does this condition holds?

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

    Each multiplier is at least $$$(1 + \frac{1}{\sqrt{B}})$$$, there are $$$\sqrt{B}$$$ of them, $$$(1 + \frac{1}{k})^{k} \ge 2$$$ for any $$$k \ge 1$$$.

    → Reply