### skywalkert's blog

By skywalkert, history, 11 months 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 (4 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

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.   Comments (17)
 » Only A and K are unlocked. What about B and F?
•  » » What do you mean? Can you see in this blog the author names and solutions for A, B, F and K?
•  » » » 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
•  » » » » 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.
•  » » » » » 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.
•  » » » » » » 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'.
•  » » » » » » » Okie thanks!
 » 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?
•  » » Ohhk, i got it. Where i was doing mistake.
 » Can anyone post the solution of B
 » 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
 » Sorry for necroposting.What is the solution in expected sqrt(n*m) for H?
•  » » And how to solve I in Klog(K) ?
•  » » » 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.
•  » » 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).
 » 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.
•  » » 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.