-wicton-'s blog

Questions about AtCoder
By -wicton-, history, 3 years ago, In English

Since I can't post on AtCoder and admins of AtCoder are also on CodeForces, I post it here.

AtCoder holds ABCs, which is for beginners. What's the definition of beginners? Recently, there appears many problems with algorithms such as FFT / NTT, flows, SAM / SA etc in ABCs.

Are these really for beginners? Of course these algorithms are in ACL, but if participants really want to solve them, them must know the tricks in them like using FFT to do the string matching, the max flow equals to the min cut, the meanings of points & arcs on SAM. All of them are not really for beginners, at least I think so.

The purpose I do this post is that I hope admins of AtCoder to give a clear definition of beginners or to avoid overly difficult algorithms in ABCs.

Since my English is pretty poor, please forgive me for the impolite (might be) wording.

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

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

Auto comment: topic has been updated by -wicton- (previous revision, new revision, compare).

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

maybe they have problems that have nowhere to publish except abc? Like some div2 here.

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

I totally agree with you. The difficulty gap between problems D and E, or problems E and F, are getting significantly larger. Reference:kenkoooo

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

    Sometimes Problem D is even harder than Problem E, like ABC198, ABC192, ABC191 and so on.

    So I think the contest authors should pay more attention on the order and more important, difficulty of the problems.

    the sol of ABC212G

    Please click the spoiler 'What is primitive root?' and look at the last sentence: You may never have heard of “primitive root,” but the idea is also used in AGC, so we recommend you remember the concept.

    Will a beginner take part in AGC or even solve the problems in AGC?

    Maybe the true meaning of 'ABC' is 'Problem A, B and C are for beginners'? [doge]

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

      I think it makes more sense to think of ABC as AtCoder Educational Contest than AtCoder Beginner Contest.

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

        You are right, but I just feel ABC too hard and I can just solve less then 6 out of 8.

        For me, ABC is a good exercise. But I regard it as a contest, and it still has something to improve.

        Maybe I should just learn more.(sigh)

        BTW, forgive me for my poor English.

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

It seems that ABC213 is even harder than ARC106.I just wondered if there will be more difficult ABCs.

BUT ABCs with $$$8$$$ problems(like JSC2021) and ARC difficulties only give us $$$100$$$ minutes to solve problems.

In my country,SuffixArray(ABC213F) and FFT(ABC196F) are algorithms used in NOI(similar to AGC).So I think the authors must define beginner as "beginner for AC Library" not "beginner for coding".

Since my English is pretty poor, please forgive me for the impolite (might be) wording.

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

