MikeMirzayanov's blog

Codeforces: Problem Difficulties
By MikeMirzayanov, 6 years ago, translation, In English

Hi Codeforces!

Meet a small innovation on Codeforces — difficulties of problems (and at the same time a new widget filtering problems in the archive). For all the problems of the archive, I’ve calculated the difficulties in the scale of the rating of participants. Approximately this means that if the rating of the problem is equal to yours, then on a typical round you would solve the problem with a probability of 0.5. And, in general, if your rating is ri, and the problem rating is rj, then the problem during the round can be solved approximately with probability:

For example, if the rating of a problem is less than yours by 200, then the expected probability of solving the problem is 0.75. With a difference of 400 rating points, the probability increases to 0.9.

For convenient search of problems in the archive, you can now use a special widget:

With it, you can find not only problems that have all the chosen tags, but also which have at least one tag from the list.

A difficulty of a problem is also displayed when choosing problems in a mashup.

I hope that now you will be able to do more effective practice, and the process of making new mashups for trainings will become easier.

UPD 1: Have you already noticed new pop-ups about judgment verdicts of your submissions?

UPD 2: (API update) Optional field rating has been added to the object Problem in API.

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

Comments Comments (98)
| Write comment?
»
6 years ago, # |
  Vote: I like it +191 Vote: I do not like it

The new pop-ups about judgment verdicts of submissions are definitely helpful! During contests, I don't have to stare at the submissions to see whether I passed the pretests anymore!

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +175 Vote: I do not like it

    Thanks. Popups go from the internals of the judging server directly to browsers bypassing the database. So no reason to press F5 (but you can if you like it).

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +96 Vote: I do not like it

      Codeforces is already a more competitive programming site than topcoder

      → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Hey, could you add a feature to show only the unsolved problems in the problem set?? That would be great.

      → Reply
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Does the difficulty consider the ratings of participants who solve a problem after contest, or only during contest?

→ Reply
»
6 years ago, # |
  Vote: I like it +49 Vote: I do not like it

Any plans on using this to have a dynamic score on the contest?

→ Reply
»
6 years ago, # |
  Vote: I like it +86 Vote: I do not like it

Very cool!

Would it be possible to add an option to view problem rating within the statement of the problem? Right now I can only see it in "problemset" tab. This would be helpful.

→ Reply
»
6 years ago, # |
  Vote: I like it +34 Vote: I do not like it

Btw,I don't like to filter problems by their tags cos it gives a great hint and we think accordingly,eg to identify a problem of dp is its main trick ...

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it +48 Vote: I do not like it

    If your goal is to get better at solving problems generally then it's the right mindset. Though if you have just learned a new technique or want to practice a given topic, then tags can be useful.

    → Reply
    • »
      »
      »
      6 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      true,generally i focus more on problem solving more and more of various types,so i try to solve it in my way first ....and learn new algo whenever a problem on it is encountered ..... and try to relate problems ....this strategy is not new...dreamoon_love_AA blog

      → Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +24 Vote: I do not like it

Is the difficulty rating of a problem accessible via Codeforces API? Great feature by the way, now I can tell that the problems I solve are too easy ;-;

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

It works great, thanks MikeMirzayanov

→ Reply
»
6 years ago, # |
  Vote: I like it +58 Vote: I do not like it

codeforces is always innovative.

proud to be a part of such a great polygon.

Thanks MikeMirzayanov.

→ Reply
»
6 years ago, # |
  Vote: I like it +27 Vote: I do not like it

great feature! I really want this type of thing.

could you add this problem rating info to the codeforces API? I use codeforces API for automatically select random problem that nobody in my problem solving group solved. I used 'solved count' for judging problem difficulty. but solved count can't represent accurate difficulty. so I want to use this problem rating instead of solved count in codeforces API!

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +10 Vote: I do not like it

