maroonrk's blog

AtCoder Regular Contest 116 Announcement
By maroonrk, history, 4 years ago, In English

We will hold AtCoder Regular Contest 116.

The point values will be 300-400-500-500-800-800.

We are looking forward to your participation!

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

Comments Comments (53)
| Write comment?
»
4 years ago, # |
  Vote: I like it +112 Vote: I do not like it

Atcoder Modulo 998244353 Contest is a better name.

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

How to propose a question in ABC/ ARC?

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

E is exactly the same as problem Dynamite in POI2011.

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

Editorial of C only says "here is the formular" :/

Can somebody explain why "the product of n binomial coefficients" work, and how?

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

    If you have an element $$$X$$$ in the array then all the element after $$$X$$$ would be a multiple of it. Let say you have the last element as $$$X$$$ and if it has the prime factorizations as $$$p_1^{q_1}, p_2^{q_2}..p_k^{q_k}$$$ then at some point in the array these primes started occuring since they have to be present in the last element for sure.


    Now calculate the answer for each prime separately. Say the power of $$$p_j$$$ at position $$$i$$$ in the array is $$$y_j$$$ (you can consider that the power of $$$p_j$$$ increase by this amount at this position). So you need to find the number of solutions for the equation: $$$\sum_{i=1}^{N} y_i = q_j$$$, the answer to this is the binomial coefficient $$$\binom{q_j + N - 1}{N - 1}$$$. Take the product for each of the primes to get the final answer.


    My submission link

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

      Thank you! I finally got it!

      A little typo: The first y_j is probably meant to be y_i.

      This was a very good explanation

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

      Can you maybe provide your code? In the third test case I mess up somehow. I think its because of the MOD, but I dont get it

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

      can you explain why we need multiply all the binomial coefficient (qj+N+1,N-1),I still can't understand this,and what this the binomial coefficient (qj+N+1,N-1) solo mean???anyway thanks for you answer,good luck for you.

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

      in this problem, $$$y_i > y_{i-1}$$$, why it also can be calculate by this fomula?

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

    My attempt at a proof:

    Let $$$f_i(x)$$$ be the answer for the question where $$$n = i$$$ and $$$x$$$ is the last element in the sequence. Then

    $$$f_1(x) = 1$$$
    $$$f_i(x) = \sum_{d|x} f_{i-1}(d)$$$

    $ Notice that $$$f_1$$$ is a multiplicative function, and that $$$f_i$$$ is the Mobius Transform of $$$f_{i-1}$$$. So, $$$f_i$$$ is also multiplicative. Then, by property of multiplicative function, if $$$x = \prod_{i = 1}^{k} p_i^{e_i}$$$,

    $$$f(x) = \prod_{i=1}^{k} f(p_i^{e_i})$$$

    $ Next observation is that the value of $$$f(p_i^{e_i})$$$ is completely dependent on $$$e_i$$$ (from the definition of our function). The editorialist has found this to be some binomial coefficient, but I just calculated the value brute force and used it.

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

I think the problem F ever occurred in an old Codeforces contest. But I have no evidence...

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

