### antontrygubO_o's blog

By antontrygubO_o, 2 months ago,

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

The point values will be added soon.

I would like to thank:

• maroonrk for the amazing coordination of this round, for improving one problem, and for allowing me to host my third AGC (and third AGC in 2022). I also want to congratulate him on winning gold in ICPC 2021!
• maspy, dario2994, errorgorn, timreizin, Um_nik, 244mhq for testing the contest.
• MikeMirzayanov for the great Polygon platform

I really hope you will like the problems.

We are looking forward to your participation!

UPD1: Point values are $500$ — $700$ — $1100$ — $1100$ — $1400$ — $1900$

The winners are:

1. ksun48

2. Petr

3. tatyam

5. tourist

• +358

 » 2 months ago, # |   +22 omg anton AGC round question btwWhy does this post have the "december cookoff" tag? isn't that tag supposed to be on a codechef round announcement?
•  » » 2 months ago, # ^ |   +3 Damn! Your handle is cursed. You get downvoted even if you say nothing wrong. By the way, this post shouldn't have 'December cookoff' tag.
 » 2 months ago, # |   +66 ANTON ORZ
•  » » 2 months ago, # ^ |   +63 AEREN ORZ
•  » » » 2 months ago, # ^ |   +34 Interesting that you guys use capital letters ORZ, because it originates from the emoticon orz that depicts kneeling person, while ORZ doesn't quite look like that
 » 2 months ago, # |   +174 Time to wake up at 4am just to solve 0 problems and cry myself to sleep…
•  » » 2 months ago, # ^ |   +82 Time to skip the round completely because I failed so miserably at testing that Anton forgot to mention me as a tester.
•  » » 2 months ago, # ^ |   +8 Facts :(
 » 2 months ago, # |   +5 I also see AGC 060 in schedule, that's great!
 » 2 months ago, # |   +25 Havn't see AGC for a long time.Now it's time for get more rating.Hope to solve two problems quickly.
 » 2 months ago, # |   +8 I have not taken part in AGC. Who can tell me the difficulty of those problems?
•  » » 2 months ago, # ^ |   +69 Div 0.8
•  » » 2 months ago, # ^ |   +27 Lately it's like a contest starting from d1B/C , so div 0.5 maybe?
•  » » 2 months ago, # ^ |   +19 Div 0.69, to be precise
 » 2 months ago, # |   +9 My first rated AGC. Just qualified for rated AGC today through today's ABC. (Rating 1213)
 » 2 months ago, # |   +45
 » 2 months ago, # |   +73 How Anton's mind works?
 » 2 months ago, # |   +68 One more time, a kindly reminder to AtCoder admins, that it would be very nice to update koltin compiler. If you have some technical issues with this update, please contact me, it's quite probably, that I would be able to help you.
 » 2 months ago, # |   +39 The contest starts in 20 minutes! Please, join!
 » 2 months ago, # |   +33 As a contestant, give me rating.
•  » » 2 months ago, # ^ | ← Rev. 3 →   -100 Nice constructive problem B! Solved it!Increasement of count of AC testcases gave me courage until I solved it. Thank Anton.
•  » » » 2 months ago, # ^ |   +14 Managed to solve B thanks to this comment lol.
•  » » 2 months ago, # ^ | ← Rev. 3 →   +31 LinkANTOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOON!
 » 2 months ago, # | ← Rev. 2 →   -98 Make a conclusion of the problems: Counting,Constructing,and Validating:)Orz DataStructures our red sun! He won first AC of C.
 » 2 months ago, # | ← Rev. 2 →   +311 Me in AGCsAs a cyan: 0 solvesAs a red: 0 solves but with more wrong submissions
 » 2 months ago, # |   +60 First time can't solve any problem in a single contest.Anton, you did very well.
 » 2 months ago, # |   +48 Congrats to Anton for making the most difficult AGC A ever. Great job. I didn't solve it for two hours.AGC045A has a difficulty of 2070.AGC059A has a difficulty of 2129.
