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

AtCoder Grand Contest 061 Announcement
Автор maroonrk, история, 16 месяцев назад, По-английски

We will hold AtCoder Grand Contest 061. This contest counts for GP30 scores.

The point values will be 500-800-800-1000-1400-2000.

We are looking forward to your participation!

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

»
16 месяцев назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Is atcoder suited for beginner?

→ Ответить
  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +55 Проголосовать: не нравится

    Yes, but not this contest.

    → Ответить
  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +48 Проголосовать: не нравится

    Atcoder holds Atcoder Beginner Contests on most Saturdays. Today I took part in one and learnt something new

    → Ответить
    • »
      »
      »
      16 месяцев назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Hi, may you explain me how to solve todays question B (abc289 — B)... Actually if you explain me what problem wants I think I can solve...

      Thanks you!

      → Ответить
      • »
        »
        »
        »
        16 месяцев назад, # ^ |
          Проголосовать: нравится +8 Проголосовать: не нравится

        At first, I left reading it at Consider an undirected graph. Its too brutal to exist as ABC B.

        Anyways, start reading it at For example (just skip graph, connected components etc jargon), then read samples and try to create a pattern that fits them. You should be able to guess it correctly.

        → Ответить
        • »
          »
          »
          »
          »
          16 месяцев назад, # ^ |
            Проголосовать: нравится 0 Проголосовать: не нравится

          For a beginner, what should be my goal in Regular and Grand Contests? I try to solve max in beginner contest(A,B,C,D,E,F) , while in Regular and Grand, my thoughts are to try A,B,C and then up solve the remaining if not solved during the contest?

          Is this good?

          → Ответить
»
16 месяцев назад, # |
  Проголосовать: нравится +49 Проголосовать: не нравится

Friendly 1-hour reminder!

→ Ответить
»
16 месяцев назад, # |
← Rev. 2   Проголосовать: нравится +7 Проголосовать: не нравится

Finally, "$$$0$$$ Solved" Round!

→ Ответить
»
16 месяцев назад, # |
  Проголосовать: нравится -8 Проголосовать: не нравится

Hope for a positive Δ and solve $$$1 \sim 2$$$ problems!

→ Ответить
»
16 месяцев назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

Hardest problem A I have ever seen

→ Ответить
»
16 месяцев назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

Probably it was the hardest AGC ever.

But problem A was really nice.

→ Ответить
»
16 месяцев назад, # |
  Проголосовать: нравится +23 Проголосовать: не нравится

So hard

→ Ответить
»
16 месяцев назад, # |
  Проголосовать: нравится +21 Проголосовать: не нравится

Maybe some helpful pics on the solution of B:

odd n
even n
→ Ответить
»
16 месяцев назад, # |
  Проголосовать: нравится +8 Проголосовать: не нравится

Some hints for problem A, or maybe progressive hints with solution?
I build this recurrence, where $$$F(n,k)$$$ denotes answer for $$$n$$$ and $$$k$$$.
$$$F(n,k) = F(n-1, F(n-1, k-1))$$$

Bur I could not progress any further.

→ Ответить
»
16 месяцев назад, # |
  Проголосовать: нравится +106 Проголосовать: не нравится

This is just sad. Wait, no, not just sad. Sad and enraging. Great job!

→ Ответить
»
16 месяцев назад, # |
← Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

Feel lucky to solve A, no idea how prove it. I just print out small cases, and notice that all numbers seems wandering about its original position, then I print out the drift for each position, then the pattern shows up:



  1  -1 
  1   1  -2 
  1  -1   1  -1 
  1   2  -2   1  -2  <--separator, the two non-zero triangles below are the same as above
  1  -1   0   0   1  -1 
  1   1  -2   0   1   1  -2 
  1  -1   1  -1   1  -1   1  -1 
  1   2  -2   2  -2   2  -2   1  -2   <---separator, the two non-zero triangles the same as above 
  1  -1   0   0   0   0   0   0   1  -1 
  1   1  -2   0   0   0   0   0   1   1  -2 
  1  -1   1  -1   0   0   0   0   1  -1   1  -1 
  1   2  -2   1  -2   0   0   0   1   2  -2   1  -2 
  1  -1   0   0   1  -1   0   0   1  -1   0   0   1  -1 
  1   1  -2   0   1   1  -2   0   1   1  -2   0   1   1  -2 
  1  -1   1  -1   1  -1   1  -1   1  -1   1  -1   1  -1   1  -1 
  1   2  -2   2  -2   2  -2   2  -2   2  -2   2  -2   2  -2   1  -2  <---separator, same here
  1  -1   0   0   0   0   0   0   0   0   0   0   0   0   0   0   1  -1 
  1   1  -2   0   0   0   0   0   0   0   0   0   0   0   0   0   1   1  -2 
  1  -1   1  -1   0   0   0   0   0   0   0   0   0   0   0   0   1  -1   1  -1 
  1   2  -2   1  -2   0   0   0   0   0   0   0   0   0   0   0   1   2  -2   1  -2 
  1  -1   0   0   1  -1   0   0   0   0   0   0   0   0   0   0   1  -1   0   0   1  -1 
  1   1  -2   0   1   1  -2   0   0   0   0   0   0   0   0   0   1   1  -2   0   1   1  -2

Strange feelings for solving A this way.... Really don't like reaching to conclusions without proof, but this time, I feel really happy with myself.....

→ Ответить
  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +8 Проголосовать: не нравится

    It is similar to Sierpiński triangle.

    Output
    → Ответить
»
16 месяцев назад, # |
  Проголосовать: нравится +48 Проголосовать: не нравится

