errorgorn's blog

By errorgorn, 2 years ago, In English

2 years ago, antontrygubO_o wrote a blog about div2ABs where he expressed his opinions that d2ABs should not be about "here is a statement, please implement what is written there". Thanks to him, the quality of d2ABs (and problem quality in general) have certainly improved. However, I still believe that there still quite large differences between how coordinators/problemsetters view d2ABs and how the intended participants view them.

From the survey made by kpw29, we can see that most people agree that most people agree that we should primarily consider the target audience when proposing a task. I too think if a task is boring to div 1 contestants, we should not think of that as a reason to immediately disqualify a problem from being a d2A.

I think when people judge the interesting-ness of d2As, they try too hard to make it pleasing to div 1 contestants by having short implementation, short statement (no reading comprehension) and at some cute ideas.

While this mindset works very well for combined rounds where div 1 contestants do need to and forced to solve d2ABs and quickly get ABCD over with, I think we should have a different mindset when considering div 2 problems.

We should not make setting interesting d2ABs our top priority but instead make it setting friendly d2ABs. By friendly d2ABs, it means that the solution is easy to justify (there is no difficult constructive proof of why this random condition is sufficient) and that the statement is without much mathematical constructs, it would be best if a 5 year old can read the statement and be able to understand the problem.

Elaborating on my point about having d2ABs contain some non-trivial ideas, sometimes this ideas take the form of something that is downright unapproachable to newer contestants where for them, it feels like a "guess and check" game where they cannot prove anything they submit and just hope that their guess is good.

I believe that this makes beginners in competitive programming think that solving competitive programming is just having good guessing skills and such observation comes from nothing other than divine sources. I recognize that having a good intuition is a valid strategy to solve competitive programming problems and I do guess observations all the time when solving problems. But we should not colude not having a proof with the complete inability to justify why something should be true (I am looking at you 1672F1 - Array Shuffling).

We should still strive observations on d2ABs more managable such that when one is able to correctly guess the observation, it would not be too hard for them to figure out why the code they submitted is correct if they wanted to. For some constructive d2ABs where the output is yes/no, it might make sense to ask for participants to print their contsruction too. Although this would make coding much more involved that it has to be, I believe this would be fine for most codeforces rounds.

Furthermore, when people set d2ABs, they sometimes use mathematical constructs that not all beginners would know of. It is not uncommon to see bitwise operations in the statement of a d2A followed by an explanation of what said bitwise operator is. If people see the need to provide a link to an explanation of what a bitwise operator is, then why not just not set a d2A that requires you to understand what a bitwise operator is to even comprehend the statement?

Imagine you are a beginner in competitive programming and you only know some basic language syntax, would you really be interested in caring about random problem where someone calculates some stupid value using some random function? There are billions of d2ABs with $$$\text{gcd}$$$, $$$\text{mex}$$$ or some bitwise functions. But how many times do you see such functions outside of d2ABs? With $$$\text{gcd}$$$ or $$$\text{mex}$$$, I think it is very rare. Because most of such problems involving these just use the "fun facts" of these functions.

Let's look at 1325A - EhAb AnD gCd as an example (which antontrygubO_o used as an example of a good d2A). The problem just asks if you know the fun fact that $$$\gcd(x,1)=1$$$ and $$$\text{lcm}(x,1)=x$$$. Despite myself belonging to the camp of formal statements, I believe that d2ABs should have as natural a statement as possible, in the sense that as much as possible, we should not have random mathematical constructs being the basis of d2ABs. I don't want to solve d2ABs where I have to recall the fun fact that $$$\gcd(x,1)=1$$$.

At the end of the day, there are many "factors" that affect the suitability of d2ABs for codeforces contests. I don't think we should sacrifice the enjoyability of d2ABs to the intended participants contestants for the sake of making them "interesting".

