I am glad to invite you to AtCoder Grand Contest 059. This contest counts for GP30 scores.
- Contest URL: https://atcoder.jp/contests/agc059
- Start time: Sunday, December 4, 12:00 UTC
- Duration: 180 minutes
- Number of Tasks: 6
- Writer: antontrygubO_o
- Rated range: 1200+
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$$$
UPD2: Thanks for your participation!
The winners are:
1. ksun48
2. Petr
3. tatyam
4. hitonanode
5. tourist
omg anton AGC round
Why does this post have the "december cookoff" tag? isn't that tag supposed to be on a codechef round announcement?
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.
ANTON ORZ
AEREN ORZ
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
Time to wake up at 4am just to solve 0 problems and cry myself to sleep…
Time to skip the round completely because I failed so miserably at testing that Anton forgot to mention me as a tester.
Facts :(
I also see AGC 060 in schedule, that's great!
Havn't see AGC for a long time.
Now it's time for get more rating.
Hope to solve two problems quickly.
I have not taken part in AGC. Who can tell me the difficulty of those problems?
Div 0.8
Lately it's like a contest starting from d1B/C , so div 0.5 maybe?
Div 0.69, to be precise
My first rated AGC. Just qualified for rated AGC today through today's ABC. (Rating 1213)
GP30 standings https://clist.by/standings/atcoder-race-ranking-2022-33151256/
How Anton's mind works?
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.
The contest starts in 20 minutes! Please, join!
As a contestant, give me rating.
Nice constructive problem B! Solved it!
Increasement of count of AC testcases gave me courage until I solved it. Thank Anton.
Managed to solve B thanks to this comment lol.
Link
ANTOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOOON!
Make a conclusion of the problems: Counting,Constructing,and Validating:)
Orz JianfengZhu our red sun! He won first AC of C.
Me in AGCs
As a cyan: 0 solves
As a red: 0 solves but with more wrong submissions
First time can't solve any problem in a single contest.
Anton, you did very well.
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.
Unfortunately AGC059A was rated 1970 on kenkoooo but I don't know the reason :(
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.
I had no idea how to solve it either!
How to do task A? :/
My solution to A, which I grossly overcomplicated:
Let 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:
AB
,BC
,CA
)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:
AB.....CB
, we can change it toA[A......B]B
by selecting the middle substring and applying the permutationA, C, B
.AB.....BA
, we can change it toA[A......A]A
by selecting the middle substring and applying the permutationB, A, C
(note thatC, 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
, orC, 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 permutationsA, C, B
,B, A, C
, orC, 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 haveABCA...BC[ABC...CABC]
and we want to flip the latter half, we can choose the permutationC, B, A
to getABCA...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
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!
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). =)
Can someone give an example of a tricky sample case for A. I am hard time figure out fault in my WA approach.
Problem A said this is the last ABC problem. So next time you may meet 123 problems instead of ABC problems (like E).
Thank you for the round.
Is B solveable in the maximum case? I misread it and probably solved it after an hour's struggle.