### antontrygubO_o's blog

By antontrygubO_o, 7 weeks ago,

I am glad to invite you to AtCoder Grand Contest 052. This contest counts for GP30 scores.

I would like to thank:

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!

• +407

 » 7 weeks ago, # |   +153
 » 7 weeks ago, # |   +54 Can we say "All hail our emperor anton" here?
 » 7 weeks ago, # |   +8 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?
•  » » 7 weeks ago, # ^ |   +3
•  » » » 7 weeks ago, # ^ |   0 Okk
 » 7 weeks ago, # | ← Rev. 2 →   +43 Finally our emperor created a round on his favourate website with his favourate problems. :qq:
 » 7 weeks ago, # |   +113 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
•  » » 6 weeks ago, # ^ |   -14 All hail our emperor Anton.
•  » » » 6 weeks ago, # ^ |   -20 I shouldn't have done that...
 » 7 weeks ago, # |   +61 How many problems did you propose in order to get 6 accepted?
•  » » 7 weeks ago, # ^ |   +65 9, but mostly to fix the difficulty balance
•  » » » 7 weeks ago, # ^ | ← Rev. 2 →   -41 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!
•  » » » » 7 weeks ago, # ^ |   +74 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.
•  » » » » » 7 weeks ago, # ^ |   -37 PS: Sorry if I wrote something wrong :(
•  » » » » » 6 weeks ago, # ^ | ← Rev. 2 →   +18 The problems were beautiful.
 » 6 weeks ago, # |   +293 Every time I read problem A of any AGC, I question my existence...
•  » » 6 weeks ago, # ^ |   +31 Every time i read your name, it answers all my doubts about me.
 » 6 weeks ago, # | ← Rev. 2 →   +46 I can stare at a problem only for so long. someone pls tell how to solve B after contest endsEdit: Editorial out right after contest. Thanks!
 » 6 weeks ago, # |   +78 This contest was genius and it was 100% worth destroying my sleep schedule to fail on it. All hail our emperor Anton.
 » 6 weeks ago, # |   +11 tfw you know how to solve C but are just a bit too slow because you thought you could squeeze in a slower solution 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.
 » 6 weeks ago, # |   +173 Show some mercy, it was so hard ;_;
 » 6 weeks ago, # |   +80 After solving A, I was like: "Thanks for cyberbulling"
•  » » 6 weeks ago, # ^ |   -17 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.
 » 6 weeks ago, # | ← Rev. 2 →   0 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.
•  » » 6 weeks ago, # ^ | ← Rev. 2 →   +3 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 :(
 » 6 weeks ago, # |   +27 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.
•  » » 6 weeks ago, # ^ |   +18 How to prove the ternary search?
•  » » » 6 weeks ago, # ^ | ← Rev. 2 →   +17 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 $\sum_{i=-\infty}^\infty |p_{i+x}-q_i|$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}|$)
 » 6 weeks ago, # |   0 In problem B how can we can we say that the weight W is always acheivable after a certain number of operations? Although mathematically it is all fine but can we intuitively deduce that W (equal to xor of all ai's and all bi's as stated in the editorial) can always be acheived?