### chokudai's blog

By chokudai, history, 2 years ago,

We will hold AtCoder Beginner Contest 132.

The point values will be 100-200-300-400-500-600.

We are looking forward to your participation!

• +67

 » 2 years ago, # | ← Rev. 2 →   +7 Copy&Pasted the e-mail announcement and forget to remove the instruction for unsubscription? LOL
•  » » 2 years ago, # ^ |   0 It's strange I did not recieve email announcement yet. I thought generally everyone recieve it at same time.
•  » » » 2 years ago, # ^ |   +3 it fixed. thanks!
 » 2 years ago, # | ← Rev. 2 →   0 Do they release editorials for these rounds? Is it in english?
•  » » 2 years ago, # ^ |   0 For beginner contests there are no english editorials.
•  » » 2 years ago, # ^ |   +6 I wrote an unofficial English editorial.
 » 2 years ago, # |   0 Auto comment: topic has been updated by chokudai (previous revision, new revision, compare).
 » 2 years ago, # |   +23 AtCoder site is terribly slow these days during the contest, it takes usually 10-15 seconds to open standing or clarification page. Please do something about it.
 » 2 years ago, # |   0 After the contest ends please tell How to solve Problem D?
•  » » 2 years ago, # ^ |   +3 place red balls then choose i gaps out of n-k+1 = (n-k+1 choose i). then place k blues in these i gaps = number of positive integral solutions of a1+..ai=k = (k-1 choose i-1) multiply both coefficients.
•  » » » 2 years ago, # ^ | ← Rev. 2 →   0 were there any corner cases? spoiler lli ans=(fact[n-k+1]*inverse[i])%mod; assert(n-k-i+1>=0); ans=(ans*inverse[n-k-i+1])%mod; ans=(ans*fact[k-1])%mod; ans=(ans*inverse[k-i])%mod; ans=(ans*inverse[i-1])%mod; cout<
•  » » » » 2 years ago, # ^ |   0 No need to handle corner cases because all values outside range will be set to 0 which will give the required answer as 0. Code.
•  » » » » » 2 years ago, # ^ |   0 Got it ,Thanks. I didn't handle the case where k>n in n choose k.
•  » » » » 2 years ago, # ^ | ← Rev. 3 →   +1 You can use c[2001][2001] with some Precomputation. c[i][j] = c[i-1][j] + c[i-1][j-1] base case : c[0][i] = c[i][0] = 1 Use this simple property to avoid such complex computation. (no need to use Inverse Modular properties .)
•  » » » » 2 years ago, # ^ |   0 it is not inverse(n), rather it is inverse(fact(n)) in your codesnippet
•  » » 2 years ago, # ^ |   0 Let us say the number of red balls is R = N — K and blue balls is B = K.Consider the case where it takes i moves. So the number of ways to split B balls into i non-empty groups is choose(B — 1, i — 1) by stars and bars method.Now between any 2 groups there must be at least one red ball since if there was no red ball, they would be one large group instead. So the groups must occupy spaces between the red balls. The number of spaces are R + 1 and groups are i. So again, by stars and bars method number of ways is choose(R + 1, i).Multiplying we get ans as choose(B — 1, i — 1) * choose(R + 1, i).You can precompute choose values for R + 1 and B — 1 in O(N) time and answer for every i in O(1) time. So complexity is O(N + K)
•  » » 2 years ago, # ^ |   0 Use just need to use PnC to solve the stuff look if we have K blue balls . then first place N-K red balls. then we have N-K+1 places to fill blue balls. Now just think if u use i of the places to fill K balls..Hope This helps u. :)
•  » » 2 years ago, # ^ | ← Rev. 3 →   0 Lets count dp[i][j], what means number of ways present number i with j addends (order is important). Then dp[i][j] = dp[i-1][j]+dp[i-1][j-1]. And the answer for i is dp[B][i]*(dp[R][i-1] + dp[R][i+1] + dp[R][i]*2), where B — blue balls, R — red balls.
 » 2 years ago, # | ← Rev. 3 →   0 How to solve D?I was thinking somewhat on the lines that x1+x2+x3+....+xi = K, so we get C(K-1, i-1) (assuming all get atleast 1), but I couldnt figure out how to arrange them :(
