Hi there! Time to write something useful (hopefully).

This year I became involved in creating competitive programming problems. As I had pretty no experience, my first problems were just all easy or trash, and I couldn't even understand how do people come up with new ideas. I searched a lot, and it turned out there isn't actually a lot of information available on the web. Here is the list of blogs, connected to this topic that I managed to find:

Blog by Sammarize on the entire problemsetting process.

Blog and one more blog by Nickolas.

Blog by one of the most productive problemsetters in the world's history Lewin on coming up with the problem ideas.

Also I really want to share a recent post by voidmax (Vladimir Romanov).

If turns out that there aren't many materials on the problemsetting topic, or at least they are not that easy to find (Please share in comments if you know some!), especially written in English. However, personally I find this topic really important for the Competitive Programming community. There is an increasing number of platforms and olympiads which need more and more problems, and when the demand exceeds the supply, the quality of the problems tends to decline.

When I was preparing my contests, I felt that the materials on problemsetting and coming up with good problems would really make the life easier. I think that I am not the only one, so I asked some of the best setters to share their view on problemsetting :D and am glad to share their opinions now!

When and how did you start problemsetting?

Endagorion: At around 16 (>10 years ago) for summer camp and local high school competitions

Um_nik: My first round was on 20.02.2014, it was my last year in school. Idk, we just discussed some ideas with my friend Umqra and then we decided that we have enough decent problems for a div2.

Errichto: 5 years ago

rng_58: SRM452, it seems 10 years ago

How do you usually come up with new problems? What ways help you to create your best problems?

Endagorion: — take a topic/algorithm and think of a way it could work in an unexpected setting (this includes combining seemingly unrelated topics)

• just think of an original problem and see if it's at all solvable, make it more general/constrained if needed. this is more tolling, but leads to more interesting problems usually

• read up random articles and see if any problems/observations can be extracted from it

• sometimes observing stuff in real life gives an idea for a problem

Um_nik: I would say that there are three general ways to create problems:

1. Take something from real life and give it a formal statement

2. Work from solution or key idea backwards

3. Use some existing problem or something from books/classes and rework it

I'm not really good at (1), I would say that my best problems are of type (3).

Errichto: Thinking about some process like boarding a plane, or writing down a sequence/string/etc. and thinking what can be computed here.

rng_58: When I come up with an interesting statement in daily life, I write the statement and save it. Then, when I need to set problems, I choose some of saved problems and solve them (in case the problems look unsolvable, sometimes I modify statements and make them solvable).

What is your sense of beauty of problems? What makes the problem beautiful?

Endagorion: — as misof puts it, "the less it looks like anything I've seen before, the better"

• short statement is good

• short (but not obvious) solution is good

Um_nik: I like when the solution is hidden under multiple layers of reductions, and each reduction needs some A-ha! moment, so the solution is a series of transformations to gradually easier and more tractable problems until you get some standard problem you know. I obviously prefer when the code is short and clean, but it is actually not necessary, there are a number of very nice problems which require some tedious data structures, but it is still an important point. Didn't see any nice problems requiring link-cut tree or weighted matching in general graph yet.

Errichto: Short and natural statement, a nice solution that doesn't require hard knowledge or going through tedious formulas.

One more opinion on what makes a good problem:

Contest tasks say a lot about the quality of a programming competition. They should be original, engaging and of different levels of difficulty. Finding a solution should cause the contestant to feel great satisfaction, whereas being unable to solve a given task should encourage an individual to broaden their knowledge and develop new skills.

From Looking for a Challenge?

rng_58: I'm the admin of AtCoder, so if you check AGC problems, I guess you can feel my sense of beauty.

There are various factors in problem solving, including the following:

1. Original observation required to solve the problem.

2. Application of typical techniques.

3. Implementation.

4. Knowledge and preparation of known advanced algorithms (i.e. library).

These four are sorted in the decreasing order of my preference. If all parts are heavy, that's simply a hard problem. If all parts are light, that's simply an easy problem. To measure the beauty of problems, I check the ratio between part 1 and part 3/4.

I regard competitive programming as "discrete math puzzle solving contest" rather than "programming".

Also, I don't want it to be like "studying". Solving problems is much more interesting than reading/learning books/papers.

Another factor that makes a problem beautiful is the naturality of the problem. Simple, natural statements give more motivation than lengthy, artificial statements.

Why do you create problems, what does it mean for you to be problemsetter?

Endagorion: It's both an art and a craft, but most importantly it's extremely fun. Helps with improving as a contestant too

