On problemsetting 2

Revision en1, by antontrygubO_o, 2020-01-12 00:46:38

Previous part

Hi there again! Previous part with opinions of some amazing problemsetters turned out to be interesting for you, so I decided to gather some more opinions :D. I really hope that this post will help someone in their problemsetting future!

#### When and how did you start problemsetting?

300iq: April, 2017

maroonrk: In 2015 Summer, I hold the first contest with friends at high school club. It was a local Japanese contest.

Radewoosh: In high school, so probably for 5 years. I was creating problems for other people from my school as my teacher told me that it's a completely different point of view.

voidmax: It was 3 years ago. I was on plane and I didn't have a clue what to do in my free time. Then I realized that I can try myself in problemsetting. Later I created first and one of my favorite problem (963B - Уничтожение дерева). I was full of inspiration and so I decided to make round... That's how it started.

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

300iq: I am just thinking a lot, trying to come up with some beautiful construction, or thinking about something that looks "completely unsolvable" and trying to solve that.

maroonrk: There are two ways:

1. To use existing ideas.

Firstly I have some algorithm or beautiful structure of something in mind, then create a problem related to it. This is an "idea->statement" problem-setting.

2. To somehow "generalize" daily events.

In daily life I often try to think "is it possible to generalize this happening?", and sometimes it succeeds. This is a "statement->idea" problem-setting.

Radewoosh: My favorite way is to do it backwards, starting with an idea what the solution should be about. (1097H - Матеуш и бесконечная последовательность)

Also, I like mixing known things, the result can be surprising. (102341L - Lati@s)

Of course, it's great when you come with something totally fresh by an accident, but this doesn't happen very often. (698F - Взаимно простые перестановки)

voidmax: Usually I take some well-known problem or structure and try to look at it in a new way.

300iq: I think subtasks ARE suitable, but it is sad when a subtask is adding something very stupid and not interesting. I participate in OI contests, so for me subtasks are OK because I am familiar with them.

maroonrk: Some subtasks are nice, but they are so rare. Besides, I strongly believe that "solving easier subtask first and then harder" should not be worth more than "just solving the hard".

So I don't think Subtasks are suitable for CF/TC since they have drain points system. And even if the penalty is calculated only by last submission time, we should be prudent in setting Subtasks.

Radewoosh: It's hard to say, when I'm competing, I'm always trying to go for the whole problem. They can be, but only if there is a good point for making a subtask (so both solving the subtask and moving from the subtask to the full problem are hard).

voidmax: Obviously, subtasks are great. I see only pluses. Sometimes problems are still interesting, even with lower limitations. Also subtasks are motivating to solve problem. A lot of people give up after trying solving hard task, but subtask can give them hope that problem is solvable.

#### What is your opinion about Thinkforces? Should round have some amount of more standard, less ad-hoc problems to be balanced?

300iq: I think Thinkforces is very good, and these problems are the best problems.

maroonrk: I think easy and medium problems can be (but not necessarily) standard problems, since it would be a nice opportunity for beginners to learn common techniques. However, hard problems should be ad-hoc to some extent. I don't like the round where the winner is determined by tasks like "Do you know this particular algorithm?", or "Can you implement this in 1 hour?". I'm not saying they should be pure ad-hoc. They can require some advanced algorithms and moderate amount of implementations, but they must have ad-hoc part.

Radewoosh: I like ad-hoc problems, most of times they are invented in the third mentioned way, so I'm always impressed by them. It depends on the problem, but if all the problems require just roaming to get the solution it isn't so nice for everybody. I like thinking about the participants during the preparation and in my opinion is good to let them have some breaks and force them to just implement something.

voidmax: I think every round should be Thinkforces (except Educational). We are writing rounds for fun, right? And where is fun when you immediately starting to write solution, without a moment of thinking about the task? I am absolutely sure that even a easy problem can be interesting. Also standard problems sometimes are dishonest. Take for example FFT problems. If you don't know FFT, you have no chance to solve that problem.

#### Should every contest have data structure problem?

Nope.

No. Data structure is just a tool to solve problems. Of course it is good that the round have a wide variety of tasks, but, If all of the round tasks can be solved without data structures, you can just leave it.

Radewoosh: Of course not, but I like giving tags to my problems and it's nice if there is a variety of them and they don't repeat too much in one contest.

voidmax: No, I think not. Most of data structure problem are similar and quite boring.

#### What is better: many tasks, to have to choose what to think about, or less tasks, to have more time to think on each problem?

300iq: I love solving ICPC contests solo, so for me first variant is better.

maroonrk: I don't have an opinion on this matter. However, I believe that contests should be designed so that one participant can solve all tasks with non-zero probability.