•  » » 2 years ago, # ^ |   +6 m = n-k ans[i] = C(m+1, i) * C(k-1, i-1)
•  » » 2 years ago, # ^ |   +3 You have to chose i places out of a total of (n-k)+1. (n-k) red balls so (n-k+1) places and you have to take any i of them to place your blue balls.
•  » » 2 years ago, # ^ | ← Rev. 2 →   +3 You can arrange i blue balls by C(k-1, i-1) and the red balls with 3 options : 2 * C(n-k-1, i-1), C(n-k-1, i) and C(n-k-1, i-2). So the answer would become : (number of ways of arranging blue balls) * (sum of 3 options of arranging red balls). My code
•  » » 2 years ago, # ^ |   0 You need to distribute K blue balls among i piles such that no pile is empty which is f1=C(k-1,i-1), now there are i-1 gaps between these piles and you need to fill at least 1 red ball in each of the i-1 gaps, after filling you will be left with z=n-k-(i-1) red balls and note that there are two more gaps one on extreme left and the other on extreme right of blue ball piles so you need to distribute z balls between i+1 piles such that each get >=0 balls which will be f2=C(n-k+1,i).So your answer will be f1*f2 . You can calculate nCr using factorial and inverse array in O(1) using O(n) preprocessing. Here is the link to my submission.I hope this helps :)
•  » » » 2 years ago, # ^ |   0 could you explain on why f2=C(n-k+1,i) ？
•  » » » » 2 years ago, # ^ |   0 Its because you first put (i-1) red balls between the i groups of blue balls, so the remaining red balls are N-K-(i-1). Now you have to divide them into (i+1) groups (i-1 + the 2 corner ones). So the number of solutions for: x1 + x2 + x3 + ... + x(i+1) = N-K-i+1 is C(N-K+1, i)
•  » » » » » 2 years ago, # ^ |   0 oh i seeN-K-(i-1) split into (i+1) groups C ( N-K-(i-1) + (i+1) -1 , (i+1)-1 )thank you ~
•  » » » 2 years ago, # ^ |   0 Awesome explanation, many thanks!I tried to solve it using pure DP but it was hard to do it in less than n^3. Can you link to some similar Combinatorics problems? Most of the problems I see on Codeforces are doable with some DP so I am quite weak with Combinatorics.
 » 2 years ago, # |   +72 Thanks for the contest! In case there aren't plans to write an English editorial, I wrote up my solutions to all of the problems at this link.
•  » » 2 years ago, # ^ |   0 You're good. You should write a blog :D
•  » » 2 years ago, # ^ |   0 thanks a lot this should be a blog
•  » » 2 years ago, # ^ |   0 Totally agree, you should start your atcoder editorial blog.
 » 2 years ago, # |   +10 How to solve F?
•  » » 2 years ago, # ^ |   +18 The basic idea is DP with square-root decomposition. For each number of terms up to K, we store the number of valid sequences satisfying these two conditions (in two separate tables) for each X up to ceil(sqrt(N)): The sequence ends in X. The sequence ends in a term Y such that X*Y <= N but (X+1)*Y > N. We then just have to deal with transitions. I outline this step in my full solution, which I linked above.
•  » » 2 years ago, # ^ |   +8 Hint: naive dp — f[i][j] = sum(k=1..n/j,f[i+1][k]). This can be optimized cause many f[i][j] have same values precisely those which have n/j = n/j'. Just maintain groups(they never change) and calculate above dp- Time = O(k*num_groups) = O(k*sqrt(n));
•  » » » 2 years ago, # ^ |   +2 can you send a link to your solution? I used the same approach but got TLE.
•  » » » » 2 years ago, # ^ |   +8
•  » » 2 years ago, # ^ | ← Rev. 3 →   +17 Geothermal explains the solution well, but I think I have easier code for the problem: code#include #include using namespace std; using ll = long long; const ll MOD = 1e9 + 7; // Finds smallest s s.t. n/s < t ll bins(ll n, ll t) { ll low = 1; ll high = n+1; while(low != high) { ll s = (low + high) / 2; if (n/s < t) high = s; else low = s + 1; } return low; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); ll n, k; cin >> n >> k; vector cou, val; ll s = 1; for (; s <= n;) { ll v = n/s; ll nxt_s = bins(n, v); cou.push_back(nxt_s - s); val.push_back(v); s = nxt_s; } int m = cou.size(); vector cur = cou; vector nxt(m); for (int i = 1; i < k; ++i) { for (int j = 0; j < m; ++j) { int t = m-1-j; nxt[t] = cur[j] % MOD; } for (int j = m-1; j >= 0; --j) { nxt[j] = (nxt[j] + (j+1 < m ? nxt[j+1] : 0)) % MOD; cur[j] = (nxt[j] * cou[j]) % MOD; } } ll res = 0; for (auto v : cur) res = (res + v) % MOD; cout << res << '\n'; } Notably I only have one table, and from position j in the table, you can transition to any position in range $[0, m-j)$, so the transitions can be done with just two for-loops. To calculate the sizes of every part (where if $x$ and $y$ are in the same part if $\left\lfloor\frac{n}{x}\right\rfloor = \left\lfloor\frac{n}{y}\right\rfloor$), I just maintain the smallest s such that $\left\lfloor\frac{n}{s}\right\rfloor = v$, and then binary search the next $s^{'}$ s.t. $\left\lfloor\frac{n}{s^{'}}\right\rfloor < v$. Then there are $s^{'} - s$ values in the part.
•  » » » 2 years ago, # ^ |   +24 You don't need the binary search — s = n/(n/s'+1) — calculate in decreasing order.
•  » » » » 2 years ago, # ^ |   +6 Nice, with that the code is just 40 rows: code#include #include #include using namespace std; using ll = long long; const ll MOD = 1e9 + 7; int main() { ios_base::sync_with_stdio(false); cin.tie(0); ll n, k; cin >> n >> k; vector cou; for (ll s = n; s > 0;) { ll nxt_s = n/(n/s + 1); cou.push_back(s - nxt_s); s = nxt_s; } reverse(cou.begin(), cou.end()); int m = cou.size(); vector cur = cou; vector nxt(m); for (int i = 1; i < k; ++i) { for (int j = 0; j < m; ++j) { int t = m-1-j; nxt[t] = cur[j] % MOD; } for (int j = m-1; j >= 0; --j) { nxt[j] = (nxt[j] + (j+1 < m ? nxt[j+1] : 0)) % MOD; cur[j] = (nxt[j] * cou[j]) % MOD; } } ll res = 0; for (auto v : cur) res = (res + v) % MOD; cout << res << '\n'; } 
•  » » 2 years ago, # ^ | ← Rev. 3 →   +12 Maybe I have a bit simpler solution (well, rather, interpretation) than others, which can be implemented very intuitively. Let's call a sequence good when each element is positive integer $\leq N$, and product of any two adjacent elements is $\leq N$. For each positive integers $m$ and $i$, let $a^{m}_{i}$ be the number of good sequence of length $m$ whose last element is $\leq i$, and $b^{m}_{i}$ be the number of good sequence of length $m$ whose last element is $\leq N / i$. For $m=1$, $a^1_i = \mathrm{min}(i,N)$ and $b^1_i = n/i$. For $m \geq 2$, it holds that $a^m_i = a^m_{i-1} + b^{m-1}_i$, and $b^m_i = b^m_{i+1} + a^{m-1}_i \cdot (\frac ni - \frac n{i+1})$, Also, it holds that $a^m_i = b^m_{N/i}$. Therefore, for each $m$, you can calculate $a^m_1, a^m_2, \cdots, a^m_{N/x} = b^m_x, b^m_{x-1}, \cdots, b^m_1$. Of course it's optimal when $x \approx \sqrt N$. The answer is $b^K_1$. Code#include using namespace std; using ll = long long; const ll MOD = 1000000007; const ll M = 128; const ll X = 32768; // >= sqrt(N) ll a[M][X], b[M][X]; int main(){ int N, K; scanf("%d%d", &N, &K); for(int i=1; i=1; i--){ b[m][i] = ( b[m][i+1] + a[m-1][i] * (N/i - N/(i+1)) ) % MOD; } } printf("%lld\n", b[K][1]); } `
•  » » » 2 years ago, # ^ |   +5 there is typo mistake. $b_i^m$ is whose last element $\leq N/i$
•  » » » » 2 years ago, # ^ |   0 you're right, thanks
 » 2 years ago, # |   0 How to solve Problem E & F ???
•  » » 2 years ago, # ^ |   +4 The idea is that we construct the graph in 3 parts (let's call them first, second and third), such that if there is an edge between u and v, then in our graph, there is an edge between u.first -> v.second, u.second -> v.third and u.third -> v.first. Now, if you run BFS on this Graph starting from vertex S.first and if you keep the destination as T.first, then you will find a path whose length is always divisible by 3, and hence you will get the answer by dividing the path length by 3. And if you cannot reach T.first, then print -1.My AC submission: https://atcoder.jp/contests/abc132/submissions/6179681
•  » » » 2 years ago, # ^ |   +4 How u came up with this approach.During the contest. Have u seen such problems.I was triying to first run a dfs from start to end and checking if i reached in between all this at my end vertex if yes then i check the count of the vertices i crossed.but it didnt worked.Also i was checking if there is a loop containing vertex with length of loop%3!=0.but i got stuck in the cases and finally was unable to figure out the sol...Plz tell am thinking in right direction or i m completely wrong
•  » » » » 2 years ago, # ^ |   0 Thx.
•  » » » » 2 years ago, # ^ |   +1 Practice
•  » » » 2 years ago, # ^ |   +4 Nice approach!
•  » » » 2 years ago, # ^ |   0 Thx. I understood. But how to solve Problem F??
 » 2 years ago, # |   0 Plz help with E.
•  » » 2 years ago, # ^ |   +3 See the link I posted above. A copy of my write-up of E is below:Create a graph of 3*N vertices, where the first N vertices represent reaching a vertex before starting a ken-ken-pa, the second set of N vertices represent reaching a vertex after one of the three actions in a ken-ken-pa, and the third set of N vertices represent reaching a vertex after two actions in a ken-ken-pa. An edge from A to B in our original graph is then equivalent to three edges: one from A to B+N, one from A+N to B+2N, and one from A+2N to B. The advantage of this approach is that once we read in the data, the solution itself is very easy to implement, as we now simply want to find one-third the distance from S to T (where the distance between two nodes is the number of edges we must traverse to reach one from the other). We can compute this using a standard BFS algorithm, which can also tell us whether T can be reached from S at all.
•  » » » 2 years ago, # ^ |   +2 why do create a graph of 3*N vertices ??,this confused
•  » » » » 2 years ago, # ^ | ← Rev. 2 →   +4 Think of it like every vertex is being split into three vertices, let's say vertex u is being converted into three copies of vertices u0,u1,u2 where u0 denotes the vertex copy of u if u is reachable with distance equal to 0 modulo 3 from some source vertex ,and similarly u1 denotes the vertex if you can reach u with distance modulo 3 as 1 from some source vertex , similarly for u2 , so that's why for every u->v edge it is equivalent to u0 -> v1 , u1 -> v2 , u2->v0 as if you move one step from u0 then the distance modulo 3 becomes 1 as initially it was(=0%3) , so from u0 you can go to v1 , similarly for u1 if we move one more step towards v we actually reach v2 since now distance modulo 3 is 2 , .. Now we need to find the shortest distance from S0 to T0 as when we start at S our distance is 0 and when we reach at T our distance modulo 3 must be 0 which implies that we have taken steps in multiples of 3 . Initially i too didn't understand proof.
•  » » » 2 years ago, # ^ |   +1 Is there any proof of this solution?
•  » » » 2 years ago, # ^ |   +1 Can you please suggest me a similar problems to Problem E?
•  » » » » 2 years ago, # ^ |   0 This problem is a somewhat harder task that uses a similar idea.