Roundgod's blog

What are standards that a problem is good or not?
By Roundgod, history, 5 years ago, In English

How do you judge if a problem is good or not? If you need to rate problems, which aspects will you consider? Please feel free to share your ideas.

UPD: I posted this mainly because I want to build a standard to rate problems when problemsetting.

  • Vote: I like it
  • +79
  • Vote: I do not like it

Comments Comments (25)
| Write comment?
»
5 years ago, # |
  Vote: I like it +12 Vote: I do not like it

I personally consider a problem fun to solve if the idea to solve involves some observations that you needed to stitch together to get the solution. Basically not some standard algorithm or do as the question says.

→ Reply
»
5 years ago, # |
  Vote: I like it +62 Vote: I do not like it

For many people, the main aspect is unfortunately the shortness of its statement.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it -9 Vote: I do not like it

    Yeah that's why I like atcoder problems.

    → Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +71 Vote: I do not like it

    It's nowhere close to "main" for me but I think that long statements can make a problem worse.

    Actually, it's more accurate to say that long statements by themselves aren't a bad thing, but statements that are much longer than they need to be. If there's some situation or background that takes some time to state then it's perfectly reasonable. But often what makes statements long(er) is not necessary at all.

    Sometimes problems have great backstories. In those cases often the problem was (or feels like it was) invented with the story, and when hearing the story the problem just naturally drops out. Stating the problem without this story might actually feel unnatural, but with the story everything is beautiful and makes sense.

    In other cases it's clear that the problem did not originally have a story or had a different one and the author for some reason decided to invent some bullshit, except it doesn't work at all. This is a typical example of statements that are longer than they need to be.

    Particularly egregious are the cases where the story has literally nothing to do with the problem. I know some of them are meant to be "parodies", but at some point the parody becomes as intolerable as the real thing; even more, the parody becomes impossible to distinguish from the real thing.

    Another thing is some unoriginal "jokes". I think there is nothing wrong with having some fun with the statement, it does not need to be dry mathematical text. But if you insert some bullshit to an already-long statement, it begins to annoy. For example, I got pretty angry when I read these (source is 1340C - Nastya and Unexpected Guest):

    because it's difficult to stand when so beautiful girl is waiting for you.
    Since Denis has all thoughts about his love, he couldn't solve this problem

    Come on, the text is already so long, and such remarks serve literally no purpose.

    → Reply
»
5 years ago, # |
  Vote: I like it +14 Vote: I do not like it

I love some of those problems in which a very small concept or a fine detail sometimes makes everything supereasy

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +83 Vote: I do not like it

Positive factors:

  • describes a situation from real life or game
  • simple statement (NOT the same as short statement)
  • solution doesn't require complicated techniques

Negative factors:

  • Alice got an array of length N as a birthday present and want to answer M "xor of f(g(h(x)))" queries on range [L,R]
  • calculate some useless math shit modulo 998353 nobody ever cares about
→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +132 Vote: I do not like it

    I like math shit modulo 998353 nobody ever cares about((((

    → Reply
»
5 years ago, # |
  Vote: I like it +63 Vote: I do not like it

I like when in a task you need to make a few observations, understand / feel which of them is reasonable to develop (maybe several recursive observations), these observations mustn't immediately lead to the solution ofc. If the task is hard, then the solution itself can represent some serious technique, and ideally, the balance between the technique and the complexity of the observations should be kept.

That is, I like when there are a lot of possibilities where to go, what observations to use or even something to take somewhere on faith. I'm not very fan of problems where there is a one-step strange (magic) solution, but I think such problems will appear in future contests a lot, cause people like it.

Don't think that one can build good standard to rate problems it's more like opinion.

→ Reply
»
5 years ago, # |
← Rev. 3   Vote: I like it +12 Vote: I do not like it

In my opinion

(+) Clear statement, easy to read in English, easy to understand the statement

(+) The problem doesnt required complicated combined tricks-algorithms-methods to solve

(+) Strong pretests & good example, maybe adding simple explanation will be good

(+) The hard of two near problems is not too different (like: easyA vs too hardB vs normal C)

(+) Can gain some experience or learning new things from solving the problems

(-) Complicated things hidden in the statement and hard to understand

(-) Long & Very long statement make coder hard to find the point of the problem

(-) Weird modulo and restriction can make some coder confuse when they dont read the statement carefully

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Why tf would you not want complicated combined algorithms to solve a problem. If it is just one observation that is boring.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      I know some complicated can help us learn new experiences. But I mean about some another problems where complicated here are (some weird math formula with ugly real numbers), (too many hard-obserserve non-relative conditions for constructive, geometric problems), (some math problem with long combinatorics formula solution) that meaningless to either solve or learn something from it. But yes, to me — a low ranker: The harder the problem is, the meaningful and new knowledges gained after solving it by ourselves.

      → Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

Well, These are my views and I don't expect everyone agrees to them.

1) The solution of the problem should be based on a certain idea or observation and the implementation of the problem should not be super lengthy. See I have recently seen a problem Divisor Paths which I found very interesting because it was based on a certain idea and once you reach that idea you can easily implement it.

2) The statement should not be too lengthy or in other words, nobody wants to know why Nastya is throwing doors at the mountains to break it. I am not totally against the problem having a story but we can keep it separate like this contest

3) Like many times people tell that they had seen a similar question somewhere else and it really hurts when you were not able to solve that problem. So before adding a problem, setters should ensure that the problem or such a similar problem is not available anywhere else.

4) It's better when the test cases are explained properly by using diagrams and so.