Radewoosh: Depends on the contest's style, you should always try to fit in. Less problems are ok if they still touch different topics.

#### Do you sometimes have a feeling that you have run out of problems? If so, how do you deal with this?

300iq: Yeah, I have this feeling every day. But somehow I come up with more and more new ideas, it just depends on the time I spend on thinking about new problems.

maroonrk: I often feel like that. At such time I stop creating problems, and concentrate on solving problems.

Radewoosh: Sometimes yes, but the first and second mentioned way usually work if you spend enough time.

voidmax: It is normal situation. Usually I create many problems in some short period and most of the time don't have any good ideas. It's a matter of time. I just wait for inspiration.

300iq: Very often. Often I come up with some idea that is trivially solvable for small $n$, but for large $n$'s looks almost impossible to solve.

maroonrk: I don't remember, but around half of them.

Radewoosh: Very rarely, I try to change them to make them OK. For example when a similar problem had appeared somewhere before.

voidmax: Almost never.

#### Opinions about problems may be subjective, but still. What is your opinion about criticizing the problems after the contest? Do people criticize problems in Codeforces comments too little?

300iq: I think that is OK to criticize the problems, and it is very useful to listen to good critics. But if one writes something without any arguments, like "Mathforces. Please stop creating new problems.", then it is useless.

maroonrk: We should be open to constructive criticism, but they are too few.

Radewoosh: No problemsetter is perfect. Even if they aren't nice I try to read all the opinions about my problems to make them better in the future, so every opinion (even if it's stupid) should count.

voidmax: Criticizing is normal. It helps authors to see the strong and the week sides of their creations. (I've almost never seen a criticizing in the comments) Also, yes, opinion is subjective, but sometimes there are objective reasons why a problem is bad.

#### Who are your favorite problemsetters?

MiracleFaFa (GP of Zhejiang is very cool, and his problems from other places too), rng_58 (I really like CDE from new AtCoder WTF, but I don't like a lot of other problems from AtCoder), izban.

rng_58, AtCoder WTF2019 was amazing!

Radewoosh: Huh, I don't think if I have any specific problemsetter, but I think that I like most of the Chinese/Korean problemsets, as they seem to really touch many different topics and don't try to avoid any of them.

#### Name best three problems authored by you (with links if possible). What are the stories behind setting them?

I am a big fan of Hall's Theorem, so somehow I created this constructive problem. My solution was very strange without any proof (just write and see), but after some time I found proof and realized that this problem may be reformulated as a good math problem! (Proof that for each k it is possible).

I like this problem because it is one of the few constructive problems that I created, and I like constructive problems.

I thought that this problem is "unsolvable", so I decided to think about it.

I found that we can use slope sorting + D&C to get the answer for each k on the array with some additional constraints, and after that, I found that it is possible to use Aliens Trick (I am a big fan of it!!!) to get the answer for segments to optimize.

I like this problem, because new ideas behind it may be used for a lot of other problems!

Two trees. Sorry, I don't remember the story behind this task.

Negative Cycle. The original version was "There are N=100000 vertices on a line and M=100000 additional edges. Check if there exists a negative cycle.". However, as you might guess, it was almost impossible to make strong tests. So I modified the problem and it was indeed a nice modification.

Meetings. When I came up with the statement, I couldn't solve this. However, around a month later, the solution suddenly came to mind when I was commuting and I got stunned.

102341D - Dedenne

Triinformathlon

Cook

It's hard to pick only three. The stories are different, but I think that in all of them I started with the solution.

1131G - Самая опасная акула This task really shines when you are finding solution with complexity $O(m)$. I tried my best to make pass $O(m)$, but I failed.

1181E2 - История одной страны (сложная) This task represent my view of 2D bracket sequence (It's normal, right?)

1239E - Черепашка

First two problems were on school olympiads for 6-9 grade. To my surprise both problems were solved.

#### What are your favorite problems of 2019?

GP of Xi'An All Pair Max Flow

AtCoder WTF (CDE)

GP of Warsaw Bulbasaur (about some max flow)

Bohemian Rhaksody (KAIST contest, Prefinals Workshop)

Поиск идеи (ROI 2019, LOL.)

Triangular Lamps Hard

e

102331H - Honorable Mention

Radewoosh: If not authored by me:

1270E - Разделите точки

1254B2 - Отправьте коробки Алисе (усложнённая версия)

1188D - Сделайте равными

1229F - Матеуш и эскейп-рум

#### History

Revisions

Rev. Lang. By When Δ Comment
en1 antontrygubO_o 2020-01-12 00:46:38 13154 Initial revision (published)