maroonrk's blog

NOMURA Programming Competition 2020 Announcement
By maroonrk, history, 5 years ago, In English

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.

  • Vote: I like it
  • +174
  • Vote: I do not like it

»
5 years ago, # |
  Vote: I like it +23 Vote: I do not like it

Reminder: The contest will start in 20 minutes.

→ Reply
»
5 years ago, # |
  Vote: I like it +38 Vote: I do not like it

Atspeeder

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +17 Vote: I do not like it

      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.

      → Reply
»
5 years ago, # |
  Vote: I like it +12 Vote: I do not like it

How to solve C?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

    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.

    → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve F?

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +10 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +20 Vote: I do not like it

        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.

        → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +18 Vote: I do not like it

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

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +36 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +13 Vote: I do not like it

      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?

      → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        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.

        → Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +42 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

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

      ?

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

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

        → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

Can anyone show us how to solve D?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it +11 Vote: I do not like it

When will be the testcases available ?

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

When will the test cases be made available?

→ Reply
»
5 years ago, # |
  Vote: I like it +36 Vote: I do not like it

Thank you all for your participation!

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      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.

      → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
        ← Rev. 2   Vote: I like it +20 Vote: I do not like it

        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

        → Reply
        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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.

          → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +10 Vote: I do not like it

        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.

        → Reply
      • »
        »
        »
        »
        5 years ago, # ^ |
          Vote: I like it +48 Vote: I do not like it

        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.

        → Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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!

→ Reply
»
5 years ago, # |
  Vote: I like it +8 Vote: I do not like it

The remaining part of the editorial has been translated.

→ Reply
»
13 months ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

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

→ Reply