Because of the goal of setting d2ABs with the intended audience in mind, I decided to ask a few coordinators and users who are specialist and below to answer questions about their thoughts of d2ABs. Since I was already asking people their opinions on d2ABs, I decided to ask some additional questions that felt interesting to me somewhat related to this topic.

Thank you to Monogon, Um_nik, dario2994, antontrygubO_o, isaf27, 74TrAkToR, darkkcyan, -is-this-fft-, sus, tdpencil, kIee,SPyofgame and ak2006 for spending their time answering these questions and giving me permission to post it here.

Note: These responses were from a month ago but I procrastinated writing this blog.

What is your philosophy on d2ABs?


  1. In general I believe the easiest problem should be completely trivial for the intended audience of the contest. A gift, so to speak. I have heard this principle from several seasoned contest organizers. This has several reasons.

    1. Someone is much more likely to do another contest if they solved at least one problem, even if it is completely trivial to them.
    2. A psychological thing: it builds engagement and commits you to the contest. If you are in a contest and can't solve the first problem relatively quickly, then you will kinda get bored and drift away. Once you solved the easiest problem you are more committed to the contest and are ready to spend more time to solve the rest.
    3. On Codeforces, it warps ratings if people don't submit to the easiest problem because they don't have ideas for it.
  2. I'm not a fan of "troll" div2ABs, that is, problems that have some weird restriction but some very simple construction. All it does is teach beginners that cp is about guessing.

    1. Also, people are often misled by thinking that if a problem solution is simple, it must also be easy to solve. Solution length, unless very excessive, is no argument as to the difficulty of a problem. I'm reminded of a certain local contest where the easiest problem turned out to be pretty hard for the participants, for exactly this reason.
  3. Easiest problems should not be annoying or tedious for the same reason as 1b.

  4. Making the problem interesting should not come at the expense of any of the above.

Monogon: A div2AB problem should be possible for a programmer with minimal knowledge of algorithms to solve, but still presents some kind of challenge. Maybe some simple observation or a slightly nontrivial implementation will be necessary, but it shouldn't feel like you're mindlessly doing exactly what the statement says if you're a beginner.

dario2994: Good very easy problems are not so different from good hard problems, they are just easier. They should be interesting for everyone, but this is often an impossible requirement to satisfy. If one cannot find an easy problem interesting for everyone, then the priority should be to make it interesting for the target audience, i.e., newcomers in competitive programming. A good very easy problem does not require any knowledge, is not "implement what is described in the statement", is solvable in any language (python I am looking at you). I prefer to give very easy problems involving some computer science instead of something which is solved with a sequence of if-checks or in $$$O(1)$$$. I don't have any strong opinion about whether a very easy problem should be trivial to implement or not.

antontrygubO_o: They shouldn't be painful (in the sense that they shouldn't have long statements, be caseworky, or have long implementation), and shouldn't be "implement what you read". The natural statement is preferred. I prefer when there is some cute idea.

isaf27: My philosophy is:

  • Perfect d2a should be the problem, that will be solved by all participants of the contest. On the other hand this problem should contain some idea, maybe very very simple and obvious, but idea. I don't like the problems "just write what is asked in the statement" even for d2a.
  • d2b should be simple, but not obvious.

74TrAkToR: These are tasks for beginners. I think they should be on the idea. There should be a minimum implementation.

darkkcyan: I think that a round on Codeforces should be fun, and maybe educational for newcomers.

The word "difficulty" is relative. A problem can be very hard for one person, but can be trivial for the others. But when judging a problem by myself, I often measure it by the time I spent to think, as well as implementation time. I wanted that for A the idea should be found in a very short amount of time, if not instantly, at least with my level, and for B might be a bit longer, but not toooo long. But a coordinator is only a barrier, the next barrier is the testing phase, which should be more accurate if we invite a good spectrum of testers.