Um_nik: I want to share the beauty of these A-ha! moments needed to find the solution with the people. That is actually very important topic for me for the last several month. I would love to share my problems with community, but to do this you have to make tests, set limitations, write formal statement and so on. And these things actually have nothing to do with solving the problem, but they may ruin the problem. You can miss some misinterpretation of statement and it will ruin the problem for your audience, it can happen that there are some randomized solutions which you cannot prove but also don't understand how to create tests against and so on. And people will not have the joy of unfolding the solution, but will write something stupid instead, because of course they will.

Errichto: I like coming up with cool problems and then seeing that others like it.

rng_58: Isn't it interesting if top people around the world solve your own problems?

There are two different types of creating a problem: coming up with an interesting statement and solving it from scratch, or working on the problem backward: by researching some construction or creating a problem directly from some idea. Briefly, these are: problem $$$\to$$$ solution and solution $$$\to$$$ problem. What are your attitudes towards these two types, which you think produces better problems?

Endagorion: As I mentioned, the first approach is harder, but generally leads to more interesting problems. Also, it's a rare case of the first approach yields a good problem without a lot of adjusting

Um_nik: As I said earlier, I think that there is third type, briefly problem->different problem.

I think that best problems are of type (1), but 1. I don't know how other problemsetters do this 2. There are also many problems of this type that are not interesting at all.

Problems of type (2) are sometimes boring, but they are easier to start with and they can evolve into something interesting if you are willing to drop initial solution and let the problem live without it. I think that inexperienced problemsetters often use this way and miss easier solution when the problem is finalized, just because they "wanted to create a problem with this particular solution".

I think that (3) type is more appealing to me, because for me it is natural to think "and what if the problem was a bit different" after a contest.

Errichto: Problem->solution is more natural and produces good statements, but it's good to be flexible. If I see a slight modification of the problem can make my solution work, I do it.

rng_58: "problem->solution" is much better. This way we can make thinking-oriented and natural problems. "solution->problem" tends to be technical and artificial problems.

What are some bad issues of problemsetting on different platforms today, in particular, in Codeforces? What can be done to improve the current situation?

Endagorion: It's not too bad in general, but:

• tests/pretests quality is not always great. Suggestion: require a description of the testset from the setter with intention listed for each test group/generator

• statements are not always well written, and especially translated. Maybe have a dedicated person with both good English and problem setting experience to review the texts

• sometimes the problems are not very original. This can not be completely solved, but enlisting a lot of testers with different backgrounds, and better authors (increasing compensation may help with these)

Um_nik:

1. Many people (often including myself) think that you HAVE to have at least one graph problem or at least one data structure problem in a contest and these "mandatory" problems are always very bad and uninspiring.

1.1. On the other side, there are many participants who don't like "mathforces" though math is a vast area with lots of different topics (for example, adamant's contest in last Ptz camp is kinda math-y towards the end, but it is not like the problems are all the same).

1. I don't like that there are no div1only rounds, I think that high-rated people who can create really good div1 rounds don't understand the difference between div2ABC and can't create decent easy problems.

2. I think that problemsetters on CF are required to spend a lot more time on statements than it is really needed because of low math-culture of participants.

3. I guess, the term is CPM -- contest per month. Mike requires steady flow of content and coordinators have to greenlight a contest even if it is not good enough.

--- solutions? ---

1. It is good to make diverse in terms of topics contest, but giving 2 kinda similar good problems is generally better than 2 different bad ones.

2. Make div1only rounds?

3. I don't know. I tried, really. cries

4. Use AtCoder model -- contest will be held when it is good.

Errichto: Codechef is bad because it has a fixed schedule. They give a contest even if they don't have high-quality problems. Atcoder is the opposite.

Codeforces rejects too few problems, I think. If something is boring, it shouldn't be accepted as div1 or div2 contest.

rng_58: In most platforms, we have trouble with finding sufficiently many high-quality problems. If you know how to improve the situation please tell me...

Name your favorite problemsetters (except you). What makes their problems that good?

Um_nik: Errichto? I don't know, last his problems were a miss, at least for me. But before that I would say that he was my favorite.

Endagorion, old/new Warsaw U

It is hard to say, it is more about feeling that problem was beautiful than saying "this problem fulfill the checklist"

Errichto: I like other Polish setters like marcin_smu and Swistakk. They produce few but very hard and interesting problems.

"what makes their problems good" is a stupid question. The fact that their problems are good makes their problems good xd

It's important to have huge CP experience (including squeezing some heuristics) and also some experience with preparing problems already. Being good in math helps because then you understand how to prove lemmas correctly.

rng_58: Among AtCoder frequent writers — sugim48, maroonrk, DEGwer.

TC — cgy4ever, dolphinigle, subscriber,

CF — Errichto, Endagorion,

SnarkNews — tourist, Petr,

