AnandOza's blog

By AnandOza, 5 years ago, In English

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.

Sample code

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)$$$.

Sample code

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)$$$.

Sample code

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$$$.

Sample code

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)$$$.

Sample code

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})$$$.

Sample code

Thanks for reading! Let me know if you have any questions or feedback for me.

  • Vote: I like it
  • +124
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

So well written, Thank you!

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Nicely explained. Thank You!!

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Problem A: string like ABBA is also right, your code is wrong.

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +14 Vote: I do not like it

    After you sort it, it will become AABB

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      oh, I missed that. sorry

      • »
        »
        »
        »
        5 years ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        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).

        • »
          »
          »
          »
          »
          5 years ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          can u plz explain the proof for E.I m finding it really difficult to get ???

          • »
            »
            »
            »
            »
            »
            5 years ago, # ^ |
              Vote: I like it +3 Vote: I do not like it

            "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.

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Thx. It helps me a lot.

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Thanks.

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Can anyone please suggest me a similar problems to Problem E?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    I liked E — Independence from ARC 099, and thought it had a similar flavor. Try it out!

    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      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.

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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??

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Does one ken-ken-pa means moving from S->T then go T->S and finally go to S ->T all using different paths?

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    In one ken-ken-pa, he does the following exactly three times: follow an edge pointing from the vertex on which he is standing.

    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.

    Determine if he can reach Vertex T by repeating ken-ken-pa.

    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).

»
5 years ago, # |
  Vote: I like it +3 Vote: I do not like it

appreciate your help!

»
5 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

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

  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I understood and BTW appreciate your help !!