### skywalkert's blog

By skywalkert, history, 3 years ago,

This editorial corresponds to 2017 Chinese Multi-University Training, BeihangU Contest (stage 1), which was held on Jun 25th, 2017.

There are 12 problems in total. You can solve them as a team member or an individual in a 5-hour contest. By the time you join as virtual participants, 770 teams, or even more, will compete with you virtually.

Editorial in the English version has been completed, which is a bit different from its Chinese version (mostly because I don't want bad editorials to ruin the contest, lol). However, for the sake of hiding spoilers, editorials are locked and will be shown as the following conditions are met:

• Editorials for the easiest 4 problems will be revealed after the replay (all unlocked);
• Each for the hardest 5 will be released if the corresponding problem has been solved by at least 5 users or teams on Codeforces::Gym (all unlocked);
• Each for the others will be published when the relevant problem has been solved by at least 10 users or teams in virtual participation (including the replay) on Codeforces::Gym (all unlocked).

Or you can find solutions in comments?

Idea: skywalkert

solution

102253B - Balala Power!

Idea: sd0061

solution

102253C - Colorful Tree

Idea: sd0061

solution

102253D - Division Game

Idea: skywalkert

solution

102253E - Expectation of Division

Idea: skywalkert

solution

102253F - Function

Idea: chitanda

solution

102253G - Gear Up

Idea: constroy

solution

102253H - Hints of sd0061

Idea: constroy

solution

102253I - I Curse Myself

Idea: sd0061

solution

102253J - Journey with Knapsack

Idea: skywalkert

solution

102253K - KazaQ's Socks

Idea: chitanda

solution

102253L - Limited Permutation

Idea: skywalkert

solution

Hope you can enjoy it. Any comments, as well as downvotes, would be appreciated.

• +49

 » 3 years ago, # |   -7 Only A and K are unlocked. What about B and F?
•  » » 3 years ago, # ^ |   +4 What do you mean? Can you see in this blog the author names and solutions for A, B, F and K?
•  » » » 3 years ago, # ^ |   -35 Calm the fuck down, dude! What I'm saying is we still don't have access to the solutions of contestants on the contest page for B and F, unlike A and K (the codes for which are available). Can you not see there? :D
•  » » » » 3 years ago, # ^ |   0 Easy, dude. All public contests in Codeforces::Gym do not show tests and allow view submissions only to solvers. These rules are fixed by Codeforces admins and we can't change the setting.'solution' in this blog only means some description about the stanard algorithms and programs. Sorry for misleading.
•  » » » » » 3 years ago, # ^ |   -29 But still somehow you guys managed to show the submissions for A and K. Nevermind! May I know the second test case of problem B, because I did the exact same thing as said in the editorial and it shows WA on TC2.
•  » » » » » » 3 years ago, # ^ |   0 Well, 'allow view submissions only to solvers', which is literally written in the setting page, means that when you have solved a certain problem, you can view all submissions in this problem, except those submitted by someone who has enabled COACH mode. So, as you team solved A and K, that's why you can see something.By the way, your last submitted code for B may fail on some cases like 26*26*26 strings of 'a' and 1 string of 'b'.
•  » » » » » » » 3 years ago, # ^ |   0 Okie thanks!
 » 3 years ago, # |   0 I tried solving A like this (m * log10(2) + 1); But it's showing ans = 20 for m=64.which is wrong. while it shows correct output for m values=4,5,6, 7 and various others.->And if i do floor(m * log10(2)); now it shows 19 for m=64 which is correct. while it shows wrong for m values = 4,5,6,7 and various others.ANyone can help?
•  » » 3 years ago, # ^ |   +5 Ohhk, i got it. Where i was doing mistake.
 » 3 years ago, # |   0 Can anyone post the solution of B
 » 3 years ago, # |   0 Can anyone explain Problem B? I am not able to understand problem statement.Also can you explain how this ans came for this test case. Input- 3 a ba abcOutput- 18221
 » 3 years ago, # |   0 Sorry for necroposting.What is the solution in expected sqrt(n*m) for H?
•  » » 3 years ago, # ^ |   0 And how to solve I in Klog(K) ?
•  » » » 3 years ago, # ^ |   0 There is a problem requiring $\mathcal{O}(K \log K)$ algorithm. You can solve that problem on LibreOJ, or just view accepted solutions.Brief description:There are $n$ sets of numbers. The $i$-th set contains $c_i$ integers. Note that a value may be contained multiple times in a set, but every two copies are considered different.You can select one integer from each set, and then get a score equal to the total sum of the selected integers.You are asked to find $k$ possible schemes with the largest scores, and output these scores in decreasing order.
•  » » 3 years ago, # ^ |   0 What is the solution in expected sqrt(n*m) for H? It should be a typo.Split the range of values into $T$ blocks, and there are at most $m$ useful blocks. If generated elements are random enough, each block will contain $\frac{n}{T}$ elements. Erasing useless elements may help the further process, but it's just an optimization of constraints.I think the expected $\mathcal{O}(\sqrt{n m})$ should be $\mathcal{O}(n + \sqrt{n m})$. And how to solve I in Klog(K)? Just boost the process of sequence merging by data structures like Heap or SegmentTree (additional definition of states required).
 » 3 years ago, # |   0 is nlogn a typo in J editorial? The best solution I could get was nlog^2(n) using online fft to calculate the partition generating function.
•  » » 3 years ago, # ^ |   +5 It can be done in $\mathcal{O}(n \log n)$ using Euler transform and Newton's method. These two approaches both require the knowledge of Taylor series expansion. Here's the detail for faster solving. Alert: TL;DR.Applying Taylor series expansion to $f(z) = \ln{(1 - z)}$ at $z = 0$, we have $\ln{(1 - z)} = \ln{(1)} + \sum_{k \geq 1}{\frac{f^{(k)}(0)}{k!} z^k} = \sum_{k \geq 1}{\frac{-(k - 1)!}{k!} z^k} = -\sum_{k \geq 1}{\frac{z^k}{k}}\text{;}$hence, for the aforementioned $F(z)$, we conclude that $\ln{(F(z))} = \ln{\left(\prod_{i = 1}^{n}{\frac{1 - z^{(a_i + 1) i}}{1 - z^i}}\right)} = \sum_{i = 1}^{n}{\left(\ln{\left(1 - z^{(a_i + 1) i}\right)} - \ln{\left(1 - z^i\right)}\right)} = \sum_{i = 1}^{n}{\left(\sum_{k \geq 1}{\frac{z^{k (a_i + 1) i}}{k}} - \sum_{k \geq 1}{\frac{z^{k i}}{k}}\right)}\text{,}$which is also a polynomial and whose first $(2 n + 1)$ terms can be calculated in $\mathcal{O}(n \log n)$.Then let's talk about how to get $F(z) \pmod{z^{2 n + 1}}$ from $\ln{(F(z))} \pmod{z^{2 n + 1}}$.Define $G(u) = \ln{(u)} - \ln{F(z)}$. Our goal is to find $u$, as a polynomial of $z$, satisfying $G(u) \equiv 0 \pmod{z^{2 n + 1}}$.Assume that we have solved the equation $G(u) \equiv 0 \pmod{z^m}$ and the solution is $u \equiv F_{m}(z) \pmod{z^m}$, where $F_{m}(z)$ is a polynomial with only first $m$ terms.Applying Taylor series expansion to $G(u)$ at $u = F_{m}(z)$, we have $G(u) = G(F_{m}(z)) + \sum_{k \geq 1}{\frac{G^{(k)}(F_{m}(z))}{k!} (u - F_{m}(z))^k}\text{.}$Note that for any positive integer $k$, $z^{k m} | (u - F_{m}(z))^k$, so if we want to solve $G(u) \equiv 0 \pmod{z^{2 m}}$, we have $0 \equiv G(u) \equiv G(F_{m}(z)) + \frac{\mathrm{d} G}{\mathrm{d} u}\left(F_{m}(z)\right) (u - F_{m}(z)) \pmod{z^{2 m}}\text{,}$where $G'(u)$ $= \frac{\mathrm{d} G}{\mathrm{d} u}(u) = \frac{1}{u}$. Then, we can get the solution $u \equiv F_{m}(z) (1 - \ln{(F_{m}(z))} + \ln{(F(z))}) \pmod{z^{2 m}}$.The rest task is to calculate $\ln{(F_{m}(z))} \bmod z^{2 m}$. (We only know $\ln{(F_{m}(z))} \equiv \ln{(F(z))} \pmod{z^m}$, right?) Since the constant term of $F_{m}(z)$ is $1$, we know that $z | \ln{(F_{m}(z))}$, and thus we can calculate it by $\ln{(F_{m}(z))} \equiv \int{\frac{\mathrm{d} F_m}{\mathrm{d} z}(z) \frac{1}{F_{m}(z)} \mathrm{d} z} \pmod{z^{2 m}}$.Holy... Well, it seems we have to solve another problem (polynomial inversion) first... Don't worry, it can be done in $\mathcal{O}(m \log m)$. Let's forget about it for a while, and focus on the logarithm (exponential?) problem.Assume that we have calculated $\frac{1}{F_{m}(z)} \bmod z^{2 m}$ in $\mathcal{O}(m \log m)$, then we can calculate $\ln{(F_m(z))}$ and $u$ in $\mathcal{O}(m \log m)$ too, which means we can solve the equation $G(u) \equiv 0 \pmod{z^{2 m}}$ in the cost of solving $G(u) \equiv 0 \pmod{z^m}$ plus $\mathcal{O}(m \log m)$ additional cost.Let $T(m)$ be the cost of solving the equation $G(u) \equiv 0 \pmod{z^m}$, we have $T(m) = T\left(\left\lceil\frac{m}{2}\right\rceil\right) + \mathcal{O}(m \log m) \Rightarrow T(m) = \mathcal{O}(m \log m)\text{.}$Well, the real remaining part is to get the polynomial inversion. Similarly, if we define $G(u)$ $= u P(z) - 1$ and $G(u_k) \equiv 0 \pmod{z^k}$, we will have $u_{2 k} \equiv u_k - \frac{u_k P(z) - 1}{P(z)} \pmod{z^{2 k}}$. Note that $z^k | (u_k P(z) - 1)$, we only care about $\frac{1}{P(z)} \bmod{z^k}$ instead of $\frac{1}{P(z)} \bmod{z^{2 k}}$, so we can get $u_{2 k} = u_k - (u_k P(z) - 1) u_k \pmod{z^{2 k}}$, and there is no more problem introduced.
 » 2 years ago, # |   0 skywalkert please release the editorial for problem E.
•  » » 2 years ago, # ^ |   0 Done. (Spent some extra time reviewing to make it more understandable.)
•  » » » 2 years ago, # ^ |   0 Thank you:)
 » 2 months ago, # | ← Rev. 4 →   0 Hi, I am the original author of problem H. Recently I have found out a really elegant way to solve it.Basically, we can realize the classic nth_element in linear time.Then, what if we deal with the m positions at once?Still, we use linear time partition, to partition array a[0, n) into three parts, [0, l), [l, r) and [r, n).The positions(elem. of b) in [l, r) is definitly solved.If any elements of b fall in [0, l), we go to solve sub-array [0, l) with those elements recursively. Also the same for [r, n). This way is faster than the 'm times of nth_element', intuitively.But the rigorous time complexity is quite difficult to prove.Notice that b is arranged in a way so that most of sub-arrays of a is not encountered.I roughly guess it O(n + m * log(n)).
•  » » 2 months ago, # ^ |   0 The submission is https://codeforces.com/gym/102253/submission/173400186
 » 2 months ago, # |   0 Nice congest