About the idea. First of all, I don't think div2A should be like Atcoder ABC A, because in Atcoder ABC A, you can do what is asked in the statement. Again, I wanted to round to be fun. The joy of solving puzzle is when you find the right idea, and thinking how smart you were. So a broad answer is just, not to make it too trivial and standard, and the rest is determined by the difficulty. That is the same for B, but yes, we must make B somehow harder. This is still an open question, but I think I should leave it there, because creating a problem is truly a hard task.

Why should we care about the quality of d2AB if most div 1 competitors forget them after 5 mins anyways?

antontrygubO_o: Question is weird: most Div1 users forget all problems after 5 minutes. But we should just aim for a better quality of problems.

Still, for me personally, boring/stupid D2A-D2C problems may ruin the round, as I am not expecting anything good in the harder problems. I understand that many Div1 users don't care, but many Div1 users would be happy with standard problems on the harder spots as well, so what?

darkkcyan: I think this is an odd question when asking a question about the easiest problems of a div2 round, made for div2 competitors. Well, it should be fun for div 1 competitors too. And for me, they are warm up problems. And for div 2 competitors, they should be fun, again. For newbies, there are educational values as well. In all cases, these problems are the introduction to the way of thinking and observing when doing contests, and I still think that they are doing a good job on that. I do see that nowadays, div2AB requires more thinking than the previous years, but that is also true for div2C and above. Thus, because they are the very firsts problems of a round, acting like guarding problems for the other problems, their qualities should be in the care as well.

because of the bulk of the participants only solve d2ABs and div1 participants are not the target audience

What things do you like/dislike about d2ABs on codeforces?

sus: I like the simplicity and typicallity of div2 A and Bs. Even though they only cover simple topics like math, brute force, and simulation, they allow any beginner cper to practice their problem solving skills. Some of the drawbacks of ABs is that they only cover a small amount of topics, so they might start to get repetetive/boring if a problem setter is feeling lazy and that you can't learn much from them after you get good at solving them. People get carried away trying to get 800 problems solved and only solve ABs trying to reach this goal.

Whenever I need to get ready for a contest, I get warmed up by quickly solving an AB. ABs serve as a stepping stool for beginners and thats what I like about them.

ak2006: I like the fact that div 2 ABs dont require much DSA knowledge and can be solved by someone who hasnt done much CP. I dislike that they might use too much math (number theory, combinatorics) which only math major or minors/math olympiad people may be acquainted with well enough to be able to solve them.

kIee: I do not like ABs at all, for contestants who cant really tackle harder problems/ spend much more time on them, AB is purely a speed contest. In addition, it's largely affected by internet speed, submission speed, etc, and their weightage is very high. Especially affected when trying to open up problems. (eg, solving AB slower by 1/2mins, can lose to another person even though i solve C faster by 15mins)

SPyofgame: Simple to read, simple to understand statement and testcase, interesting idea, not too focus on a specific type of problem, easy to solve but still require thinking a bit instead of doing without brain

Do you think d2ABs must necessarily be short implementation?

tdpencil: I believe d2A should. d2B should probably be more implementation based or should permit longer implementation. Just because newbies and beginners are going to try div 2 A and if they don't know how to code it up fast or they don't know how to write such long code then its going to be challenging for them.

sus: I think i dont care. There are 1 liners, there are 30 liners and there are those in between. Just another problem doesnt make a difference to me.

Some high rated users have difficulty differentiating d2As-d2Cs what would be a good rule of thumb to determine the correct position of a easy problem?

dario2994: Gauging the difficulty of problems is hard. It is hard to distinguish d2As from d2Bs as it is hard to distinguish d2Ds from d2Es. The difficulty is on a spectrum and there is not a cheap trick to distinguish. Experience helps and I don't think that high rated users find it harder to distinguish d2As from d2Bs than low rated users. But it might be that high rated users are more aware of their inability to make the distinction compared to low rated users.

antontrygubO_o: It's hard for me to imagine that someone may actually have difficulty with this, to be honest. Look at D2A-Bs of recent contests, you will most likely agree that B is harder than A in most of them.

