We will hold AtCoder Grand Contest 061. This contest counts for GP30 scores.
- Contest URL: https://atcoder.jp/contests/agc061
- Start Time: http://www.timeanddate.com/worldclock/fixedtime.html?iso=20230212T2100&p1=248
- Duration: 180 minutes
- Number of Tasks: 6
- Writer: Endagorion
- Tester: Golovanov399, potato167
- Rated range: 1200 -
The point values will be 500-800-800-1000-1400-2000.
We are looking forward to your participation!
Is atcoder suited for beginner?
Yes, but not this contest.
Mass hating that.
Mass hating that.
Karol_programista, did you write this comment during our last team contest?
Atcoder holds Atcoder Beginner Contests on most Saturdays. Today I took part in one and learnt something new
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!
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.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?
In regular, maybe. In AGC, it is cool to get AC on A
Friendly 1-hour reminder!
Finally, "$$$0$$$ Solved" Round!
There we go :3 Another unsolvable A.
Hope for a positive Δ and solve $$$1 \sim 2$$$ problems!
Problem $$$A$$$ of Grand Contest used to be of difficulty [1200-2000] acc to Atcoder for CF it is [1400-2400]
B might be 3000+ lol this happened before. Maybe a second time?
Maybe.I think B is harder than C.
orz 3150 perf man
lol my guess is right. Skip B if you see weird standings mid-contest.
Hardest problem A I have ever seen
Probably it was the hardest AGC ever.
But problem A was really nice.
So hard
Maybe some helpful pics on the solution of B:
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.
This is just sad. Wait, no, not just sad. Sad and enraging. Great job!
Wow! Um_nik didn't solve a binary search question. I won't feel as bad anymore :D (Huge fan btw.)
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:
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.....
It is similar to Sierpiński triangle.
cool~
Unpleasant as hell, expected nothing else.
.
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).
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$$$.
We did not anticipate solutions that would explicitly use this idea (editorial described a Dijkstra-based solution where multiple carries are allowed).
In editorial for problem C, What does PIE stand for ?
I believe it's "Principle of Inclusion and Exclusion"
Does anybody have any ideas on what could the solution for C be if $$$b_i$$$ were not necessarily increasing?
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$$$.
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).
Nice contest