Блог пользователя ADJA

Автор ADJA, история, 4 года назад, По-английски

(this was originally intended as a comment to another post, but it turned out very lengthy, so I separated it into its 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 criticize, 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 and other coordinators' style or not, let's not forget that they have done a lot of work, and let's thank them 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, and let's consider it as a "trend", and not particularly tie it to a single 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 fully valid. If you look at ABC and ARCs, you will find plenty of algorithms, data structures, 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 AGCs, 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 standard. It's probably easier to come up with a fresh adhoc than with a fresh DP problem), but let's not forget about other 95% of population. For a lot of 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 with different skills; similar thing applies to setting contests.

Defining a problem

  1. For the lack of clarity, 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 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 or computer 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 of course it's subjective.
  2. 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 a 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 this debate is about. So what is it about?

  3. I think people generally don't fight against adhoc/constructive problems themselves. They fight against unbalanced distributions in a lot of recent contests, and I agree with them. When there are too many problems with a similar topic, it becomes boring. If the recent trend was "2-3 binary search problems in every contest", then people would fight against 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 a 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, or a simple parsing. There are a lot of problems that can be set with these.
    • Implementation is also important. I, and I think a lot of other people, find implementation interesting too. Figuring how 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 combination 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 algorithms 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, IOIs (and other OIs), and Google Code Jam rounds. They often have a great distribution. If there were 50% of adhoc problems there, that would be weird, right?
  2. 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, etc), shrink number of problems to 5-6, and take that.
    • Or let's take 8-10 random problems from a good online judge (like Timus, or even CF archive itself), again throw away too hard or weird problems, and that should be good.
    • And anyway if more than 30% of your problems are on the same wide topic, or feel artificial, or something, you should reconsider it and mix things up.

What are your ideas for a good distribution? And what do you generally think on the debate?

  • Проголосовать: нравится
  • +301
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +10 Проголосовать: не нравится

Auto comment: topic has been updated by ADJA (previous revision, new revision, compare).

»
4 года назад, # |
  Проголосовать: нравится +272 Проголосовать: не нравится

let's provide constructive suggestions

please no

»
4 года назад, # |
  Проголосовать: нравится -48 Проголосовать: не нравится

