We will hold AtCoder Regular Contest 116.
- Contest URL: https://atcoder.jp/contests/arc116
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20210328T2100&p1=248
- Duration: 120 minutes
- Number of Tasks: 6
- Writer: kort0n
- Tester: beet, heno239, tempura0224
- Rated range: — 2799
The point values will be 300-400-500-500-800-800.
We are looking forward to your participation!
Atcoder Modulo 998244353 Contest is a better name.
How about Atcoder DP Contest?
Atcoder DP MODULO 998244353 Contest
How to propose a question in ABC/ ARC?
E is exactly the same as problem Dynamite in POI2011.
Editorial of C only says "here is the formular" :/
Can somebody explain why "the product of n binomial coefficients" work, and how?
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
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
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
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.
Its called stars and bars technique, you can read this
in this problem, $$$y_i > y_{i-1}$$$, why it also can be calculate by this fomula?
perhaps it is y[i] >= y[i — 1].
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
$ 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}$$$,
$ 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.
I think the problem F ever occurred in an old Codeforces contest. But I have no evidence...
I proposed the $$$K=1$$$ version before in a CF round 794E - Choosing Carrot, but I didn't know of the general case.
Oh... I think I have a wrong memory now. T_T
I remembered that problem while solving F but failed to generalize it :(
anyone please explain the solution of C ! how the product of binomial is giving us the answer
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.)
You are explaining the solution of B and not of C
what is f ($$$A_i$$$) for even $$$n_i$$$ in the F editorial?
In the editorial of F, Case 2 should be all odd, not all even, right? Since $$$f()$$$ was just defined for odd lengths.
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
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
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]$$$ ?
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.
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.
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)
This was my solution too. Also worth pointing out that for N <= 19, one may just want to do the obvious N*M dp
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.
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'.
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
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!!!
E is (also) the same as NOI2020 Qualification Round — Firefighter + a binary search.
Anyone please explain how to solve problem D. The editorial is very poorly written.
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:
The transitions of this DP is, for each $$$0 \le k \le N$$$ and $$$k$$$ is even,
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
Can any one please tell me why this solution for Problem B is giving wa? Is it for using Moduler inverse? my solutuion
The part where you are precomputing powers of 2. It is overflowing.
But I was using (1<<xx)%mod
Issue is first the
1 << xxoverflows, then you mod that value, so you're doing(arbitrary overflowed value) % mod.Oh Allah!! That was really stupid of me!! Thank you very very much!! :D
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
Your binomialCoeff function overflows
Thank you!! I now found the issue, thank you so much!!
Here is a strange way to solve problem C.
First,We have a naive dp in $$$O(nm\ln m)$$$
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.
my code
[user:Olerwanhong] — What do you mean by $$$F(i) = F(i - 1)*1$$$, where $$$1(i)=1$$$? It is unclear to me.
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.
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
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 ?
There is a word "Constraints" instead of "Output" in problem A.
Why is there no contests this week ( I am new to Atcoder ) . I thought Atcoder has atleast 1 contest every week.
actually, it's not