Блог пользователя tem_shett

Автор tem_shett, история, 4 года назад, По-русски

There was a problem 1400E - Очистите мультимножество in Educational Codeforces Round 94 (рейтинговый для Див. 2) (yesterday's contest) and it got difficulty 2200.

Why is it strange? It wouldn't be, IF...

Get look at this 448C - Про покраску забора. Yeah, these problems are same! In fact, even editorials for them are same.

As you've already guessed difficulties are different. Actually 448C - Про покраску забора got only 1900!

It looks like that such a huge difference is a result of their positions in problemset (E and C exactly).

Of course, this situation is rare enough to be a huge problem. But more tasks more similar situations. Anyway for now it's just a strange fact.

Also I want to thank sevlll777 as a person who found 448C - Про покраску забора.

What do you think about this?

  • Проголосовать: нравится
  • +102
  • Проголосовать: не нравится

»
4 года назад, # |
  Проголосовать: нравится +14 Проголосовать: не нравится

Really strange, yeah

»
4 года назад, # |
  Проголосовать: нравится +6 Проголосовать: не нравится

Auto comment: topic has been translated by tem_shett (original revision, translated revision, compare)

»
4 года назад, # |
  Проголосовать: нравится +24 Проголосовать: не нравится

Yes, it is clear that C will try to solve more people than E, and they will have more time to do it. In any case, it's a pretty cool fact, but it seems even funnier to me that the author originally made an English text with Russian names of tasks. I in no way want to humiliate the author, I also had similar failures, it's just really funny :)

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +11 Проголосовать: не нравится

    Yeah, the article firstly had only russian version, because I use russian version of codeforces. But it also strange that problems included by id don't translated to english with english version of cf. Maybe it need to be fixed. MikeMirzayanov

»
4 года назад, # |
Rev. 2   Проголосовать: нравится +55 Проголосовать: не нравится

Many problems with later positions have a very high difficulty despite not being very hard. 571D - Campus has 3100 but is quite easy. However getting it right in 2 hours together with all the previous problems is very hard, indeed there are I think 4 ACs during the contest.

They are just artifacts of the way the difficulty system works.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится -145 Проголосовать: не нравится

    Pleassse, don't say "easy" about problems. For you maybe it quite easy, but for many others not. Just say "easier than it's difficulty says".

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +73 Проголосовать: не нравится

      I didn't say "easy", I said "quite easy". And I think the meaning of "easy" was obvious from the context.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    It is same problem as described below. See rating the top users are 2600-2760. So 3100 is extrapolation error.

»
4 года назад, # |
Rev. 3   Проголосовать: нравится +18 Проголосовать: не нравится

It is rating inflation. When 448C take place Div.1 started from 1700. So 1700 was rating for top users from div.2. See rating change. And if you calculate rating for task.  you will see that rating calculated correct based on CF formula. But it has limitation based on user rating in competition.

So it's calculated correct but not relevant to nowaday.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +14 Проголосовать: не нравится

    So you want to say, that old problems are harder the new with similar difficulty?

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +16 Проголосовать: не нравится

      old problems at the top of div2 yes. For other rating it require more research.

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится +8 Проголосовать: не нравится

      The correct answer is. When task rating is higher than rating of people in competition than it calculated incorrect (CF formula is bad for extrapolation). All we know is 448C was too hard for 1700 and 1400E is near ok for 2100.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

I'm pretty sure ratings are completely based on the # of people who solve the problem during the contest, so later problems are usually more inflated as most people start from the beginning, leaving less time for the end problems.

»
4 года назад, # |
  Проголосовать: нравится +11 Проголосовать: не нравится

One thing I want to add here. Apart from one being C and the other being E, the problem E version has $$$a_i = 0$$$. My submission 90938786 passed the tests during the contest (where I did not handle the case). But after system testing, it got Wrong Answer. I guess many other contestants did similar mistake. That might have contributed a bit to the rating of this problem.

