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.
Auto comment: topic has been updated by -wicton- (previous revision, new revision, compare).
maybe they have problems that have nowhere to publish except abc? Like some div2 here.
I totally agree with you. The difficulty gap between problems D and E, or problems E and F, are getting significantly larger. Reference:kenkoooo
As a OIer who has took part in 66 rated contests (including 47 ABC contests) in AtCoder so far, I think I have a little voice in the problem.
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]
I think it makes more sense to think of ABC as AtCoder Educational Contest than AtCoder Beginner Contest.
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.
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.
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.
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-ISis difficult for a beginner to understand,and some problems are based on participants' comprehension.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.
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.
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.
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.
But you can use std::map on rounds where prewritten code is not allowed(for example OI).
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).
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.
I hope the Atcoder admin and ABC contest writers can see your blog.
https://www.youtube.com/watch?v=cKgnDmpb4BU&list=RD9tIFSo_bEVY&index=2
From a comment by rng_58
Seems its blues as beginners. Yeah, probably I am rated too low :(
No one should have excuses not to learn algorithms. I believe that beginners should learn algorithms too.
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?
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.
Actually, whats even the use of algorithms when its all stupid greedies out their. Almost every round nowadays have no algos upto Div2 D
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.
That's like saying "lol git gud".
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.
But the thing is, if we have 6 problems, 1h 40m is enough time. But with 8, we should get at least 2h.
Hey. You've mentioned "SAM / SA" in ABCs. Could you tell me what are those (so I can google them as they seem interesting)?
Suffix automaton and suffix array.
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.
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'.
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.
AtCoder Senior Beginner Contest
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.
Beginners are up to date with the times, as well.
Well, I see contests as practice, I don't see the difference between them.
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
So this is why I prefer Codeforces to AtCoder...
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
So we wont't care the gap?
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.
Make ABCs
easygreat again! lolWhat is SAM/SA?Plz let me know,I have heard about FFT,NTT but i have never heard about these two terms SAM/SA
SAM(SA)is a kind of data structures in solving string problems.
SA means 'suffix array'. And SAM means 'Suffix AutoMaton'.
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.
agree, but understanding difficult algorithms also needs learners' time & level. I just think the gap is too big :(.
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.
based on the rating cap for ABC, it is appropriate to include tasks involving advanced techniques imo.
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?!
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)