These are some really cool introductory problems on these algorithms. So I think a beginner(who doesn't know these algorithms/tricks) can learn them after the contest.

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

    However,some of the solutions are based on AC Library,which may not provide helps on understanding the algorithm and is not available in some OJ or offline contests.Something such as SA-IS is difficult for a beginner to understand,and some problems are based on participants' comprehension.

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

      The lib can be used on other platforms, see https://atcoder.github.io/ac-library/production/document_en/appendix.html and the script expander.py

      I regularly use it here on codeforces.

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

      A counter-example for "ABC AC Library Contest": ABC212H, which is obviously a Fast Walsh-Hadamard Transform problem.

      Maybe AtCoder admins regard this as a common beginner trick.

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

      some of the solutions are based on AC Library,which may not provide helps on understanding the algorithm

      Does it make a contest bad if some of the solutions are based on std::map from STL Library, which may not provide helps on understanding the red–black tree algorithm?

      This looks like a very interesting experiment. Let's give it a bit more time before judging. If AtCoder beginners adapt and start cracking problems, which are perceived as super-hard by the other platforms' standards, then I don't see anything wrong with that.

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

        As timreizin said,STL is built-in while AC Library won't be included in C++ standard.

        Meanwhile,STL won't be used as a specific algorithm but a instance of them.When using STL,we don't need to know tricks about the algorithm.

        Right,it seems that I don't know well about AC Library,but I know some offline contests don't allow them.

        If there are more mistakes in my word,plz tell me.

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

        But you can use std::map on rounds where prewritten code is not allowed(for example OI).

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

        I think it cannot be judged so simply.

        Algorithms in STL are very well-known, and they're universal.

        What matters most is that devs see algos in STL as data types, while ACL sees algos as algos themselves, which means we can regularly use STL, but when we use algos (maybe in ACL), we need to know something of an algo (such as MF=MC).

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

    But then ABC should be named at "AtCoder Edu Contest" instead of "AtCoder Beginner Contest". If ABC is for beginners, I think, for example, it would be more useful to prepare an interesting DP problem for participants.

    I'm not against the edu rounds, but since it's named at ABC, it should provide problems that fit beginners.

    For example, CodeForces, does well in it. Have you ever been solving problems of Div. 2 or 3 with high-tech algorithms? at least it's not common.

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

      I hope the Atcoder admin and ABC contest writers can see your blog.

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

    https://www.youtube.com/watch?v=cKgnDmpb4BU&list=RD9tIFSo_bEVY&index=2

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

From a comment by rng_58

ABCs (= easy CF Educational) are mainly targeted for blues and below who are serious about competitive programming and dream to become reds in the future.

Seems its blues as beginners. Yeah, probably I am rated too low :(

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

No one should have excuses not to learn algorithms. I believe that beginners should learn algorithms too.

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

    I was never meant it that we should not learn new algorithms.

    I just think the gap is too big. For example, ABC 213, tasks A~E are ordinary, where task E tested shortest path algorithm, and task F tested SAM / SA, task H tested divide and conquer FFT / NTT. Imagining you're a beginner, is it reasonable?

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

    There are many many simpler algorithms (because I consider the algorithms mention in the blog are advanced) that beginners need to learn first.

    Directly starting to learn the mentioned algorithms is quite a big leap.

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

      Actually, whats even the use of algorithms when its all stupid greedies out their. Almost every round nowadays have no algos upto Div2 D

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

        Yes, that's true. Most of Cf div2s recently hade "case" based problems/ad-hoc/constructive/trick in the first 3 problems(at least).

        Man that was a very horrible time for me.

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

    That's like saying "lol git gud".

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

If you look at just the first 6 problems then it looks like a normal atcoder beginner round. I guess they added two extra problems to make round interesting for more experienced people. I personally don't mind having two extra tough problems if I manage to solve first 6 in time.

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

    But the thing is, if we have 6 problems, 1h 40m is enough time. But with 8, we should get at least 2h.

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

Hey. You've mentioned "SAM / SA" in ABCs. Could you tell me what are those (so I can google them as they seem interesting)?

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

I’m not atcoder admin, but I’ll be happy to share my point of view ) It seems to me it is a beginner contest not in a sense like “leetcode easy/medium” or “CF div3”, but in a sense of recognizing the algorithms. Because mostly it needed no strong math and almost no alteration to standard algorithm.

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

    This is pure generalization and makes no sense. If you look at things this way, Div. 2 boils down to the exact same concept. Tell me how many algorithm-based problems in Div. 2 required any more creative thinking that ABC 212 F? Take every single DP problem in Div. 2 and it boils down to implementing a DP scheme you've already seen somewhere. The same could be said for virtually any segtree, shortest path, toposort, binary search or other problems.

    You mention strong math, are we even taking same contests on CodeForces? Where did you see the need for strong math background in a Div. 2 A-E? It's all simple stuff, that appears in ABC as well. Some ABC 2-3 months ago required use of rotation matrices/decent trigonometry knowledge, are you telling me that solving an equation or playing around with binomial coefficients requires more math experience than that (and this is what happens in most Div. 2 rounds on here)?

    Last but not least, A-C in ABC is just logic and observation-based or some sorting which is the simplest Div. 3 you get, while F-H is closer to the first half of Div. 1 than anything else. Take a look at G in yesterday's round and tell me it's just 'implement a standard algorithm'.

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

I hope there will be more difficult problems without difficult algorithm, which I think is more important on thinking-skill improving. That's what I want to face in ABCs and ARCs.

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

AtCoder Senior Beginner Contest

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

I only see it as helpful and useful. Generally, we don't find such Qs in usual contests. If you see many times even in Educational, we can find some such concepts in E and F.

I think it is a positive thing, as now you know which were previously unknown to you.

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

Since ABC is the topic of discussion..

AtCoder doesn't include tags on problems like codeforces

So if any AtCoder problem setters see this, pls put what topic a problem is based of in the editorial

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

    So this is why I prefer Codeforces to AtCoder...

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

I don't understand this post. They are educational, so that's the point: if you didn't know how to use this algorithm, you can learn it from the editorial and use it in future contests, so you can "become red in the future". Atcoder is the best platform <3

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

    So we wont't care the gap?

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

      The high rating of last two problems of the recent ABC's is not due to concept difficulty but mainly to high end Algorithm. If suppose you already knew that particular algorithm and just focus on the thinking part on how to map that algorithm to the problem. Then it is relatively easier compared to similar rated problem from ARC which have much more thinking and adhoc related. Obviously, I did'nt solve them during contest but it is the great way to encounter these popular algos through ABC. I loved this new format.

      And of course, we should focus more on problem solving skills rather than just knowing algorithm but because of this, the codeforces div2s have mainly ended up having greedy,constructives. This new format just keeps the balance right.

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

Make ABCs easy great again! lol

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

What is SAM/SA?Plz let me know,I have heard about FFT,NTT but i have never heard about these two terms SAM/SA

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

    SAM(SA)is a kind of data structures in solving string problems.

    SA means 'suffix array'. And SAM means 'Suffix AutoMaton'.

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

Personally, I think the ABC contest is very similar to the Educational Contest.

In fact, if the contest is divided only according to the difficulty, many confusing situations will come out. There are some questions that may require advanced algorithms or data structures (e.g. FFT, SAM), but they only use them very simply and you only need to understand the basic idea of these algorithms. They are more like practice problems for a particular algorithm, so it is clearly inappropriate to think that they should be classified as high level competitions. Likewise, some of the very clever problems in AGC may use only the most basic things, but require very clever intelligence. They are indeed very hard, but they are not knowledge-oriented problems; they are more like works of art composed of various genius ideas.

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

    agree, but understanding difficult algorithms also needs learners' time & level. I just think the gap is too big :(.

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

So I have to claim that I'm not against edu rounds, but the gap. Maybe, for example, using segment tree to optimize DP will be more educational for beginners. Maybe skills such as divide and conquer FFT etc are for regular contests, where the gap will be smaller for participants. I haven't explain this clearly, so I explain here.

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

based on the rating cap for ABC, it is appropriate to include tasks involving advanced techniques imo.

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

    I just checked people around 2k rating at Atcoder and found one from my country that's ~1900 here. That's not even top of div2 here. What sort of advanced techniques are these contestants supposed to handle?!

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

Recent problems from ABC are very hard and a lot of Japanese competitors complain about it. But it seems that the admins think ABC is a kind of contest which corresponds to Educational Codeforces Round, aiming to create mature competitors whose main battlefields are ARCs and AGCs. (I learned this from Twitter but I won't bother to leave the link here)

→ Reply