maroonrk's blog

AtCoder Grand Contest 061 Announcement
By maroonrk, history, 15 months ago, In English

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!

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

Comments Comments (39)
| Write comment?
»
15 months ago, # |
  Vote: I like it +10 Vote: I do not like it

Is atcoder suited for beginner?

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +55 Vote: I do not like it

    Yes, but not this contest.

    → Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +48 Vote: I do not like it

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

    → Reply
    • »
      »
      »
      15 months ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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!

      → Reply
      • »
        »
        »
        »
        15 months ago, # ^ |
          Vote: I like it +8 Vote: I do not like it

        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.

        → Reply
        • »
          »
          »
          »
          »
          15 months ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          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?

          → Reply
          • »
            »
            »
            »
            »
            »
            15 months ago, # ^ |
              Vote: I like it +11 Vote: I do not like it

            In regular, maybe. In AGC, it is cool to get AC on A

            → Reply
»
15 months ago, # |
  Vote: I like it +49 Vote: I do not like it

Friendly 1-hour reminder!

→ Reply
»
15 months ago, # |
← Rev. 2   Vote: I like it +7 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
  Vote: I like it -8 Vote: I do not like it

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

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Problem $$$A$$$ of Grand Contest used to be of difficulty [1200-2000] acc to Atcoder for CF it is [1400-2400]

    → Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    B might be 3000+ lol this happened before. Maybe a second time?

    → Reply
»
15 months ago, # |
  Vote: I like it +16 Vote: I do not like it

Hardest problem A I have ever seen

→ Reply
»
15 months ago, # |
  Vote: I like it +23 Vote: I do not like it

Probably it was the hardest AGC ever.

But problem A was really nice.

→ Reply
»
15 months ago, # |
  Vote: I like it +23 Vote: I do not like it

So hard

→ Reply
»
15 months ago, # |
  Vote: I like it +21 Vote: I do not like it

Maybe some helpful pics on the solution of B:

odd n
even n
→ Reply
»
15 months ago, # |
  Vote: I like it +8 Vote: I do not like it

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.

→ Reply
»
15 months ago, # |
  Vote: I like it +106 Vote: I do not like it

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

→ Reply
»
15 months ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

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

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    It is similar to Sierpiński triangle.

    Output
    → Reply
»
15 months ago, # |
  Vote: I like it +48 Vote: I do not like it

Unpleasant as hell, expected nothing else.

→ Reply
»
15 months ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +41 Vote: I do not like it

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

    → Reply
»
15 months ago, # |
  Vote: I like it 0 Vote: I do not like it

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

→ Reply
  • »
    »
    15 months ago, # ^ |
      Vote: I like it +1 Vote: I do not like it

    I believe it's "Principle of Inclusion and Exclusion"

    → Reply
»
15 months ago, # |
← Rev. 2   Vote: I like it +20 Vote: I do not like it

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

→ Reply
  • »
    »
    15 months ago, # ^ |
    ← Rev. 5   Vote: I like it +30 Vote: I do not like it

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

    → Reply
»
15 months ago, # |
← Rev. 2   Vote: I like it +25 Vote: I do not like it

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

→ Reply
»
11 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice contest

→ Reply