I want to hide the problem tags and filter problems with difficulty. But it doesn't show the unsolved problems. Is it intended or a bug? upd: fixed.

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -8 Vote: I do not like it

    Dude, if you know the tag whats the point of hiding it!

    → Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Currently, if I'm logged in and enter a difficulty in the "Filter Problems" widget, it only lists problems that I've already solved. This doesn't happen if I'm logged out or don't enter a difficulty, in which case it also lists unsolved problems.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Really nice. Is it possible to share on how did you arrive at the formula ?

→ Reply
»
6 years ago, # |
  Vote: I like it +37 Vote: I do not like it

Best thing about Codeforces . Innovations always going on.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

In order to list unsolved problems when filtering by difficulty, I need to check the option "Show tags for unsolved problems". It would be great if there was an option to filter by difficulty without having to show tags for unsolved problems, as these can give hints which spoil the problem.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +40 Vote: I do not like it

Awkward... https://codeforces.me/blog/entry/46304

→ Reply
»
6 years ago, # |
  Vote: I like it +36 Vote: I do not like it

Really nice feature, I love it a lot. However, the ratings are in intervals of 100. Why is that? Can we have them in intervals of 10, at least?

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

Thank you ! Codeforces is my love.

→ Reply
»
6 years ago, # |
  Vote: I like it +35 Vote: I do not like it

Felt like I was reading a problem statement

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +101 Vote: I do not like it

Hello, thank you very much for the cool addition!

But, you can see the rating of the problem only if you select it from the problemset...

Would it be possible to see at when you are direct on the problem / task page? ( Because you may have selected the task from a contest page, not from the problemset page )

→ Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

This is a great feauture! Good job, MikeMirzayanov! I have a small suggestion. It would be great if these difficulty ratings are also shown on the dashboard of previous contests. This would help while upsolving a particular contest as opposed to isolated problems

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Some problems have no rating, what about them?

→ Reply
»
6 years ago, # |
  Vote: I like it -14 Vote: I do not like it

How will you calculate problem rating before contest ?

Also, in problemset, how it has been calculated ?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Nice feature, but... it probably looks mainly on number of users who solved a problem. That's not always accurate on ICPC contests. "Monsters and Potions" has rating 2500 [don't read if you are planning to solve Southern Subregional!], just because everyone was too lazy to read a long statement during the contest. That problem is rather 1500. Isn't it better to disable this feature for ICPC contests? Leave it only for problems from rounds?

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

    It's for practice

    Also, i think it's some kind of weighted average from the rating of all the people that solved the problem on-contest, there is no direct correlation between score and number of solutions if you scroll through a bunch of examples on the problemset

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

    Number of people who solved it during the contest or in general? If it is in general then it should be changed to only official solutions.

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

      Imagine a contest with 13 problems: 5 are very easy, 2 are very hard, and the remaining 6 have the same mid-level difficulty.

      What happens on the contest. Firstly top teams solve 4 of 5 very easy problems. Weaker teams follow them. Then one of the top teams finds one of mid-level problems and solves it, because it is easy for a top team. Another top team finds another mid-level problem and solves it, because it is easy for this team too. Third top team finds another mid-level problem and solves it.

      What we have now? Four very easy problems are opened, and three mid-level problems are opened. Noobs follow the monitor and go for these three mid-level problems. The last, 5th very easy problems remains unopened until, say, the end of the 2nd hour. Top teams discover it, say "LOL why nobody solved it" and solve it. Noobs don't have time for it, because they are busy with mid-level problems — they have more AC counts! In the end, the 5th very easy problem becomes like 8th or 9th solvable problem.

      This is what happened on that Southern Subregional. Surely, it's wrong to estimate difficulty by only AC counts. Something like 10% percentile of rating can say more in this case — if a noob team solves it, everybody can too, they just didn't try it on the contest.

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

        Wait, sorry, i was talking about regular contests. I should have written it in the main blog not under your comment, sorry again.

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

        Reminds me of CERC 2014 where problem L was solved by 3 teams. I was the first person to solve it there in-contest and I was thinking "wtf why did nobody solve this yet". It wasn't super easy, but something like the first or second mid-level problem and the organisers said they were disappointed so few teams solved it.

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

    Arguably, parsing the statement of the problem and understanding it is part of solving the problem. Or rather I should say realizing that a problem is easy is part of the difficulty of the problem.

    → Reply