»
4 года назад, # |
  Проголосовать: нравится -7 Проголосовать: не нравится

There are also some other weird things also about problem rating.1400D - Zigzags from educational round 94 has difficulty of 1900. So, if an expert solves 4 problems in time, he should obviously get positive rating change. Isn't it? But, there are experts who solved 4 problems and got negative rating change. Why?

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    Task rating 1900 is after ceiling. Task D rating without ceiling is ~1821 (according to my calculation). Rating to solve 4 tasks (with maximum penalty) without rating change is 1786 (you can check it here).

    • »
      »
      »
      4 года назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      Then, isn't D worth of 1786 at most. Maybe it's less. Cause there are participants who solved D but couldn't manage to solve 4 problems. Then, D would be at max 1800. Isn't it?

      • »
        »
        »
        »
        4 года назад, # ^ |
          Проголосовать: нравится +16 Проголосовать: не нравится

        No if those participants have rating less than 1786. There are many participant with rating <1700 who solved D but not solved B.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

this problem is the harder version of the 448C problem (ai = 0) XD

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Maybe at that time,everyone has a lower rating than now. So the difficulty is calculated lower.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    U mean at that time problems with same rating as of now is tougher compared to now ??

    • »
      »
      »
      4 года назад, # ^ |
      Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

      I don't think so. In fact, sometimes I observe that some old (say from round 200 to 400) contest problems are overrated. (In fact, I just solved 899E - Segments Removal which is 2000 rated which took me less than 10 minutes to think and around 20 minutes to code which is definitely much faster than I do recent 2000 rated problems.)

      I also think that gaining rate now is as tough (if not tougher) as ever. This observation is based on the virtuals I have given.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Although the solution to both the problems are same but reducing 1400E to 448C is not straight-forward, I'm still not sure how can I prove that both the problems are basically same.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    You can just submit your code of any of that problems to another. And it will pass, so they're equal.

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +16 Проголосовать: не нравится

    Proof By AC:).

  • »
    »
    4 года назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    First note that in 1400E, the order in which operations are performed is irrelevant. Give disjoint and nested the obvious meaning for type-1 operations (those that remove one occurrence of each number from $$$l$$$ to $$$r$$$).

    Given two type-1 operations $$$(l_1,\, r_1)$$$ and $$$(l_2,\, r_2)$$$, if they are not disjoint then the pair of operations $$$(\min{\{l_1, l_2\}},\, \max{\{r_1, r_2\}})$$$ and $$$(\max{\{l_1, l_2\}},\, \min{\{r_1, r_2\}})$$$ is equivalent, but is nested. By repeatedly making such substitutions for many pairs of type-1 operations, it is possible to arrive at a sequence of operations in which every pair of type-1 operations is either disjoint or nested.

    Given such a sequence, it is easy to see that the nesting relationship allows one to describe the type-1 operations as several rooted trees. Then, we can translate a type-1 operation $$$(l,r)$$$ at depth $$$d$$$ in its tree in 1400E-speak to "paint a horizontal strip covering planks $$$l$$$ through $$$r$$$ between height $$$d-1$$$ and $$$d$$$" in 448C-speak. A type-2 operation $$$(i, x)$$$ gets translated to "paint a vertical strip covering the highest $$$x$$$ meters of plank $$$i$$$ that are not already painted."

    The reduction of 448C to 1400E should be easy using similar ideas.

»
4 года назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

This is certainly due to their position in the problemset, many people would not have had the time to solve it and some might not have even opened it because it is "E" and not "C".

My opinion about problem ratings: These are calculated based on the rating of participants, since nowadays participation is more than ever, so codeforces has more data to process and to calculate problem ratings. Since larger is the data more is the accuracy, so i think nowadays calculation of problem ratings is much more accurate.

»
4 года назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

Thinking a lot about this now

»
4 года назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Problems on Codeforces are rating-inflated.