Блог пользователя antontrygubO_o

Автор antontrygubO_o, 3 года назад, По-английски

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

4. hos.lyric

5. jqdai0815

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
  • Проголосовать: не нравится

»
3 года назад, # |
  Проголосовать: нравится +63 Проголосовать: не нравится

The duration in the contest page is 150 minutes. Which one is correct?

»
3 года назад, # |
  Проголосовать: нравится +56 Проголосовать: не нравится

I did nothing tbh.

»
3 года назад, # |
Rev. 4   Проголосовать: нравится +10 Проголосовать: не нравится

As a tester, I can confirm the contest is very well balanced in terms of topics and difficulty. Enjoy!

»
3 года назад, # |
  Проголосовать: нравится +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.

»
3 года назад, # |
  Проголосовать: нравится +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.

»
3 года назад, # |
  Проголосовать: нравится +49 Проголосовать: не нравится

A reminder that the contest starts in less than an hour! Please, join :)

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +131 Проголосовать: не нравится
Meme
»
3 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Good luck, everyone that joined.

»
3 года назад, # |
  Проголосовать: нравится +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.

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +19 Проголосовать: не нравится

    Actually It is closer to ABC .
    The first two problems involved ABC
    Still I couldn't solve any . :(

  • »
    »
    3 года назад, # ^ |
    Rev. 2   Проголосовать: нравится +3 Проголосовать: не нравится

    the names of the problems are really ABC!

    but for the content ......

    It's too hard to me :(

»
3 года назад, # |
  Проголосовать: нравится +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!

»
3 года назад, # |
  Проголосовать: нравится +129 Проголосовать: не нравится
there is one impostor among us
»
3 года назад, # |
  Проголосовать: нравится +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=pretests
helloween

  • »
    »
    3 года назад, # ^ |
    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.

»
3 года назад, # |
  Проголосовать: нравится +22 Проголосовать: не нравится

I think you got the wrong Belik

»
3 года назад, # |
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.

»
3 года назад, # |
  Проголосовать: нравится +228 Проголосовать: не нравится

I was so close to C but I didn't add if (m == n - 1 && m != 2) ans = (ans + 1) % p; :(

»
3 года назад, # |
Rev. 2   Проголосовать: нравится +29 Проголосовать: не нравится

How to deal with the bonus version (use only 5 subsequences) of A ?

»
3 года назад, # |
  Проголосовать: нравится 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.

  • »
    »
    3 года назад, # ^ |
      Проголосовать: нравится +13 Проголосовать: не нравится
    Hint 1
    Hint 2
    Hint 2.5
    Hint 3
    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +3 Проголосовать: не нравится

      Thanks Sir , Now I understood it . :)

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится 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?

    • »
      »
      »
      3 года назад, # ^ |
        Проголосовать: нравится +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?

      • »
        »
        »
        »
        3 года назад, # ^ |
          Проголосовать: нравится +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:

        1. these transformations are a bit messy, we should try doing something about them.
        2. transformations on each letter are cyclic, i.e. A->B->C->A.
        3. what else can we do with transformations? For example, it might be nice if transformations were something like AAA -> BBB -> CCC -> AAA.
        4. 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.
        5. 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".
»
3 года назад, # |
  Проголосовать: нравится +5 Проголосовать: не нравится

How to solve bonus of C?

»
3 года назад, # |
  Проголосовать: нравится 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.