### Um_nik's blog

By Um_nik, history, 5 weeks ago, ,

Hello Codeforces!

Sadly there will be no OpenCup round this weekend, but instead I invite you to participate in a mirror of t.me/umnik_team Contest which will be held on Timus Online Judge this Sunday, 12 MSK. This contest was originally held on Petrozavodsk Summer Camp 2018 (if you participated in the camp, please do not participate in this contest). This is an up-to-3-person team contest with ICPC rules (one computer per team). Difficulty level is comparable to OpenCup rounds (not TooDifficuIt-hard, but certainly not for Div.2).

Author of most of the problems is me, with huge help from Merkurev and one problem from Kronecker.

Hope you will enjoy the contest.

• +212

 » 5 weeks ago, # |   +47 Friendly warning that one of problems from this contest appeared on Prime New Year Contest, but I guess it's not like results of some mirror of Petrozavodsk contest are very important, so I wouldn't say that this exclude anybody from participating if he just pretends this problem doesn't exist.
•  » » 5 weeks ago, # ^ |   0 Absolutely correct, thanks, I half-forgot that this problem was there, probably because it is not that hard :)
•  » » » 5 weeks ago, # ^ |   0 Which one was that?
•  » » » » 5 weeks ago, # ^ |   +10 Don't look if you didn't participate in Prime New Year Contest and going to participate in the mirror. SpoilerIt was problem 29 from Prime New Year Contest. SpoilerAnd it will be problem J in the mirror.
•  » » » » 5 weeks ago, # ^ |   +10 By this point I can assure you that you know something like half of problems from this contest, no point in you participating there :p
•  » » » » » 5 weeks ago, # ^ |   0 Really? I don't think that this contest was published anywhere, and if I remember correctly, there were no teams from Warsaw in that camp.
•  » » » » » » 5 weeks ago, # ^ |   +9 On University of Warsaw we usually use problems from Summer Petrozavodsk camps for internal competitions. In particular we used two of your problems yesterday :p
•  » » » » » » » 5 weeks ago, # ^ |   0 How do you get access to them?
•  » » » » » » » » 5 weeks ago, # ^ |   +10 By the courtesy of snark :)
•  » » » » » » » » » 5 weeks ago, # ^ |   +18 Weird stuff, this contest is not even on opentrains :)
•  » » » » » » » » » 5 weeks ago, # ^ |   +8 Being absent or being added with a two years delay on opentrains is not that uncommon ;p
•  » » » » » » » » » 5 weeks ago, # ^ |   +80 I mean, weird that you have access to the contest and it's not even on opentrains. So Snark have time to send the contest to you, but don't have time to upload it to opentrains.
•  » » » » » 5 weeks ago, # ^ |   0 Makes sense, thanks.
 » 4 weeks ago, # |   0 Is there problems pdf?
•  » » 4 weeks ago, # ^ |   0 You can see the statement by clicking on the problem.Or do you want to print it out? I can send you some version, since we changed limits in 2 problems.
 » 4 weeks ago, # |   +24 Really hard problems QAQI'm surprised so few people did G, to me it was trivial, just a lot of work. Initially my code was way too slow, then I swapped binary search in baby-step giant-step to the gnu_pbds hashmap and suddenly random instances took like 1.5s. Pretty odd, I thought that binary search could never be beaten.In C the weight of the tree is just $\sum_{i = 1}^{n} deg(i) \cdot i \cdot n - i \cdot (n-1)$ so you only need $E[deg(i)]$ for all $i$, but that seems to be pretty hard to get. Apparently sampling trees uniformly at random given degrees of nodes isn't easy, so how is counting solutions possible?How to solve D?
