Please subscribe to the official Codeforces channel in Telegram via the link https://t.me/codeforces_official. ×

### maroonrk's blog

By maroonrk, history, 6 months ago,

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!

• +124

 » 6 months ago, # |   +112 Atcoder Modulo 998244353 Contest is a better name.
•  » » 6 months ago, # ^ |   +6 How about Atcoder DP Contest?
•  » » » 6 months ago, # ^ |   +11 Atcoder DP MODULO 998244353 Contest
 » 6 months ago, # |   +26 How to propose a question in ABC/ ARC?
 » 6 months ago, # |   +16 E is exactly the same as problem Dynamite in POI2011.
 » 6 months ago, # |   +7 Editorial of C only says "here is the formular" :/Can somebody explain why "the product of n binomial coefficients" work, and how?
•  » » 6 months ago, # ^ | ← Rev. 2 →   +30 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
•  » » » 6 months ago, # ^ |   0 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
•  » » » 6 months ago, # ^ |   0 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
•  » » » 6 months ago, # ^ |   0 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.
•  » » » » 6 months ago, # ^ |   0 Its called stars and bars technique, you can read this
•  » » » 6 months ago, # ^ |   0 in this problem, $y_i > y_{i-1}$, why it also can be calculate by this fomula?
•  » » » » 5 months ago, # ^ |   0 perhaps it is y[i] >= y[i — 1].
•  » » 6 months ago, # ^ |   +2 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.
 » 6 months ago, # |   +11 I think the problem F ever occurred in an old Codeforces contest. But I have no evidence...
•  » » 6 months ago, # ^ |   +39 I proposed the $K=1$ version before in a CF round 794E - Choosing Carrot, but I didn't know of the general case.
•  » » » 6 months ago, # ^ |   +1 Oh... I think I have a wrong memory now. T_T
•  » » » 6 months ago, # ^ |   +1 I remembered that problem while solving F but failed to generalize it :(
 » 6 months ago, # |   +2 anyone please explain the solution of C ! how the product of binomial is giving us the answer
•  » » 6 months ago, # ^ | ← Rev. 4 →   0 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 -> BHere 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.)
•  » » » 6 months ago, # ^ |   0 thank you for replying ! But i still don't get it . particularly this line from the editorial The answer for fixed AN can be found as the product of n binomial coefficients, where n is the number of prime factors of AN, by focusing on where in the sequence the number of times each prime factor is multiplied increases ! A more example / explanation with mathematical symbol would be really helpful
•  » » » 6 months ago, # ^ |   0 You are explaining the solution of B and not of C
 » 6 months ago, # |   0 what is f ($A_i$) for even $n_i$ in the F editorial?
 » 6 months ago, # |   0 In the editorial of F, Case 2 should be all odd, not all even, right? Since $f()$ was just defined for odd lengths.
 » 6 months ago, # | ← Rev. 5 →   +56 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.
•  » » 6 months ago, # ^ |   0 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]$ ?
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +3 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.
•  » » » » 6 months ago, # ^ |   0 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.
•  » » » » 6 months ago, # ^ | ← Rev. 3 →   +2 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)
•  » » 6 months ago, # ^ |   0 This was my solution too. Also worth pointing out that for N <= 19, one may just want to do the obvious N*M dp
 » 6 months ago, # |   +71 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.
 » 6 months ago, # | ← Rev. 3 →   0 Can someone explain to me what's wrong with my approach in Problem C? Submission LinkHere, dp[i][j] = No. of sequence with 'j' elements which ends at 'i'.
 » 6 months ago, # | ← Rev. 4 →   0 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
 » 6 months ago, # |   +38 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!!!
 » 6 months ago, # |   +26 E is (also) the same as NOI2020 Qualification Round — Firefighter + a binary search.
 » 6 months ago, # |   +9 Anyone please explain how to solve problem D. The editorial is very poorly written.
•  » » 6 months ago, # ^ |   +24 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
•  » » » 6 months ago, # ^ |   0 Got it thanks.
•  » » » 6 months ago, # ^ |   0 I didn't understand what dp[i][j] is storing is this case ! can anyone give me an example ?
 » 6 months ago, # | ← Rev. 2 →   0 Can any one please tell me why this solution for Problem B is giving wa? Is it for using Moduler inverse? my solutuion
•  » » 6 months ago, # ^ | ← Rev. 2 →   0 The part where you are precomputing powers of 2. It is overflowing.
•  » » » 6 months ago, # ^ |   0 But I was using (1<
•  » » » » 6 months ago, # ^ |   0 Issue is first the 1 << xx overflows, then you mod that value, so you're doing (arbitrary overflowed value) % mod.
•  » » » » » 6 months ago, # ^ | ← Rev. 2 →   0 Oh Allah!! That was really stupid of me!! Thank you very very much!! :D
 » 6 months ago, # | ← Rev. 2 →   0 I think the problem C appeared before in 414B - Mashmokh and ACM. Just with smaller constraints. But learned a new approach while solving C as it got larger constraints and need more efficient technique.
 » 6 months ago, # |   0 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
•  » » 6 months ago, # ^ |   +3 Your binomialCoeff function overflows
•  » » » 6 months ago, # ^ |   0 Thank you!! I now found the issue, thank you so much!!
 » 6 months ago, # | ← Rev. 2 →   +5 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.
•  » » 6 months ago, # ^ |   0
•  » » » 6 months ago, # ^ | ← Rev. 2 →   +5 [user:Olerwanhong] — What do you mean by $F(i) = F(i - 1)*1$, where $1(i)=1$? It is unclear to me.
•  » » » » 5 months ago, # ^ |   0 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.
 » 6 months ago, # |   0 How to solve B?Couldn't understand the editorial.
 » 6 months ago, # |   +16 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
 » 6 months ago, # |   0 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 ?
 » 6 months ago, # |   0 There is a word "Constraints" instead of "Output" in problem A.
 » 6 months ago, # |   0 Why is there no contests this week ( I am new to Atcoder ) . I thought Atcoder has atleast 1 contest every week.
•  » » 6 months ago, # ^ |   +5 actually, it's not