antontrygubO_o's blog

AtCoder Grand Contest 055 Announcement
By antontrygubO_o, 3 years ago, In English

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

The point values will be 400 — 700 — 900 — 1200 — 1500 — 1800

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!

  • Vote: I like it
  • +551
  • Vote: I do not like it

Comments Comments (35)
| Write comment?
»
3 years ago, # |
  Vote: I like it +63 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +56 Vote: I do not like it

I did nothing tbh.

→ Reply
»
3 years ago, # |
← Rev. 4   Vote: I like it +10 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it +378 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +43 Vote: I do not like it

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.

→ Reply
»
3 years ago, # |
  Vote: I like it +49 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +131 Vote: I do not like it
Meme
→ Reply
»
3 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Good luck, everyone that joined.

→ Reply
»
3 years ago, # |
  Vote: I like it +91 Vote: I do not like it

"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.

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +19 Vote: I do not like it

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

    → Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +3 Vote: I do not like it

    the names of the problems are really ABC!

    but for the content ......

    It's too hard to me :(

    → Reply
»
3 years ago, # |
  Vote: I like it +72 Vote: I do not like it

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!

→ Reply
»
3 years ago, # |
  Vote: I like it +129 Vote: I do not like it
there is one impostor among us
→ Reply
»
3 years ago, # |
  Vote: I like it +16 Vote: I do not like it

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

→ Reply
  • »
    »
    3 years ago, # ^ |
    ← Rev. 2   Vote: I like it +5 Vote: I do not like it

    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.

    → Reply
»
3 years ago, # |
  Vote: I like it +22 Vote: I do not like it

I think you got the wrong Belik

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +48 Vote: I do not like it

XD, at this time, I participated in the qualification for ICPC 2022. Account owner — Ivan Bochkov (tranquility). He named his account my name.

→ Reply
»
3 years ago, # |
  Vote: I like it +228 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
← Rev. 2   Vote: I like it +29 Vote: I do not like it

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

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply
  • »
    »
    3 years ago, # ^ |
      Vote: I like it +13 Vote: I do not like it
    Hint 1
    Hint 2
    Hint 2.5
    Hint 3
    → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +3 Vote: I do not like it

      Thanks Sir , Now I understood it . :)

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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?

      → Reply
    • »
      »
      »
      3 years ago, # ^ |
        Vote: I like it +19 Vote: I do not like it

      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?

      → Reply
      • »
        »
        »
        »
        3 years ago, # ^ |
          Vote: I like it +26 Vote: I do not like it

        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".
        → Reply
»
3 years ago, # |
  Vote: I like it +5 Vote: I do not like it

How to solve bonus of C?

→ Reply
»
3 years ago, # |
  Vote: I like it 0 Vote: I do not like it

How to solve the bonus of D with low complexity? Means not use the algorithm mentioned in the editorial. Or maybe it can't.

→ Reply