tl;dr testers exist for a reason

Do you prefer div 2 rounds or educational rounds more? Why?

tdpencil: I prefer educational rounds. This is because i can pretty much depend on the difficulty of educational rounds and expect to learn something. Most edus are made by the same people so the quality of problems are about the same. For div2s however, a variety of people make the problems and it can be argued that some are much easier than others, meaning not all div2s are at the same difficulty (on average). I would argue that having div2s be varying difficulties is an issue but thats just my opinion.

ak2006: I prefer regular rounds since they use much less math for some reason — edu rounds arent very educational and arent much DSA based as they should be.

sus: I prefer div 2 rounds because educational rounds are the same as any other round for beginners: every round is an educational oppurtunity when you are new. The only reason I prefer div2s is becuase it is easier to gain rating in them. Sometimes I solve C in div2s which is worth a lot more than AB but in edu rounds C is worth the same.

Ratings of d2ABs

I decided to ask people to give rate some d2ABs from 1 to 10. These div 2ABs were chosen to get a hopefully diverse set of current meta of d2ABs. But take the numerical rating with a giant pinch of salt.

In the words of dario2994, "it seems to me as "rank from 1 to 10 these apples and these cars according to their color, their speed, their consistency, and your overall feeling". It would be a random number."

Anyways, here are the assigned scores in a table form. I have bolded the scores which were assigned the coordinator of the respective contest (you can see that I'm pretty biased).

1266A 1281A 1339A 1391A 1581A 1583B 1598A 1610A 1634B 1642A
-is-this-fft- 10 8 9 3 5 3 8 2 5 6
antontrygubO_o 9 2 7 5 7 10 7 6 10 7
Um_nik 3 0 7 4 4 6 4 5 2 3
Monogon 5 7 10 6 3 5 9 7 4 6
darkkcyan 7 8 9 5 7 7.5 8 9 9 7
isaf27 10 2 6 5 8 6 9 6 10 4
errorgorn 6 1 10 4 9 7 10 5 3 4
kIee 1 8 10 2 7 3 8 4 2 9
sus 3 3 8 4 2 7 6 4 1 9
mean 6 4.33 8.44 4.22 5.78 6.06 7.67 5.33 5.11 6.11
stddev 3.28 3.35 1.51 1.20 2.39 2.21 1.80 2 3.62 2.15

From this, we can see what is pretty universally agreed to be good d2ABs (the comments are my opinion):

  • 1339A - Filling Diamonds — timeless masterpiece of print(input())
  • 1598A - Computer Game — although this can be solved by performing dfs and the problem is classic by all standards, it is a wonderful d2A due to the fact that the intended solution is so elegant yet easily motivable by beginners

We can also see what the "controversial" problems are:

  • 1266A - Competitive Programmer — requires quite a bit of requisite knowledge on number theory which is pretty unrelated to competitive programming in general, why am I required to recall from primary school math that a number is divisible by $$$3$$$ if its sum of digits is also divisible by $$$3$$$?
  • 1281A - Suffix Three — textbook "implement what is in the statement"
  • 1634B - Fortune Telling — the odd/even parity idea is overused and here it is too artificial, making the problem feel forced

Full Comments about each Problem

Here are the full text comments for each problem if you want to read them.



I think it would be interesting to see how users from various ratings rate each of the 10 d2ABs stated earlier in the blog. So I have created a google form where you can rate these d2ABs. I will release the results after a couple of days.

Maybe I will do some data analysis on the results. I tried to do some data analysis on the scores assigned by coordinators (after normalization) and got this:

This chart looks very dumb by all standards but hopefully we can see better trends after I get more data.

Anyways, I encourage members of the community to share their thoughts in the comments about the current direction that d2ABs are heading towards, especially for people who are specialist or below since d2ABs are targeted towards them.

Also, to future problem setters, maybe this will allow you to get more d2ABs accepted by seeing the preferences of your coordinator lol

Results of Poll

You can access the results of the poll here. I have manually added the scores of those people who I personally asked to send scores and the names of people who have posted their scores in the comments.

I have done some basic data analytics and I believe that the results is quite interesting. For the data analytics part, I used mostly the same procedures as those described by my comment. The only different was that I only did normalization for everyone to have mean=0, because it does not make sense that "1 5 9" would be normalized to the same thing as "8 9 10". Also, I removed entry 5 when I did the analytics because it had an extremely low mean score. When I checked it, it turns out that the person had given $$$7$$$ problems a score of $$$1$$$, so I just removed it. You can check my jupyter notebook file here.

Anyways, here is the plot on the average scores given to each problem.

We can see that 1281A actually has a bimodal distribution — either you love it or hate it. From manually looking at the scores assigned to it, I don't think there is any clear correlation between rating and whether you would like this problem. Suggesting that the idea of d2ABs having "do what author tells you = bad problem" is not agreed upon even on most div 1 users.

Here is the plot of using PCA to squish down $$$10$$$ dimensions ($$$1$$$ dimension for each score) into $$$3$$$ dimension so that we can visualise it better. The third dimension is represented by the size of the point (I hope that this will allow you to imagine the point as being nearer or further away). The points are colored by the rank (or rating) of the user.

One of the striking thing is the fact that there is a vague correlation between rating and our correlation on this chart, going from the bottom right corner to the top right corner. I know that I do not have sufficient data from div2 users but I think we can kind of conclude that the opinions of most coordinators on d2ABs differs quite abit from the cluster of div 2 users on the middle right. It seems that -is-this-fft-'s and Monogon's philosophies on div2ABs are more suited for having d2ABs that are targetted towards their intended audience.

Thanks to everyone who submitted to the poll!

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

| Write comment?
2 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Well, to be honest, 1325A - ЕхАб И нОд is (literally) my favourite problem on the entire platform. It has such an elegant solution, and I often use it to teach new people the cool mathematics behind competitive programming.

2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Golden blog, thanks a lot!

2 years ago, # |
Rev. 2   Vote: I like it +17 Vote: I do not like it

I guess I'm in the minority here but questions like 1339A. Filling Diamonds seem very uninteresting to me. For A's, implementation/simulation challenges even seem more interesting than "1-observation-kill"s like that. Maybe it's because a lot of the time, I solve the question without understanding why my observation is correct, which is my own fault I guess. It seems like very often, div 2 C is easier to reason about than div 2 A, and the solution is much more natural. I have a pretty weak math background (which I'm trying to work on) so I suppose that's why I feel this way.

  • »
    2 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    May I ask for some examples of d2ABs that you would give a 10/10?