•  » » 4 weeks ago, # ^ | ← Rev. 3 →   +19 For D the answer is 4*a-1/3. With the power of WolframAlpha. First attempt/*input 2 */ #include typedef long double ld; using namespace std; int main() { ios_base::sync_with_stdio(false); ld a; cin >> a; ld x1 = (sqrtl(4 * a + 1) - 1); x1 *= x1; x1 /= 4; ld x2 = (sqrtl(4 * a - 3) + 1); x2 *= x2; x2 /= 4; ld x3 = (sqrtl(4 * a + 1) + 1); x3 *= x3; x3 /= 4; ld S = ((1 + 2 * a) * sqrtl(1 + 4 * a)) / 2; S += (1 - sqrtl(1 + 4 * a) + a * (-6 + sqrtl(-3 + 4 * a) - sqrtl(1 + 4 * a))) / 6; S += 2.0 * powl(x2, 1.5) / 3.0 - a * x2; S -= 2.0 * powl(x1, 1.5) / 3.0 - a * x1; S *= 2; cout << fixed << setprecision(10) << S << "\n"; } 
•  » » 4 weeks ago, # ^ |   +9 $ans=4a-\frac 1 3$ for $a \ge 2$
•  » » 4 weeks ago, # ^ |   +17 Did you get accepted on G? My solution does not involve computing discrete logarithms.
•  » » » 4 weeks ago, # ^ | ← Rev. 2 →   0 Yeah. I don't know any better way to get the size of the generated subgroup than to take $(p-1) / gcd(p-1, a_{1}, \dots, a_{k})$ where the values in the interval are $g^{a_{1}}, \dots, g^{a_{k}}$ for some generator $g$.So I used discrete logarithm to turn the input values into exponents of the generator, and multiplication into addition. Then I used the standard technique of interval GCD segment tree with addition to get the result.
•  » » » » 4 weeks ago, # ^ | ← Rev. 2 →   +16 It shouldn’t be fast enough though... at least if p is 10^12 I don’t think this approach can pass.To find order of subgroup, it’s just the lcm of all order of elements as the multiplicative group is cyclic. It’s easy to maintain if you consider ratios of consecutive elements.EDIT: I see what you mean now, the complexity is like sqrt(p(n+q)) I guess. Still, it can be done without polynomial dependence on p.
•  » » » » » 4 weeks ago, # ^ |   0 $p$ was at most $10^{9}$ in the problem
•  » » » » » 4 weeks ago, # ^ |   +24 When I came up with this problem, I didn't know that you can solve (add on segment, gcd on segment) with segment tree. Then I_love_Tanya_Romanova solved it with this approach during testing. Our implementation of this works about 6.5 seconds which was enough in original contest, but not in this version. Though I didn't try to optimize it, looks like very fast hashtable is the key.My original solution had complexity $O((n+q) (\log n + \log p) \log p$, and it works around the same time. To get lower times I did some insane optimizations, main one is this: I needed to calculate $O(\log p)$ powers of the same number in one query, and instead of doing $O(\log p)$ binary exponentiations, I did 5 or 6 layers of sqrt-decomposition-like thing, getting $O(k(\sqrt[k]{p} + \log p))$ (where $k=6$), which is 2-3 times faster.
•  » » 4 weeks ago, # ^ |   +10 You know degree for all not_-1 vertices, and all other vertices are the same, so they have equal $E[deg(v)]$. Sum of all deg is $2n-2$, so you know $E[deg(v)]$ for all $v$.
•  » » 4 weeks ago, # ^ |   0 Maybe G is hard because people like me don't know what group means in mathematics?
•  » » » 4 weeks ago, # ^ |   +24 There were the definitions, right?
•  » » » » 4 weeks ago, # ^ |   +26 I saw the sample and didn't scroll beyond. Sorry.
•  » » » » 4 weeks ago, # ^ |   +10 It's not like you are already familiar with a concept right after reading definitions.
•  » » » » » 4 weeks ago, # ^ |   0 This is true. But this problem is about the multiplicative group modulo prime number, with which participants are mostly familiar, things like existence of primitive root are known. So even if you didn't know what is group, I think you could read the definitions and understand that you are dealing with object you know.
 » 4 weeks ago, # |   +14 Help, how to solve B?
•  » » 4 weeks ago, # ^ |   +34 let $A = {a_1,a_2,\cdots,a_k}$ (sorted by dfn)$f(x)$ = the sum of the weight from root to x.$ans = f(a_1) + f(a_2) + \cdots + f(a_k) - f(lca(a_1,a_2)) - f(lca(a_2,a_3)) - \cdots - f(lca(a_k,a_1))$
 » 4 weeks ago, # |   +25 How to solve A & E?
•  » » 4 weeks ago, # ^ |   +19 A: First of all, we consider that whether a single 0 or 1 occur in the rule. Obviously, only one of 0 or 1 occur in the rule, Otherwise the answer is N or -1. Suppose there exists 0 but not 1, because it is a prefix-free system, a fact is that if W can be decoded, only if 0^k+W can be decoded. For any S, if we consider restrciting a suffix cannot be decoded, we only have to think about how to divide the prefix part. Because 0 can be decoded, and each part we devided at least contains a 1, so we can only divide into p(the number of 1s) parts. We can only create this way by connecting every 1 with the continuous 0s. Now the problem becomes finding the shortest prefix that cannot be decoded and the answer should be added by the number of 1s. We can easily find it by reversing those strings and building an AC-Automaton.Well, I think it is a quite good problem and also a nice contest. Many thanks to Umnik~PS: I actually translate this solution from my solution in Chinese written in August,2018. Maybe I miss some important details or have some mistakes.
•  » » » 4 weeks ago, # ^ |   +3 Thanks you :)
•  » » 4 weeks ago, # ^ |   +10 For E, $O(n^3)$ is obvious but got TLE. I guess some methods like FFT/NTT would be used to optimize it (since 40961 is a modulus of NTT). But I have no clue.
•  » » 4 weeks ago, # ^ |   +30 E: We need to compute $\sum((s[i] == 0) \times C(i, x)\times C(n - i - 1, y)$ for each $x, y$. Fix $y$, it turns out to use FFT/NTT.
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   +8 Sorry, I don't understand. Fix y, then how to change it to a convolution?
 » 4 weeks ago, # |   +10 Scoreboard of original contest, if anyone interested.
 » 4 weeks ago, # |   +25 How to solve I & F?
•  » » 4 weeks ago, # ^ |   +10 I`ve passed F with just bruteforce from a highest weight (but I have nothing to prove it).
•  » » » 4 weeks ago, # ^ |   +6 Hmm. I did the same thing except memorizing, so it gave TLE. I was thinking that but didn't implement.
•  » » » 4 weeks ago, # ^ | ← Rev. 3 →   +13 Notice that there are at most two transitions for each state. ($W_i \ge \sum_{j •  » » 4 weeks ago, # ^ | +16 I: Lucas's theorem. We need to compute$\sum{C(n, i)\times C(n - i, i)}$. Represent$n$as$(a_1a_2...a_k)_p$. So we concern only$i$such that its$p-base$representation$(b_1b_2...b_k)_p$,$2b_i \le a_i\$.
 » 4 weeks ago, # |   +23 J: https://core.ac.uk/download/pdf/81194617.pdf. The idea smth likes https://codeforces.com/contest/1089/problem/D reduce to smaller graph.