### maroonrk's blog

By maroonrk, history, 4 years ago,

We will hold NOMURA Programming Competition 2020.

The point values will be 100-200-600-700-900-1000.

We are looking forward to your participation!

P.S. We are planning to set a lower bound for the rated range of AGC, so if you want to reach 2000 before the AGC next week, this contest will be a good opportunity for you.

• +174

 » 4 years ago, # |   +23 Reminder: The contest will start in 20 minutes.
 » 4 years ago, # |   +38 Atspeeder
•  » » 4 years ago, # ^ |   0 I don't really get it, do you think DEF was super easy or completely unsolvable?
•  » » » 4 years ago, # ^ |   +17 Judging from the solve statistics, for most participants, their ranking was largely based on ABC speed. D had about 70 solves while C had about 2000, so there was an exceptionally large gap between the two.
 » 4 years ago, # |   +12 How to solve C?
•  » » 4 years ago, # ^ |   +36 We maximize the number of nodes we have at each level. First, note that there can only be as many nodes at any level as there are leaves at or below that level in the tree. Second, note that there can only be twice as many nodes at any level as there were non-leaf nodes at the previous level. At each level, we add the minimum of these two values to the answer. We print -1 if any level has fewer nodes than it must have leaves.
•  » » » 4 years ago, # ^ |   0 Thanks Geothermal actually i thought the same logic ...i did a pretty silly mistake ... when i was multiply with 2 , i didn't set any upper limit moreover i declared that variable as int so i was getting WA all the time... my submission https://atcoder.jp/contests/nomura2020/submissions/13743838
 » 4 years ago, # |   0 How to solve F?
•  » » 4 years ago, # ^ |   +10 I probably won't be able to go into specifics, but a general outline of my solution is below.First, we consider the conditions required for a sequence to be good. It turns out that the following condition is both necessary and sufficient: for all $i < j$, if $A[i]$ contains a $1$ as its $k$'th least significant bit and $A[j]$ contains a $0$ as its $k$'th least significant bit, then $A[i]$ and $A[j]$ must be equal in the $1$st through $k-1$'th least significant bits.We can extend this to note that for any bit $k$, all elements ranging from the first one with a $1$ in position $k$ to the last one with a $0$ in position $k$ must be equivalent in all bits $1$ through $k-1$.To count sequences satisfying this condition, we do DP, where $dp[i][j]$ is the number of ways to set the $i$ most significant bits such that there are $j$ elements not forced to be equivalent. Then, we can compute the number of ways to transition from an array with $j$ elements to one with $k$ elements, for each $k$, by computing the number of ways to assign 0s and 1s to bit $i$ such that, when we merge every element from the first $1$ to the last $0$, we're left with exactly $k$ elements. This takes $O(nm^2)$ time if implemented naively, but using prefix sums can speed it up to $O(nm)$.
•  » » » 4 years ago, # ^ |   0 I'm not sure your observation for what's good, as stated, makes much sense. How about a1 = 2(010) and a2 = 5(101)? Then although they differ in their 2nd least significant bit, with the former having a 1 and the latter a 0, they don't have matching least significant bits. And the array is already in ascending order, so it's definitely good. What I got when thinking was that for any ia[j], it's enough and necessary to have them vary in precisely one bit (and basically Snuke's operations are in vain).
•  » » » » 4 years ago, # ^ |   0 In that case, say Snuke removes everything except the 10 from a_1 and the 01 from a_2. Then, a_2 is less than a_1, but they can't be swapped, so (unless I'm misunderstanding your inputs?) this array cannot necessarily be sorted, as my condition suggests.
•  » » » » 4 years ago, # ^ |   +20 The condition is not "we can sort the array", but "we can sort the array after any remove-bit operations". In your example it's possible to remove the highest bit to make array 2 1, which can't be sorted.
 » 4 years ago, # |   0 https://atcoder.jp/contests/nomura2020/submissions/13742190I tried to debug this solution for two hours.. please help me where this fails.. Can I know the test cases? Will comment on the code if it is required...