anyone please explain the solution of C ! how the product of binomial is giving us the answer

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

    If you set the max(B) and min(B), the numbers between them can be chose or not, so the case number is $$$2 ^ {delta~index - 1}$$$(after sorting).

    Sorry, I I read it wrong.(C -> B

    Here is the explaination of the problem C: It's easy to see that we can separate different prime factors. And if $$$n = p^t$$$, we can iterate i from 1 to t(the number we choose), then $$$\dbinom t i \dbinom {n - 1}{i-1}$$$ is counted.(the first part we choose the set, the second part is the number of putting the $$$n$$$ numbers into $$$i$$$ indexes.)

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

what is f ($$$A_i$$$) for even $$$n_i$$$ in the F editorial?

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

In the editorial of F, Case 2 should be all odd, not all even, right? Since $$$f()$$$ was just defined for odd lengths.

→ Reply
»
4 years ago, # |
← Rev. 5   Vote: I like it +56 Vote: I do not like it

For problem C, I had a different solution from the editorial that I personally found more intuitive, so I'll share it here in case it helps anyone.

For a long valid sequence, many of the values are duplicates, and there are only at most $$$\mathcal O(\log M)$$$ distinct values since every new multiple must be at least twice the previous. So now let's count the number of distinct valued sequences for each length from $$$1$$$ to $$$\log M$$$. This can be done with dynamic programming: $$$dp[i][A]$$$ is the number of sequences of length $$$i$$$ ending in value $$$A$$$. For each $$$A$$$, we iterate over all its multiples, so the transition is $$$\mathcal O(M \log M)$$$ over all $$$A$$$ as it's a sum of harmonic series. The dp table is thus computed in $$$\mathcal O(M \log^2 M)$$$.

Once we have the table, the actual answer is

$$$ \sum_{i=1}^{\log M} \left( \binom{N - 1}{i - 1} \cdot \left(\sum_{A=1}^M \text{dp}[i][A]\right) \right) $$$

because for a given distinct sequence of length $$$i$$$, we can repeat some numbers $$$N - i$$$ more times to get an actual valid sequence of length $$$N$$$. This reduces to stars and bars: we're distributing $$$N$$$ items into $$$i$$$ groups, with at least one item in each group.

Submission: https://atcoder.jp/contests/arc116/submissions/21360034

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

    Great explanation, i thought of a similar dp approach, where basically we let $$$dp[i][j]$$$ be the total number of valid arrays such that the suffix $$$[i,n]$$$ is composed of equal elements and all the first $$$i$$$ elements are distinct, but how do you count the scenarios where some elements of the suffix are distinct? For instance, array of the following type : $$$[1, 2, 4, 8, 8, 16]$$$ ?

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

      The approach doesn't care about prefixes or suffixes, it essentially finds the "compressed" version of the array. So in your example, the compressed version would be $$$[1, 2, 4, 8, 16]$$$. After counting the compressed versions, we can then increase the counts of certain values (for example, increasing the counts of 2 and 4 by 1 would give us $$$[1, 2, 2, 4, 4, 8, 16]$$$) until we have $$$N$$$ elements. That's what the $$$\binom{N - 1}{i - 1}$$$ factor does.

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

        Now it's clear to me, thanks a lot! Basically if we imagine the sequence as $$$[1, 2, 4, _ _ _, 16]$$$ it's obvious that we need to fill $$$n-1$$$ slots using $$$i-1$$$ elements, therefore: $$${n-1}\choose{i-1}$$$ needs to be used.

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

        First of all, thanks for such a detailed explanation. I just wanted to make the last part clearer:

        let's say we have formed a sequence of i distinct elements. Now, to extrapolate it to N elements, we have to repeat some elements.

        So, we are essentially filling N-i blanks with i elements such that order doesn't matter.

        This is same as distributing x = N-i identical objects to r = i bins = C(x+r-1, r-1) using stars and bars as already mentioned.

        Hence, the answer becomes: C( (N-i) + (i) -1 , i-1) = C( N-1, i-1)

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

    This was my solution too. Also worth pointing out that for N <= 19, one may just want to do the obvious N*M dp

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

The same problem as E appeared in JOI Spring Camp 2010, and I even solved it 5 years ago. (https://atcoder.jp/contests/joisc2010/submissions/573439).

But I completely forgot it and realized this fact only after the contest. Sorry for my poor memory.

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

Can someone explain to me what's wrong with my approach in Problem C? Submission Link

Here, dp[i][j] = No. of sequence with 'j' elements which ends at 'i'.

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

The question C is same as Prob, but with strict constraints. This can be solved by just using the same formula, instead of non-decreasing sequence, we can find for strictly increasing sequence, and now we have different lengths of strictly increasing sequences stored in dp table(which will be at max. be of $$$(log(m))$$$ size), now for a given dp cell $$$dp[l][i]$$$ where l is the length of the sequence ending with i, we can fix i to the in the last position of n places and now we have to choose l-1 places out of n-1 places for the remaining elements, after fixing these l elements, we can fill the remaining vacant positions, by just taking a number from non-vacant position and filling the vacant positions with the number till the preceding non-vacant position. In this way we can get all the sequences.Sub

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

Please make the editorials of AtCoder Rounds more intuitive and more elaborate. Just giving the formulas directly or explaining the approach in a few lines does not help!!!

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

E is (also) the same as NOI2020 Qualification Round — Firefighter + a binary search.

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

Anyone please explain how to solve problem D. The editorial is very poorly written.

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

    The necessary and sufficient conditions for $$$A$$$ is, for each $$$i$$$, The number of elements in $$$A$$$ is even such that $$$i$$$-th bit is $$$1$$$. Because of $$$M \le 5000$$$, we are enough to think $$$2^i \le 5000$$$ ($$$i \le 12$$$).

    Let's thinking about doing following DP:

    • $$$dp[i][j] = \{$$$ The number of sequence thought about only $$$i$$$-th bit or higher, and remaining of $$$M$$$ is $$$j$$$ $$$\}$$$

    The transitions of this DP is, for each $$$0 \le k \le N$$$ and $$$k$$$ is even,

    • $$$dp[i-1][j-k*2^{i-1}]$$$ += $$$dp[i][j] \times nCk$$$

    Then, the answer is $$$dp[0][0]$$$ .

    This solution works at most $$$O(NM \log M)$$$, but actually we can cut most of transitions.

    code

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

Can any one please tell me why this solution for Problem B is giving wa? Is it for using Moduler inverse? my solutuion

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

    The part where you are precomputing powers of 2. It is overflowing.

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

      But I was using (1<<xx)%mod

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

        Issue is first the 1 << xx overflows, then you mod that value, so you're doing (arbitrary overflowed value) % mod.

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

          Oh Allah!! That was really stupid of me!! Thank you very very much!! :D

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

Can someone help me to understand why for big numbers my solution for C doesn't work.

I think its because of the MOD, but I don't get it, I am using MOD everywhere I can. solution

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

    Your binomialCoeff function overflows

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

      Thank you!! I now found the issue, thank you so much!!

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

Here is a strange way to solve problem C.
First,We have a naive dp in $$$O(nm\ln m)$$$

$$$ dp(i,j)=\sum_{d|j}dp(i-1,d) $$$

Consider $$$F(i)=\sum_{j=0}\frac{dp(i,j)}{j^i}$$$ ,then $$$F(i)=F(i-1)*1$$$,where $$$1(i)=1$$$for any integer $$$i$$$.

then ,$$$F(n)=1^n$$$.Just calculate it like fast pow. $$$O(m\ln m\log n)$$$ in total.

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

    my code

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

      [user:Olerwanhong] — What do you mean by $$$F(i) = F(i - 1)*1$$$, where $$$1(i)=1$$$? It is unclear to me.

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

        Sorry,maybe I made some mistakes.

        Let $$$F_i(x)=\sum_{k=0}\frac{dp(i,k)}{k^x}$$$ (the Dirichlet generating function of $$$dp(i,k)$$$),and $$$1(x)=\sum_{k=0}\frac{1}{k^x}$$$

        We have $$$dp(i,k)=\sum_{d|k} dp(i-1,d)$$$,so $$$F_i(x)=F_{i-1}(x)*1\Rightarrow F_n(x)=(1(x))^n$$$

        Calculate $$$1(x)^n$$$ like fast power gives an $$$O(m\ln m\log n)$$$ solution.

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

A even stranger solution to C.

Consider the $$$O(nm \ln m)$$$ DP, we can find that $$$f_{i,j}$$$ is equivlant to $$$f_{i,k}$$$ if $$$\lfloor \frac{m}{j} \rfloor = \lfloor \frac{m}{k} \rfloor$$$. So we can use $$$g_{i,j}$$$ where $$$g_{i,j}=\sum\limits_{\lfloor \frac{m}{k} \rfloor =j}f_{i,k}$$$, there are only $$$\sqrt m$$$ different $$$\lfloor \frac{m}{k}\rfloor$$$($$$892$$$ or so).

We can then use matrix to optimize it to $$$O(m\sqrt m\log n)$$$,which can pass with small constraints.

https://atcoder.jp/contests/arc116/submissions/21417559

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

Could some one please help in dynamic programming part of problem E ? How we are finding minimum number of vertices required to get time less than or equal to X ?

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

There is a word "Constraints" instead of "Output" in problem A.

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

Why is there no contests this week ( I am new to Atcoder ) . I thought Atcoder has atleast 1 contest every week.

→ Reply