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!
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:
Note: The examples above are both my own problems, which I'm using as examples of mistakes I made.
Thanks for the advice!
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).
When authors use 1e5, participants use avx2.
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.
How to test well an O(n^2) solution with avx2?
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.
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".
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
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.
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
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.
bitset in author solution = good problem
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)
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.