•  » » 2 months ago, # ^ |   +23 Unfortunately AGC059A was rated 1970 on kenkoooo but I don't know the reason :(
•  » » » 2 months ago, # ^ |   +5 Sorry, then it should be the third one. The two harder than it are AGC045A(2070) and AGC050A(1973).AntontryGub Contest (or Anton Grand Contest) is still too crazy for me anyway.
•  » » 2 months ago, # ^ |   +13 I had no idea how to solve it either!
 » 2 months ago, # |   +22 How to do task A? :/
 » 2 months ago, # |   +67
 » 2 months ago, # |   +87 My solution to A, which I grossly overcomplicated: SolutionLet the substring be $s_1s_2s_3\ldots s_m$ of length $m$. We want to make the number of indices $2 \le i \le m$ where $s_i \neq s_{i - 1}$ zero (call these bad indices). In one move, we can reduce the number of these indices by at most $2$, since an operation will not change the number of bad indices within a substring. Also, a substring has at most two neighbors (to the left and the right) that it can merge with. Therefore, if there are $x$ bad indices, the minimum number of moves it needed to clear out all the bad indices is $\lceil \frac{x}{2} \rceil$.Let's consider the types of bad indices. We can split them into two types: $s_i = s_{i - 1} + 1 \bmod 3$ (for example, AB, BC, CA) $s_i = s_{i - 1} - 1 \bmod 3$ (for example, AC, CB, BA) Note that if we have two bad indices of different types, we can use them to reduce the number of bad indices by $2$. For example: If we have AB.....CB, we can change it to A[A......B]B by selecting the middle substring and applying the permutation A, C, B. If we have AB.....BA, we can change it to A[A......A]A by selecting the middle substring and applying the permutation B, A, C (note that C, A, B would also work). The other cases can be shown to work in the same way. Also note that if we apply one of the permutations A, C, B, B, A, C, or C, B, A to some substring, all the bad indices in the substring will get their types flipped.Using these two kinds of moves, we can do the following: while there is at least one bad index of both type 1 and 2, we can remove one of each in a single move. Eventually, there will only be $y$ bad indices of a single type.Suppose WLOG that this remaining type is type 1, and that the resulting string has the form ABCABCABCABC.... Then, let's pick the middle bad index and apply one of the permutations A, C, B, B, A, C, or C, B, A to the last half of the bad indices. If we pick which one to apply correctly, we can reduce the number of bad indices by 1 and flip the type of the last half of the indices. For instance, if we have ABCA...BC[ABC...CABC] and we want to flip the latter half, we can choose the permutation C, B, A to get ABCA...BC[CBA...ACBA].Now, if we flip the latter half, we can keep removing two at a time until we get to zero. This solution is optimal for odd $x$, since it achieves $\lceil \frac{x}{2} \rceil$ operations (the minimum possible). However, for even $x$, it's possible that this solution will take $\frac{x}{2} + 1$ operations: which is worse than the $\frac{x}{2}$ minimum possible.How can we tell if $\frac{x}{2}$ is achievable? Note that we can also apply operations on strings of the form A[B.....A]B -> A[A....B]B. If our string only has bad indices of type 1, a little math will show that we can only apply this operation to substrings [B...A] of length $y$ such that $y \equiv 1 \bmod 3$. A little more math, and we can see that using this operation, we can remove any multiple of $6$ bad indices of the same type at a time (e.g. using $y = 4$, [1111]11 -> 2211 -> 2[21]1 -> [21] -> empty). So, if the string had $t_1$ and $t_2$ bad indices of each type at the start, and $t_1 + t_2$ is even, the answer will be $\frac{t_1 + t_2}{2}$ (the minimum achievable) if $|t_1 - t_2| \equiv 0 \bmod 6$.It turns out that not only is this a sufficient condition, it is also necessary. If you work out the cases, you'll find that any operations that removes $2$ bad indices does not change the value of $|t_1 - t_2| \equiv 0 \bmod 6$ (you only need to check $4$ cases where the first bad index is AB, the other cases are symmetric).So, if $t_1 + t_2$ is odd, then the answer is $\lceil \frac{t_1 + t_2}{2} \rceil$. Otherwise, the answer will be $\frac{t_1 + t_2}{2}$ if $|t_1 - t_2| \equiv 0 \bmod 6$, and $\frac{t_1 + t_2}{2} + 1$ otherwise.Luckly the code is pretty short compared to the explanation :P
 » 2 months ago, # |   +78 How to get a good result in AGC? Find and understand the right paper 6 clicks deep from a Google search (paper, screencast — about 10 minutes from searching to start of coding).Next step: learn to actually solve those problems :) Thanks for the round!
•  » » 5 weeks ago, # ^ |   0 I did the contest virtually, and couldn't solve the problem either. However, amusingly, I've just found that the problem has a sneaky reduction to an old problem of mine (which you managed to solve in contest, if I'm not mistaken). =)
 » 2 months ago, # |   +6 Can someone give an example of a tricky sample case for A. I am hard time figure out fault in my WA approach.
 » 2 months ago, # |   +46 Problem A said this is the last ABC problem. So next time you may meet 123 problems instead of ABC problems (like E).
 » 2 months ago, # |   +10 Thank you for the round.
 » 2 months ago, # | ← Rev. 2 →   0 Is B solveable in the maximum case? I misread it and probably solved it after an hour's struggle.