Hi all, Atcoder Beginner Contest 132 was today. Atcoder only publishes Japanese editorials for beginner contests, so I wrote an unofficial English editorial. Hope it helps!
A: Fifty-Fifty
After sorting the input, a "good" string will look like "AABB". Therefore, we simply sort and check for this format.
B: Ordinary Number
It suffices to simply check every range of 3 and see if its middle element should be counted. A simple way is to sort each range of 3 and check that the middle element remains in the middle.
Runtime: $$$\mathcal{O}(n)$$$.
C: Divide the Problems
If we first sort the problems by difficulty, the necessary condition is equivalent to "the first half of the problems will be for ABCs, and the second half will be for ARCs". If we assign $$$B$$$ to the hardest ABC problem (problem $$$(N/2)$$$, after sorting) and $$$R$$$ to the easiest ARC problem (problem $$$(N/2+1)$$$, after sorting), we need to select $$$K$$$ such that $$$B < K \le R$$$.
Therefore, we have $$$R-B$$$ choices for K. (Note: if $$$R$$$ and $$$B$$$ are equal, there is no choice of $$$K$$$ that splits the problems in half.)
Runtime: $$$\mathcal{O}(N \log N)$$$.
D: Blue and Red Balls
In order for Takahashi to take exactly $$$i$$$ moves, we need $$$i$$$ separate "buckets" of blue balls. Let us say we have $$$R = N-K$$$ red balls and $$$B = K$$$ blue balls. Then, we may separately compute $$$X$$$ as the number of ways to order the $$$R$$$ red balls and the $$$i$$$ buckets of blue balls, and compute $$$Y$$$ as the number of ways to distribute the $$$B$$$ blue balls into the $$$i$$$ buckets. The output for $$$i$$$ moves is then $$$X \cdot Y$$$.
Let us compute $$$X$$$. If we imagine the $$$R$$$ red balls already in a row, there are $$$R+1$$$ spaces to put a bucket of blue balls (it can go left of all the balls, right of all the balls, or in the $$$R-1$$$ gaps between consecutive red balls). Therefore, $$$X = \binom{R+1}{i}$$$.
Let us now compute $$$Y$$$. To distribute $$$B$$$ blue balls into $$$i$$$ buckets, we can imagine all the blue balls in a row and insert $$$i-1$$$ dividers into the $$$B-1$$$ spaces between the balls to separate them into buckets. Therefore, $$$Y = \binom{B-1}{i-1}$$$.
Note: computing binomial coefficients can be done for this problem either by precomputing Pascal's Triangle in $$$O(N^2)$$$ time or by precomputing factorials and their inverses, since $$$N \le 2000$$$.
E: Hopscotch Addict
Repeating ken-ken-pa $$$k$$$ times corresponds to following a path of length exactly $$$3k$$$ in the graph. Therefore, we need to find the shortest path from $$$S$$$ to $$$T$$$ whose length is a multiple of 3.
In order to solve this, we create a new graph $$$G'$$$ with $$$3N$$$ vertices and $$$3M$$$ edges. For each vertex $$$v_i$$$ in the original graph $$$G$$$, we create three vertices $$$v_0$$$, $$$v_1$$$, and $$$v_2$$$ in $$$G'$$$. For every edge $$$(u, v)$$$ in $$$G$$$, we create edges $$$(u_0, v_1)$$$, $$$(u_1, v_2)$$$, and $$$(u_2, v_0)$$$ in $$$G'$$$.
In this way, a path from $$$u_i$$$ to $$$v_j$$$ in $$$G'$$$ corresponds to a path in $$$G$$$ whose length is congruent to $$$j-i \text{ (mod 3)}$$$.
Therefore, we can run a BFS on $$$G'$$$ to find the shortest path from $$$S_0$$$ to $$$T_0$$$, which corresponds to the shortest path with length a multiple of 3 in $$$G$$$. If we find such a path, we simply divide its length by 3 to get the number of ken-ken-pa.
Runtime: $$$\mathcal{O}(N + M)$$$.
F: Small Products
Let's divide the numbers from $$$1$$$ to $$$N$$$ into "small" and "big" numbers. We call "small" numbers those that are at most $$$\sqrt{N}$$$, and "big" numbers those that are greater than $$$\sqrt{N}$$$.
This means that any two small numbers can be adjacent, and no two big numbers can be adjacent. When putting a small number $$$s$$$ and a big number $$$b$$$ adjacent, we require $$$s \cdot b \le N$$$.
Thus, we can split the possible values of $$$b$$$ into $$$\sqrt{N}$$$ buckets $$$B_i$$$ based on the maximal small number they can be paired with (for example, if $$$N=10$$$, the big numbers $$$4$$$ and $$$5$$$ can be paired with the small number $$$2$$$, but not with $$$3$$$, so they would go in $$$B_2$$$).
When we have built a partial sequence, we only care about the last value in the sequence when deciding how to build the rest of the sequence. Moreover, we actually only care about the $$$2\sqrt{N}$$$ categories the last element can fall into (either a small number or a bucket of big numbers).
Let $$$s(i, j)$$$ be the number of sequences of length $$$i$$$ ending with a small number $$$j$$$. Let $$$b(i, j)$$$ be the number of sequences of length $$$i$$$ ending with a big number in $$$B_i$$$.
A small number $$$j$$$ can be placed after any other small number, or after a big number in $$$B_k$$$ where $$$k \ge i$$$.
$$$\displaystyle s(i,j) = \sum_{k=1}^{\sqrt{N}} s(i-1,k) + \sum_{k=j}^{\sqrt{N}} b(i-1,k)$$$
A big number $$$j$$$ can be placed after any small number $$$k \le j$$$. We have $$$|B_j| = \frac{N}{j} - \frac{N}{j+1}$$$ possibilities for this big number.
$$$\displaystyle b(i,j) = \left( \frac{N}{j} - \frac{N}{j+1} \right) \sum_{k=1}^{j} s(i-1,k)$$$
This directly leads to an $$$\mathcal{O}(k \sqrt{N}^2)$$$ dynamic programming solution, which can be sped up to $$$\mathcal{O}(k \sqrt{N})$$$ by precomputing $$$\sum_{k=1}^j s(i-1,j)$$$ and $$$\sum_{k=j}^{\sqrt{N}} b(i-1,k)$$$ for all j, after we compute everything for $$$i-1$$$ and before we compute everything for $$$i$$$.
Runtime: $$$\mathcal{O}(k \sqrt{N})$$$.
Thanks for reading! Let me know if you have any questions or feedback for me.
So well written, Thank you!
Nicely explained. Thank You!!
Problem A: string like ABBA is also right, your code is wrong.
After you sort it, it will become AABB
oh, I missed that. sorry
These solutions got AC, so they should be accurate — see here for the full runnable code if you're curious (I omitted supporting code/functions in this blog for brevity).
can u plz explain the proof for E.I m finding it really difficult to get ???
"E: 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. " quoted from https://pastebin.com/zArycucT so v0 is basically the first set, v1 the second, v2 the third.
Thx. It helps me a lot.
Thanks.
Can anyone please suggest me a similar problems to Problem E?
I liked E — Independence from ARC 099, and thought it had a similar flavor. Try it out!
Thank you!
Can you link to similar Combinatorics problems like Problem C?
I tried to solve it using pure DP but it was hard to do it in less than n^3.
Most of the problems I see on Codeforces are doable with some DP so I am quite weak with Combinatorics.
In problem D' Explanation, "Let us now compute Y. To distribute B blue balls into i buckets, we can imagine all the blue balls in a row and insert i−1 dividers into the B−1 spaces between the balls to separate them into buckets. Therefore, Y=(B−1 i−1)."
Let's say , we have 4 blue balls to be distributed into two buckets. The possibilities are {1,3},{2,2}. But, (4-1 C 2-1)==(3 C 1)==3.
Am i missing any possibility , or misunderstood the explanation??
{3, 1} is another possibility.
https://brilliant.org/wiki/identical-objects-into-distinct-bins/ Read distribution of identical balls into non-empty Distinct bins from Brilliant.
Does one ken-ken-pa means moving from S->T then go T->S and finally go to S ->T all using different paths?
So if he is at vertex A, he goes to an adjacent vertex B, then a vertex C, then a vertex D, such that A-B, B-C, C-D are all edges in the graph. That is, he goes from vertex A to some vertex D that's exactly 3 steps away.
So you only need to go from S to T once, but you need to do it with 3k steps (where k is the number of ken-ken-pa).
appreciate your help!
In this question F small products, for big numbers
Instead of using condition
If(j==(n/j))dpbig[i][j]=0
Why cant I use this condition ?
If(((n/j)*(n/j))<n) dpbig[i][j]=0
I understood and BTW appreciate your help !!