Ad hoc literally is “doesn’t fit into any other categories”, so it’s already diverse on its own. Your complaint with diversity doesn’t work then and the same with the comparison to binary search, as each adhoc problem uses a different unrelated way to solve compared to another one.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +29 Проголосовать: не нравится

    Come on. Please reread point 1 under "Defining a problem". I hoped there are no comments like this.

    If a lot of problems don't fit into any categories, then "ad-hoc, no category" category is overrepresented too, right?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится -24 Проголосовать: не нравится

      I read point 1. You give many bullet points to seem like you are describing a very specific type of problem but the points are all so vague there is plenty of room for diversity (in terms how you arrive at a solution, implementation, etc.), even among problems that fall into that category.

      "It's very observation oriented (you consider problem on paper or computer to find some patterns, etc). After you notice something, it becomes easy."

      Literally every good cp problem needs some level of observation. What's better that "After you notice something, it becomes easy?" A problem being easy before you notice anything? So like you read the problem and you instantly know the solution?

      "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."

      Somewhat fair. Most of the things that you mention are too hard for <= div2C. You mention sets/maps, and I don't think sets/maps are that much more interesting than arrays. In general though, problems that don't require these well-known techinques can be very diverse, as DucPro said.

      "Often it feels like there is not much benefit from a computer"

      What does this even mean

      "and implementation is light."

      Fair. However, easier problems should have light implementation, and that's half the contest right there. Harder problems rarely have trivial (<= div2C level) implementations.

      "It could be purely math competition problem, or not too far from it."

      Disagree. I think that there has been barely any of these kinds of problems lately.

      "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 of course it's subjective."

      Literally every CF problem has some sort of background to "contextualize" the problem. "Ad-hoc" describes the solution of a problem, not how a problem is presented.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +7 Проголосовать: не нравится

        I think the main disagreement is essentially with the statement "problems that don't require these well-known techinques can be very diverse". While this can be true, very often "ad-hoc" problems, especially easier ones, end up having one of these three general strategies:

        1. Find value to sort by/order to do something in, sort it, then just do some basic iteration or prefix sums.
        2. Find a formula that allows you to quickly find some value with little implementation outside the formula.
        3. There is specific condition that can be described in single short if statement that solves the whole problem such as "is certain elements in these positions" and very similar. Sometimes combined with strategy 1 where you need to sort first.

        Hopefully this is a more specific enough definition for the recent trend of problems for you that at least I and I believe other people are seeing. Specifically I would call them Greedy, Dumb Math, and IQ test. Sure the premise and proof may be completely unique, but at the end of the day, you still end up writing one of these three things.

        These are where all the statements along the lines of it "Often it feels like there is not much benefit from a computer" come from. While the proof of solution may be long, the solution itself and its code can be described in a single sentence by one of the strategies stated above and does not look more clear and logically layed out when coded, which is why it feels like it should be a math contest problem because that is where you would also have to write proof.

        These problems to me feel the same way as people who think "all dp problems that are just optimized by using a segtree or similar to do faster transitions are the same" (which is very similar to actual message I saw). I enjoy some every now and then, but I dislike contests where nearly every problem is one of these (look what it did to my rating :( ). Like the op says, the main demand people really want is just more diversity in problem types as opposed to the three above, not an abolishment in these problems.

        I will also disagree very much with the statement Harder problems rarely have trivial (<= div2C level) implementations. Just look at past few contests smh.

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        I am not sure what you are coming at. I tried to describe the recent trend as accurately as I could, want to try to do it better? Or do you think there is no trend for such problems?

        I see you attack the bullet points separately, but in reality you should consider them together. Recent "trendy" problems can be described as AND of these bullet points (maybe some subset of them), not OR.

        And of course problems in different topics need observations. Problems of all level can have light implementation. And nobody is saying <= div2C should have difficult algorithms, but it doesn't mean they all should be adhoc puzzles.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +59 Проголосовать: не нравится

    "Doesn't fit into any categories" ≠ "are diverse". The problems can all be similar but not fit in a defined cp category. OP gives some pretty good points on defining what makes the recent ad-hoc problems feel similar under point 1 of "Defining a problem".

    I agree that OP's binary search example is a little extreme and would be a more blatantly obvious lack of diversity that would never be approved by a coordinator, but I still feel the complaint with the ad-hoc trend is relevant and warranted. There's a very clear difference in how these problems feel in comparison to more traditional DP/implementation/graph problems.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +19 Проголосовать: не нравится

    uses a different unrelated way

    If this were true, how would you ever improve...

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

For me "play with a problem on paper, then code something trivial when done" is much more interesting than "write some STL/DS and play with its details while coding the trivial solution".

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +77 Проголосовать: не нравится

    Sure, different people like different things. It's bad when one of the extremes is rather overrepresented.

    Also, just to clarify, [simple] problems with STL/DS don't necessary need to have trivial solution.

»
4 года назад, # |
  Проголосовать: нравится +57 Проголосовать: не нравится

I do agree with you and I want to keep this in the "recent actions" list for some more time, hence this comment.

»
4 года назад, # |
  Проголосовать: нравится +36 Проголосовать: не нравится

For me, that indeed doesn't add beauty to the problem, and feels repulsive

I thought only I felt like that. Though some DS problems can also be like that (but still they are more exciting to do!).

So I think when asking for opinions like in Anton's post, it's important to include a great range of people with different skills; similar thing applies to setting contests.

It was very sad to see Anton begin his post by opinions from a very elite group.

But still Adhoc and Constructive do matter like others.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +21 Проголосовать: не нравится

    When I first switched from math to CP, one of the things I was attracted by is that CP problems often feel natural and real-life. Unfortunately, that's not the case for many recent Codeforces problems.

    And no, I won't accept "Mike received an array for his birthday" as a real-life scenario :)

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I don't think real life scenarios should be a factor in trying to determine a problem's goodness. They just add complexity to a simple question, hence shorter problem statements.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    That's true, real life situation or "legend" shouldn't be a requirement of course. Even though I prefer when there is one, it's somewhat subjective.

    But I notice that a lot of "artificial" problems also tend not to have any good legend behind them too.

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

On an unrelated thing: it's somewhat hard to have a discussion or debate on Codeforces, when the "losing" (less popular, I guess) comments are downvoted and CF hides them. I would be nice if, for example, the author of the post could manually unhide comments, or turn off the comment hiding feature in the post completely.

  • »
    »
    4 года назад, # ^ |
    Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    I mean, if being agreed with is just a function of being seen, if CF didn't hide bad comments, wouldn't the 'winner' of any debate just be the person who comments more? It seems pretty helpful to me for us to be able to shut up people who are just indefinitely spewing nonsense.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +11 Проголосовать: не нравится

      Well, it's not only about being agreed with. Hiding comments feels a bit like censorship, especially when a comment is downvoted just because majority doesn't agree with it, not because it's nonsense/abusive/spammy/offensive/etc.

      But sure, hiding comments often has its benefits too.