GCJ — David Arthur, Bartholomew Furrow.

Name best three problems authored by you. What are the stories behind setting them?

Endagorion: Martian Colony: the first problem I set and was really happy with

Infinite binary embedding (Petrozavodsk 2015, Mikhail Tikhomirov contest 1): a good example how thinking and tinkering with a problem a lot can yield something really good

Addition without carry (ROI 2018): this came to be from solving a somewhat original problem, coming up with a really beautiful solution which was too hard for most contests, and leaving the most interesting subtask

Um_nik: I hope that my best problems are in the future (*cough* lame cough)... But this is doubtful, I think that number (1) from this list is my ceiling (I'm not that good at problemsetting, yes).

1. Square Function (Ptz Summer 2016, Ural FU Dandelion Contest, Problem A) — I read the problem from "Concrete Mathematics" (it was to prove some statement about the answer to this problem), then came up with O(n^3) algorithm and then gradually speed it up to where it is now.

2. Oppa Funcan Style Remastered -- a variation on the theme of http://acm.timus.ru/problem.aspx?space=1&num=2107 with completely different solution

3. Corporate Mail (Ural FU Junior Championship 2016, Problem D) -- I guess I just love problems about implicit graphs and I'm glad I have come up with one (not one actually, but whatever)

Errichto: From a recent year or so:

• Disjoint triangles: (hard problem, simple statement, not so long or complicated)

• Contest balloons: (I came up with that while watching ICPC WF stream of 2017 where commentators joked about some possible future problem about balloons. I'm proud of the funny statement, while solution is very standard and boring)

• Moving walkways: (came up with that while running through airport and resting a bit on moving walkways)

• DoubleLive: (I started with a solution and from that created a hard but natural-ish problem)

As a bonus, here's a problem that is bad, Different names: (the statement is so long and unnecessary, I should have just said that you should print a string that satisfies something for every substring of length K)

rng_58: AtCoder WTF С2 and E (Sorry, two problems. If you want to try more — in TC/AtCoder tournament rounds I try to use my best problems, so try them.)

When I took a train, I wondered "what ratio of seats will be filled before people start sitting next to each other?" Experimentally, I got the result $$$\frac{1}{2} - \frac{1}{2e^2}$$$, but it was very hard to describe. Finally I came up with an elementary description and made it a problem.

I don't have a lot of problemsetting experience yet, but I still would like to write some own thoughts on problemsetting at the end of this post.

How do I create problems?

When I want to create a problem but am stuck on a certain idea, or am just running out of ideas, it really helps me to just open some random old contest and to read a few problem statements. Even without trying to solve them, I get some new ideas which may transform into problems; moreover, seeing an interesting/beautiful/cute statement brings me into the inspired mode needed for the coming up with problems.

One side note is that a lot of my problems are created in the order solution $$$\to$$$ problem, in particular, Vus the Cossack and Strings (CF 571 Div2 C), Vus the Cossack and a Graph (CF 571 Div2 F), Candies! (CF 572 Div2 C), Count Pairs (CF 572 Div1 B), Shortest Cycle (CF 580 Div1 B). Moreover, I think that this way of creating problems is somewhat underrated, and is one of my favorite ways. It has several advantages: first, it allows not so good competitors to come up with difficult problems from the end (and therefore allows them to set Div1 contests). Secondly, in my opinion, it allows producing idea-based problems on a more regular basis than problem $$$\to$$$ solution allows. Although this approach is easy to use in a wrong way (as coming up with a problem based on a formula you have somehow found in Wikipedia (Count Pairs (CF 572 Div1 B)), when used right, it produces really cool problems.

On Div2 A issue

I think that most setters don't really care about Div2 A and Div2 B problems. It's a usual practice to not care about Div2A until the very last days and then just to create something. It's really weird to hear "I can come up with 3 Div2 A in an hour" from some people: in the end, for a large part of participants Div2 A and B are the only problems they will solve at this contest, and you created just a weird something for them. One example of an amazing Div2 A (in my opinion) is: Case of the Zeros and Ones: it is easy, but still it contains an idea!

An advice for those who want to set a contest

I think that many authors, especially new ones, may be so excited about setting their first contests, that the fact of setting contest becomes more important than everything else. For example, one may come up with a cool Div2 E and want to create a contest just for it. They may include problems which they themselves just find okay but not really like, just to set a contest faster. This is especially true when the author doesn't have much free time because of studying/job.

So, advice: If you want to set a contest that people would really like, keep modifying your problemset until you like every problem in it, no matter how long will it take.

I really hope that this post will help someone in their problemsetting future!

UPD1: I would recommend reading the second part of "Creating problems" by voidmax

UPD2: Next part