•  » » 4 years ago, # ^ |   +27 You do know the third sample is failing, right?
•  » » » 4 years ago, # ^ |   0 Really sorry for that .. during the contest it showed SCRAMBLED_5 something...https://atcoder.jp/contests/nomura2020/submissions/13749671This fails in one test case why?
•  » » » » 4 years ago, # ^ |   0 Check cases where N = 0.
•  » » » » 4 years ago, # ^ |   0 I haven't seen your code but mine was also failing on one case and it was $N=0$. The answer is $1$ only if $A_0$ is $1$.
 » 4 years ago, # |   +18 How to solve D? Editorial is gonna be ready in a day...
•  » » 4 years ago, # ^ |   +36 The crucial observation is that in each component there can be only one vertex with $-1$. Each new edge decreases the number of components by one, except for the case when it forms a cycle. So we should count the number of cycles — it's dp in $O(n^2)$.
•  » » » 4 years ago, # ^ |   +13 I did get that observation, but couldn't deal with "in how many ways we can close a cycle" after some edge additions, can you share your code?
•  » » » » 4 years ago, # ^ |   0 Sure, the cycle part is in the end.
•  » » » 4 years ago, # ^ |   0 what do you mean by 'number of cycles'? what is dp[i][cnt] in your code?
•  » » » » 4 years ago, # ^ |   0 Let's merge connected components in the beginning. Then vertices of the new graph are these components and we count sum of number of cycles in all possible assignments. To do that, we count the number of cycles of each length and then multiply it by the proper coefficient, meaning that other vertices can have any value.
•  » » » » » 4 years ago, # ^ |   0 thanks
•  » » 4 years ago, # ^ | ← Rev. 2 →   +42 When all $-1$ are replaced, we get a so-called function graph, except we don't care about directions. The number of edges is $N$ — number of cycles. For each possible cycle, we want to find the number of assignments of $-1$ that result in it.Let $C$ be a component in the input graph that contains a cycle. This cycle will be there all the time, so we subtract $(N-1)^K$ for each of them. From now on, we can ignore them.When can a cycle that didn't exist be created? Consider trees rooted at vertices $i$ with $P_i=-1$; there are $K$ such trees with sizes $S_1, S_2, \ldots, S_K$. A cycle will visit some subset of these trees in some order. If it visits a subset $X$, there are $(|X|-1)!$ orderings and the number of assignments that result in such a cycle is $\prod_{j \in X} S_j \cdot (N-1)^{K-|X|}$ if $|X| \gt 1$, or $(S_j-1)(N-1)^{K-1}$ if $X = {j}$. Proof: just fix a cyclic sequence of trees that go in the cycle and for each tree, make an edge from its root to a vertex from the next tree in the sequence; the remaining $K-j$ edges can be assigned arbitrarily.We want to get the sum $c_k$ of $\prod_{j \in X} S_j$ over all subsets with size $k$, for each $k \gt 1$; then, the answer can be computed using the formulas above. This, in fact, is just polynomial multiplication — $c_k$ is the coefficient of $K-k$ in $\prod_{j=1}^K (x+S_j)$. This can be computed most easily using divide&conquer with Karatsuba's algorithm in $O(N^{\log_2 3})$ (the log-factor from d&c is eaten by Karatsuba), or with FFT in doubles in $O(N \log^2 N)$.
•  » » » 4 years ago, # ^ |   0 Thx for the explanation! However, I'm confused about this bit:$\prod_{j \in X} S_j \cdot (N-1)^{K-j}$ if $j \gt 1$, or $(S_j-1)(N-1)^{K-1}$ if $X=j$Should that be: $(\prod_{j \in X} S_j) \cdot (N-1)^{K-|X|}$ if $|X| \gt 1$, or $(S_j-1)(N-1)^{K-1}$ if $|X|=1$?
•  » » » » 4 years ago, # ^ |   0 Fixed. I was already thinking about $j$ as the variable of the sum later.
•  » » » 4 years ago, # ^ | ← Rev. 2 →   0 Thanks for the explaination. Can you share the O(Nlog^2N) code? I saw your submission at Atcoder and it seems to be O(N^2) dp approach.
 » 4 years ago, # |   +13 Can anyone show us how to solve D?
 » 4 years ago, # |   0 I think it's the first time I see a competition privacy agreement with an opt-out option, nice!Although you don't have to agree to the "exclusion of anti-social forces" either — does that mean that terrorists or mafia can still compete, but not receive prizes? :Ь
 » 4 years ago, # |   +11 When will be the testcases available ?
 » 4 years ago, # |   0 When will the test cases be made available?
