maroonrk's blog

AtCoder Grand Contest 061 Announcement
By maroonrk, history, 3 years 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?
»
3 years ago, hide # |
 
Vote: I like it +10 Vote: I do not like it

Is atcoder suited for beginner?

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +49 Vote: I do not like it

Friendly 1-hour reminder!

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

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it -8 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
 
Vote: I like it +16 Vote: I do not like it

Hardest problem A I have ever seen

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
Vote: I like it +23 Vote: I do not like it

So hard

→ Reply
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
 
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
»
3 years ago, hide # |
← 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
  • »
    »
    3 years ago, hide # ^ |
     
    Vote: I like it +8 Vote: I do not like it

    It is similar to Sierpiński triangle.

    Output
    → Reply
»
3 years ago, hide # |
 
Vote: I like it +48 Vote: I do not like it

Unpleasant as hell, expected nothing else.

→ Reply
»
3 years ago, hide # |
← Rev. 2  
Vote: I like it 0 Vote: I do not like it

.

→ Reply
»
3 years ago, hide # |
 
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
  • »
    »
    3 years ago, hide # ^ |
     
    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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

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

→ Reply
»
3 years ago, hide # |
← 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
  • »
    »
    3 years ago, hide # ^ |
    ← 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
»
3 years ago, hide # |
← 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
»
3 years ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

Nice contest

→ Reply