Sorry for my poor English.
I am talking only from Div2 perspective as I think Div1 contest are still ok from this point of view.
During 2020 codeforces moved from having problems with variation over known algorithms and data structures to constructive heavy contests. I am not saying that having constructive problems are bad but their amount is way too high and I guess most of us will agree that now a days problems on topics like binary search, DP, Graphs or segment tree or other data structures etc are almost extinct in Div2 rounds.
Lets take last Div2 Codeforces Round 696 (Div. 2) as an example someone who knows programming language and basic number theory could solve problems till E and can get 1st rank. So in theory someone could become a master or International Master with just number theory and programming language knowledge.
I used to like constructive problems a lot (Actually one of my stronger topics) but now a days there are just so much constructive problems that they are just more or less becoming boring in my personal opinion.
I would like to present my points why this is wrong
- Sometimes many problems are just checking too much cases or having just one observation. It just makes the contest that who can observe something quickly other than visualising the problems from different angels and brainstorming.
- Variety of problems in a contest are decreasing
- Contests are lacking a main thing that you can learn new topics by upsolving problems and reading editorials as now most of them are based on few observations which are less likely to repeat or generalised. Now you can learn new topics only through Div1 contests or through only last few problems of Div2.
- People reach div1 without having too much experience of basic data structures and algorithms and then have to solve problems that require good experience over those topics and in turn creates knowledge gap.
I would like to ask contest admins to also look a contest from a perspective that is it teaching some new topics to someone who is just starting and also people to practice common topics to get a stronger grasp on them. Having too much constructive problems neglects this aspect of contest.
Exactly. When I solve constructive problems, I feel like I am wasting my life. Trying hard to find an observation (which might almost never be repeated), while learning nothing new. On my face, I have Sad_reacts_only. I am curious though, do ad-hoc problems actually help people to improve in general? To me, they only seem like solve-and-throw.
I think they help improve one's problem-solving skills. As far as I have observed, with proper problem-solving strategy most of the constructive problems can be solved feasibly. I think they help us to think from a broad perspective. In my opinion, the joy of problem-solving lies in exploring the unknown and not memorizing a bunch of common techniques to get some internet points. Even though I am not so good at Adhoc problems, I enjoy thinking about them. And I code mostly for enjoyment. So maybe that is why I am a bit biased.
When I solve constructive problems, I feel like I am wasting my life. Trying hard to find an observation (which might almost never be repeated), while learning nothing new.
It isn't true you are learning nothing new. While most people seem to like ad-hoc because they're "completely new and original ideas" for each problem, the type of div2 ad-hoc people are referencing is really just being able to use intuition and
guessabuseapply common invariants. So through doing them, while they may seem unrelated, you are actually learning common strategies for proving processes go in some direction.However, I do find these to be the most boring problems of all. They have little programming value added usually, despite being in a programming contest, and are almost always the least memorable types of problems to me, as there lack of "movement" so to speak in the solution makes them not very intriguing. And I think it won't be long before the Chinese OIers produce content on how to systematically approach these problems too lol, as to me they in fact they are the most "textbook-like" despite people saying this about ds problems, as I have been improving by literally listing through invariant ideas I've seen before until I guess one right, as opposed to being able to work up to the solution. Also I think having contests filled with too many of these produces invalid comparisons of skill.
But this blog topics in general has been discussed many times lately, and I think setters/coordinators want to introduce more variety in areas of div2 problems, but I rather have contests with low variety than none. But I think high rated setters do overvalue the "standardness" of some problem proposals relative to div2 knowledge, which is what also enforces more invariant spam problems. That sums up all my thoughts.
You are definitely right. I'm fine with these types of problem but I feel like learning new algorithms and data structures are of very little use to solve these types of problems. I gradually learned to just guess some key observation by playing with a few cases.
Why don't you propose one?
imo you don't need to become a problemsetter to have the right to complain about problems lol
Also, even if someone proposes such problems, I doubt they will make it past the round coordinator.
They will tell you that it is something standard or a variation of something standard, not realizing that their own experience is not the same as that of most of the participants out there.
Yes. Thanks god it's not some inexperienced idiots doing coordination otherwise we'll be seeing contests full of CSES copy pasta.
That's definitely not what I said! (No one wants the unrated Codechef type contests)
I just want the experienced coordinators to keep in mind the above fact.
For example,
doesn't affect more than $$$90\%$$$ of the people here. Such problems should make it to at least the Div2. rounds of CF.
The only issue I can see here is paying the author for unoriginal work.
Why do you want to make a rated contest with recycled problems? Just upsolve them if you want to solve them again...
And what happens to those 10% who has advantage because the author decided to recycled problems? Do we completely ignore the "competitive" part of the "competitive programming"? That stuff should NEVER happen even if we know just a single person is affected, let along 10%.
Like I don't understand how do you ever think what you're saying makes sense.
Why are you taking all my statements to the extreme? When did I ask to recycle a problem?
Anyway, I agree with you on the "competitive" part, I was earlier speaking purely from the "being educational" perspective of a contest (which I think once in a while, a few Educational Rounds can take care of).
I mean he clearly knows what kind of data structure problems to put in div2 A.
I have proposed one contest actually in August and finally got a reviewer assigned. Hopefully you will see the contents in upcoming months.
P.S — I don't mean that problem setters or admins are not putting efforts. I only want to comment on their problem selection part.
My point was that if you know ANY data structure problems to put in div2 ABC without it being some copy pasta of another problem, they'll be happy to accept it.
I don't remember any constructive problems in the recent contests. Can you show an example?
Edit: well, there is one, I even solved it during the contest. But point still stands, they are very rare.
Last contest (round 696), A, B, and E were all constructive output: make binary string, number, and permutation that satisfies conditions. Not too rare it seems.
B is debatable, it's just output the n-th number of the sequence. A, ok, didn't read, ig author likes such tasks.
What about other rounds? I've briefly read the statements, don't seem like that.
Edu 102: C is construct permutation
Round 695: A is construct number
Round 694: 1D is construct vertex set of tree
Can you show me a recent round without a constructive output? And some people consider constructive just based on thinking process too, but I wouldn't.
Also, I think it's possible to make a completely constructive and/or ad-hoc round that still feels diverse. The thing is with all I have listed except the 1D, the problem is just realize a single invariant and then have 1-liner unenlightening implementation, which is recently often the general idea for many of the problems of the round. Though in very latest contests besides 696, I do think they've been more diverse. And the Edu 102 is I think around my ideal div2 round.
Vertex partition is a "constructive output"? In that sense every NP problem falls into "constructive" if you are asked to print proof.
I just don't understand what ad-hoc/constructive tasks exactly are. What to avoid when setting a contest.
Well ad-hoc and constructive are very blanket terms. Constructive is just any problem in which you are assembling some sort of arrangement as the output. Ad-hoc is any task that doesn't fall under a typical algorithm or ds category.
However, when people complain about these problems being over abundant, they almost always mean the "invariant using only for loop with if statement" type problems, which I believe is the case with this blog. Because it doesn't fall in a more specific category, it's often labeled as an ad-hoc or constructive, which isn't wrong, but overly broad. I think there should probably be term created specifically for that style of problem. And on a side not, a cool idea would be someone to make a graph of problem types that shows different levels of specificity and wot terms are subsets of others, as categorizing problems is kind of hard with people having different mindsets of specificity.
Though "single line invariants" are my personal least favorite kind of problem, there is no reason to avoid it, or any other specific type of problem when setting a contest. The only thing to try to avoid in my opinion, is setting too many problems with too similar a solution, as it's more fun to have to make many very different ideas and code in a contest. As naïve as it may sound, look at the solution codes for each problem and if too many look from a distance all very similar it probably is not diverse enough. In other words take into account the problems as a whole too when considering how interesting they are.
Yeah, it's possible to make such rounds. But simple problems tend to have less steps, e.g. single invariant, in solving process.
This is definitely a conversation that's happened on CF before, and I've made comments in the past in support of DS/Alg problems. However, I do want to note that since then, I've kind of accepted that DS/Alg proponents like myself are fighting a losing battle. Codeforces' format has always been more speed oriented than other formats like USACO or long challenges, and when you have to provide a lot of problems to solve in a short time span, it makes sense that problemsetters would tend towards ad-hoc, which typically have shorter implementations. And given how so many problems have already been written by now, the average DS/Alg problem is considered standard by most competitors, and there's probably already been some random contest from 4 years ago that used the same idea. It's much harder to come up with a unique DS/Alg task. I love those types of problems, but they'll probably be few and far between.
(Also, totally agree with SuperJ6's comment above that Div 2 ad-hoc problems are not as unique as most people think, they're usually just finding the right greedy invariant that's showed up in some capacity before)
I would like to see more problems that are a twist of classic problems / well know (not that well known actually) algorithms. Educational rounds often have those like this problem F that is a maxflow problem
I agree with SuperJ6 saying that the div2 ad-hoc problems have a certain feel to them which is usually present in almost all of them. The ad-hoc problems would be better if they were similar to the ones from ARCs but it would be best if there was more variety of problems like you've mentioned. Also SuperJ6 mentioned that the authors usually overestimate the standard-ness of a problem because they're higher rated. I guess a solution to this could be having a few more div2 competitors in the problem setting.
I agree completely but constructive might not be the best word to describe it. Recently I've been considering if I need to study MO stuff just to keep up with this trend.
by MO you mean IMO right? Is that a reference to Mr.'s anton obscure past?
Not only IMO because not everyone goes to IMO and it's not the only math competition. And I'd lie if I said that anton's not one of the reasons for saying this but he's not the only reason of course. I just generally feel like there are too many problems recently that you kinda need to come up with the solution out of thin air (sometimes not even really coming up with it, just guessing) then coding is trivial.
Atcoder :thinking:
I think this is a problem in div 1 as well, particularly on the easier problems :(
Looking at the past few div 1 contests (I'll only talk about problems I managed to solve),
Codeforces Round 694 (Div. 1): up to problem E, there are no algorithmic or data structure problems. D is a constructive problem in a graph, E is DP.
Good Bye 2020: Up to problem G, I think G is the only algorithmic problem, and there are no data structure problems. D and F are graph problems,
Codeforces Round 692 (Div. 1, based on Technocup 2021 Elimination Round 3): Up to C, again no algorithmic or data structure problems. A and C are constructive problems, and B is a simple math problem.
I think it's really sad. Nowadays it's very common to not encounter any data structure or algorithmic problems in a contest, and it's not uncommon to face only problems where you need a single idea, then can write very simple code, or are requested to construct something.
As a sidenote, I think it would be really really cool to see more types of algorithmic tasks, like approximation algorithms and distributed algorithms (like this problem from datatähti open 2017) represented.
I'll disagree with your opinion on Good Bye 2020.
A, B -- nothing interesting for us.
C -- during the contest I wrote a dynamic programming solution. In my opinion, DP's are definitely algorithmic problems. I just checked the editorial and it also mentions a simpler greedy solution without any difficult coding, so I understand that our opinions can be different.
D -- okay, but ad-hoc.
E -- I don't understand why the task isn't "algorithmic". I know that I can do most of my work on paper, but the final result -- at least for me -- wasn't a simple sum you could rewrite to your code and get a mindless AC; for instance, you had to count the number of times each bit is set in the elements of the sequence to get the complexity down by a factor of $$$n$$$ (this isn't a hard trick for us, but it's still an algorithmic trick in my opinion).
F -- my solution uses a standard generalization of Find&Union. Definitely a data structure (a simple one, though, probably too simple for F). Editorial says about some solution computing MST, so some algorithms are in use here as well.
G -- a couple of ideas and a heavy implementation; hashes everywhere.
H -- a quite hard DP, definitely algorithmic.
I -- an ad-hoc, quite algorithmic (kinda resembles SMAWK in my opinion).
On the other hand, I'll admit that the problems (apart from G--H--I, possibly) weren't too implementation-heavy and didn't require you to invent hard data structures, while the "older" Codeforces used to have plenty of those. Is it worse now? Personally, I don't particularly miss problems that gave you an array and told you to perform $$$7$$$ different kinds of operations on it (unless they're really cool operations). However, I wish we had more problems that feel very natural, but require complicated algorithms and/or data structures.
teri kyu gaand jal rahi hai fir bsdk? Master ni ban paa raha?
Easy way to gain contribution — "write a blog criticizing something".
If you think this is for just contribution then downvote this post and my comments. Simple
I think it's really hard to generalize things from constructive problems unless you really spend time and effort for it. Constructive problems also encourage people to memorize them instead of trying to generalize knowledge from them imo.
I like adhoc and constructive problems myself but too much of anything is bad I think. Probably if there was over abundance of ds-algo problems in contests instead, people would have complained that time too. I did a lot of live contests and vc the ones in which I couldn't participate in past one month, but my algorithmic knowledge didn't move even an inch. Tbh, I sometimes don't even feel like upsolving the problems :( Sure, I didn't go beyond div2D though but still just wanted to share my thoughts :)
Codeforces Round #696 (Div. 2) need various skills:
Overall, I think it is a good Div 2 round.
I thought Codeforces Round 695 (Div. 2) was one of the better rounds too. Though A was constructive, it needed you to think a bit xD. C was observation + greedy, D was DP, E was graphs.
B may have been a bit harder than expected, but I think this is a quality div2 too. It got a lot of hate though cause people probably got a lot of WAs on A.
I completely agree
the round which I enjoyed the most :p
Is it not enough to have a separate type of rounds (Educational) for that?
As a person who has actually seen several (hundreds) problem proposals, I assure you that contest admins do not reject algo/ds problems just because they are algo/ds. We reject them because they are rehashes (or just copies) of textbook problems most of the time.
If you fix some algorithm and say "I will come up with a problem about this algorithm", most probably you will come up with either "write this algorithm" problem or some problem from 5 years ago. That's just the reality of problemsetting now.
If you try to come up with a problem on some not-easy algorithm, which is actually interesting to solve, most probably there will be 2-3 layers of reductions before applying the algorithm itself, thus rendering this problem having at least div2D difficulty. Almost all div2ABC problems are inevitably just implementation / simple greedies / math, because anything else will be harder.
Then there is a thing that people who propose problems usually want to set contest as early as possible. People don't like to do more work than it is kinda necessary, even though they should. For almost all the problemsetters if they want to conduct a contest with X problems, they have to come up with at least 2X problems, usually more than that. For not experienced authors you can multiply that by 2 easily, because half (I'm being modest here, 80% is not unreasonable) of their problems will be well known or boring.
But most authors come with attitude "Here, take my gorgeous 5 problems, they are very diverse, ideally balanced by difficulty and just awesome. Also you should prepare them yourself because I'm very busy". And we have to shatter their beliefs, by rejecting 3 problems, and downgrading their div2D to div2B because they did not see an easy solution. Then they are starting to send you 5 problems a day, most of them even worse than initial problems because they were created in 1 day, just because "I want to set a contest, why did they reject my awesome problems". Some problems do not get rejected right off the bat, and authors now think that they are prefect, because this fcking coordinator is nuts, he accepts only perfect problems, there can be no other explanation why 10 last problems were rejected (explanation — they were awful). You can remember several new setters complained about 70 problems being rejected, like that's making 5 problems not rejected being the greatest. It is not. It just means that your internal level of "problem I'm not ashamed to show to coordinator" is waaaay too low.
"Ad-hoc" problems have better chances to be not already used 5 years ago, so of 70 problems sent what's left is mostly ad-hoc, because you didn't spend time creating the problems you actually like, you just spammed admin with hundred problems hoping that he will accept 5 of them because you want to set a contest.
So, my advice. If you want to see more algo based contests, set them yourself, but take your time, and listen to coordinator, he has much more experience. We also like great algo/ds problems. You just don't provide them. So we have to construct contests from good problems of other types.
If you just want to solve good problems and learn standard concepts — SOLVE ARCHIVES. We don't let old problems to new contests because obviously we don't, but it doesn't mean you can't solve them on your own. I don't understand why is it so hard to grasp.
I'm sure div2 participants mostly wouldn't mind slightly different problems from 5 years ago if it's not googleable. For me most div2 problems are similar to older problems anyway so it wouldn't change a thing for more experienced people.
Then they should go to archive and solve problems of 5 years old.
Well they get the mostly the same experience for A-E but for 1-3 years old problems... Concrete example: some dude that got 3 div2 contests with basically the same dfs tree problem. This other problem: https://codeforces.me/contest/1362/problem/E where the greedy works but I've seen this exact greedy years ago and even discussed how to prove it in discord...
I don't understand what you are saying. Admins are not perfect and sometimes we have similar ad-hoc problems too? That's true, what's your point? I'm not saying that we do not check ad-hoc problems for being available on the net, I'm saying that in my experience ad-hoc problems are less frequently (but that still happens) happen to be on the net.
No, my point is that admins are not perfect and almost every time you have similar ad-hoc problem thus don't be so strict at least for div2.
"happened twice" != "almost every time". What a weird solution to the problem. We can't know all the problems, so let's just don't care about our problems being unique.
I'll repeat it once more: If you want to solve old problems — archives are open for you. On regular contest we want to have new problems. And it's not admins mistake that setters do not provide nice algo/ds problems.
Those are just 2 examples I have right there. I can just open up all the other contests and post a huge list here of problems that are really similar to previous problems. If that's allowed why not allow similar data structure/algorithm problems?
Sure, please make a table of pairs of very similar problems. I'll take a look. "I remember something similar don't remember where" doesn't count.
Being a regular participant of div 2 for more than 8 months, I won't mind solving tweaked standard data structures and algorithm problems from 5 years ago, if they are not googleable (covered with a good story).
It might get boring for div 1 participants who have been doing this sport for a lot of years.
And regarding solving old archive problems, I will not mind solving problems from archive but it will be good and healthy and if 10k other people are also solving those problems and having a healthy discussion.
This sometimes happens that when I solve an old problem and I don't understand a part of the editorial or I am not able to understand where I am going wrong and I post a comment about it, it goes unnoticed. Many other people will definitely have the same experience.
I think that admins also need to change their problem selection criteria somewhat. They don't just need to make sure that their problem set is all brand new but they should also ensure that a new participant should learn new things ( which doesn't happen that much in constructive problems).
Side note: were those problems from 5 years ago really that new or were standards for problems lower as well?
I do virtuals of old contests sometimes and I can't believe the stuff that used to get accepted! Take as a concrete example 932F - Escape Through Leaf (this is only 3 years old and the frequency of such problems increases as we look at older contests). The problem is "do small-to-large merging of CHT" and the reduction to that is almost immediate. This would probably never get accepted on CF today but was it really that fresh in 2018?
I'm not saying that I want to see such problems in contests but it seems that standards have gone up a lot too.
The problem you mentioned is boring, but I don't think that it was a copy of something 3 years ago, CHT was not that popular yet. I have never wrote Li-Chao tree as of now, not to say 3 years ago, so implementing your proposed solution would be hard for me. Some problems are more technical, that's fine.
If by "standards have gone up" you mean "more algorithms are considered textbook and more problems are considered well-known" then of course it is true.
Great analysis!
These issues are related to the originality of the algorithmic problems proposed.
Personally, i think div 2 problems don't need to be entirely original because they are made for people that dont have that much background on CP
That is the reason why I like Atcoder Begineer Contests, Everytime their last three problems are Algo/Ds Based mixed with tricks, almost every ABC I participated it contains Dp, Segment Tree, etc in it.
Specially probem F of ABC are really educational.
The feeling when you comment on your own post! As a matter of fact above 2 comments are made by same person having duplicate profile :D.
Everyone knows that if contest appeared on codeforces, it was rejected on atcoder
And if it comes on codechef it was rejected on code forces
Actually there is no place for people other than antontrygubO_o here as people are huge fan of him coordinating shitty contests rejecting dsa problems assuming that the solution is too standard but saying that the problem is standard for div2 when you are an LGM is a shame for the coordinators like this in my opinion. At least 100 downvotes are welcomed
Constructive problems often more math-involved. And this is good for participating in russian school olympiads, because they nowadays tend to have more constructive / math problems, almost without algorithms. Just look at previous two school regional russian olympiads, they have almost no algorithms, they require you to make math observations and solution is most of time has very simple code. Perhaps, the reason why latest school programming tasks are more math involved / more constructive is because of the same reason: hard to make new problem on basic algorithm, so authors have same trouble with making new ideas of tasks.
For me, writing some classic algorithm is not fun, but observation + modified classic algorithm is perfect task which is really rare.