highighiq's blog

Atcoder beginner contest changes?
By highighiq, 3 years ago, In English

As you know, atcoder's beginner contest has always 6 problems. Why it has 8 problems now?

And Is this problem(abc213f) for beginners? It's so difficult I think.

Sorry for my poor English

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

»
3 years ago, # |
  Vote: I like it +8 Vote: I do not like it

I think recent ABCs are getting significantly harder I can't even get to solve problem E. But before ABC190 I could be able to solve all.

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

I think the style of ABC has changed for a while now for the better actually :)

ABCs nowadays are very educational, and is now a category of its own. A lot (if not all) of these problems now feel like introductory problems to common techniques from higher CP level. Before, Atcoder used to strictly reject these kind of problems. They still do now for ARC + AGC apparently.

The problem F you linked is also an example. You want to calculate longest common prefix between all pairs of suffixes. How to calculate LCP of two suffixes? For those who just know basic suffix array and LCP, LCP of two suffixes is the RMQ between them in the SA/LCP array. How to calculate sum of all LCPs? Easy, calculate sum of all RMQs. It's feels very basic for those who have seen SA/LCP before, but impossible for those who haven't.

Before, ABCs were just treated as the div2 version of ARC, and is simply the lower half of ARC + 2 mindlessly easy problems. Now we don't even see them together anymore.

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

    Personally, I have been learning a lot by solving the C and D problems in the AtCoder ABCs. The above reasoning seems correct.

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

    Yeah, it's indeed educational. I learned 0-1 BFS and LCP array from that contest.

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

      I stumbled on 0-1BFS but what is LCP?

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

        Longest common prefix array. It is linked with suffix array and helps in solving some problems.

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

      How to learn new techniques like suffix array and LCP? read articles or something? Having a hard time learning how to construct suffix array and LCP.

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

        I learned about suffix array in codeforces pilot course and building LCP array in one of the blogs by user adamant.

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

    So beginners are just supposed to learn these techniques?
    Weren't problems like the ones you mentioned above the purpose of the ACL contest?
    I feel like they should just stick with the previous ABC format instead of adding 2 more hard problems in the same amount of time, when beginners who the contest is intended for barely used to even make it past the first 5 problems.

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

      Just solve ARC C,D,E if you want harder problems. Anyways, if you can consistently solve old ABC-F, you are not a beginner any more.

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

    Agreed. In my opinions, problems in ABCs is more "educational" and "introductory", while ARC needs more math skills and derivations.

    For me, I realized that the problem F is something related to SA at the first glance of it. But I only know the general idea of SA and didn't know the details in its implementation. I copy/paste code from oi-wiki, but I mistook variable "sa" for "rk" when calculating answer and couldn't debug out of it during contest! I feel like a donkey after realizing my foolish mistakes. This contest really teach me a great lesson on SA

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

Yes I also think F was really tough.And after solving upto E there was very little time left.

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

Yes according to https://kenkoooo.com/atcoder/#/table/ Problem ABC 213F is rated 2215 which according to This https://silverfoxxxy.github.io/rating-converter is equivalent to 2400 Codeforces difficulty Which is way to tough for a beginner contest.

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

I think they have changed for the better. I used to put off learning string algorithms, polynomial interpolation, convex hull, flows, game theory but now I am forced to learn them cuz if I don't, I won't be able to touch the last 2 problems in ABC now.

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

    Yes, you would need them but do you think those will help a beginner? I mean the contest is meant for beginners.

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

      yes its true that the topics touched by last problems of ABC are even more advanced than div2F of Codeforces. CF Div2 Rounds need atmost lazy segtree in terms of knowledge to AK the contest. [99% of rounds]

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

      Contests designed for beginners should aim to help them improve and learn new things, not to create a ceiling for them to stay beginners forever. ABC is doing this very well I believe — I've noticed that identifying and using one or two standard techniques is a considerable fraction of the insight needed to solve the problems, naturally getting more advanced for the harder problems. This is unlike ARCs or regular codeforces contests.

      → Reply