antontrygubO_o's blog

By antontrygubO_o, 2 months ago, In English,

Disclaimer: as always, everything in this blog is just my opinion.

Some problemsetters don't take easy problems seriously. One very popular opinion is that the D2A-B problems are just stupid implementation exercises intended for beginners to learn how to code.

It's true that D2A-B problems are mostly like this on most platforms. This is one of the reasons why a lot of people don't like combined rounds: they think that solving D2A-B problems can't be interesting and just takes time which could be spent on solving fascinating problems of higher level. From point of view of most participants, easy problems just can't be good, because if problem requires some thinking than it's not easy enough for D2A-B level. Easy problems can't be interesting, they say!

This situation really upsets me. This kind of attitude from the community leads a lot of problemsetters to care about easy problems even less. At the same time, I am sure that easy problems can and should have nice ideas in them. Yes, even D2A-B level problems can need some observation/insight!

I will start with some examples of D2B level problems which I consider really nice. I recommend trying them! Some comments are under spoilers.

1325B - CopyCopyCopyCopyCopy

Comment

1300B - Assigning to Classes

Comment

1270B - Interesting Subarray

Comment

A few more nice D2Bs where you have to think a bit:

1305B - Kuroni and Simple Strings

1189B - Number Circle

1091B - New Year and the Treasure Geolocation

You may be surprised, but even D2As can have nice ideas in them! Here are some examples:

1326A - Bad Ugly Numbers

Comment

1305A - Kuroni and the Gifts

Comment

1269A - Equation

Comment

556A - Case of the Zeros and Ones

Comment

1174A - Ehab Fails to Be Thanos

Comment

Here are a few more nice D2A problems:

1325A - EhAb AnD gCd

1237A - Balanced Rating Changes

1206A - Choose Two Numbers

1189A - Keanu Reeves

1119A - Ilya and a Colorful Walk

I hope you found these problems nice. All of them require at least some insight/observation, and they are still easy enough for beginners and for D2A level. All of them have quite a short and clear statement, and you don't have to waste a few minutes understanding the problem's statement.

However, first problems in rounds aren't usually like this. Very often the first problems are just: Do what's written in the statement, or Bruteforce all possibilities to find the answer. Majority of D2A-Bs don't have any idea at all. Here are some "best" examples:

1281A - Suffix Three

1228A - Distinct Digits

1200A - Hotelier

1186A - Vus the Cossack and a Contest

1097A - Gennady and a Card Game

At this point a lot of readers may disagree with me. Some people may say:

Yes, these problems aren't interesting for you, but if there isn't any idea in these problems from your perspective, it doesn't mean it's the case for beginners. For them even these problems are tough and interesting enough. Implementation problems also can exist, and they are useful to learn how to code for beginners. After all, this is not a thinking contest, this is a programming contest!

And they would be right to some extent. However,

  • Codeforces is not a platform where you learn how to code. There are a lot of much better places to learn programming language syntax, and we are here to solve problems, not to learn how to code.

  • The first problems aren't only for beginners. All participants of the round solve these problems, and it's sad when from the very beginning of the round you are bored by the first problems, which turned out to be statement comprehension + implementation exercise. I am often upset when the first problems are such exercises, and get much more excited about the round as a whole and further problems if D2A-B are nice.

  • I think that the best way to make someone love CP is to show nice, cute, beautiful problems. Too standard/boring first problems may destroy wish to proceed in CP in beginners.

After all, the first problems are the ones that the largest number of participants will try to solve, and half of the participants won't even get past D2B. How can we not care about D2A and D2B then?

Yes, setting nice D2A and D2B which require some ideas and are still easy enough is hard. Really hard. But setting good problems is hard in general. If you decided to spend some time to make a good round you should spend some time and try to make all problems good. I believe that D2A and D2B level problems shouldn't be created like this:

I have to note that the situation now is much better than it was a few years ago, and that the quality of all problems, even of D2A-B has improved a lot since then. But I still hope that after reading this blog some of you will spend more time thinking on D2A-D2B problems before submitting contest proposal on CF :P From my side as a coordinator, I try to not let boring problems get into CF rounds, and I hope to become better at this in the future.

What are your thoughts? Should authors spend more time coming up with nice easy problems, or is it just a waste of time?

Read more »

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

By antontrygubO_o, 3 months ago, In English,

Hello Codeforces!