2 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Sorry, what exactly is the last graph supposed to show? There are no labels on the axes.

  • »
    2 years ago, # ^ |
      Vote: I like it +127 Vote: I do not like it

    You can use your own imagination to interpret the image. Here is one interpretation.

    my interpretation
  • »
    2 years ago, # ^ |
    Rev. 2   Vote: I like it +20 Vote: I do not like it

    Short answer: idk

    Long answer: This is data science and I don't know what I'm doing, so I might be writing bullshit. Please correct me if I writing something wrong. You can see the jupyter notebook file here.

    I normalized the responses of each person to $$$\text{mean}=1$$$ and $$$\text{stddev}=1$$$ there are quite a few anomalies such as darkkcyan giving a score of $$$7.75$$$ on average while um_nik giving a score of $$$3.90$$$ on average.

    I wanted to plot the scores given by people on a way that is easy for humans to visualize. So the way I did that was using principal component analysis (PCA) to transform $$$10$$$ dimensions into $$$3$$$ dimensions (it is $$$2$$$ in the original diagram, I will use $$$3$$$ here because I saw that most of the variances are in the first $$$3$$$ dimensions only).

    The third dimension is given by the size of the points (bigger points is higher value). To figure out what the value of each axis means we will look at the PCA components (check the notebook for the full table).

    The main value of each feature are like this:

    feature 1:

    • likes 1281A, 1339A
    • dislikes 1634B

    feature 2:

    • likes 1266A, 1281A
    • dislikes 1583B, 1610A

    feature 3:

    • likes 1634B
    • dislikes 1391A, 1581A

    I thought there would be some nice way to tell what each feature means but I don't think there is.

    Also, this graph looks slightly different in the 2d version because I somehow lost the scores I gave to each problem a month ago so I just did my scores again (so the plot in the original post is slightly wrong), but it seems I gave pretty much the same scores?