»
6 years ago, # |
  Vote: I like it +12 Vote: I do not like it

It is a great innovation for me! Now I can try to solve problems whose difficulties is around my current ratings so as to improve myself more efficiently. Thanks Codeforces!

Besides, I suggests that difficulty ratings are also shown on the dashboard of previous contests. It will be more convenient for me to solve problems.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

Epic! i would suggest to show difficulties in problems statement beneath the problem tags , Thank you MikeMirzayanov

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +8 Vote: I do not like it

Thanks for the awesome feature.

I suggest problem difficulty should be displayed on contest page such as this after contest.

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Really helpful , thanks

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +40 Vote: I do not like it

Very cool!

One question: consider a problem from a 5h ACM contest; if I have a rating 2500 and the problem has 2500, does it mean that I (my team?) would have had a probability 0.5 to solve it during a "typical" 2h individual CF contest, or during a "typical" 5h ACM team contest?

→ Reply
»
6 years ago, # |
← Rev. 7   Vote: I like it 0 Vote: I do not like it

Thank you for the great feature, MikeMirzayanov!

If I may suggest, it might be a good idea to add a parameter for rating deviation, as in the Glicko rating system. This would provide credibility to the rating of the problem, and distinguish ratings of new problems with few solvers from ratings of older ones.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The difficulty should be visible also on the problem page like the tags

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Great news! Small question: is there any bias in difficulty for D and E problems just because they're 4th and 5th among all the contest problems? For instance, problem D may have 2500 instead of real 1800 just because problem C from its contest is a long implementation problem and participants had not enough time after it to solve D.

→ Reply
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Thank you for this system, but, unfortunately, sometimes rating of tasks very strange and has big error

→ Reply
»
6 years ago, # |
  Vote: I like it +8 Vote: I do not like it

Congratulations to Codeforces team for this excellent job.

I'm curious, did you based the work on this, also amazing, blog post? If so, what modifications did you apply? How do you handle things like div2E problems that no one solved during the competition?

→ Reply
»
6 years ago, # |
  Vote: I like it +40 Vote: I do not like it

MikeMirzayanov I always wanted to say this, but could not think of where to say this. So, this maybe the right place. Codeforces has a hell lot of amazing tutorials. I have been benefitted a lot by reading them. But the problem is they are buried somewhere in the thousands of blog posts already on codeforces. There are some tutorials on topics that I don't even know exist. I don't know that codeforces has tutorial blogs on those topics. I usually come across them when I see them see in the recent actions section when someone comments on those blog posts. As I am not on a great level in terms of my ratings, there are many topics that I don't know of like segment tree beats, Berlekamp-Massey and so on. Also, there are a lot of tutorials on common topics but they way they have been explained in codeforces blog make them a lot more practical and helpful than other resources or tutorials on the internet like I would never have known that ternary search can be coded in a way similar to the binary search as explained here and also the blogs on maths topics like the mobius function and blog posts on geometry and other stuff.

But again, the problem is I don't know many of them exist but when I find them, they are a treat to read. I believe that there are many other people who have been and will be benefitted by the tutorials available on codeforces.

There have been some blog posts that have tried to collect the available tutorials but they include only a handful of these. So, it would be amazing if a separate section can be created on top for the tutorials that are available on codeforces in which one can see the topics and the tutorial blog posts on them that are available on codeforces.

I know it's a lot of work but maybe the community can help somehow by proposing the available tutorial blog posts to be added to the section.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

that's great it's very helpful

→ Reply
»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

Realy good development.We can learn about the difficult and we don't need to search question anymore.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

deleted

→ Reply
»
6 years ago, # |
  Vote: I like it +2 Vote: I do not like it

There is every reason to say codeforces is the best, I just love it. Thanks MikeMirzayanov

→ Reply
»
6 years ago, # |
  Vote: I like it -40 Vote: I do not like it

There is a issue, what if in a contest somebody accepts a problem with their second account, that way it wouldn't be accurate

