wrusb's blog

What makes a great competitive programming problem?
By wrusb, history, 2 months ago, In English

Lately I've been trying to get into problemsetting, and one question keeps coming to mind: what actually makes a problem "great"?

I searched around a bit, and the only blog I found discussing this topic in depth was antontrygubO_o's "On problemsetting": https://codeforces.me/blog/entry/70178

The only problem is that it was written about 7 years ago. Since then, competitive programming has changed quite a lot, so I was wondering what people think nowadays.

I'd love to hear opinions from both experienced problemsetters and contestants.

Some questions I have:

  • What makes a problem memorable or enjoyable to solve?
  • What are the biggest mistakes beginner setters usually make?
  • Are there any recent problems or contests that you think are great examples of good problemsetting?
  • When creating problems, what do you care about the most? Originality? Elegance? Educational value? A nice story? Something else?
  • How do you come up with new ideas without accidentally reinventing an existing problem?

Or just share your own thoughts about problemsetting in general. There probably isn't a single "correct" answer, so I'm interested in hearing different perspectives.

Hopefully this thread can become a nice collection of advice for people who want to write better problems.

Thanks!

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

»
2 months ago, hide # |
 
Vote: I like it +43 Vote: I do not like it

I think part of making a problem good is to make it not bad. I can tell you a couple of mistakes I made and that you should avoid:

  • Avoid problems whose main difficulty is recognizing a list of known techniques and implementing them. A good problem should reward problem solving and insight, not just familiarity with several algorithms. This is one example of such a problem; If you know what bridges are, you will solve the problem with some implementation skills. You need no smart observations at all.
  • Do not design the problem around your solution. The intended solution should arise naturally from the problem, not because you manipulated the constraints or made tests to eliminate other reasonable approaches. Here is an example (you can see how the number of testcases is large).

Note: The examples above are both my own problems, which I'm using as examples of mistakes I made.

→ Reply
  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    Thanks for the advice!

    → Reply
  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    Feels like good advice and stuff I heard elsewhere but aren't most construction problems almost a contradiction to your second point or am I just stupid. I agree with the part that weird constraints specifically to eliminate an approach is weird cuz i lowk find it annoying when authors do that (pls stop using n<=1e6 and just use 1e5 pls guys).

    → Reply
    • »
      »
      »
      2 months ago, hide # ^ |
       
      Vote: I like it 0 Vote: I do not like it

      When authors use 1e5, participants use avx2.

      → Reply
      • »
        »
        »
        »
        2 months ago, hide # ^ |
         
        Vote: I like it 0 Vote: I do not like it

        I think you need to test well. (Welcome home chtholly lmao) If you spam too much n in the millions you will TLE hell java and sometimes even C++. Someone may find an unintended approach with the same complexity (or your approach but a different flavor) and go through hell.

        → Reply
        • »
          »
          »
          »
          »
          2 months ago, hide # ^ |
           
          Vote: I like it 0 Vote: I do not like it

          I think you need to test well.

          How to test well an O(n^2) solution with avx2?

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

            Just code it up and run it. Or if you want to be super safe you can use theoretical arguments: CF judge CPU runs at 4GHz and we assume the ALU has 4 ports simultaneous 256-bit additions (8 ints each) at a time. This is extraordinarily generous assuming that there are no extra instructions for moving things between L1 and registers or any data dependencies that degrade our 32 ints/cycle throughput. (A CPU has way more than 1 billion clock cycles in a second. When's the last time your code with 1e9 operations has passed?) Then the theoretical max throughput is 1.28e11 per second. If you have n = 10^6 and 12 seconds limit, brute will not work.

            → Reply
            • »
              »
              »
              »
              »
              »
              »
              2 months ago, hide # ^ |
               
              Vote: I like it 0 Vote: I do not like it

              This thread started when I responded to "pls stop using n<=1e6 and just use 1e5 pls guys". I pointed out that if you will always use 1e5, you will be dealing with this, for example:

              https://codeforces.me/contest/1420/submission/149759731

              I do not think that you should "spam too much n in the millions".

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

                Ah ok fair

                Although TBH in my eyes there is way too much overlap between "my solution that runs in intended $$$O(n \log n)$$$ or even worse if intended complexity is $$$O(n \log^2 n)$$$" and "ooh super fast bitset/AVX brute force" that can really only be fixed well with huge input sizes and long time limits

                → Reply
    • »
      »
      »
      2 months ago, hide # ^ |
       
      Vote: I like it +8 Vote: I do not like it

      I didn't say you shouldn't start from a solution (which might be the case for some constructive problems). I said you shouldn't design the problem around your solution, and those are different things.

      Starting from a solution just means you have an interesting idea or observation and ask yourself, "What problem does this naturally solve?" Designing around your solution means you keep modifying the statement, constraints, or tests specifically to rule out every other reasonable approach until only your intended one survives. In the latter case, the problem is usually rewarding guessing what the setter had in mind.

      Because of this, I don't think every constructive problem is bad; I actually like them.

      → Reply
  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it 0 Vote: I do not like it

    The problem with the second example is not the number of testcases. The real problem is that you do not need any observations at all: since you are allowed to output numbers that exceed both a and b, you can just print 9223372036854775783 on every testcase (except if a or b equals zero, then there is no answer).

    https://codeforces.me/gym/106098/submission/385135475

    → Reply
»
2 months ago, hide # |
 
Vote: I like it +1 Vote: I do not like it

I only have experience from making contests for my college's club. But I can tell you that if you are having fun creating a problem, it will probably be good for the contestants too. Just enjoy the process.

Also, a piece of advice: don't make the statement too hard to read or understand. If someone opens a problem and sees two thousand lines of a confusing story, they might just skip it.

→ Reply
»
2 months ago, hide # |
 
Vote: I like it +20 Vote: I do not like it

bitset in author solution = good problem

→ Reply
»
2 months ago, hide # |
 
Vote: I like it 0 Vote: I do not like it

The only problem is that it was written about 7 years ago. Since then, competitive programming has changed quite a lot

But has it, really? I don't think I will ever be able to distinguish a 2019 CF problem from a 2026 CF problem apart from, idk, modern references. There are newer techniques sure, but it seems like none of them pass the simplicity/generality threshold to ever become commonplace. Other than that, and the sample size being larger than 7 years ago, I'd say it's more or less the same formula (and will remain this way for a while)

→ Reply
  • »
    »
    2 months ago, hide # ^ |
     
    Vote: I like it +1 Vote: I do not like it

    I think we're looking at "change" from different perspectives. If we're talking about the algorithms contestants use, then I mostly agree. But if we're talking about what makes a good Codeforces problem, how ideas are presented, what gets accepted by coordinators, and what participants expect, I do think there has been noticeable evolution over the past several years.

    → Reply