→ Reply
»
5 years ago, # |
← Rev. 2   Vote: I like it +12 Vote: I do not like it

Of course, beauty is in the eye of the beholder. Also, it's more about a problem in a problemset, not invidually.

  • Most problems should be very original. No problem should be completely unoriginal except when it's specifically some training round for noobs.
  • Difficulties should fit.
  • Most problems shouldn't be too difficult to implement (compared to how difficult it is to figure out the idea) or just with too much casework.
  • The topics should be sufficiently different between problems.
  • "Decider" problems, i.e. last in division that you expect more than one person to solve, should be held to a higher standard.
  • Things like deciphering the statement or printing in a specific format should be minimised.
  • It's ok to have a "bad" problem if the rest of the problemset is "good".

Then, I don't like problems that involve too well-known or too unknown theory. Not in the sense that it's hard to figure out, but that if you have some specific background, it's very easy, and if you don't, it's very hard. FFT used to fit that many years ago before it became more common.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Why is it "ok to have a "bad" problem if the rest of the problemset is "good""?

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it +10 Vote: I do not like it

      Let's say that you have 6 problems and one of them is some boring "support operations on paths in a tree" shit. I don't mean a total repost or a well-known problem with a twist, but you should know the type. That's a bad problem because everyone who has practiced and read editorials should know what to do, so you get a good score if you type it quickly without bugs, no thinking required.

      For most people, this will be the case, but fast implementation is still a skill that is worth scoring, so it makes the scores less clustered and lets people who are overall "better" ahead of people who are only good in some aspects. At the same time, if someone's really good at the stuff that makes programming contests interesting — the thinking part, there are still 5 problems on which they'll be better and which they can enjoy.

      Then there are some people who actually aren't familiar with this well-known type of problems, but are able to solve it by themselves anyway given reasonable time, and it will give them something (way more than to people who have no clue).

      A fail is when this is, say, problem D and almost nobody solves E or F, and ABC are too easy. Then you're basing the final ranking on "can code anything fast and handles reasonably easy problems". It's also a fail if it's F because then, the hardest problem is typing.

      → Reply
»
5 years ago, # |
  Vote: I like it +59 Vote: I do not like it

The number of times the word "statement" is found in this comment section is scary.

If I enjoyed solving the problem, it is good. If I didn't — it is bad.

→ Reply
  • »
    »
    5 years ago, # ^ |
    ← Rev. 2   Vote: I like it +40 Vote: I do not like it

    What if you didn’t solve it?

    (btw for me, I think if I didn't solve it, it's quite a bit more likely that I think problem is good.)

    → Reply
»
5 years ago, # |
  Vote: I like it +63 Vote: I do not like it

I find that it is a lot more interesting to describe what makes a problem bad? and what doesn't make a problem bad? :P

There are some negative comments here about "complicated techniques". To me the use of advanced algorithms and data structures by itself is not a bad thing. I think that there is something wrong (and I hope that's what the others mean too) if knowing the complicated technique is the hardest part of the problem.

For example, here is a really bad problem (I think there was something like that in a real contest):

You are given an array of DAGs, there is a token on each DAG. Two players play a game, on every turn the player moves one of the tokens. The loser is the one who cannot move. You're given $$$Q$$$ queries of the form "who wins if we only consider the subarray $$$[l, r]$$$".

To me this is a really bad problem because you will solve it if and only if you understand prefix sums and the theory of Grundy numbers. It may be considered as an example problem in a tutorial or lecture, but IMO it has no place in a serious contest.

But here is something nice: ARC 061 F, coincidentally also about games. Probably some people commenting here wouldn't like it because it contains FFT which is some evil hard technique. But the problem isn't about FFT. You have to make some observations about the game. Then the problem becomes efficiently evaluating a certain combinatorial formula. Then you will notice that it makes sense to calculate together things that have $$$i + j = k$$$, for every $$$k$$$. And then you see the application of FFT. Although knowing that FFT exists is a part of the problem, it's not the problem.

PS. Grundy numbers and FFT may not be "advanced enough" for some readers, but the same idea holds with even harder concepts as well. I just wanted relatively accessible examples.

→ Reply
»
5 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Uniqueness of the problem's idea.

→ Reply
»
5 years ago, # |
  Vote: I like it -14 Vote: I do not like it

Good: math. Bad: data structures shits.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it +48 Vote: I do not like it

    Good: data structures. Bad: math shits.

    Funny enough (or not), data structures problems seem closer to what computer science and algorithms is about than math. For math problems solved using a computer, we have Project Euler.

    → Reply
    • »
      »
      »
      5 years ago, # ^ |
        Vote: I like it -23 Vote: I do not like it

      But don't people seem to say that AtCoder has the 'best' problems? And I think they can be described as : "mathy"

      → Reply
»
5 years ago, # |
  Vote: I like it +50 Vote: I do not like it

For me the most interesting problems are simple and neat yet hard. I love problems where I ask myself how and why this isn't already well-known.

Also, sometimes complicated problems have really neat solutions so I would consider those also really nice.

In summary, the best problems for me have simple statements, are something which one could naturally ask and their solutions are original and creative.

→ Reply
  • »
    »
    5 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    I think this is the answer I would agree most with. I especially feel something like this for the past ICPC WF problems. I think they are unique in some sense (the combination of the natural statement + idea is usually a great fit, plus that I feel it’s quite impressive that most of the problems can be solved in less than 100 LOC — even though they’re probably not solved by most of the contestants like that). Unfortunately, this applies more heavily to the problems that we wouldn’t reach during an actual WF. Similarly, I think JOI problems do a very good job of achieving that feeling.

    → Reply