Yet more thought on recent "adhoc/constructive" problems discussion.

Правка en1, от ADJA, 2020-07-14 04:17:49

(this was originally intended as a comment to another post, but it turned out very lengthy, so I separated it into it's own post)

As it's often in debates, I think in this one there is too much polarization on both sides (people just attack each other), and a lot of ambiguity. I think there are some points to be made.

Premise

  1. Let's be kind to each other. Like it or not, this is just a current trend in the history of Codeforces, and it too will pass. No need to attack anyone personally. If you want to critizise, let's provide constructive suggestions.
  2. I've set contests before too, and I know that setting problems and coordinating is a very difficult job. It requires a lot of hard work, skill, experience, and patience. So like Anton's style or not (and this applies to other coordinators too), let's not forget that he has done a lot of work, and let's thank him for that. Thank you!
  3. It's also very mean to single out one person for the possible issue. While Anton may have a lot of impact here, there are many moving factors at play here, and let's consider it a "trend", and not particularly tie it to a person. Let's discuss the "trend" itself and how we can possibly make thing better if needed. I also personally enjoy a lot of Anton's problems too, even though I find them maybe too much math/adhoc/etc heavy (especially when there are several in a row). But let's discuss this in depth below.
  4. I also don't find comparison to Atcoder valid. If you look at ABC, and ARCs, you will find plenty of algorithms, data structures, and so on and so on. Sure, AGC may be skewed towards adhoc and math, but that's not only what Atcoder is.
  5. Some fun observation: I find a lot of very high rated people really enjoy AGC, and adhoc/constructive/etc problems. I personally can't really appreciate AGC beauty myself (probably because I am less skilled and don't usually get to problem C/D), and I think similar thing happens here. Very high skilled people may like adhoc/etc more for different reasons (for example, they may find a lot of DP/etc very standatd. It's probably easier to come up with a fresh adhoc than a fresh dp problem), but let's not forget about other 95% of population. For them, even something like manipulating things in a set may be exciting (especially with a great real life statement). So I think when asking for opinions like in Anton's post, it's important to include a great range of people; similar thing applies to setting contests.

Defining a problem

  1. For the lack of clearness, people use a lot of words to describe the recent trendy problems. Ad-hoc, math, constructive, etc, etc. Let's not pick on these words ("hey, it's not constructive at all!"), because I feel they are used interchangeably for the lack of a clear concept. So what's is the current "trend"? I feel there are several things to describe it (only some of them may apply):
  • It's very observation oriented (you consider problem on paper to find some patterns, etc). After you notice something, it becomes easy.
  • It doesn't require much of well-known algorithms and techniques (including, but not limited to, dp, graphs, data structures, sets/maps, etc.), and doesn't fit into these standard categories.
  • Often it feels like there is not much benefit from a computer, and implementation is light.
  • It could be purely math competition problem, or not too far from it. I also notice that a lot of these problems have very artificial statement and setting (like you are given array/permutation and some weird limits/operations/structure, and you need to find something). For me, that indeed doesn't add beauty to the problem, and feels repulsive, but it's subjective of course.
  1. Related to the previous point. A lot of people try to describe what they want, but do it poorly. They say: we want more data structures/dp/graphs/implementation/standard problems/etc etc. I think there is again a lot of ambiguity and lack of clear concept, so let's not criticize it as "not every contest should have a DP/data structure problem", or "there shouldn't be standard problems" – this is clearly not what people actually want. Let's also not say that "ad hoc problems matter" or constructive problems are cool. That's also of course true, but I think that's not what debate is about. So what's it about?
  2. I think people generally don't fight against adhoc/constructive problems themselves. They fight agains unbalanced distrubutions in a contest, and I agree with them. When there are too many problems with a similar topic, it becomes boring. If recent trend was "2-3 binary search problems in every contest", then people would fight agains binary search too. I think people don't mean "there shouldn't be adhoc problems", or "we want graph problems in every contest", or "DP never appears anymore" – they just say they see a big skew to adhoc problems recently, and it's a valid concern.

So what to do?

  1. I think an important discussion would be what is the good problem distribution in a contest should be. Some points:
  • I think it's very possible to give "algorithms/data structure/implementation" problems even as div2 A-D. "Data structure" here can be something as simple as sorting, or using a set, or making elements unique. There are a lot of problems that can be done with these.
  • Implementation is also important. I, and I think a lot of other people, find implementation interesting too. Figuring to best implement something that doesn't seem very elegant at first is a great problem as of itself in programming competitions.
  • Problems in a contest can be beautiful, but their combinations can still be bad. I think Global Round 9 is a great example of this. When first 5-6 problems don't need almost any algos and are done as "play with a problem on paper, then code something trivial when done" – it gets boring.
  • Let's look at famous well prepared contests, like NEERC ICPC semifinals, IOI (and other IOs), and Google Code Jam rounds. They often have a great distribution. If there were 50% of adhoc problems there, that would be weird, right?
  1. So what is a great distribution for a contest? I may suggest doing something like this to get a good distribution.
  • Let's take a well prepared team contest (like NEERC ICPC semifinal), exclude everything that is team competition related and not suitable for individual contests (really hard data structures, hard geometry), shrink number of problems to 5-6, and take that.
  • Let's take 8-10 random problems from a good online judge (like Timus of something), again throw away too hard or weird problems, and that should be good.

What are your ideas for a good distribution?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en3 Английский ADJA 2020-07-14 13:35:50 98
en2 Английский ADJA 2020-07-14 04:47:47 574 Tiny change: '------\n\n1. Let' -> '------\n\n\n1. Let' (published)
en1 Английский ADJA 2020-07-14 04:17:49 6770 Initial revision (saved to drafts)