vkgainz's blog

By vkgainz, history, 4 years ago, In English

Hi Everyone,

Pardon me if this is the wrong place to post; I'm new with blogs and all, but felt like I could probably put it here.

I know there are lots of CF predictors out there that give you your expected delta based on your rank and seed in the contest. Has anyone made a predictor that would tell you what rank you would need to gain a certain delta?

Basically, is there any app that lets me input the participants of a contest to get my seed and a given delta value and outputs a predicted rank? For example, if I wanted +50 delta on the next contest, I could put those two parameters in and it would give me the expected rank I need to get that in contest (around ~400 or something).

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

»
4 years ago, # |
  Vote: I like it +1 Vote: I do not like it

i think you can do it with cf_viz site. it doesnt have the expected rank to get such delta but you can do simple binary search to find it. XD

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

    In cf_viz they ask for points in contest. Can you please tell me where I can points earned in a vc ?

»
4 years ago, # |
  Vote: I like it +21 Vote: I do not like it

It depends on number of participants in the contest. So it can not be predicted.

Participants are those who have made at-least one submission during the contest. All registrants are not participant.

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

    Yeah, fair enough. I'm wondering if it's feasible to try to make a prediction based on a bunch of past rounds' results -- given the official results for lets say, 100 past rounds of a Div 2 or something, map the seeds to the ranks to the deltas and use that to create a model that would let you predict a similar thing for next round. I guess it will have to assume that the rating distribution of competitors doesn't change too much round to round, but since there are so many, that shouldn't be too much of a problem.

    It would be interesting to maybe implement this. Unfortunately, I don't really know any ML to actually implement this.

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

A tangentially related question: is anyone aware of a tool that reports your performance rating for CF rounds (i.e., the rating at which you would gain or lose no points for your performance)? Ideally, this would look like an extra column on the standings page indicating each rank’s performance (much like how many rating predictor extensions add a delta column to the standings). This seems relatively easy to implement (just take a virtual competition rating predictor, then throw in a binary search), but as of yet I’m not aware of any tool that provides these predictions accurately.

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

    If you use any userscripts extension (e.g. tampermonkey), awoo wrote this simple script: https://pastebin.com/XPB6ipyv

    It uses the heuristic performance = oldRating + 4 * delta.

    It ends up looking like this:

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

      Thanks for sharing that script! That's a good workaround, but I'm curious whether any more precise tools exist, since this performance heuristic can be fairly inaccurate at times, especially in cases involving large rating changes. It seems like this would be relatively easy to implement, given the existence of virtual contest rating change calculators, so I'm surprised that I haven't been able to find a tool like this yet.

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

        I think the reason it hasn't been implemented is due to the amount of data you need to deal with.

        Manually calculating your performance for a certain contest isn't too hard (just binary search with cfviz), so I don't see the need for that.

        In order to calculate performance for large number of contests (all contests a user participated in, for example), such a tool would need to:

        1. Download the data for each contest
        2. Calculate the data for each contest

        A third option is to have cfviz calculate it, but cfviz just does the same thing as listed above.

        This would be extremely slow and you'd have to deal with (possibly) 100x more data than a regular rating predictor has to deal with. Caching the data for each contest also doesn't seem viable, as you'd probably need a few hundered megabytes to do so. There are obviously other workarounds, but in general they are rather time and memeory inefficient.

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

          I don't see why this is inherently unworkable--one very intuitive way to avoid these recalculations is to compute performances after every contest, then store the results in a database and have the extension pull the data from said database. This requires relatively little storage space (and virtually none on the user's end), and querying the database can be handled very quickly.

          Obviously, this may make implementation somewhat more difficult, but I do think it's fair to say that such an extension is possible and could theoretically be implemented efficiently.

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
            Rev. 3   Vote: I like it 0 Vote: I do not like it

            Won't it be better to avoid storage on server side, and just store the information in cookies? It's still virtually nothing on user's end

            Do you need other participants' data for calculations too, in that case this won't work

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

            To be fair, this is a lot of work for a tool that just calculates performance (which is not something that is in high-demand, unlike rating calculators). Thus, I wouldn't be surprised that I haven't been able to find a tool like this yet.

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

        I don't remember the details, but I think I heard an exact computation is the same but with a quadratic term of delta added.

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

          Yes, it's $$$c + 4d + \frac{4d^2}{c}$$$. You would need a truly big delta for $$$c+4d$$$ to be significantly inaccurate...

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

            How is this formula accurate? In Codeforces Round 673 (Div. 1), my rank was 639, rating change 2010 -> 2004. Contestant with rank 643 had 1905 -> 1928. Acc. to this formula my performance was worse than him but I ranked better.

            • »
              »
              »
              »
              »
              »
              »
              3 years ago, # ^ |
              Rev. 7   Vote: I like it +1 Vote: I do not like it

              Good point, there's still one detail. There is a correction step to make sum of deltas zero (or slightly non-positive), and you cannot predict this correction step without knowing ranks of all participants, so the performances are going to be a few points off. This correction is a constant added to all deltas in the round.

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

              OK, so upon further thinking I realized there's a mistake in my earlier reasoning: rating update formulas are based on expected ranks, not on ratings.

              Usually you can expect both to be very closely related -- someone with higher rating is going to be expected to have a lower rank. But how good is the approximation? I checked Codeforces Round #658 (Div. 1) to have an idea:

              From this, looks like contestRating + 4*delta is a very accurate approximation when abs(delta) < 50, a slightly less accurate approximation when delta > 50, and potentially a very bad approximation when delta < -50. So there would be value in having the exact performance values for those extreme cases.

              (Computing exact performances for this contest took some time, so providing exact data for all contests would be impractical without a database of some sort, like Geothermal suggested.)

              EDIT: I helped meooow port the code I used to calculate performances above to his extension Carrot, now you can see performances in the ranklist for past contests!

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

    Hi, I have added a performance column to Carrot.

    It's not perfect, but it's very close (0-4 more than the exact value). However this is for older contests, for contests after the new rating system was put in place rating prediction and performance calculation both deviate.