•  » » 4 years ago, # ^ |   0
•  » » » 4 years ago, # ^ |   0 It's out already on the link you posted. Turns out I had the right solution for E, but messed up implementation :(. Anyway, thanks!
 » 4 years ago, # |   +36 Thank you all for your participation!
•  » » 4 years ago, # ^ |   +26 Thank you for good contest
 » 4 years ago, # |   0 In short, D can be solved by counting (directed) cycles for every assignment. Each connected components can be a part of new cycles with a path from some node to the “root”. If we choose k components, the contribution will be coef * (k-1)! * constant, where coef is the x^k’s coefficient of (1+s_1 x)(1+s_2 x)... And we count cycles already formed.
 » 4 years ago, # | ← Rev. 2 →   0 Was polynomial multiplication intended in D? My solution can improved to $O(nlog^2)$ with FFT. But I doubt it is the intended solution given the constraints.
•  » » 4 years ago, # ^ |   0 The model solution is of O(N^2) time.
•  » » » 4 years ago, # ^ |   +5 Can it be $O(n \log n)$ not $O(n \log^2 n)$? Model solution needs to expand product of $(1 - x\frac{c}{n})$ (or at least I think so after looking at formulas in it, sadly I don't speak Japanese) over all components with one $-1$ where $c$ is component size. Basic divide an conquer takes $O(n \log ^2 n)$. Can we use the fact, that those coefficients aren't arbitrary integers, to reduce complexity? I can't see any way to do so.
•  » » » » 4 years ago, # ^ | ← Rev. 2 →   +20 noshi (red on AtCoder) found an interesting explanation as follows:for $A_i \leq log n$ : calculate $\log(1 + A_i x)$ (this can be done in O(N)) $(1 + A_i x) ^k : k * \log$ and calculate exp of sumfor $A_i > log n$: number of terms $\leq n / log n$, so use D & Cand combine them together
•  » » » » » 4 years ago, # ^ |   0 I guess you mean generating function of $\log(1 + A_ix)$. That's really clever. Sadly it seems impossible to make this fit and basic D&C not especially since running time highly depends on FFT implementation.
•  » » » » 4 years ago, # ^ |   +10 Yeah, I also thought about that. We want to get $\prod_{i \ge 1} (x+i)^{c_i}$ where $c_i \ge 0$ and $\sum i \cdot c_i \le N$.One idea (not sure if useful) is that there are only $O(\sqrt{N})$ values of $i$ such that $c_i \neq 0$, we can separately multiply all polynomials $(x+i)$ with odd $c_i$ to get $R(x)$, compute the polynomial $Q(x)$ for all $c_i$ halved and get $R(x) \cdot Q(x)^2$. $Q(x)$ is just the same problem for $N/2$ and $R(x)$ has small degree, but idk how much that helps.
•  » » » » 4 years ago, # ^ |   +48 Say that we want to calculate $\prod_{i} (x + i)^{d_{i}}$. We know that $\sum_{i} i \cdot d_{i} \le S$. We can find $(x + i)^{d_{i}}$ in $O(d_{i})$ time using binomial theorem. Now let's multiply these polynomials in reversed order: Res = Poly(1); for (int i = S; i > 0; i--) Res = Res * genBinom(i, d[i]); $i$-th iteration works in $O((d_{i} + d_{i + 1} + \ldots + d_{S}) \log S)$ time, so everything works in $O(\log S \cdot \sum_{i} i \cdot d_{i}) = O(S \log S)$ time.
 » 4 years ago, # |   0 Is there a way to solve D using linearity of expectation? I tried something along the lines of for each -1 node the probability of creating a new edge is the equal to the probability of a randomly selected node being in a different connected component and summing these random variables. However I couldn't get it to work.
 » 4 years ago, # |   0 Can someone please help to find out why my solution of C is failing 7 testcases? I tried to but I am not able to figure out whats wrong. Solution for C
