I am glad to invite you to AtCoder Grand Contest 052. This contest counts for GP30 scores.
- Contest URL: https://atcoder.jp/contests/agc052
- Start time: Sunday, March 7, 12:00 UTC
- Duration: 160 minutes
- Number of Tasks: 6
- Writer: antontrygubO_o
- Rated range: 1200+
I would like to thank:
- maroonrk for allowing me to host a contest on AtCoder and for the great coordination of this round
- 244mhq, gamegame, TheOneYouWant, hugopm, HIR180 for testing this round
- MikeMirzayanov for the great Polygon platform (only Polygon this time)
Statements are very short, and I really hope you will like the problems.
We are looking forward to your participation!
UPD 1: The point values will be 400-800-1000-1000-1500-2000, and the duration is decided to be 160 minutes
UPD 2: Congratulations to the winners!
Thanks for your participation :P
Can we say "All hail our emperor anton" here?
Why is it 1200+ rated , I am new to atcoder and currently brown , I was waiting for this for a week until I came to knew that it is 1200+ rated (Today) . I know I can participate unofficially but still rated contest have their own charm , This is not right to make them rated for 1200+ according to me . Y have a lower threshold?
Click
Okk
Finally our emperor created a round on his favourate website with his favourate problems. :qq:
As a tester (my only comment as tester so far, despite having tested other rounds), this round seems inspired and I'm amazed at the quality of problems. I would highly recommend participating to have your mind blown.
P.S. All hail our emperor Anton
How many problems did you propose in order to get 6 accepted?
9, but mostly to fix the difficulty balance
It was meant to be joke. I would like to sincerely apologize to Anton. You are among the people whose name is enough in announcement to keep me awake at 1am during some contests. Sorry!
The coordinator rejects bad problems. If you propose $$$100$$$ bad problems, most of them will be rejected. If you propose $$$6$$$ good problems, most of them will be accepted.
The problems were beautiful.
Every time I read problem A of any AGC, I question my existence...
Every time i read your name, it answers all my doubts about me.
I can stare at a problem only for so long. someone pls tell how to solve B after contest ends
Edit: Editorial out right after contest. Thanks!
This contest was genius and it was 100% worth destroying my sleep schedule to fail on it. All hail our emperor Anton.
Also fun fact: I figured out B when I thought about what happens if the tree is a star — if we consider everything XOR'd by $$$X$$$, then $$$(w_1 \oplus X, w_2 \oplus X, \ldots, w_k \oplus X)$$$ changes to $$$(w_1 \oplus X \oplus (w_2 \oplus X), 0 \oplus w_2 \oplus X, \ldots, w_k \oplus X \oplus (w_2 \oplus X))$$$, which is $$$(w_1 \oplus w_2, X \oplus w_2, \ldots, w_k \oplus w_2)$$$, so $$$w_2$$$ and $$$X$$$ only swap places. From that, I intuited that we must be able to add a variable and convert the problem to swapping, and what's a better extra variable than a vertex weight! Kinda roundabout, but a natural way to look at a problem — look at a specific case and generalise.
I have a question how can we prove that W can be generated after doing the operation any number of times
Show some mercy, it was so hard ;_;
After solving A, I was like: "Thanks for cyberbulling"
Can't agree more. I was only able to solve it coz I saw jiangly solved it under 4 min, so thought of some constructive approach.
After reading the editorial, I realize that I completely misread problem B during the contest. I thought it was $$$w := w_1 \oplus w$$$ instead of $$$w_1 := w_1 \oplus w$$$. In hindsight I forgot to apply the rule of thumb that pronouns are usually intended to have the most recent possible referent, or could have noticed the potential ambiguity and asked for clarification. But the wording of this problem could definitely have been improved to avoid this issue.
Still, nice contest! C, D, E were all very nice problems, and I might well have liked B if I understood it. F seems above my pay grade (but that's not a bad thing), and I would have liked if A's solution was more interesting (but it's not a bad problem).
Hopefully your next contest will be rated for me.
I also misread problem B exactly like you.
And I have a very short solution for that problem.
Let $$$f_u$$$ be sum xor of all edge's weight that is incident to u. We can see that after operation $$$(u, v)$$$, $$$f_u$$$ and $$$f_v$$$ are swapped.
So we can prepare multiset of $$$ms_1$$$ of all $$$f_u$$$ in the beginning, and $$$ms_2$$$ of all $$$f_u$$$ in the end. It's "YES" if $$$ms_1 == ms_2$$$ and "NO" otherwise.
It took me 20 minutes :(
I have a different approach for task E :
Consider $$$a_i=[(s_{i+1}-s_i)\bmod 3 = 1]$$$. Changing a letter in the middle is equivalent to swapping two consecutive elements in $$$a$$$, and changing the first or the last letter is equivalent to changing the first of the last element in $$$a$$$. It's easy to see that if you changed $$$a_1$$$ from $$$0$$$ to $$$1$$$, you will never change $$$a_1$$$ from $$$1$$$ to $$$0$$$. (However, it could be moved to the end and changed as $$$a_{n-1}$$$, but it seems this could happen only when $$$n\le 3$$$ or all $$$a_i$$$ are equal, though I didn't prove it)
Iterate how many times you changed $$$a_0$$$ from $$$0$$$ to $$$1$$$ (or from $$$1$$$ to $$$0$$$), suppose the number is $$$x$$$. $$$x$$$ should be equal to $$$t_0-s_0$$$ modulo $$$3$$$. For each $$$x$$$ you could calculate the answer in $$$O(n)$$$. It turns out the answer is a convex function of $$$x$$$, thus the minimum can be calculated in $$$O(n\log n)$$$ using ternary search.
How to prove the ternary search?
Suppose you got the arrays $$$a$$$ from $$$s$$$ and $$$b$$$ from $$$t$$$, let $$$p_i$$$ is the $$$i$$$-th $$$1$$$ in $$$a$$$, and $$$q_i$$$ is the $$$i$$$-th $$$1$$$ in $$$b$$$. Add infinite $$$0$$$ to at the beginning of $$$p$$$ and $$$q$$$ and infinite $$$n$$$ at the end, then the answer for a given $$$x$$$ is
which is convex. ($$$|x-y|=\sum_v |[x>v]-[y>v]|$$$, so you only need to consider a special case where all numbers are $$$0$$$ or $$$1$$$, where the answer is $$$|x-\mathrm{Constant}|$$$)
In the proof of sufficiency of max limit of number of 1's in Problem C's editorial, I think the claim that if $$$y$$$ was the most frequent at some time then at any later time for any element $$$z$$$ (number of $$$z$$$'s)<=(number of $$$y$$$'s+1) is not correct. Here's an example of the algorithm applied on the array $$$[1,1,2,2,4,4]$$$ with $$$P=5$$$.
Pick any $$$x$$$ having max frequency so I pick $$$1$$$ in the first move. In the second move max frequency occurs for both $$$2$$$ and $$$4$$$ but I choose to let $$$x=4$$$. However $$$1+4$$$ is divisible by $$$5$$$, so I pick $$$y=1$$$ and thus the elements picked by me are $$$1$$$ $$$1$$$ $$$4$$$ in that order.
However now I observe that elements left with me are $$$[2,2,4]$$$, the frequency of $$$2$$$ is $$$2$$$, while frequency of $$$1$$$ is $$$0$$$. But I had picked $$$1$$$ in the first move so the frequency of $$$2$$$($$$=2$$$) should not have exceeded frequency of $$$1+1$$$($$$=1$$$). But this is a contradiction.
If I have understood anything incorrectly in editorial please let me know. I think letting $$$y$$$ to be random if $$$cur+x$$$ is divisible by $$$P$$$ is causing problem.