→ Reply
  • »
    »
    6 years ago, # ^ |
      Vote: I like it -14 Vote: I do not like it

    No one has second account.(in ideal) :))

    → Reply
»
6 years ago, # |
  Vote: I like it +54 Vote: I do not like it

Thanks for a new feature — looks interesting!

Is there any reason why all the numbers are rounded to 100? Is there anything bad in scale with smaller jumps (maybe even unit jumps, like we have for rating itself).

Could you please share code used to calculate this rating? At least its algorithmic part. I can think of more than one model which can be used to get such approximation, so I'm curious what exactly stays behind it.

Also, are there any pitfalls/issues that we are already aware of? Some things that I am already suspicious about are how various kinds of contests are handled (i.e. individual/team events, longer rounds etc. — same non-trivial problem will often be much more solvable in 3h round compared to 2h round) and how rating inflation is handled (I guess for contests from 2010-2012 the score that you get from those ratings will be somewhat misleading because back then even 2200+ was a big deal — but I didn't go through old problems and their ratings thoughtfully to see if there is anything suspicious).

→ Reply
»
6 years ago, # |
  Vote: I like it -7 Vote: I do not like it

why watermelon problem has 1200 difficulty. I think this problem have a high difficulty.(It is easy problem i think)

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

    I don't know why but I have already seen some interesting difficulties on some easy problems too. The accuracy of those ratings might be improved by taking the AC ratios into consideration.

    Also, since it had been a long time, it is possible to see some awkward difficulties on old problems, because the ratings and some ideas have been changed.

    → Reply
»
6 years ago, # |
  Vote: I like it +22 Vote: I do not like it

Is there any way we can see the problem ratings from the problem or contest page itself? Right now, it seems to only be the problemset page, which makes it hard to find for the rating of a particular problem (I guess one workaround right now is try to make a mashup).

→ Reply
»
6 years ago, # |
  Vote: I like it +33 Vote: I do not like it

1A(Theatre Square)'s difficulty is 1300? I think it could be lower.

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it 0 Vote: I do not like it

I'm really wondering about the formula . After playing around with it a bit, I've found that the probabilities it gives seem more extreme (closer to 0 or 1; farther from 0.5) than I would believe once you consider that Codeforces contests only have partial feedback (like pretest and systest phase). While I do understand where the formula came from, I feel that the definition of it being the probability that one would solve it in contest isn't really precise; maybe it would be something more like the probability that one would solve it in a contest with full feedback?

→ Reply
»
6 years ago, # |
  Vote: I like it +25 Vote: I do not like it

Is there any way to hide/turn off the scores displayed? Like tags, it gives the extra information that can make you think a certain way/alter the problem solving process in a way that could be undesirable.

→ Reply
»
6 years ago, # |
  Vote: I like it +6 Vote: I do not like it

Is it also possible to show the rating of the problem in the problem page? I think it would be great! Thanks :)

→ Reply
»
6 years ago, # |
  Vote: I like it +1 Vote: I do not like it

How about adding other tags?

→ Reply
»
6 years ago, # |
  Vote: I like it +14 Vote: I do not like it

Why not add the difficulty in the tag? It seems that the difficulty can only be seen at Problemset page.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Yeah.

→ Reply
»
6 years ago, # |
  Vote: I like it +11 Vote: I do not like it

Please, add also difficulty of the problem to the problem page.

Because now we can see difficulties on the Problemset page, but cannot see at the single problem page. And it's required to visit problemset page, try to find this task to see rating

→ Reply
»
6 years ago, # |
  Vote: I like it -11 Vote: I do not like it

codeforces is the best website for coding.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Very nice new stuff comming to CF, I stopped practicing 2 years ago after my ACMICPC run came to an end, however now I can practice and learn new stuff for future contests on CF, and coaching new teams, feels good man!!!!

→ Reply
»
6 years ago, # |
  Vote: I like it +4 Vote: I do not like it

Thanks for the awesome feature.. I have one suggestion or request.. Please give an option to just see problem rating in tags instead of showing both rating and topics in tags. I want to see rating but not topics..

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

    Also it would be nice if difficulty can be viewed in contest's problems page to see the difficulty of all contest problems without having to check each problem separately.

    → Reply