2 years ago, # |
Rev. 2   Vote: I like it +18 Vote: I do not like it
My scores
2 years ago, # |
  Vote: I like it 0 Vote: I do not like it

I agree. Some DivA / B are quite easy, You see, you figure out stuff and solve, while some Div2 A's are like 1672A. It's perfect combo of scary, Implementation and theory. I still don't know what I did to get this accepted 154711927. This will be one of my favorite cp problems.

2 years ago, # |
Rev. 2   Vote: I like it +28 Vote: I do not like it

"antontrygubO_o: Question is weird: most Div1 users forget all problems after 5 minutes."

after the last global round that sounds to me like anton is projecting himself onto "most div1 users" (if you don't understand, old div1D that he upsolved then said that an easier version is div1E because omg! such geniosity slipped into the global round). That's simply not fair, anton sends problems to IMO, you're not "most div1 users".

  • »
    2 years ago, # ^ |
      Vote: I like it +8 Vote: I do not like it

    Having good memory is important for success in CP

2 years ago, # |
  Vote: I like it +3 Vote: I do not like it

I don't care how div2AB problems are, just make them so that i dont brick on them

2 years ago, # |
  Vote: I like it +84 Vote: I do not like it

I think that too many of the current Div2A/B are much more guess-based than implementation-based. It's cool to have some observations in easy problems, but there's a difference between observation and wild guess. In my opinion, if a Div2A problem has a very easy solution with a wild guess (for example, if something like print(input()) works), it should also have an implementable solution without these guesses. Some of the recent problems are too one-sided; you either guess that something works, or don't. For me, the perfect Div2A problem is something that can be very easily implemented with some observation, but still doable without this observation. Math tricks are fine, as long as it's not too complicated. I don't mind something like "do what the authors tell you" in Div2A, but not in later slots, and this "what the authors tell you" should be short.

I also think that Div2A statements should meet one of the following constraints, preferably both:

  • the statement is short and easy to grasp
  • the statement is based on some real-world model, which makes it much easier to understand

Some of Div2A statements (mostly those which don't meet these two constraints) are too difficult to fully comprehend. Sometimes understanding the statement for someone who isn't experienced in reading complicated problems is like 99% of the difficulty of the problem. Yes, ICPC contests often contain long statements, but remember, an ICPC-contest is solved by 3 people in 4-5 hours, not by one contestant in 2 hours, so it's more suitable for ICPC.

While I'm on the topic of statements, I want to ask contestants and other problemsetters/coordinators: what do you think about the stories/non-formal legends in the statements? Sometimes it feels like that the story is just redundant for me. I am guilty of setting some problems with unnecessary long legends as well; this one, for instance, is a complete disaster of the statement, even for C-slot. In time, I arrived at the following rule of thumb for legends:

  • if a problem was initially invented with a legend, try to write a formal statement and a non-formal one, and choose which one is better;
  • if a problem was initially stated formally, in 99% of cases, it's better not to even try adding a legend. Usually it ends up only making the problem much more difficult. Some short (one or two statements) legend might be fine, but definitely not longer than that.

What are your thoughts? How do you decide whether to include a story or not?

My votes on the problems: