We will hold AtCoder Beginner Contest 132.
- Contest URL: https://atcoder.jp/contests/abc132
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20190629T2100&p1=248
- Duration: TBD (around 2 hours)
- Number of Tasks: 6
- Writer: DEGwer(DEGwer), gazelle(gazelle), yuma000, potetisensei, tozangezan(EnumerativeCombinatorics)
- Rated range: ~ 1999
The point values will be 100-200-300-400-500-600.
We are looking forward to your participation!
Copy&Pasted the e-mail announcement and forget to remove the instruction for unsubscription? LOL
It's strange I did not recieve email announcement yet. I thought generally everyone recieve it at same time.
it fixed. thanks!
Do they release editorials for these rounds? Is it in english?
For beginner contests there are no english editorials.
I wrote an unofficial English editorial.
Auto comment: topic has been updated by chokudai (previous revision, new revision, compare).
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.
After the contest ends please tell How to solve Problem D?
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.
were there any corner cases?
I was getting runtime error for this assert.
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.
Got it ,Thanks. I didn't handle the case where k>n in n choose k.
You can use c[2001][2001] with some Precomputation.
Use this simple property to avoid such complex computation. (no need to use Inverse Modular properties .)
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)
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. :)
Let`s 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.
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 :(
m = n-k ans[i] = C(m+1, i) * C(k-1, i-1)
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.
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
You need to distribute
K
blue balls amongi
piles such that no pile is empty which isf1=C(k-1,i-1)
, now there arei-1
gaps between these piles and you need to fill at least1
red ball in each of thei-1
gaps, after filling you will be left withz=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 distributez
balls between i+1 piles such that each get>=0
balls which will bef2=C(n-k+1,i)
.So your answer will bef1*f2
. You can calculatenCr
using factorial and inverse array in O(1) using O(n) preprocessing. Here is the link to my submission.I hope this helps :)
could you explain on why f2=C(n-k+1,i) ?
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)
oh i see
N-K-(i-1) split into (i+1) groups
C ( N-K-(i-1) + (i+1) -1 , (i+1)-1 )
thank you ~
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.
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.
You're good. You should write a blog :D
thanks a lot this should be a blog
How to solve F?
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)):
We then just have to deal with transitions. I outline this step in my full solution, which I linked above.
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));
can you send a link to your solution?
I used the same approach but got TLE.
https://atcoder.jp/contests/abc132/submissions/6182428
Geothermal explains the solution well, but I think I have easier code for the problem:
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.
You don't need the binary search — s = n/(n/s'+1) — calculate in decreasing order.
Nice, with that the code is just 40 rows:
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
For each positive integers $$$m$$$ and $$$i$$$, let
For $$$m=1$$$, $$$a^1_i = \mathrm{min}(i,N)$$$ and $$$b^1_i = n/i$$$. For $$$m \geq 2$$$, it holds that
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$$$.
there is typo mistake. $$$b_i^m$$$ is whose last element $$$\leq N/i$$$
you're right, thanks
How to solve Problem E & F ???
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
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
Thx.
Practice
Nice approach!
Thx. I understood. But how to solve Problem F??
Plz help with E.
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.
why do create a graph of 3*N vertices ??,this confused
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.
Is there any proof of this solution?
Can you please suggest me a similar problems to Problem E?
This problem is a somewhat harder task that uses a similar idea.
F:https://www.hackerrank.com/challenges/p-sequences/problem
Thanks to the Atcoder team for another fun contest!
I wrote an English editorial on Codeforces, if anyone would like to read one.
Hi, I submitted solutions for 3 problems and they appear in 'My Submissions',however they don't reflect in 'Standings'.What did I do wrong?
Are you sure your submittions were submitted before the race ended?
Thank your guys for preparing a good contest.