»
6 years ago, # |
  Vote: I like it +3 Vote: I do not like it

When will problem difficulty score be added to codeforces API?

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +25 Vote: I do not like it

MikeMirzayanov Its possible separate tags with difficulty? I want to see the difficulty of problems, but don't see tags.

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

    Go to your profile Select Settings Scroll Down and in between multiple options, you will find Show tags for unsolved problems. uncheck it and no tags will be shown.

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

      Yeah, I know, but I want to see the rating of problems.

      → Reply
      • »
        »
        »
        »
        6 years ago, # ^ |
          Vote: I like it +1 Vote: I do not like it

        I am actually able to see the ratings of problems even after disabling it. Can someone tell me how to insert an image in the comment ?

        → Reply
»
6 years ago, # |
  Vote: I like it +15 Vote: I do not like it

Thats the best thing Codeforces has ever done, now there is no need of SPOJ to practice specific types of problem.

Thanks, team Codeforces.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The pop-up feature of judgement verdicts is not working in my browser. What can be the reason and how does it look like? I still have to press F5 continuously.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Will there be such things for sgu problems too?

Or maybe tags at least??

→ Reply
»
6 years ago, # |
← Rev. 2   Vote: I like it +11 Vote: I do not like it

How long after contests should we expect to wait for difficulties to come out? I'm asking because the ones for the two previous contests (here and here) have not been updated.

UPD: Thanks, they have been updated now.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Hi MikeMirzayanov thanks for all the hard work you are putting into codeforces... Thanks to your hard work, Now we can filter problems according to their points and inclusively e.g (1800-2300) with tag.. Is it possible to add a feature to filter problems by the number of user who solved that problem inclusively for example (1200-2200 here i meant that the problem is solved by >= 1200 and <= 2200 users)... We can sort ascending or descendingly by user count... But it might be quite helpful if this feature of filtering problem is added... Just a personal point of view..

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can somebody explain why 1071C - Triple Flips has 2900 rating and 1071D - Familiar Operations has 2700, despite the fact that the first was solved by 40 persons, while the second by 20 during the contest?

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

ahmed_aly any consideration to add this to the CF ladders on A2OJ? The current difficulty measure scale of Div2C — 4, Div2D — 5, Div2E — 6, isn't always that accurate. For example, I'm currently doing the Div2E ladder, and there was a problem labeled level 6 difficulty that was pretty easy (had 1800 CF rating) and a problem labeled level 4 difficulty that wasn't super easy (had 2100 CF rating).

If you don't think it's worth doing, that's fine. I love A2OJ a lot right now, so it's just a suggestion.

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

pop-ups about judgment verdicts of our submissions have stopped working (since the DDOS attack I guess). Is it just me or others are facing the same issue? Please fix it. It was a cool update. Thanks

→ Reply
»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Is it possible to sort problems in favourites section by their difficulties ?

→ Reply
»
6 years ago, # |
  Vote: I like it +19 Vote: I do not like it

UPD: (API update) Optional field rating has been added to the object Problem in API.

===

UPD: Добавил в API опциональное поле rating к объекту Problem.

→ Reply
»
5 years ago, # |
  Vote: I like it +13 Vote: I do not like it

First, I have to say this is an incredibly useful feature that does help me a lot in practicing. With that being said, I'm curious why it sometimes takes quite a long time to add problem difficulties for some contests. For example, it's been more than 2 weeks since Codeforces Round #599 but none of the problems is updated yet.

→ Reply
»
4 years ago, # |
  Vote: I like it +5 Vote: I do not like it

In some problem why i get less rating than a friend of mine for same problem submission and the problem is correct in one chance?

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

Can we have something like similar problems suggestion for each problem, which will be decided by votes ? I usually struggle with finding problems in a specific field, like solely segment tree or abusing STL data structures as they all share the tag "data structures".

→ Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

This problem has difficulty only 2700 but nobody solved it during the contest

549E - Sasha Circle

→ Reply