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 jqdai0815-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.
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.
Absolutely correct, thanks, I half-forgot that this problem was there, probably because it is not that hard :)
Which one was that?
Don't look if you didn't participate in Prime New Year Contest and going to participate in the mirror.
It was problem 29 from Prime New Year Contest.
And it will be problem J in the mirror.
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
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.
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
How do you get access to them?
By the courtesy of snark :)
Weird stuff, this contest is not even on opentrains :)
Being absent or being added with a two years delay on opentrains is not that uncommon ;p
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.
Makes sense, thanks.
Is there problems pdf?
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.
Really hard problems QAQ
I'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?
For D the answer is 4*a-1/3. With the power of WolframAlpha.
$$$ans=4a-\frac 1 3$$$ for $$$a \ge 2$$$
Did you get accepted on G? My solution does not involve computing discrete logarithms.
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.
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.
$$$p$$$ was at most $$$10^{9}$$$ in the problem
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.
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$$$.
Maybe G is hard because people like me don't know what group means in mathematics?
There were the definitions, right?
I saw the sample and didn't scroll beyond. Sorry.
It's not like you are already familiar with a concept right after reading definitions.
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.
Help, how to solve B?
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))$$$
How to prove it ?
How to solve A & E?
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.
Thanks you :)
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.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.
Sorry, I don't understand. Fix y, then how to change it to a convolution?
Could you be so kind and elaborate a bit more on how to reduce this sum to convolution? I tried to calculate $$$f(l, r)$$$ — the number of subsequences of length $$$l + r + 1$$$ with $$$(l + 1)$$$'th element being $$$0$$$. I.e. I tried to preprocess some sums and the answer for length $$$k$$$ would be calculating $$$a_l = f(l - 1, k - l)$$$ and outputting $$$\sum_{i=1}^k a_i \cdot (C(n, k) - a_i)$$$. I computed $$$f$$$ using divide and conquer and NTT that is in $$$\mathcal{O}(N^2 \log^2 n)$$$ which is too slow. Could you hint further how can one achieve $$$\mathcal{O}(N^2 \log n)$$$ if that is the intended complexity?
Good afternoon, could you please send the solution to problem 2122 with acm.timus.ru I would be very grateful to you https://acm.timus.ru/problem.aspx?space=1&num=2122&locale=en
Scoreboard of original contest, if anyone interested.
How to solve I & F?
I`ve passed F with just bruteforce from a highest weight (but I have nothing to prove it).
Hmm. I did the same thing except memorizing, so it gave TLE. I was thinking that but didn't implement.
Notice that there are at most two transitions for each state. ($$$W_i \ge \sum_{j<i} W_j$$$) And another upper bound is $$$w_i$$$.
The time complexity is $$$O\left(\sum_{i=1}^{n} \min (2^{n-i},w / 2^{n-i})\right)= O(\sqrt w)$$$.
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$$$.
J: https://core.ac.uk/download/pdf/81194617.pdf. The idea smth likes https://codeforces.net/contest/1089/problem/D reduce to smaller graph.
How to solve H without obvious $$$\mathcal{O}(n \log^2 n)$$$ interpolation followed by $$$\mathcal{O}(m \log^2 m)$$$ evaluation (which is too slow)?