Unpleasant as hell, expected nothing else.

→ Ответить
»
16 месяцев назад, # |
← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

.

→ Ответить
»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I'm not sure about my solution to E. While doing DP (being in box $$$[0, 2^k-1]$$$ move from $$$a$$$ to $$$b$$$ and calculate the shortest path for each mask) I think that when I consider interval $$$[0, 2^k-1]$$$ I only allow to move from $$$2^{k-1}-1$$$ to $$$2^{k-1}$$$ at most twice (again, I'm not sure about that).

→ Ответить
  • »
    »
    16 месяцев назад, # ^ |
      Проголосовать: нравится +41 Проголосовать: не нравится

    That is correct. Proof (due to maroonrk):

    Consider the scope $$$[0, 2^{k + 1})$$$, and suppose we have two blocks of operations that look like this:

    $$$2^k - 1 \to 2^k = a_0 \to a_1 \to \ldots \to a_X = 2^k - 1$$$.

    Let $$$a_0, \ldots, a_X$$$ and $$$b_0, \ldots, b_Y$$$ are the blocks. We will try to merge them to obtain $$$2^k - 1 = c_0 \to c_1 \to \ldots \to c_Z = 2^k - 1$$$, so that all XORs are applied the same number of times as before. We want to have $$$c_z = (2^k - 1) \oplus a_x \oplus b_y$$$, where $$$x, y$$$ are non-decreasing (in $$$z$$$).

    Put $$$c_0 = (2^k - 1) \oplus a_0 \oplus b_0$$$. In general, let $$$c_z = (2^k - 1) \oplus a_x \oplus b_y$$$.

    • If, say $$$x = X$$$ (there are no more operations in the first block), then $$$c_z = b_y$$$, and we can apply the rest of the operations in $$$b$$$.
    • If $$$a_x \to a_{x + 1}$$$ is a XOR, apply it to obtain $$$c_{z + 1} = (2^k - 1) \oplus a_{x + 1} \oplus b_y$$$.
    • Suppose that both $$$a_x \to a_{x + 1}$$$ and $$$b_y \to b_{y + 1}$$$ are $$$+1$$$s. If the carries happen in the same bit, we also have $$$c_z = (2^k - 1) \oplus a_{x + 1} \oplus b_{y + 1}$$$. Otherwise, if $$$a$$$ has the lowest carry bit of the two, then $$$c_z + 1 = c_{z + 1} = (2^k - 1) \oplus a_{x + 1} \oplus b_y$$$ by looking at explicit bit expansion of $$$c_z$$$. Note that the latter can not result in $$$2^k - 1 \to 2^k$$$, as this is the highest possible carry.

    We did not anticipate solutions that would explicitly use this idea (editorial described a Dijkstra-based solution where multiple carries are allowed).

    → Ответить
»
16 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

In editorial for problem C, What does PIE stand for ?

→ Ответить
»
16 месяцев назад, # |
← Rev. 2   Проголосовать: нравится +20 Проголосовать: не нравится

Does anybody have any ideas on what could the solution for C be if $$$b_i$$$ were not necessarily increasing?

→ Ответить
  • »
    »
    16 месяцев назад, # ^ |
    ← Rev. 5   Проголосовать: нравится +30 Проголосовать: не нравится

    Consider the case when we have $$$n$$$ blocks $$$(4i, 4i + 2), (4i + 1, 4i + 3)$$$ of two pairs each, and $$$m$$$ pairs $$$(4a_i + 1.5, 4b_i + 1.5)$$$ (ties between pairs irrelevant). If $$$G$$$ is the graph with $$$n$$$ vertices and $$$m$$$ edges $$$(a_i, b_i)$$$, the answer is the sum of $$$4^x 3^{n - x}$$$, where the sum is over all ways to choose an endpoint of every edge, $$$x$$$ is the number of covered vertices (i.e. chosen at least once). This doesn't appear to be in $$$P$$$, although I have no rigorous proof of $$$NP$$$-hardness or anything like that (technically #$$$P$$$-hardness is a better characterization, naturally I mean polynomial-time solvability).

    I guess an even simpler example is when each block is simply $$$(2i, 2i + 1)$$$, edges are $$$(2a_i + 0.5, 2b_i + 0.5)$$$, and the summands are simply $$$2^x$$$.

    → Ответить
»
16 месяцев назад, # |
← Rev. 2   Проголосовать: нравится +25 Проголосовать: не нравится

For problem F, we should be able to do better than $$$O(N^5)$$$.

Note that if we set $$$x = y$$$, we are just computing the characteristic polynomial of the matrix. This can be computed in $$$O(N^3)$$$ time, instead of using $$$O(N)$$$ evaluations of matrix determinant (see https://ipsen.math.ncsu.edu/ps/charpoly3.pdf or https://rkm0959.tistory.com/141 ). (In fact, I believe we can compute this in $$$O(N^\omega)$$$ time.)

Now, instead of setting $$$x = y$$$, let's fix the ratio of $$$r = x/y$$$. Then, we can run black-box characteristic polynomial for $$$O(N)$$$ different values of $$$r$$$ and then polynomial interpolate to get our desired 2-variable polynomial $$$A$$$. This runs in $$$O(N^4)$$$ time.

I'm not sure if we can do better; I wasn't able to to extend the char-poly algorithm directly, and intuitively, it kind of makes sense that adding a dimension should increase the runtime (at the very least, it would be very surprising if the 3-variable analogue could be done in $$$O(N^3)$$$ time).

→ Ответить
»
11 месяцев назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Nice contest

→ Ответить