We will hold NOMURA Programming Competition 2020.

- Contest URL: https://atcoder.jp/contests/nomura2020
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20200530T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: kobae964, satashun, gazelle
- Rated range: ~ 2799

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.

Reminder: The contest will start in 20 minutes.

Atspeeder

I don't really get it, do you think DEF was super easy or completely unsolvable?

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.

How to solve C?

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.

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

How to solve F?

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)$$$.

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 i<j, with a[i]>a[j], it's enough and necessary to have them vary in precisely one bit (and basically Snuke's operations are in vain).

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.

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.

https://atcoder.jp/contests/nomura2020/submissions/13742190

I 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...

You do know the third sample is failing, right?

Really sorry for that .. during the contest it showed SCRAMBLED_5 something...

https://atcoder.jp/contests/nomura2020/submissions/13749671

This fails in one test case why?

Check cases where N = 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$$$.

How to solve D? Editorial is gonna be ready in a day...

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)$$$.

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?

Sure, the cycle part is in the end.

what do you mean by 'number of cycles'? what is dp[i][cnt] in your code?

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.

thanks

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)$$$.

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$$$

?

Fixed. I was already thinking about $$$j$$$ as the variable of the sum later.

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.

Can anyone show us how to solve D?

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? :Ь

When will be the testcases available ?

When will the test cases be made available?

after 4-5 days at https://www.dropbox.com/sh/arnpe0ef5wds8cv/AAAk_SECQ2Nc6SVGii3rHX6Fa?dl=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!

Thank you all for your participation!

Thank you for good contest

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.

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.

The model solution is of O(N^2) time.

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.

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 sum

for $$$A_i > log n$$$: number of terms $$$\leq n / log n$$$, so use D & C

and combine them together

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.

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.

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:

$$$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.

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.

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

_t can exceed long long range https://ideone.com/WCUZ3U

thank you very much! can you explain why s[i]=1e18 would not give incorrect answer?

It will be minimized by the number of nodes at next level

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!

The remaining part of the editorial has been translated.

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

with edge case $f_{1,j}=1 \ (j \geq 1)$, the ans is $$$f_{n,m}$$$.

define

so the recurrence can be written as the form

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)$$$:

then $$$t(x)$$$ should satisfy

the solution is $$$t(x) = x(1-x)$$$, then we have

But it's not enough. If we have $H_n(u) = G_n(x)$ which satisfy

then $[u^m] H_n(u) = m^n [u^m]H_1(u)$. Now we need solve $$$u$$$:

That is

We can solve that

The answer is

Of course, it can also be calculated in time complexity $\Theta(n)$.