Um_nik's blog

By Um_nik, history, 3 years ago,

Time: Feb 7, 11:00 UTC+3

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

• +272

 » 3 years ago, # |   0 How to solve L, E, C?
•  » » 3 years ago, # ^ |   +29 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.
 » 3 years ago, # |   +8 How to solve H?
 » 3 years ago, # |   0 Auto comment: topic has been updated by Um_nik (previous revision, new revision, compare).
•  » » 3 years ago, # ^ | ← Rev. 2 →   +1 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"?
 » 3 years ago, # |   +58 Thanks for participation! Link to the editorial in the post, it should be clickable, but if it isn't, please write me.
 » 3 years ago, # |   0 How do you solve B?
 » 3 years ago, # | ← Rev. 2 →   +38 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
•  » » 3 years ago, # ^ |   +11 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.
•  » » » 3 years ago, # ^ |   +10 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.
 » 3 years ago, # |   +8 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.
•  » » 3 years ago, # ^ |   +13 I'm pretty sure you can't just solve max matching just by trying random matchings; there are graphs with few max matchings, so finding one randomly is probably impossible.I think the editorial is referring to randomized algorithms like https://github.com/kth-competitive-programming/kactl/blob/master/content/graph/GeneralMatching.h.
•  » » » 3 years ago, # ^ |   +13 I think referring to some heuristic algorithms for finding augmenting paths which don't have good time bound in non-bipartite graph.
 » 3 years ago, # |   +6 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
•  » » 3 years ago, # ^ |   +10 Or use a "better formula" (courtesy of Wikipedia):Of course, with a brute force when $k$ is small.
•  » » 3 years ago, # ^ |   +39 The issue is not in calculation of $\ln$ itself, the issue is in taking difference of them, which creates awful relative error.
•  » » » 3 years ago, # ^ |   +13 But it's good enough if you use Python and tell its Bigdecimal to have, say, 50 decimal digits of accuracy.
 » 3 years ago, # |   0 How to solve G,I,J?I don't know why so many people solve the problem G.
•  » » 3 years ago, # ^ |   0 There is a link to the editorial in the post.
•  » » » 3 years ago, # ^ |   0 Thank you.
 » 3 years ago, # |   +5 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?
•  » » 3 years ago, # ^ |   +5 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$.