| # | User | Rating |
|---|---|---|
| 1 | tourist | 3748 |
| 2 | Benq | 3540 |
| 3 | Petr | 3470 |
| 4 | Radewoosh | 3355 |
| 5 | ecnerwala | 3347 |
| 6 | maroonrk | 3345 |
| 7 | jiangly | 3324 |
| 8 | scott_wu | 3313 |
| 9 | ainta | 3298 |
| 10 | boboniu | 3289 |
| # | User | Contrib. |
|---|---|---|
| 1 | 1-gon | 200 |
| 2 | Errichto | 197 |
| 3 | rng_58 | 194 |
| 4 | SecondThread | 186 |
| 5 | awoo | 185 |
| 6 | Um_nik | 182 |
| 7 | vovuh | 179 |
| 8 | Ashishgup | 175 |
| 9 | antontrygubO_o | 174 |
| 10 | -is-this-fft- | 173 |
As Morphy hasn't posted this yet, and as the last big contest of 2020 is over, I think it's time.
2020 was a hard year for all of us, but it still gave us a lot of great contests and, luckily, no notorious coincidences. So, what were your favorite problems in 2020?
We invite you to participate in CodeChef’s September Lunchtime, this Saturday, 26th September, from 2000 hrs to 2300 hrs IST.
Please Note — Unusual starting time. The Contest will begin at 2000 hrs instead of 1930hrs
The contest will feature 5 problems for 3 hours. I am author of all problems. I hope you will like them.
Also, if you have some original and engaging problem ideas, and you’re interested in them being used in CodeChef's contests, you can share them here.
Joining me on the problem setting panel are:
Prizes: The top 10 Indian and top 10 Global school students from ranklist will receive certificates and CodeChef laddus, with which they can claim cool CodeChef goodies. Know more here.
Good luck and have fun!
Hello everyone!
I finally decided to write some response/explain my view after all recent discussions of my problems and rounds I coordinate, and I would like to make a few points.
1. After some recent contests there were a lot of comments saying that Data structure problems should appear as easy problems (say, D2A-D2D in a Div2 of $$$6$$$ problems)
I don't think I agree with this. To begin with, I don't think that having Data Structure problem is a requirement for a good contest at all, not just in first few positions.
However, for positions D2A-D2D, I just don't see a way to properly include data structure problems. Take some Data Structure problem, it consists from two parts:
The problem is, that even the simplest Data Structure (say, Segment Tree), makes the first part already at least D2D difficulty in a Div2 of $$$6$$$ problems. Now, if the second part is completely trivial, then the problem shouldn't be used in official CF contest (maybe in Educational Round only): implementation part can't be much harder than thinking part. If the second part isn't trivial, the problem can't be less than D2E. Therefore, I can't really see how can Data Structure problem appear on positions D2A-D2D.
Remark: Here I don't even count sets/maps as Data Structures.
2. A lot of people lately are sad because graphs, dp and all other topics don't appear now. Only constructives and ad hocs are left!
To begin with, this is not true. All topics appear! I went through last $$$3$$$ Div2 contests I coordinated. Among them:
1372E - Omkar and Last Floor and 1363F - Rotating Substrings are DP.
1364D - Ehab's Last Corollary, 1363C - Game On Leaves and 1363E - Tree Shuffling are graph problems.
1363D - Guess The Maximums is binary search problem.
However, it's somewhat true that easier problems are more often not related to these concepts. From my perspective, the reason for this is similar to the reason I provided in argument above: it's impossible hard to create an interesting DP/Binary Search/Graph problem which could fit positions D2A-D2C. Just because that concepts themselves are already quite challenging.
And I don't want to accept standard problems on DP/Binary Search/Graphs just to make the set more diverse or because you want it, and won't do so, I think.
3. While I understand that many people really like these topics and want them to appear as early problems, I believe that a lot of this feedback is coming from participants who learned some new algorithms/techniques and are sad when they don't become red they don't see these problems in contests.
Well, from my perspective, CP isn't about knowing algorithms, it's more about solving problems. Algorithms are tools. Knowing many algorithms means that you have a lot of tools, but if you don't know how to apply them, this won't help. That's why you should learn how to solve problems, not just learn algorithms.
4. Some people think that contests by me/coordinated by me aren't diverse enough, and contain too many constructive problems.
And well, I agree with this. I also believe that having too many constructive problems is not a good thing for a contest. From this perspective, Codeforces Global Round 9 wasn't very good. I also believe that the problemsets should be more diverse. However, when choosing between having less diverse problemset and accepting fairly standard problem, I will always prefer first.
Still, this is a valid objection. I will try to make problemsets more diverse :)
5. Some people think that I just won't accept Data Structure/Flow/Some string structures/Anything except ad hoc.
This is a very wrong point of view. I will accept problems in which idea is interesting enough. The problem is: it's much harder to create a problem on these topics which would at the same time be interesting than creating a good ad hoc problem. It seems that CP has evolved significantly in recent few years, and some things which weren't standard $$$4$$$ years ago, are very standard now. So yes, the reason why good nonstandard problems on these topics appear less now, is that there aren't many of them in proposals! However, still, expect to see some problems on these topics in future contests :D
6. While I understand people who say that it's sad when algorithms don't appear in contests, I don't think I understand people who get joy from struggling with implementing some problems. I am not against problems with quite long implementation, as long as implementation difficulty is smaller than the thinking difficulty. My opinion is best expressed here:
7. I would like to thank:
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.
This problem is easy enough for D2B, it had $$$8679$$$ solves from official participants during the contest. However, it still requires an observation: length of the LIS is equal to the number of distinct elements.
Again, you need an observation that the answer is the difference $$$a_{n} - a_{n-1}$$$ in the sorted array.
Again, easy enough, but you still need an observation: if there exists some interesting segment, there exists one of length exactly $$$2$$$.
A few more nice D2Bs where you have to think a bit:
1305B - Kuroni and Simple Strings
1091B - New Year and the Treasure Geolocation
You may be surprised, but even D2As can have nice ideas in them! Here are some examples:
There are A LOT of possible constructions, so it's hard to get stuck on this problem, but you still have to be creative.
Observation: everything works out if you sort arrays. Cute, simple, extremely easy to implement.
Again, there are a lot of approaches to this problem, but you still have to think to find them.
556A - Case of the Zeros and Ones
You need an observation: while there is at least one $$$1$$$ and at least one $$$0$$$, we can perform the operation, so the answer is just the difference between amounts of $0$s and $1$s!
1174A - Ehab Fails to Be Thanos
There are a lot of ways to solve this problem, but you can solve it with a cute observation: if it's even possible to reorder the array, then sorting the array will satisfy the condition!
Here are a few more nice D2A problems:
1237A - Balanced Rating Changes
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:
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?
Hello Codeforces!
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:
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!
Information about prizes will appear soon.
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!
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.
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.
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.
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.
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.
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.
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.
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.
Retired_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.
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
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.
Radewoosh: In random order:
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 - 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?)
First two problems were on school olympiads for 6-9 grade. To my surprise both problems were solved.
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.)
Radewoosh: If not authored by me:
102331H - Honorable Mention: by 300iq
1254B2 - Send Boxes to Alice (Hard Version)
1229F - Mateusz and Escape Room
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...
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.
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
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
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
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 Fedosik 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
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 :(.
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!
(You will see my cyan hair in the next few days)
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:
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:
Announcement of Good Bye 2019
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?
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!
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
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:
Take something from real life and give it a formal statement
Work from solution or key idea backwards
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).
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.
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:
Original observation required to solve the problem.
Application of typical techniques.
Implementation.
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.
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?
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.
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)
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).
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.
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.
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? ---
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.
Make div1only rounds?
I don't know. I tried, really. cries
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...
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.
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).
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.
Oppa Funcan Style Remastered -- a variation on the theme of http://acm.timus.ru/problem.aspx?space=1&num=2107 with completely different solution
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.
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.
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!
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
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.
Tutorial of Codeforces Round #580 (Div. 2)
Tutorial of Codeforces Round #580 (Div. 1)
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, Fedosik, I_love_tigersugar, 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. Miracle03
Div 2:
1. kkkkk11
2. sucuk
3. ujrepacul
4. zzffxx
5. VahitGuetta
Announcement of Codeforces Round #580 (Div. 1)
Announcement of Codeforces Round #580 (Div. 2)
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?
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, Fedosik, kefaa, zoomswk, ecnerwala, AllCatsAreBeautiful, DmitryGrigorev, Markellonchik, dasfex, Discombobulated, ankeet, 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. CSWhisky
2. handsomeIvan
3. philologist
4. teamskiy
5. NeoGul
Announcement of Codeforces Round #572 (Div. 1)
Announcement of Codeforces Round #572 (Div. 2)
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!
After 6 months without contests, CsAcademy is finally back!
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?
