Блог пользователя AnandOza

Автор AnandOza, 5 лет назад, По-английски

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.

  • Проголосовать: нравится
  • +124
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

So well written, Thank you!

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Nicely explained. Thank You!!

»
5 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    After you sort it, it will become AABB

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      oh, I missed that. sorry

      • »
        »
        »
        »
        5 лет назад, # ^ |
        Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

        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 лет назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            5 лет назад, # ^ |
              Проголосовать: нравится +3 Проголосовать: не нравится

            "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 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Thx. It helps me a lot.

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Thanks.

»
5 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

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

  • »
    »
    5 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

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

    • »
      »
      »
      5 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

      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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

appreciate your help!

»
5 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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