### antontrygubO_o's blog

By antontrygubO_o, 15 months ago,

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

The point values will be 400700900120015001800

I would like to thank:

Problem statements will be short again, and I really hope that you will like the problems. However, I have to warn you that contest will be closer to ABC than to AGC...

We are looking forward to your participation!

UPD1: Thanks for your participation!

The winners are:

1. ksun48

2. tourist

3. djq_cpp

5. amiya

Special congratulations to tranquility , the only person to solve F.

Sadly, nobody got E in the contest time, though a few people were close. I encourage you to try it, or to read editorial, I think that it's the best problem I ever invented.

I hope you enjoyed the contest!

• +551

| Write comment?
 » 15 months ago, # |   +63 The duration in the contest page is 150 minutes. Which one is correct?
•  » » 15 months ago, # ^ |   +45 180, info on AtCoder page will be updated soon
 » 15 months ago, # |   +56 I did nothing tbh.
 » 15 months ago, # | ← Rev. 4 →   +10 As a tester, I can confirm the contest is very well balanced in terms of topics and difficulty. Enjoy!
•  » » 15 months ago, # ^ |   +99 Yeah, balanced in terms of topics XD
 » 15 months ago, # |   +378 Always wanted to do something like this... The point values will be 400 — 700 — 900 — 1200 — 1500 — 1800 These point values look like the problems are solvable. As a tester, I assure you they are not. I'm not saying that the contest is bad or anything, the problems are amazing and unbelievable. Like, I can't believe that there are people who are able to solve them.
 » 15 months ago, # |   +43 Wow, this is the first AGC in 4 months, looking forward to the contest.Your last AGC is great but I forgot to participate. I don't want to forget yet again.
 » 15 months ago, # |   +49 A reminder that the contest starts in less than an hour! Please, join :)
 » 15 months ago, # | ← Rev. 2 →   +131 Meme
 » 15 months ago, # |   +3 Good luck, everyone that joined.
 » 15 months ago, # |   +91 "However, I have to warn you that contest will be closer to ABC than to AGC..."This has been the worst trade deal in the history of trade deals, maybe ever.
•  » » 15 months ago, # ^ | ← Rev. 2 →   +19 Actually It is closer to ABC . The first two problems involved ABC Still I couldn't solve any . :(
•  » » 15 months ago, # ^ | ← Rev. 2 →   +3 the names of the problems are really ABC!but for the content ......It's too hard to me :(
 » 15 months ago, # |   +72 So I've actually succeeded in predicting the existence of a problem about 3-value strings. I was kind of wondering this announcement was fair... (though the prediction helped me only by $\varepsilon$).Anyway the problems are really nice, thanks!
 » 15 months ago, # |   +129 there is one impostor among us
•  » » 15 months ago, # ^ |   0 tour1st in atcoder is djq_cpp. He maybe the second youngest LGM in codeforces(16 years old) and he became a LGM when he was only 14. He is very likely going to IOI2022.
•  » » » 15 months ago, # ^ |   +3 Who is the youngest LGM on codeforces and what is his age
•  » » » » 15 months ago, # ^ |   +3 djq_cpp was the youngest, but now orzdevinwang is. They became LGM both in age 14.
 » 15 months ago, # |   +16 I kinda cheesed A with a randomized solution (cleaned up a little from my in-contest submission). Basically I try greedily choosing the maximum LCS between $\texttt{AA...AABB...BBCC...CC}$ and $S$, going through all permutations of $\texttt{ABC}$.On my computer, it runs under 2s for maxtests, but just barely. Also, I submitted it once and got WA (but really TLE because I break once the time is almost up).Also nice tags :P tests=pretestshelloween
•  » » 15 months ago, # ^ | ← Rev. 2 →   +5 I also used the strategy and it passed.Maybe you should submit the solution a few times more,because it really depends on luck.I got TLE several times too.
 » 15 months ago, # |   +22 I think you got the wrong Belik
 » 15 months ago, # | ← Rev. 2 →   +48 XD, at this time, I participated in the qualification for ICPC 2022. Account owner — Ivan Bochkov (tranquility). He named his account my name.
•  » » 15 months ago, # ^ |   +19 Bruh, sorry for confusion :P
 » 15 months ago, # |   +228 I was so close to C but I didn't add if (m == n - 1 && m != 2) ans = (ans + 1) % p; :(
 » 15 months ago, # | ← Rev. 2 →   +29 How to deal with the bonus version (use only 5 subsequences) of A ?
•  » » 15 months ago, # ^ | ← Rev. 2 →   +11 Submission (same idea as IOI 2021/4) In the $3 \times 3$ matrix, after removing $3$ subsequences you have only $3$ distinct values, and one of them is $0$.
•  » » » 15 months ago, # ^ |   0 Thanks a lot :)
 » 15 months ago, # |   0 Can someone help me with this editorial Editorial What does shifting ith character to the left i times means and how AAAX can be transformed to XXXX. It's problem B of AGC.
•  » » 15 months ago, # ^ |   +13 Hint 1We can write 1 instead of A, 2 instead of C, and 3 instead of B. For example, string "CABA" will become [2,1,3,1]. Hint 2we can increase i-th element of that sequence by i. For example, [2,1,3,1] will become [2+0, 1+1, 3+2, 1+3] = [2, 2, 5, 4]. Hint 2.5Take everything modulo 3 Hint 3How do these changes affect transformations (ABC -> BCA -> CAB -> ABC)?
•  » » » 15 months ago, # ^ |   +3 Thanks Sir , Now I understood it . :)
•  » » » 15 months ago, # ^ |   0 I still do not get it.Problem says "...if is equal to ABC, BCA, or CAB...we can transform..."Editorial says "...we can transform string AAAX..."How can we transform a string AAAX when the problem statement basically says we can not?
•  » » » 15 months ago, # ^ |   +19 Amazing solution, but how did you or anyone else come up with it? Specially the "we can increase i-th element of that sequence by i and take mod 3" step blew my mind. How does one realize that he should do this step?
•  » » » » 15 months ago, # ^ |   +26 Beaufitul solutions arise from good problems, and that's why AGCs have such reputation :)First of all, actual answer is that you develop intuition of what you should do (and learn various techniques) by solving a lot of similarish problems.Having said that, one possible thought process might be: these transformations are a bit messy, we should try doing something about them. transformations on each letter are cyclic, i.e. A->B->C->A. what else can we do with transformations? For example, it might be nice if transformations were something like AAA -> BBB -> CCC -> AAA. wait a sec, we can do that for strings of len 3 by applying inverse of transformations on letters (A -> C -> B -> A) on the second letter once and on the third letter twice. we can also do it for strings of len >3 by applying it i times on i-th letter. This is equivalent to "we can increase i-th element of that sequence by i and take mod 3".
 » 15 months ago, # |   +5 How to solve bonus of C?
 » 14 months ago, # |   0 How to solve the bonus of D with low complexity? Means not use the algorithm mentioned in the editorial. Or maybe it can't.