ozon

We are glad to invite you to the upcoming “Ozon Tech Challenge 2020”, which will start at Mar/03/2020 17:35 (Moscow time). The round will be open and rated for everybody!

This round is initiated and supported by Ozon.

Ozon — one of the leading players in e-commerce (provides its customers with over 2.5 million product names in 24 categories), a tech company that actively developing its IT department. They already have the largest Golang team in Russia, a proprietary WMS fulfillment management system completely written by the Ozon team, 250 million lines of logs per day, collected on the site and in the Ozon mobile application. Ozon experts perform at the leading profile conferences GoperCon, Heisenbug, GoWayFest, GolangConf, and also at the company site meetups are held for the IT community.

The company shows great interest in the support of the developer community — for schoolchildren there is Ozon Academy, for the older audience there is an internship program Ozon Tech Camp and training program Ozon Masters.

Participants will be asked to solve 8 problems in 2 hours 15 minutes. Scoring will be announced a bit later.

The problems were created by Akikaze, Ari, Kuroni, zscoder, xuanquang1999, and antontrygubO_o

We would like to thank:

Thanks to Ozon for the gifts to the participants:

  • top 10 participants will receive stylish branded backpacks and branded T-shirts;
  • 11-20th participants will receive compact portable chargers for 10000 mAh and branded T-shirts;
  • 21-60th participants will get branded t-shirts;
  • another 30 T-shirts will be played among the rest of the participants, who solved at least two problems, randomly.

We hope everyone will find an interesting problem for themselves. Wish everyone a successful round and high ratings! Good luck!

UPD1:

Score distribution:

500 — 1000 — 1250 — 1750 — 2000 — 2500 — 3250 — 4000

UPD2: Editorial

UPD3: Congratulation to the winners!

  1. tourist
  2. maroonrk
  3. peehs_moorhsum
  4. ksun48
  5. Endagorion
  6. Benq
  7. gisp_zjz
  8. neal
  9. Um_nik
  10. yasugongshang

Information about prizes will appear soon.

Read more »

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

By antontrygubO_o, history, 5 months ago, In English,

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 - Destruction of a Tree). 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 - Mateusz and an Infinite Sequence)

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

Of course, it's great when you come with something totally fresh by an accident, but this doesn't happen very often. (698F - Coprime Permutation)

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

What is your opinion about subtasks? Is this format suitable in CF/TC/AtCoder contests??

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?

300iq:

Nope.

maroonrk:

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.

voidmax: Less tasks is better.

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.

How often do you discard your problem ideas?

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?

300iq:

MiFaFaOvO (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.

maroonrk:

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.

voidmax: ko_osaga, majk, antontrygubO_o

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

300iq:

102268H - Hall's Theorem:

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.

102331H - Honorable Mention:

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!

maroonrk:

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.

Radewoosh: In random order:

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.

voidmax:

1131G - Most Dangerous Shark 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 - A Story of One Country (Hard) This task represent my view of 2D bracket sequence (It's normal, right?)

1239E - Turtle

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?

300iq:

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.)

maroonrk:

Triangular Lamps Hard

e

102331H - Honorable Mention

Radewoosh: If not authored by me:

Parada by Errichto

102331H - Honorable Mention: by 300iq

voidmax:

1270E - Divide Points

1254B2 - Send Boxes to Alice (Hard Version)

1188D - Make Equal

1229F - Mateusz and Escape Room

Read more »

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

By antontrygubO_o, history, 5 months ago, In English,

So 2 weeks ago I changed my rank to specialist and color to cyan. Everything was alright, but today I woke up and my hair became cyan too! How does this even work

MikeMirzayanov please take a look into this issue...

Spoiler

Read more »

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

By antontrygubO_o, 5 months ago, In English,

Hi there! The recent Good Bye 2019 was very important event for us, and thanks for all the positive feedback we got, especially from Radewoosh! As a follow-up, we would like to share some background on its preparation.

Problems:

A: This one was the hardest to come up with. We wanted it to be super easy but still to include some idea, and this is like the $10$th version of the problem.

B: Initially there was another problem at this position. However, it turned out to be too hard for B (one orange couldn’t do it during the testing), and people didn’t like it in general, so we came up with another task.

C: Funny, but we didn’t know that it’s always possible to make array good with adding at most $$$1$$$ element before the contest.

D: This problem was created just 3 days before the contest to make it more balanced :O. We are glad that the contest did turn out to be well-balanced.

E: Initially we wanted this problem to be at position C, but the coordinator told us it was too hard for it and we moved it to D. However, testing showed that we have to move it even further!

F: This problem caused a lot of troubles because we wanted to cut $$$n^2$$$ brute force solution which was working very fast. Luckily, nobody managed to pass it in $$$n^2$$$ during the contest, but in upsolving savinov managed to!

G: Before there was another problem at this position, but this problem by a recent round by hugopm turned out to be too similar to it :(, so we had to replace this position.

Initially, I wanted to send the current problem G to IMO (asking to prove that there exists a nonempty set with zero-sum), and I think it would make a great P2, but we wanted to make this contest the best we could make, so I decided to use it here. We are glad you also found it beautiful!

I think it may be interesting how this problem was created. I wanted to come up with some problem with permutations, and the first (and obvious) version was:

Prove that for any permutation $$$p$$$ of $$$n$$$ elements there exists some set $$$S$$$ such that

$$$\sum_{x \in S} x = \sum_{x \in S} p_x$$$

Of course, this is a very bad problem, as even $$$S = {1, 2, \dots, n}$$$ would suffice. So I decided that permutation wasn't necessary, and the next version of the problem was:

Prove that for any array $$$a$$$ of $$$n$$$ elements such that $$$1\le a_i \le n$$$ there exists some set $$$S$$$ such that

$$$\sum_{x \in S} x = \sum_{x \in S} a_x$$$

But this one was too obvious and too well known...

I just decided to regroup terms, so that the new version became:

Prove that for any array $$$a$$$ of $$$n$$$ elements such that $$$1\le a_i \le n$$$ there exists some set $$$S$$$ such that

$$$\sum_{x \in S} (x - a_x) = 0$$$

It was left to just set $$$b_i = i - a_i$$$ and to ask to find subset with zero sum! Funny, that this simple process led to such problem O_O

Creating tests was really hard for this problem, you can read about one testcase here, but we are glad that not so many heuristics solutions managed to pass!

H: We needed some programming task (or otherwise some people would kill us). Initially we came up with the $$$q = 0$$$ version of that problem and considered it as Div2B — Div1A level, but then we thought about the queries and GandalfTheGrey managed to find $$$n\log{n}$$$ solution!

We had problems with TL with this problem as well, wanting to cur $$$n\sqrt{n\log{n}}$$$ solutions, but didn’t manage too, unfortunately.

Fun fact: initially we considered G and H to be of about the same difficulty. The contest proved that we were very wrong :D

I: I loved this task a lot (this is my favorite problem in general) and wanted to create something with a similar idea (Idea: count some function for every cell such that some operation changes values of functions nicely).

Firstly I wanted to send it to IOI, but after I decided that it's really hard to come up with meaningful subtasks for this problem, so I decided to use it here.

I would like to point out, that problems E, G, I were created in direction solution -> problem. For some reason people keep saying that this way gives bad problems too often, and I want to persuade others that this way of creating problems is great :D

During the contest

We were really surprised when the first 2 accepted solutions of problem G came from people with ratings 1900 and 1700 :o

At the end of the contest, we thought that the decision to make it $$$3$$$ hours was wrong, as the number of attempts to pass some heuristics in G and some $$$nsqrt{nlog(n)}$$$ in H was increasing in last $$$30$$$ minutes :(.

Post-contest impressions

We expected people to complain about bad TL in F, H, about bad tests in G, and about the contest being too Mathforces in general (yes, that’s why I wrote Mathforces Thinkforces in the announcement. We were really surprised by the amount of positive feedback though, thank you a lot!

There was a very interesting post-contest discussion involving Radewoosh and Swistakk. We intended to make the problems heavily thinking oriented and less coding oriented, and we think that we succeeded. However, we would like people to share their opinions: do you think a lot of ad-hoc problems in one contest are bad for Codeforces?

Thank you for the amazing year though, we hope to return with other good contests!

Happy New Year!

(You will see my cyan hair in the next few days)

Read more »

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

By antontrygubO_o, 5 months ago, In English,

Hello again, Codeforces!

We are glad to invite you to Mathforces Thinkforces Good Bye 2019, which will take place on Dec/29/2019 17:05 (Moscow time).

Some information about the round:

  • Rated for all participants!
  • 3 hours!
  • No subtasks!
  • There will be an interactive problem in this round. You can read the guide for interactive problems here
  • Editorial will be published right after the system testing

All problems in this round were prepared by us, antontrygubO_o and kefaa2. We worked on this round for a long time and tried to make all the problems very interesting. We hope that you will enjoy the round!

We would like to thank:

The number of the problems and point distribution will be announced shortly before the round (or earlier).

Good luck and have fun!

UPD1: Using opportunity, we would like to advertise the match between tourist and Um_nik, which will start in half an hour after this round ends.

UPD2: The last contest of the decade on Codeforces will feature 9 problems .

Score distribution:

500 — 1000 — 1500 — 2000 — 2750 — 3250 — 3750 — 4000 — 4500

UPD3: Editorial

UPD4:

Congratulations to winners:

  1. Radewoosh
  2. Um_nik
  3. yosupo
  4. FizzyDavid
  5. ksun48
  6. isaf27
  7. Petr
  8. WZYYN
  9. AndreySergunin
  10. saba2000

Read more »

Announcement of Good Bye 2019
 
 
 
 
  • Vote: I like it
  • +1517
  • Vote: I do not like it

By antontrygubO_o, 6 months ago, In English,

Everything in this blog is only my opinion, motivated by the recent round. If you disagree with it, let's discuss in the comments!

It's always hard to prepare a balanced problem set, and when the contest turns out to be unbalanced, an army of angry coders will destroy you in the comments section. But how can setters make Codeforces contests balanced?

Before, authors usually had to spend more time coming up with new problems which would close a too large gap between some $$$2$$$ problems. But now we have an easier solution! Any time there is a big difficulty gap in a contest, add subtasks to it!

View on subtasks by MikeMirzayanov:

Subtasks became really widely used in Codeforces contests recently. I looked at last $$$30$$$ contests rated for Div1 users. In turns out that:

Rounds $$$30 - 21$$$ had only $$$1$$$ subtasks in total,

Rounds $$$20 - 11$$$ had $$$3$$$ subtasks in total,

The last $$$10$$$ rounds already had $$$7$$$ subtasks in total.

Codeforces rounds in the nearest future:

But what can be bad about subtasks if they are making contests so balanced? I have several thoughts.

To begin with, subtasks shouldn't be treated as a panacea. That means, that we can't create a random set of problems with hope to make it balanced by adding several subtasks: they should be treated as a safety bag. As MikeMirzayanov says, In a perfect world, probably, subtasks are not needed

Setter has to really aim to make a balanced round, and after that, if testing shows that there is some very large gap, then maybe try to close it with a subtask. This means that subtasks should be pretty rare in general. However, we see that the number of subtasks in Codeforces contests is growing. Did setters really become worse in making the rounds balanced during the last year? I don't think so, and, to be honest, it feels like the trend now is "Oh it's not balanced, don't bother, just add subtask". The earlier the round is ready the better!

Now the actual complaints about the subtasks on Codeforces:

1. The difficulties are almost always ruined.

Let's look at several examples:

Codeforces Round #602(Div 1). Both problems A and B1 in this round have difficulty $$$500$$$. However, I believe that B1 is easier than A.

Codeforces Round #601(Div 1) Problem B1 is worth $$$500$$$ points, B2 is worth $$$750$$$ points, while the only step that B2 makes with respect to B1 is that you can iterate only through prime divisors, not through all divisors!

And an example that really a lot of people were angry about:

Codeforces Round #584(Div 1), where both E2 and G1 were worth $$$1500$$$ points, which is nonsense.

2. The strategy of solving the easy subtask before trying hard gives more points than just solving hard from scratch too often.

Again, look at Codeforces Round #584(Div 1) with G1 worth $$$1500$$$ and G2 worth $$$2250$$$. Here implementing G1 before even trying G2 is the best strategy.

The same is true about B1 and B2 in Codeforces Round #602(Div 1) (for not too high rated users), about G1 and G2 in Codeforces Round #568(Div 2), and so on.

As pointed out by teja349 here, this would have been okay if the penalty was last submission time, but the decreasing problem value Codeforces system makes the situation with subtasks really sad. Basically, this gives a motivation to solve all easy problems first and doesn't give you nor motivation either time left to work on the harder version.

3. The subtasks should have some weight as problems even on their own, but often they are dead problems.

I will explain what I mean. Consider problem B1 from Codeforces Round #602(Div 1). I am sorry, but there is just nothing good about this problem. It's clear that it was created just for balance, and it's clear that no author with some self-respect would come up with exactly this problem, it's suitable only as a subtask. But as a result, we get a Frankenstein problem.

One more Frankenstein:

E1 from Codeforces Round #577(Div 2) — I really like E2 version, but E1 just makes you code all the possible positions on the board, and I don't think that there exists a person that would find that beautiful.

4. Often, the solution for subtask doesn't have anything in common with the solution of the original problem

Again, refer to problem B1 from Codeforces Round #602(Div 1), E1 from Codeforces Round #577(Div 2).

Just to clarify: I don't think that all problems with subtasks are bad. In particular, I think that F1 and F2 from Codeforces Global Round 4 were fitting perfectly, same about E1 and E2 from Codeforces Round #588(Div 1).

However, I don't feel that subtasks have been really successful in Codeforces (yet). Setting a good subtask doesn't require much less effort than coming up with a new problem, and should be treated with the same amount of responsibility, but it seems that's not true here (yet).

What do you think?

Read more »

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

By antontrygubO_o, 8 months ago, translation, In English,

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

Read more »

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

By antontrygubO_o, history, 8 months ago, In English,

If I don't become the international grandmaster before the new year, I’ll dye my hair cyan (according to my true level) for a week.

Read more »

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

By antontrygubO_o, 10 months ago, translation, In English,
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...
Tutorial is loading...

Read more »

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

By antontrygubO_o, 10 months ago, translation, In English,

Hello again, Codeforces!

I am glad to invite you to Codeforces Round 580, which will take place on Aug/18/2019 16:45 (Moscow time). Round will be rated for both divisions.

All problems in this round were created and prepared by me, antontrygubO_o. I tried to make them interesting and hope that you will enjoy them!

A lot of thanks to arsijo for the excellent coordination of the round, kefaa2, gepardo, danya.smelskiy, re_eVVorld, Xellos, GandalfTheGrey, prof.PVH, KAN for the testing and valuable comments, and to Mike MikeMirzayanov Mirzayanov for the amazing platforms Codeforces и Polygon.

Participants in each division will be offered 6 problems and 2 hours 10 minutes to solve them. As usual, I strongly recommend reading statements of all problems!

I wish you good luck and high rating!

UPD1:

Scoring distribution of Div $$$2$$$ round: 500 — 1000 — 1500 — 1750 — 2250 — 3000

Scoring distribution of Div $$$1$$$ round: 500 — 750 — 1250 — 2000 — 2500 — 3000

UPD2:Editorial

UPD3 Congrats to winners!

Div 1:

1. TLE

2. Um_nik

3. mnbvmar

4. Benq

5. CauchySheep

Div 2:

1. kkkkk11

2. sucuk

3. ujrepacul

4. zzffxx

5. Illicit

Read more »

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

By antontrygubO_o, history, 10 months ago, In English,

Suppose than person A comes up with an interesting task, but is not able to solve it. Then, A sends this problem to his friend B and asks for help in solving it. After B successfully does that, the question appears: whose problem is that, A's or B's?

I don't like the approach when A is considered an author as in that case he can, for example, just spam B with tons of statements he just came up with without any intuition if those are solvable, and that doesn't sound as highly intellectual work. From the other hand, I don't like approach when B is considered the author too: he is doing the same amount of job as any contestant would do during the contest. A more interesting example: if A sends his problem to both B and C and they solve it with a difference of 5 minutes. Would be weird to say they both are coauthors, would be weird to say that the first one who solved is author either.

To avoid confusion, I just prefer not to share my unsolved problems with anyone, but in this case, some interesting problems may be lost. What are your thoughts on this question?

Read more »

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

By antontrygubO_o, 11 months ago, translation, In English,

Hello, Codeforces!

We are glad to invite you to the Codeforces Round #572, which will be held on Friday, 5 July at 18:05. The round will be rated for both divisions (as this time we thanked MikeMirzayanov).

Round was prepared by us, antontrygubO_o and kefaa2. This is our first round, and, as we hope, not the last one!

A lot of thanks to arsijo for the excellent coordination of the round, gepardo, GandalfTheGrey, progmatic2, zoomswk, ecnerwala, AllCatsAreBeautiful, DmitryGrigorev, Markellonchik, dasfex, Taran_1407, slicedclementines, DenisPushkin, austrian_artist, mmello, sas4eka for the testing and valuable comments, and to Mike MikeMirzayanov Mirzayanov for the amazing platforms Codeforces и Polygon. (please rated)

Participants in each division will be offered 6 problems and 2 hours to solve them. We strongly recommend reading statements of all problems! The scoring distribution will hopefully be announced before the round begins.

We wish you good luck and high rating!

UPD1: Shortly after the contest, we'll be on the community Discord server to discuss the tasks.

UPD2: Slight corrections: participants in Div $$$1$$$ will be offered $$$5$$$ problems, one of which will have $$$2$$$ subtasks, while participants in Div $$$2$$$ will be offered $$$6$$$ problems, one of which will have $$$2$$$ subtasks. Please note that subtasks will be unusual this time and will differ not only by constraints.

UPD3:

Scoring distribution of Div $$$2$$$ round: 500 — 1000 — 1250 — (500 + 1250) — 2250 — 2750

Scoring distribution of Div $$$1$$$ round: (250 + 750) — 1250 — 1750 — 2250 — 2500

UPD4: Editorial

UPD5 Congrats to winners!

Div 1:

1. Um_nik

2. ugly2333

3. Radewoosh

4. Marcin_smu

5. Endagorion

Div 2:

1. esbee

2. handsomeIvan

3. philologist

4. teamskiy

5. NeoGul

Read more »

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

By antontrygubO_o, history, 15 months ago, In English,

Yesterday I saw the announcement of the contest Code Mutants on Codeforces, it said contest will take place today (19th February). I went through the announcement, it said:

"Top 3 contestants will be rewarded with 250 Laddus!! from CodeChef.Some of the top contestants will be selected for onsite round where prizes worth 10,000 INR are waiting for you!!"

I thought: "Cool! I definitely should try it, I feel inspired!"

So I felt inspired and went to the CodeChef. In announcement there, I saw the following:

Hoping to get to onsite, I filled in this form!

Then, the contest started. Tasks turned out to be very interesting! Even more impressive was innovative Tex formatting:

After I solved the first task, I tried to submit it and clicked Submit. However, it was testing too long. "Maybe it's TL?" — I asked myself. After it was testing for 5 more minutes, I dropped that idea.

That was kinda strange. I went to my submissions of that problem and discovered that I had no submission for it. Moreover, after I tried to send the solution 5 more times, I still had no submission for it. However, after I got too nervous, I got the following message from Codechef:

So it was receiving my submissions, just wasn't displaying them anywhere. Still happy about the great contest, I went to the contest page and saw that tasks were so hard that nobody managed to solve a single problem!

However, it turned out that some solutions still were tested, though not displayed there. I went to the scoreboard and saw that somebody managed to submit a few problems. However, there were some cheaters, who, as their penalty indicates, submitted problems even before the contest started.

It got really suspicious. I went to the announcements, expecting to see the message telling about technical issues, but here is what I saw:

Nice! That's exactly what would help me now.

However, later they acknowledged that they experience some technical issues:

Anyway, I really enjoyed the contest! I have never laughed so much during the actual online competition. Tell about the contests that you enjoyed!

Thanks for attention

P.S. I didn't want to imply anything bad about the problem setters or to express any disrespect to organisers: they still have done a lot of work. Just wanted to share the best contest of my life impressions!

Read more »

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

By antontrygubO_o, history, 16 months ago, In English,

After 6 months without contests, CsAcademy is finally back!

https://csacademy.com/contest/fii-code-2019-round-1

Read more »

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

By antontrygubO_o, history, 16 months ago, In English,
 
 
 
 
  • Vote: I like it
  • +345
  • Vote: I do not like it

By antontrygubO_o, history, 16 months ago, In English,

I am just curious.

Suppose some problem has a randomized solution which fails with probability at most . If it has, say, 100 tests, the probability of failing some of them is about . Therefore, once in 104 it may happen that correct randomized solution doesn't pass.

Has anyone experienced anything like that? Maybe even the exact solution that didn't pass got AC after submitting it the second time? Or am I getting something wrong?

Read more »

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

By antontrygubO_o, 16 months ago, In English,
 
 
 
 
  • Vote: I like it
  • +97
  • Vote: I do not like it