Lately I've noticed that there have been very few(almost none) Graph,Binary Search,Data Structures,Two Pointer,Dp (and other known concept) problems in Div.2 C and Div2 D. Most of Div2C&D have been contructive problems. It's kind of a trend now. I don't hate these problems but why are Div2 A,B,C,D all based on some logic and don't use any of the well known concepts like binary search,Data Structures,graph,Dp etc. I mean I would like to see all kind of problems rather than just constructive in every contest. Have you guys noticed this as well ?Why are contest setters doing so?
Tagging some problem setters to find out the reason :DeadlyCritic Ashishgup awoo BledDest MagentaCobra vovuh adedalic Monogon Errichto antontrygubO_o Ari Roms
You created an account only for asking this? XD
I def agree with you, I would also like more ds and well known algorithms as a part of the problem.
I wanna defend myself:
my A is not constructive, it's probable nothing, maybe geometry, I don't think so.
my B is not constructive, It's ad hoc.
my C is not constructive, it's greedy.
my D is neither constructive, it's DP.
Yes, I agree You might call my B or my C constructive, but they are not, to be honest. But what could I use as B/C? I think constructive is a good option.
Updated
Tbh, I liked your problems. You had a prob D which was a tree problem, your E was a graph problem and I'm fine if there is one constructive prob in a contest. I am not pointing fingers and saying that your contest was too constructive(It wasn't). The point I was trying to make is that off late Div2C&D have been constructive in most contests and this is becoming a trend now.
I see. I'm pointing that constructive is a good concept, especially for easy Div 2 problems.
I like how A is "nothing" :D
A lot of constructive problems are greedy. Also, problems can belong to multiple categories. This is such a bad argument. Imagine setting a problem that's about implementing a segtree with ugly merge rules and when people complain that the idea was obvious but the implementation was too difficult so it's a stupid implementation problem, you say "it's not implementation, it's segtree". Missing the point entirely.
A constructive problem is characteristic in that the construction isn't just an extension of the non-constructive version (e.g. yes/no, compute minimum property), but requires different ideas to solve. The construction is the problem, not just an easier way to decide if a solution is correct.
It's not always a perfectly obvious decision, but you can decide based on that which of your problems are constructive.
Constructive tends to yield some really interesting problems. Since it's so versatile, constructive encourages you to actually think about the problem and make observations instead of identifying the right paradigm and copying it.
As I said I don't hate these problems but in a contest I (and I'm sure most people) would like to be tested on a range of topics and not just one topic.
Oh you forgot to tag antontrygubO_o, because of Global Round 9.
Since I've always had this question, what does tagging even do? Do you get a notification if you get tagged?
Yes
I think the amount of constructive problems appearing as 2C and 2D is being overstated -- out of the 4 most recent contests (excluding Div 3), only two of them had either 2C or 2D as constructive, and none of them had both 2C and 2D as constructive.
Last Three rounds which were rated for Div2 and constructive problems in them
Codeforces Round #655 (Div. 2) : Problem B Problem C
Codeforces Global Round 9 Problem B Problem C Problem D
Codeforces Round #654 (Div. 2) Problem D
I don't see how 655C is constructive? The answer is just the minimum amount of operations.
What??? Of course it was constructive. We proved, by construction, that it is always possible to do it in no more than 2 moves. Construction doesn't always mean really constructing a solution right? The proof can be constructive too. Just like Global Round 9 Problem C.
Global Round 9 C doesn't need any construction.
If $$$a_1 \lt a_n$$$, there is at least one $$$i$$$ such that $$$a_i \lt a_{i+1}$$$, so we can always do one more operation and after this operation we can still have $$$a_1 \lt a_n$$$.
By induction all cases with $$$a_1 \lt a_n$$$ are solvable.
(Global Round 9 E is a textbook example of a constructive problem, however, so I'm surprised it wasn't included. F is also debatably constructive).
So you basically constructed a solution in which at each step you take such an $$$i$$$ such that $$$a_i \lt a_{i+1}$$$. The proof of the existence of such an $$$i$$$ is by induction.
So it is construction.
I take an $$$i$$$ such that $$$a_i \lt a_{i+1}$$$ because that's literally the only thing I'm allowed to do according to the problem statement. I never care about which $$$i$$$ it is.
Take following problem: find shortest path between vertices A and B in a graph. Dijkstra's algorithm can be used to reconstruct the path, so is this problem constructive?
Find maximum flow between vertices A and B in a graph. Max-flow algorithm can be used to find this flow, so this is also constructive.
Find the shortest edit distance between strings A and B. This is a DP problem, but you can traverse the DP backwards to construct a sequence that transforms string A into string B, so it is constructive.
By your (very broad) definition of constructive, is any problem not constructive?
For that matter, GR9C can't be said to be constructive either. The output is just "YES" or "NO".
I think people have somehow confused "ad hoc" with "constructive".
Downvotes coming but what's the difference?
Ad hoc means it doesn't fit into a category and having a solution to this problem doesn't really help you with having solutions to other problems in any way. Knowing the number of ways you can solve a rubic's cube in exactly 100 moves is ad hoc. It's cool, but for anything other than solving a rubic's cube, it isn't really helpful in life.
Constructive means you need to construct some solution. If someone asks you to come up with some operations that sort an array, or turn some lights on or off in a certain way, that would be constructive. Usually most constructive problems are ad-hoc because if the solution is constructing a way of doing it, that solution usually won't apply to much else, but occasionally that isn't true.
An example of a constructive but not really ad-hoc problem is: Given an undirected tree, direct all edges so that the length of the longest path is minimal. Print the direction of each edge.
You will almost certainly solve that problem by constructing a way to do it with a maximum path length of 1. But the solution is 2-coloring the tree. That's a common idea that is used a lot, so it isn't ad-hoc, but it is definitely constructive, since you clearly can't do better than 1, and you have found a way to do it with max path length of 1.
Huh isn't it just the exponentiation of the transitions matrix?
Yeah, I guess it isn't a great example of an ad-hoc problem since you could use that approach in other instances...
Maybe just 'the solution idea doesn't fit into any known categories' is a good enough definition on its own without an example.
There are some typical categories to which problems belong. Some problems are composed of multiple parts that belong to different categories, some categories are part of other ones (DFS on trees is part of trees). There's no fixed rule for what kind of categories we want, we just naturally gravitate towards the ones we use because they're useful. There are also small ideas that aren't useful as categories of their own, or specific algorithms, or too general terms.
An ad-hoc problem is just saying "we can't fit this into very useful categories".
In that sense, the Rubik cube problem is a decent example. Matrix multiplication or exponentiation or abstraction (to a matrix in this case) aren't used as categories because they're a well-known theoretical formula, a short idea and too general, respectively. If the category of the problem is its solution, that's pretty damn ad-hoc.
That doesn't make it not ad-hoc.
Then by that logic, if one were to add to the problem : " Also, print the sequence of operations" it would make it constructive? Even though the work (to think about the solution) remains exactly the same?
If proof to some problem consists of showing the existence of solution by actually constructing the solution, whether the problem asks the solution to be printed or not, it should be tagged as CONSTRUCTIVE.
Maybe in some cases, but definitely not always. For instance, almost all game theory problems are solved by constructing the winning strategy against any possible opponent move. I don't think it is helpful to call game theory 'constructive'. Usually you go into it not even knowing what you are trying to construct.
The hard part is identifying the set of winning states. Then providing a proof (which is almost always constructive) is pretty easy.
There are also lots of other problems out there in which the editorial contains some long and in-depth construction for how to do something and then like 99% of solutions are just "lol randomizer go brrrrr", with the intuition that "this almost certainly isn't breakable" and no one cares how to actually do it deterministically because we all got AC anyway.
I believe there is a decent distribution of topics in Div2Ds (even my last Div2D was Binary Search).
As for Cs, I think that A-Cs should generally be approachable by everyone (even newbies who might not know any topic) — so logical questions (AdHoc/Mathematical) make more sense.
Problem A-C can be Sorting,Data structure,binary search based(and other topics which even newbies are aware of). And don't they already have Div3 for that. I know a problem setter has to think of lot of things but I think that Div2C&D must use more concepts than they are using right now.As I said I don't hate these problems but since we already have A-B which are gerneral AdHoc/Mathematical we can allow C-D to be BS,Graph,Dp etc(just like your last Div2D). This balances the round perfectly(In my opinion).But I do undserstand your point as well.
Thanks for the regular contests btw.
The problem with having only Adhoc/logic based questions as Div2 A,B,C is that it becomes difficult for beginners to transition from consistently solving Div2C in contests to consistently solving Div2D as the level gap between these problems is too large.
So having moderately-easy DS/Algo/DP based problems as Div2B/C will definitely help many of the beginners in that transition as they'll get more exposure towards that particular Topic/Algo.
Why have you created a new account for this? take your downvote
Without trying to judge either too much, it is clear that we have two very different styles of problems. I'll give them neutral-sounding names to avoid some prejudices.
"Type A" problems: "classical Codeforces problems", most problems up to say, about round #600. Usually they contain some amount of "standard" techniques. However, they are not standard problems and are usually not solvable only by knowing standard stuff: you still have to think and observe stuff. Tend to be more implementation-heavy than type B.
"Type B" problems: "classical Atcoder problems", usually fall under the category of ad hoc, although the OP of this blog calls them "constructive". Also known as "Thinkforces". Usually are very simple after making certain observations and have near-zero implementation. Tend to have complexity $$$O(\text{size of the input})$$$.
I should note that these descriptions do not really do these two types justice. You have to solve some problems from each type and really feel the difference, that there are two kinds.
Very radical suggestion: can we separate these two types of contests? We already have three different "contest series" (regular rounds, "Global" rounds and "Educational" rounds) which have no detectable (to me) differences except minor differences in the format. Why not have regular rounds consisting of mostly type A problems, and call type B contests something else? Actually there already exists a site for type B problems, called Atcoder :P. Seeing how there is some kind of uproar after every type B contest (and there has been a lot more such contests (possibly due to antontrygubO_o's work as coordinator?)) it would maybe make sense.
Here are some other hitherto unpublished thoughts I have had while reading the numerous discussions on this topic. I'd like to think I am fairly neutral as I like both kinds of problems and don't have a strong preference as to which I'd like to see in a contest.
Some people have said things like "type A problems can be learned but type B problems are IQ tests/based on luck/whatever". I don't think this is true. Analyzing situations, making observations, coming up with lemmas is a skill like any other. It can be learned and practiced. When I first attempted to solve AGC problems I was stunned. Now I'd like to think I get respectable results.
Under rotavirus's now deleted blog several people were saying things like "do you really prefer implementing parsers" etc. I feel like that's comparing two extremes. Once again I don't think people are complaining about problems where you have to think, they are complaining about problems of a more specific type that I can't define except calling them "type B" :P. Type A problems still contain a lot of thinking.
I find it funny that people are saying "contests now have only ad hoc problems, it's not diverse at all". Since ad hoc is more or less defined as "anything that doesn't fall under any other category", ad hoc seems the most diverse of all categories.
The blog isn't deleted, it's moved to drafts
I think the important part is that the rest of us can't see it anymore
I can post it but I won't because the half of discussion is deleted :weary:
Maybe you should consider to post your blogs in other platforms and give us a link
Interestingly, I think I do well on "Type B" (and that's why my rating has gone up lately) but my AtCoder rating is < 2000 right now. But maybe there are other factors like Atcoder isn't "speedforces" and Atcoder is at a worse time of day for me.
I think Atcoder Beginner Contests are often "speedforces", and there is often medium / hard "Type A" problem(s) in them. Even last Atcoder Grand Contest (AGC 046)'s B and C were "Type A" DP problems in my opinion.
Yeah, ABC is not generally type B. I meant ARC and AGC.
As I have said earlier I don't hate these "Type B" problems but the only point I'm trying to make here is that we already have Problem A-B as these "Type B" problems , so we can allow C-D to be more of these "Type A" problems.
The result would be that the round tests us on a range of different topics.
Some problem setters mentioned that they try to make A-C as "Type A" problem for the newbies .We will still have A-B for newbies who don't know any concept and they'll still have A-B in their range.
Honesty I don't think anyone will oppose this coz this way the round would have a mixture of both "Type A" and "Type B" problems.
We can definitely allow, but why should we prioritize "Type A" problems over "Type B" problems? We should strive for better problems. Being "Type A" problem doesn't automatically make it better than "Type B".
Why should we test people on "topics" rather than on their problem-solving and observing ability? Most people who whine about constructive problems, just want contests to be biased towards them, due to their knowledge / experience.
In my opinion, we shouldn't complain about type of problems. We should strive for problems which force people to think in a way they have never seen. If we want to compare between such a "Type A" problem and such a "Type B" problem, most people should like the "Type B" problem more, as it doesn't force people to learn segment trees and gives fair chance to those who don't.
You misunderstood me. I'm not saying that we should have all problems "Type A" problems. I already said that in a contest A,B,C,D should be a mixture of Type A as well as Type B problems.
And saying that having "Type B" would give fair chance to those who don't know is a bit illogical tbh.What would you do then, scrap all Binary Search, Graph,Dp etc. problems so that all contestents have a fair chance ?
I think we both can agree on that the problems A-D can be a mixture of both "Type A" and "Type b" problems without any type dominating the other.
I think you misunderstood me too. I never meant to say we should eliminate type A problems. I meant we shouldn't care even if one type dominates the other, as long as problems are unique. And if we have to compare a unique type A problem (unique type A problems tend to be less unique as you practise) to a unique type B problem, we should like the type B problem more, as it is less biased to people who know segment trees and such. Type B problems often force people to think more, where most type A problems can be solved by just knowing what to think (from previous experience) and joining bits and pieces from other problems. Also, as problem-setters mentioned in other comments, unique type B problems are easier to create. As type B problems tend to be more unique, shouldn't they be dominating?
My argument is, a problem can be good, in fact even better if it doesn't have any mixture of so-called well-known data structures and algorithms. We should prioritize thinking over knowing. Do you disagree with it?
I don't think it's good. Many people will avoid one type of contests.
I have just seen your tremendous progress in atcoder this year. I have a question:
Do you think reading editorials help in atcoder problems? Many of them seem to be so unique that I feel I have learnt nothing after reading editorial. I understand how the solution works, but I don't understand how someone thought of this solution. What can I do to improve in such problems?
I don't think that's a bad thing. I'd much prefer people skip type B contests than whine for a week every time there is one. I don't know wjat it will do to the ratings though.
First I should note that the tremendous progress in rating is mostly just due to starting this year and Atcoder's rating system.
I don't really read editorials before solving problems. If I do I only read the first sentence that is new information. I don't know what you "should" do.
Can't A and B type problems combine together to make a hybrid type C problem, just a question that is it possible?
Both type A and type B problems are fine imo, but I think there are too many type B contests compared to type A and there should be a balance. I think too many type B problems result in some users who don't even know standard techniques(eg. basic segment tree) with high rating(Master/IM). I don't know what codeforces rating is supposed to represent but many people on codeforces are also interested in participating in OI/ICPC and they may get a wrong idea of their skill level due to too many type B problems and they will end up having a reality check at OI/ICPC.
Do you know any such user? I don't think many such users exist. Also, what's wrong with having such users? Their skill level is already high, maybe their knowledge level isn't. If someone is intelligent enough to reach IM without knowing segment tree (and similar), learning segment tree should be a piece of cake for him/her. Petr even invented fenwick-tree after IOI by himself without learning. Those who are interested in OI/ICPC, will/should practise in OI/ICPC problems anyway, those will surely give them good preview of how those problems look like.
To be honest I think it was possible to reach Master/IM wothout knowing segment trees even before type B became common.
This is just my personal opinion, but I think that most problems on codeforces shouldn`t be ad-hoc/constructive. I think that the best problems are the ones in which two criteria should be met:
$$$1$$$. There should almost always exist a straightforward(not necessarilly in implementaion, but rather in idea) bruteforce solution to the problem.
$$$2$$$. By looking at a small testcase, it should always be obvious what the answer is.
My main point is that the goal should be to take some existing solution, and then optimize it so that it passes the time/memory constrains. But in the adhoc/ constructive/formula problems the goal is often to just understand what the answer should be, and when write the solution in like 2 minutes. These problems aren't related to programming, any person skilled in math could solve them(find all the needed observations) after some time, but he wouldn't be able to do so with just bfs/dfs for example.
Also, I think adhoc problems just really discourage many people. For example, many people learn and know segment trees, hashing, dijkstra, dsu, etc, but have almost zero chance of using them on the contest.
Well, in my opinion, ad-hoc problems (which seems to be the term you are looking for when you say that a problem doesn't use well-known concepts) is what makes competitive programming problems so special. Anyone can memorise code that does something. Not everyone can figure out how to solve problems using that code.
If you think about it, most problems are ad-hoc to some degree. For example, almost no OI-style problem will literally be "implement X algorithm". Instead, you have to think about the problem and make some observation about its properties, which will help you realise which technique you have to apply to solve the problem. In that sense, "ad-hoc" problems are really just problems which test more of the thinking and observation, without requiring you to code a well-known algorithm afterwards.
In that regard, I feel that there is nothing wrong with contests that are purely ad-hoc problems. It still tests your problem solving ability, which I feel is much more important than testing "do you know X algorithm or Y concept". Of course, some people may prefer contests which are less heavy on observation making and more heavy on implementation skill or advanced topics. This is honestly a matter of personal preference. I feel that codeforces currently has a diverse enough range of setters with different preferences that there are contests for everyone to enjoy.
Also, while I'm not well-versed in problemsetting, I do feel that more ad-hoc problems emerge when you work forwards from the problem to the solution, and more classic problems emerge when you work backwards from the solution to the problem. Maybe there are so many ad-hoc problems because problem authors prefer the former method?
Wtf man there are ad hoc problems in the math olympiads. The only thing which makes cp unique is implementation/debugging
Well, there seems to be implementation/debugging in other areas of computer science as well, so we're both wrong :)
Anyways, would you not agree that cp ad-hoc problems are rather different in style and requirement than math olympiad ad-hoc (which usually requires more proving and less observing?)
I mean, it's makes it unique among the field of mind games
Ah, I see. I meant that ad-hoc problem solving is the unique point of cp among the field of computer science. Sorry for the misunderstanding!
Lmao man comparing cp to other computer science is so stupid
P.s sorry, comparing cp to other computer science isn't stupid. CP should educate programmers that their code will never work right from the first run, so they should write code in such a way that it's easy to debug.
Btw that's why these stupid mathforces problems are bad
Well, my perspective of cp seems very different from yours :)
yes cp educates us a lot including the skill of solving math problems but the skill of debugging is the greatest among the learned skills
Answer to this question :
Something like this happens when you tag people, skittles1412.
I guess Ashishgup rounds were great.They had game,2-D grid dfs,dfs on tree i guess it was problem E in one of his rounds and even in one contest i remember problem B on strings if done in o(n) complexity use simple dynamic programming and ofcourse in his last contest problem D was on binary-search,and all this with good mixed pool of adhoc so i guess his rounds were perfect.Also forgot to mention problems on number theory in his last round.
Your fanboy bias apart, AshishGup making 3 rounds clearly diluted the quality of his problems. It seemed every 'acceptable' problem made it to one of the sets, with no attempt to make either a high quality or perfect round. Might just be my personal opinion, but the rounds were far from perfect.
Do you have any logical argument against constructive / adhoc problems, except "I would like to see more problems with well-known data-structures and algorithms"? I think adhoc problems (intelligence + luck) should be prioritized over problems that require specific knowledge / experience (knowledge + experience + intelligence + luck). Why force people to know segment trees, which we will probably never use outside CP? More adhoc problems mean people will try more to increase their problem-solving and observing ability than to learn mobius-inversion + treap + fft + convex hull. Any problem that forces people to think in a way that he has never seen, is objectively better than problems that can be solved by knowing what to think and joining bits and pieces from old problems.
They have nothing common with programming
Hard constructive problems can be implementation-heavy too. It's just that, those codes aren't blind joining of bits and pieces of so-called well-known data-structures and algorithms.
dude, we can increase these skills from math problems too, and not only from math problems but even from physics problems, chemistry problems, chess problems and even playing football/billiard.
So? How does your statement imply that we shouldn't prioritize problems in CP, which require more thinking?
I want a computer to be a significant instrument for solving. I want CP to be unique. But these problems make CP "another mind game".
If we decrease constraints from N=1e6 to N=10, most problems can be solved by hand, constructive or not. The only problems I can think of, which require computer in the process of solving are brute force and constructive problems where you need to write a brute force to find a pattern. If we keep constraints to N=1e6, almost no problems can be solved by hand, constructive or not. So, I don't see your argument to be specifically against constructive problems. CP is unique in a sense that your solution needs to be scalable to fit TL, ML.
The computer is also useful in situations when one has coded a solution, but it provides the wrong output at the samples, which makes the participant find a mistake. In math competitions, there aren't any samples, so participant should prove the correctness of their solution by themselves
The same can be done in many constructive problems too, by coding generator+checker.
I mean it is useful in general, for all types of cp problems, which makes it unique from math competitions
On a completely unrelated note, Why aren't there any Errichto rounds anymore.The last one was way back in 2019 ?
How do I improve on ad-hoc problems? How do I improve on these so-called IQ testing problems? "Type B" problems as -is-this-fft- called. I am quite bad at these problems. The Editorials don't help much in these kinds of problems, too unique and too specific to be useful. I would appreciate a problem-set where I can practice such skills in one place. AGCs come to mind but they are often too hard for me. Any ideas much appreciated.
You should learn how to think well, and how to find your way through problems, the best way to learn this is practicing hard, probably.
Not to mention that the Global round consisted of 8 constructive algorithms, out of 9 problems.