Hello everyone!
I finally decided to write some response/explain my view after all recent discussions of my problems and rounds I coordinate, and I would like to make a few points.
1. After some recent contests there were a lot of comments saying that Data structure problems should appear as easy problems (say, D2A-D2D in a Div2 of $$$6$$$ problems)
I don't think I agree with this. To begin with, I don't think that having Data Structure problem is a requirement for a good contest at all, not just in first few positions.
However, for positions D2A-D2D, I just don't see a way to properly include data structure problems. Take some Data Structure problem, it consists from two parts:
- Knowing/implementing the Data Structure
- Actually thinking about the problem, and how this Data Structure should be applied
The problem is, that even the simplest Data Structure (say, Segment Tree), makes the first part already at least D2D difficulty in a Div2 of $$$6$$$ problems. Now, if the second part is completely trivial, then the problem shouldn't be used in official CF contest (maybe in Educational Round only): implementation part can't be much harder than thinking part. If the second part isn't trivial, the problem can't be less than D2E. Therefore, I can't really see how can Data Structure problem appear on positions D2A-D2D.
Remark: Here I don't even count sets/maps as Data Structures.
2. A lot of people lately are sad because graphs, dp and all other topics don't appear now. Only constructives and ad hocs are left!
To begin with, this is not true. All topics appear! I went through last $$$3$$$ Div2 contests I coordinated. Among them:
1372E - Omkar and Last Floor and 1363F - Rotating Substrings are DP.
1364D - Ehab's Last Corollary, 1363C - Game On Leaves and 1363E - Tree Shuffling are graph problems.
1363D - Guess The Maximums is binary search problem.
However, it's somewhat true that easier problems are more often not related to these concepts. From my perspective, the reason for this is similar to the reason I provided in argument above: it's impossible hard to create an interesting DP/Binary Search/Graph problem which could fit positions D2A-D2C. Just because that concepts themselves are already quite challenging.
And I don't want to accept standard problems on DP/Binary Search/Graphs just to make the set more diverse or because you want it, and won't do so, I think.
3. While I understand that many people really like these topics and want them to appear as early problems, I believe that a lot of this feedback is coming from participants who learned some new algorithms/techniques and are sad when they don't become red they don't see these problems in contests.
Well, from my perspective, CP isn't about knowing algorithms, it's more about solving problems. Algorithms are tools. Knowing many algorithms means that you have a lot of tools, but if you don't know how to apply them, this won't help. That's why you should learn how to solve problems, not just learn algorithms.
4. Some people think that contests by me/coordinated by me aren't diverse enough, and contain too many constructive problems.
And well, I agree with this. I also believe that having too many constructive problems is not a good thing for a contest. From this perspective, Codeforces Global Round 9 wasn't very good. I also believe that the problemsets should be more diverse. However, when choosing between having less diverse problemset and accepting fairly standard problem, I will always prefer first.
Still, this is a valid objection. I will try to make problemsets more diverse :)
5. Some people think that I just won't accept Data Structure/Flow/Some string structures/Anything except ad hoc.
This is a very wrong point of view. I will accept problems in which idea is interesting enough. The problem is: it's much harder to create a problem on these topics which would at the same time be interesting than creating a good ad hoc problem. It seems that CP has evolved significantly in recent few years, and some things which weren't standard $$$4$$$ years ago, are very standard now. So yes, the reason why good nonstandard problems on these topics appear less now, is that there aren't many of them in proposals! However, still, expect to see some problems on these topics in future contests :D
6. While I understand people who say that it's sad when algorithms don't appear in contests, I don't think I understand people who get joy from struggling with implementing some problems. I am not against problems with quite long implementation, as long as implementation difficulty is smaller than the thinking difficulty. My opinion is best expressed here:
7. I would like to thank:
- People who provide objective criticism
- People who support my position
- MikeMirzayanov for great systems Codeforces and Polygon
it was just my opinion and i don't have any intention of hurting your feelings.Its really hard to prepare a contest and you are doing a great job in that.keep going!!
Before blaming anton , people forget one thing
Problems were not made from algos , algos were made to solve problems in an easier way
The reason why good nonstandard problems on these topics appear less now, is that there aren't many of them in proposals!
That's enough for me.It isn't your fault if you are not given problems on these topics.
100% Agree with you. There are many people like me who don't know much about DSA and in the DSA learning phase so, it would be good to have some starting problem which does not require DSA to solve. Thanks for writing this blog.
Ad hoc problems are necessarily insightful. Hence, I think ad hoc problems are generally more insightful than those following conventional paradigms. Therefore your approach to problem setting is ideal for those who favor insight over implementation. Personally I have a strong preference to the former.
Well, from my perspective, CP isn't about knowing algorithms, it's more about solving problems. Algorithms are tools. Knowing many algorithms means that you have a lot of tools, but if you don't know how to apply them, this won't help. That's why you should learn how to solve problems, not just learn algorithms.
this is one the most beautiful statement I've ever seen about competitive programming..thanks a lot for your efforts, and keep going!
The best part of the blog :
CP isn't about knowing algorithms, it's more about solving problems. Algorithms are tools. Knowing many algorithms means that you have a lot of tools, but if you don't know how to apply them, this won't help.
Loved it! ❤️
Dear antontrygubO_o, I totally agree with you. But please tell us how to improve in your type of contests, I feel that your problems can just be solved randomly(just my feeling). I mean i solve almost all of your problems with this strategy: (tell me if there’s better one): 1. Take a random idea and work on it to solve the problem in that way. 2. If the problem is solved, you're just lucky! Otherwise return to step 1. This strategy is so likely to fail or take a very long time to solve the problem. Basically, I’m asking if there is a way to practice and get better on it! I’ve not found any way of practice that guarantees the problem D will be solved in a contest. It often takes a long time to solve the problems just because I should try various different ways and trying each of them results in so much time wasted!
What you are describing is problem solving. You try different ideas and see which of them work. With experience you start to feel what ideas are more likely to work, so you try them first.
If the problem doesn't require this step it means that it is mechanical implementation, that's not for contests, that's for exams.
Um_nik has the best advice for this: just solve more problems.
There is no algorithm to solve these problems, just a collection of heuristics that you learn. "Taking a random idea" and using this to solve the problem is a terrible approach, because if your idea was truly "random" there is a 0% chance of it working. Im guessing when you say "random" you mean the first idea that comes to your mind, which is often better than random due to your experience.
Some heuristics are: 1- try the simple stuff first, if it ends up failing you don't waste much time. 2- If you are stuck try to prove some lemmas that you think would be helpful (e.g. "if i could guarentee X the problem is much easier" 3- Try solving an easier version of the problem, this often gives intuition for the original problem 4- When trying to prove something, first try to disprove it. Its often easier to find counterexamples and this saves a lot of time
That said, just memorizing these heuristics isn't gonna be that helpful. Solving problems is the best way to improve.
What you said is the content of the book "How to solve it?". This approach is based on that you have a toolkit. As beginners, we need chances to learn and practice these known mature approaches.
Yes, that is why I said solving problems is the best way to improve.
Out of genuine curiosity, can you point out a problem that you think is a good problem that doesn't follow that strategy, and why you think it is a good problem?
There are a lot ones where the basic problem is "implement this simulation efficiently", for example yesterdays E.
If they are not to simple for ones level they are mostly good ones.
We give. I just don't think you reach them in contests.
Nailed It!!!
Please tell me where was your DP problem in Codeforces Global Round 9.
First learn to solve div 2B/C then you can talk about DP.
First Learn to comment with your original account. Then we'll talk.
This is my original account.
Don't bother..he's angry because Truth_hurts
Why don't we shift to traditional 5 problems/contest. In that case Div 2D you can make non-adhoc as you said in the post. In recent contests first 4 problem are adhoc and then 5th one most Div 2 people don't have much time to solve. Bring back 5 problems/contest tradition. It will also reduce server load.
Yeah. 6-7 problems also seem to make the gap between D and E become both more larger or smaller than before.
__
You are really upsolving well if you can understand G,H and I are constructive. Hope to see ur such performance in contest too.
How is 1375G constructive?
It's constructive, otherwise how do you solve it? Guessing the solution? Fuck that shit, you should solve the problem and how to solve that without finding a valid construction to it?
You have a wider definition of "constructive" than me :)
If savage was antontrygubO_o
Just curious, do people give a "constructive" tag to all the problems they don't know what to call?
I haven't read all the problems, just saw the tags and wrote them down here.
I'm so impressed by whoever gave G a "constructive" tag. It's not constructive at all, those tags are a lie, to be honest. I guess if a problem is $$$95\%$$$ ad hoc and $$$5\%$$$ constructive, then people will give it a "constructive" tag because there'd no "ad-hoc" tag in CF.
Btw Who assigns tags to the problems ?
Whoever solves it, and probable some other restriction(like 10 rated rounds or so).
Don't the authors set the tags in Polygon?
It has nothing to do with codeforces I guess.
When you reach 1900 you get an option to add or remove tags from a problem from a recent contest.
If the tags aren't accurate then I guess I unnecessarily said some wrong stuff to Anton. Sorry antontrygubO_o
If a problem has tag 'x', then it means this problem can be solved using 'x'.
can someone tell me what is "ad-hoc" problems? i really don't know is it other name for "implementation" ?
a problem which doesn't fit into any standard category like dp, strings, greedy etc
Just adding my thoughts here, CF problems are interesting,period!. But in my opinion, a good contest should have a variety of problems.It may be true that setting an unknown DP problem may be difficult, but it depends on the perspective, a DP problem which seems boring to a red coder may be interesting to a DIV 2 participant.
It may NOT be possible to cover all variety of problems in one contest(w.r.t DIV2 rounds), but if we take a sample size of say 10 contests,it would be great to see a good mixture of all genres of problems, say Data structures,DP,greedy,binary search,graphs and ofcourse AdHoc. This way it would be really helpful for novices like me,who will get to practice wide variety of problems.
The above comments are NOT a criticism towards codeforces or problem writers in any way but just my general view.
I have one more thought on "algorithms don't appear in Div2A-D anymore!". I just remembered my old comment which documents how they did not really appear in Div2A-D even in 2018, way before antontrygub started coordinating anything. I think easy problems on CF have not been about just applying algorithms for a long time.
Actually very well said bcoz cp is about logic building and how efficiently u are able to solve problems and ad hoc problems are best problems for logic building and thinking out of the box manner and I don't understand why there is a problem if 1 out (4 or 5) rounds is ad-hoc as the other contests can make u improve in algos and ds. And creating a contest isn't easy task so don't criticize the coordinator in any manner. I hope ppl take it in positive way :))!!!
With due respect to the high effort that goes into ensuring the quality of CF rounds I see multiple issues in this post.
I think CF focuses too much on problem quality. I think the contest-quality matters more. The balance of topics is to me a key factor that contributes contest-quality and recent posts suggest it is the same for other Div2 users. Say Problem X has 100 beauty but is a repeated topic from the set, I'd much rather have a problem Y with 90 beauty of a different topic. Note that beauty here is subjective, and should be evaluated based on opinions of Div2 testers more than reds (as explained in point 3 below).
I agree Div2A-C will have to be ad-hoc. That's not an issue. The problem is when in many rounds even D, E end up being greedy/adhoc/constructive. I think it is imperative to try and diversify problem topics in D-F. I think coming up with a good non-adhoc D/E/F is not much harder than an ad-hoc problem of that level. Also, the definition of 'good' should not be based solely on the choices of math enthusiasts/olympiad participants. CF is a 'programming' platform, and I think the outcry on the recent shift to minimal coding problems is justified to some extent. Note: Personally I enjoy math problems and agree there should be some. But an over-representation in the same set is not good. Neither am I a fan of the ugly irritating implementation problems of CodeChef either. A balance can be struck imo.
You are trying to justify selection for Div2 Problems using opinions of nutella users. I get why they prefer ad-hoc problems (because others are too easy/boring for them?), but this is very different for div2 users. I think for div2 rounds, opinions of div2 participants should take precedence over non-competitive red users.
I think you are trying to argue against the feedback by criticizing the extremes. No one wants a div2D DS problem, but an increase in the frequency of DS problems (as E/F) would be appreciated. Div2D and E can have observations while including other topics like Searching/DP/Graphs etc.
A lot of us are here to improve our skills and knowledge (perhaps for contests like IOI/ICPC), and current contests don't align with this goal.
Cheers :)
Those "Reds" are experienced problem setters here in cf, you can find Anton's interview with them in his blogs.
Agreed:) I'm not disputing that. It's just about problem-tastes. Problems boring for them can be interesting/challenging for div2 users is all I'm saying.
He agreed that his problems aren't diverse enough and he also thinks diverse problemset is better. However, when choosing between having less diverse problemset and accepting fairly standard problem, he will always prefer first. Do you think he should allow a standard / repeated DS problem just for diversity?
If someone wants more DS problems for IOI/ICPC, shouldn't he/she practise more problems from IOI/ICPC type contests, to get a preview of similar problems. Lots of standard problems already exist, there is no reason to repeat them in new contests, even in Div2.
If the problems are too standard I agree less diverse problemsets are fine. But it doesn't have to be binary. If it's agreed a push for more diverse problem-sets is needed (even if it can't be achieved every time), then that's perfect. I don't have anything more to add.
Also about practising using IOI/ICPC type contests. Well, that's easier said than done. I think everyone agrees virtuals don't have the same feel as a live timed contest with something (maybe rating) at stake. I don't think it's wrong to support such contestants with slightly similar styles in CF contests. Also can you elaborate on why you think we've collectively exhausted all problems with topic-based ideas. I don't see why they have to be 'repeat's.
I don't think more topic-based problem is impossible. But most data structure problems I have faced was just rehash. I have seen at least 5 different problems in last year, with the same idea: improve a n^2 dp to nlogn, by converting a loop to range query data structures. Yes, they are different problems, but essentially repeated ideas and too similar to known problems. Topic-based ideas tend to be repeated more, as it's more probable that someone else thought of it.
If you describe that as repetition, then you could say every constructive and many easier ad-hoc are the same: write some examples, see pattern, write a few lines to code. I think that is a very narrow (well actually overly broad lol) way to look at problems as "essentially repeated ideas", though I do agree topic-based problems tend to repeat ideas more.
I agree that stronger cp-ers will likely find different problems interesting than less strong cp-ers. For instance, someone with little experience of lazy seg-tree will likely feel challenged by a straight-forward implementation of a lazy seg-tree, while someone with more experience will feel bored.
I think that ad-hoc problems have the ability to appeal to coders of all strengths.
If someone wants to practice easy dp/ds problems, they can practice using old cf problems or problems on other websites. If someone wants to practice ioi/icpc problems, they can practice using past ioi/icpc problems. If someone wants to solve hard dp/ds problems, there are plenty of hard dp/ds problems in the problemset. I do not think a cf contest with 5/6 ad-hoc problems is preventing anyone from improving or learn techniques that they want to learn.
I think there should be slightly more problems with data structures, although not at high difficulty level except when they're really interesting. Remember that for less experienced contestants, they aren't overdone.
As someone who was involved in the popularization of data structures problems on IOI (HSC 08-10, ISC 15-18, shortlist author in 11&13), I always viewed the idea of an "easy data structures problem" as an oxymoron (a figure of speech in which apparently contradictory terms appear in conjunction). It's a topic that requires extensive preparation, where the only way to make it "easy" is to take out the thinking/problem solving aspects...
There is no issue with adhoc/constructive problems. The problem is if it goes repeatedly. Who wouldn't want to solve these problems?
1179B - Tolik and His Uncle
1325D - Ehab the Xorcist
1365E - Maximum Subsequence Value
1360G - A/B Matrix
1349B - Orac and Medians
But, there are also some other types of problems that are interesting too. Like these.
1371E2 - Asterism (Hard Version)
1372D - Omkar and Circle
1370D - Odd-Even Subsequence
14E - Camels
1361B - Johnny and Grandmaster
Basically none of these problems are that hard and not trivial for experts to solve after knowing the necessary algorithms.
What we need is mixing of these types. Now, it's heavy on adhoc/constructive side.
So, we are out of equation right?
What's the purpose of div2? I think improve us for div1. Am I right?
Somethings which weren't standard 4 years ago, is not standard now. Quite agree. But we haven't started 4 years ago. These are still not standard for us. We need to think out the standard things just like you guys used to do 4 years ago when these standard things(not standard then) began to appear.
For a lot of people, this platform is the way to OI and ICPC. These contests require adhoc techniques as well as using algorithmic techniques. A lot of problem needs these standard things as smaller parts of problem. Real time contest is better than Virtual Contests to learn anything for a lot of people.
In div2 contests, we are participating. Not experienced ones. So, why would these problems look standard for us? Maybe you have solved 10 problems like this. We haven't. We still need to try this in contest environment.
I have no issues with ad-hoc/constructive problems. I love solving each of them and thinking myself as foolish. But, that doesn't mean standard problems for orange/red ones can't appear for not so pro div2 contestants.
So you want a rated contest to have repeated problem / problems which are too similar to existing problem? I don't understand why you need to try this "in contest environment". I am confident that you actually don't and solving a problem outside contest has exact same effect on learning. Many experienced 2000+ coders also participate in Div2, Div2E and often Div2D are supposed to be targeted towards them.
Let's take this example. 1340B - Nastya and Scoreboard
The only thing that makes trouble is adding sticks to make a valid digits. From where to where we can reach. For some inexperienced coders, it is not handy. But, once you do this. It's easy for expert/specialist.
Now, the difference is, in practice mode, someone would do this in 2-3 parts or more(who wants to do some terrible implementation at once). In contest, you are doing this task continuously. So, you would not probably find the struggle you do in contest.
And I don't think if I stop doing contest and just solve OJ problems for two months and come back, I won't see as much improvement as much I would do participating in contests and solving problems which I couldn't get in contests.
Anyway, out of these problems, which are standard??
616D - Longest k-Good Segment(learned to use two pointers)
1187E - Tree Painting(learned rerooting technique)
1199E - Matching vs Independent Set(shapened my greedy)
507D - The Maths Lecture
1173D - Nauuo and Circle
1173C - Nauuo and Cards
667C - Reberland Linguistics
19E - Fairy
161D - Distance in Tree
1081E - Missing Numbers
1294F - Three Paths on a Tree
All problems were new to me, I needed to struggle and got ideas.
What do you mean by "someone would"? I wouldn't. Why should I? You can easily practise solving problems offline, in the exact same way you would do them in contests. Get used to solving problems offline with the same seriousness, otherwise you will get stuck after you reach yellow, Div1 contests are very rare you know.
I haven't read any of the problems you commented. But let's say some problems are standard, but new for you. CF contests are not only for you. If 100+ people with rating<2100 have seen something too similar, why should we ignore them and prioritize repeated problem over unique ones? I think you are assuming that every Div2 users are inexperienced. Many Div2 contestants have solved 1500+ problems.
I am confident that real time contest is no different from offline solving in learning problem-solving. The only difference is, real time contests teach how to solve problems with clock ticking.
Actually having less DS problems in D2A-D2D is good for welcoming new programmers.
I like most of problems in CF. Although I dont read and solve all problems in a conetst, but I do like those that I read. By the way in some rounds there are some (in my opinion) some "not interesting" and silly problems, but generally I enjoy reading problems and participating in rounds. Thank you antontrygubO_o
The problem with ad-hoc problem is if person don't guess then there is no solution. If that is problem B, then it is very hard to drop it and go for C. In div 1 that is fine, but in lower divisions or combined rounds it seems not. And if that is one such problem, probably fine, say you have B and C: B is ad-hoc, C is technical with lots of failure potential during implementation. Then you give me an option: I can spend time on C, write stress, write solution, debug and get my points or sit with pen on B. Global #9 was a good example of no option round.
Like recent Google Kickoff D is a good example, where C is idea, D is technical. They cost about same, maybe D a little more expensive. But C is like 20 lines of code, when D is a little bit longer and of course lots of potential bugs there.
Is there any problem which can be solved without using both guessing and memory (experience of seeing something very similar)? If all problems require either of them, isn't guessing better than memory as guessing seems closer to intelligence and creativity than memory?
I think most problems involve some sort of guessing, but the options are often so limited that we can try most of the options (thanks to TL, ML, constraints. e.g. N=1e18: solution is either O(1) or binary/ternary search or matrix expo), whereas adhoc problems often have infinite options to proceed.
We are talking about different things here. Of course you need to guess for all problems. But I just want to remind, that those are actually programming competitions, so I would really like to have an option to write some code. Like yesterday codechef took me quite some time to solve tree queries and there were many cool ideas that I liked there.
I mean there are problems, when you just need to see solution. Like in jeopardy, there are questions you can answer without knowing the fact, or you had to read same book as the author. It is very sad to see scoreboard with 5 problems, when E is not opened, D is solved by 3 participants, C has 10-15 AC and then we have A and B completed my majority of participants in first 20 minutes and then 1:40 they just stared at the wall and tried to guess who to find that formula in C. And then B failed systems tests because of the overflow :)
If you take recent global round, every problem is beautiful. But I am talking about balance. When you're putting a set together, I strongly believe that main goal is to make it fun.
I think I have one more thing to add.
It's possible to like ad hoc problems in general and at the same time think that certain ad hoc problems simply are not very interesting.
I think I can define one such class of problems that I don't find interesting: "build a pattern (matrix/graph/string/family of subsets/whatever) with given properties" but only if there is very little you can do besides just coming up with the correct pattern. I usually like such problems if there are some other observations you can make about the thing you are constructing that reduce your search space, or even solve the problem. Or if you can break it down like "make a graph with properties A and C, now find a way to give it property B, oh it turns out we can do it if the first graph also satisfies property D which we know how to do" etc. But if the only way to solve it is drawing the correct thing in your notebook I don't think it's (**in general, with many exceptions**) very interesting.
Examples of interesting "build a pattern" problems: AGC 041 C, AGC 031 C, AGC 027 D.
Examples of not interesting "build a pattern" problems: SRM 784 Hard, AGC 021 C.
Does that make sense?
Why isn't there an "Ad-hoc" tag in the problemsets?
Nice reply of critisism.
My explain: Anton made codeforces more about thinking than implementing, thus igniting opposition the ones who never used much of their brain to think while participating in codeforces...
I really enjoy the thinking process that goes into the Div2A-D problems. Its much better than implementing a complex data structure with just a simple observation. You can always mechanically learn standard DSA, but you can't learn the art of thinking, without thinking XD