•  » » 4 years ago, # ^ |   0 _t can exceed long long range https://ideone.com/WCUZ3U
•  » » » 4 years ago, # ^ |   0 thank you very much! can you explain why s[i]=1e18 would not give incorrect answer?
•  » » » » 4 years ago, # ^ |   0 It will be minimized by the number of nodes at next level
 » 4 years ago, # |   0 Can Anyone Hack my solution basically I assume more number of nodes at bottom level and try finding out the lowest level below which we can have one child per node and above that level each node two child policy or a leaf. Submission link:- Folia Please help for finding the mistake as only some cases fails.Thanks in advance!
 » 4 years ago, # |   +8 The remaining part of the editorial has been translated.
 » 6 months ago, # | ← Rev. 3 →   0 I have an $\Theta(m + m \log_m n)$ time complexity solution for problem F.It's based on official $\Theta(nm)$ solution.For the recurrence $f_{n,m}=(m+1)f_{n-1,m}+\displaystyle\sum_{i=1}^{m-1}i2^{m-i-1}f_{n-1,i}$with edge case $f_{1,j}=1 \ (j \geq 1)$, the ans is $f_{n,m}$.define $F_n(x)=\displaystyle\sum_{i \geq 0} f_{n,i} x^i$so the recurrence can be written as the form $F_n(x)=\left( x +\dfrac{x^2}{1-2x}\right)F_{n-1}'(x)+F_{n-1}(x)$set $G_n(x) = F_n(x)t(x)$ in order to calculate $G_n(x)$ only with $G_{n-1}'(x)$, and without $G_n(x)$: $\dfrac{G_{n+1}(x)}{t(x)}=\left( x +\dfrac{x^2}{1-2x}\right)\dfrac{G_n'(x)t(x)-G_n(x)t'(x)}{t(x)}+\dfrac{G_n(x)}{t(x)^2}$then $t(x)$ should satisfy $\dfrac{1}{t(x)}=\left( x +\dfrac{x^2}{1-2x}\right)\dfrac{t'(x)}{t(x)^2}$the solution is $t(x) = x(1-x)$, then we have $G_n(x)=\left( x+\dfrac{x^2}{1-2x}\right)G_{n-1}'(x)$But it's not enough. If we have $H_n(u) = G_n(x)$ which satisfy $H_n(u) = u \dfrac{\partial H_{n-1}(u)}{\partial u}$then $[u^m] H_n(u) = m^n [u^m]H_1(u)$. Now we need solve $u$: $G_{n-1}(x)=u\dfrac{\partial H_{n-1}(u)}{\partial u} = u \left( \dfrac{\partial u}{\partial x}\right)^{-1} G_{n-1}'(x)$That is $\dfrac{u}{u'}=x+\dfrac{x^2}{1-2x}$ $u=x(1-x)$We can solve that $H_1(u) = \left( \dfrac{1-\sqrt{1-4u}}{2}\right)^2 = \displaystyle\sum_{i\geq 2}\binom{2i-2}{i-1}\frac{u^i}{i}$ $H_n(u) = \displaystyle\sum_{i\geq 2}\binom{2i-2}{i-1} i^{n-1} u^i$The answer is \begin{aligned}[x^m] \frac{H_n(x-x^2)}{x-x^2}&=[x^m]\displaystyle\sum_{i\geq 2}\binom{2i-2}{i-1}i^{n-1}(x-x^2)^{i-1} \\ &= \displaystyle\sum_{i=2}^{m+1}\binom{2i-2}{i-1}\binom{i-1}{m-i+1}(-1)^{m-i+1}i^{n-1} \end{aligned}Of course, it can also be calculated in time complexity $\Theta(n)$.