It's because high-level chess games often end in draws, whereas tourist usually wins even against high-level contestants.

I updated the ratings today: click here! Elo-MMR seems pretty stable, with the peak ratings still nowhere near 4000.

It's useful to treat most contests as practice, but it sounds like you need a break. You don't have to compete at all if what you enjoy is solving problems slowly. That's probably more useful in real life applications anyway.

I think you can use either of the two Scanners from https://github.com/EbTech/rust-algorithms/blob/master/src/scanner.rs for input, and regular println! for output.

Or you can do it exactly as in this post, using flush() after an interactive round of outputs. Let me know if it doesn't work!

The I/O in my codebook reads and writes only one line at a time, so I think it'll handle interactive problems. Did you try it that way? It's important for the output to flush after every line, which println! will do for you.

The admins are already looking at these cases of mismatched Divisions. A cap or similar fix might be coming.

Hey all, I should point out that we're seeing not only differences between the two ratings systems, but also differences in the settings of their parameters.

A high starting $$$\sigma$$$ parameter is what enables new players' ratings to change so fast. Topcoder does this too. Usually these changes are manageable; the edge case of users reaching ridiculous ratings after only competing in Div 3, occurred because their division placement was based on a different system (the old one). In other words, the user competed in Div 3 when really, according to the new system, they should already be in Div 1. Now that the migration is done, this will never happen again.

Another change is that the update weight parameter was decreased, because the admins want ratings to be a more reliable indicator of long-term performance. If you feel that your recent hot streak has been erased, don't fret. Elo-MMR will magnify your next few wins in support of your streak. This momentum effect allows stability to coexist with faster updates when a true jump in skill occurs. For example, you can see ksun48's's new ratings accelerate in the last half of 2020, converging almost as fast as the old ratings. (With a higher update weight, Elo-MMR can converge even faster.)

The system has memory so, if you perform at that level a second time in the near future, you'll see a similar or maybe even bigger increase.

Care to elaborate?

What DMOJ did seems fine to me. We sketched a fancier migration plan which might be optimal in terms of user experience, but is a bit annoying to maintain! The idea is as to keep two databases in the backend:

1. The user-visible ratings which are initialized as-is, but with some $$$\sigma$$$ value so that they can be interpreted as Elo-MMR ratings.

2. The hidden ratings which are retroactively computed with Elo-MMR.

From then on, both databases will receive Elo-MMR updates simultaneously. The trick is that your new performance computations in both databases 1 and 2 will be based on only database 2 ratings. Since ratings are basically weighted averages of past performances, a player's two ratings will converge to each other after enough rounds.

Unlike the simpler smoothing, this method ensures that your rating goes up (down) when you perform above (below) your rating. On the other hand, you now have two full-fledged Elo-MMR databases that interact.

That would complicate the user interface. For the majority of users, the new rating will be slightly higher, so it's worthwhile to compete to get your new rating. If the admins wish to do so, it's still possible to instantly converge the ratings of inactive users after a year.

We'd have to study the bumps more carefully before making an informed decision. For example, the bumps at 900 and 1000 might simply be due to the starting rating. CodeChef used to give players a starting rating of 1500, but in February changed it to 1000. In the Elo-MMR chart, we started newcomers at $$$\mu=1600,\ \sigma=280$$$, but changed this to $$$\mu=1500$$$ on the same date as CodeChef's change. Since $$$\sigma$$$ is set to asymptotically converge to $$$80$$$, this means a player's starting rating after applying a 3-sigma penalty is one of:

The Glicko rating system implemented your idea of a time-based decay by gradually increasing $\sigma$. This technique extends naturally to Elo-MMR if you want, though we're not doing it here.

A couple of smaller organizations (outside of sport programming) expressed an intent to do so, but let's wait and see!

Ah yes thank you!

Auto comment: topic has been updated by EbTech (previous revision, new revision, compare).

If you just want to know if the current line has more tokens, you can check the buffer's status. I didn't implement this, but you can derive it from any of the existing Scanner implementations.

However, checking whether there's a next line might stall if stdin is waiting for the user to type something.

While I haven't studied this scientifically, my experience on Codeforces suggests that "natural" Rust code (meaning, without crazy/unsafe low-level optimizations) is about equally likely to be faster or slower than natural C++, so that overall it's about as competitive as C++. Some of the standard library algorithms (like sort_unstable) and data structures (sets and maps) are really fast!

The only bit of unsafe I actually use in contests is my I/O Scanner: I don't trust myself to write new unsafe code under time pressure.

ekzhang also contributed a random number generator to rust-algorithms!

Maybe the deadline should be something like 2 mins after the contest starts? Hardly anyone would be able to determine whether they can solve F in that much time... though some people might decide to skip a contest whose statements look "too wordy".

It started as a fun project a few years ago, out of a curiosity to see whether good theoretical foundations would solve some of the issues with programming contest rating systems. The more recent work was undertaken to turn that project into an academic publication. Hope this helps!

The Codeforces system is monotonic: https://codeforces.me/blog/entry/20762

Although I think Elo-MMR produces nicer ratings, both systems are free from such exploits! Glicko-1 should also be monotonic I think, though I haven't verified it.

If it uses Glicko-2 then I suspect the same exploit will work. The trick is to massively inflate your volatility by alternating between losing and winning.

Looks like we independently went after some of the same problems: https://arxiv.org/abs/2101.00400 (on Codeforces history, the distribution looks like this)

Do you plan to publish yours soon? I'm curious.

That's an interesting question! To rate problems, I suggest using the algorithm from the Performance Estimation section. In other words, consider the problem to "win" against a contestant if that contestant doesn't solve it.

This works best if the problem was used in a rated contest; it's harder to apply in ICPC. Furthermore, whether a problem gets solved or not seems to be affected by what other problems come before it, so ideally we should find some way to adjust for those.

Update: you'll find it at www2021.thewebconf.org soon!

The Codeforces stats and ratings list are already updated! The repo also allows you to compute all the ratings yourself if you like. Please note that the algorithm has been tweaked slightly from the first version of this blog post.

There will be more in the coming weeks and months! We're working on getting it into a conference, and I'll be sure to blog about it too. In the meantime, I'm available to help if anyone wants to try something with the code.

Jan 2021 update!

There's more I'd like to say about the Elo-R (now named Elo-MMR) system. I teamed up with inutard to write this publication. It contains experiments showing better accuracy than competing systems, and an optimization which makes it faster too (at a small cost to precision).

Based on the results in the TrueSkill-SPb paper you mention, it's likely that TrueSkill-SPb can be made to perform very well if implemented and tuned optimally. I don't have access to such an implementation, but if anyone would like to help, the codebase is open-source. I'd love to get a fair comparison! In the meantime, I'd like to point out two advantages of Elo-R:

• Due to its simplicity, I can rigorously prove properties such as monotonicity (so the player's incentive is always to win), robustness (bounds on maximum rating change), and runtime (I haven't seen any proofs on how many iterations TrueSkill requires).

• Elo-R can handle a variety of log-concave performance distributions, and has been tested for Gaussians and logistics. In principle, TrueSkill should be able to do so as well, but we'll have to wait for a logistic implementation to see how its speed and accuracy compares. One issue is that, when performances are non-Gaussian, the posterior can be rather complex. Elo-R tracks a more complex posterior in order to retain more information.

Elo-R lacks a realistic tie model, though I would argue the same is true of the alternatives. With Elo-R, we have two approaches: 1) take the limit as $$$\epsilon\rightarrow 0$$$, or 2) treat it as half-win half-loss, as Codeforces does. I haven't thought much about team models yet, though it would be a useful extension if done right!

No, I don't consider 20 close to infinite. It's an exceptional case where the algorithm still seems to behave reasonably, but I think it overweights the evidence a bit. For similar reasons, the evidence is overweighted for the top and bottom players. As I said, we'll eventually have to study how much damage this assumption makes, and whether some bias-correction is needed. Same with any exogenous or endogenous model for ties (mine isn't perfect either).

Ok you're being a bit unclear (or is it the paper?), since you said earlier that true posteriors are ugly non-Gaussians. Arguably, minimizing KL after each round is a more rigorous approximation, but we wouldn't call it exact inference. Still, I'm very interested if it's possible, in the logistic case and with reasonable complexity in terms of $$$\epsilon$$$, to compute the posterior that minimizes KL to the truth!

P.S. my dataset is updated if you'd like to run your code again. It also auto-fetches new data if you add the contests to contest_ids.json. Since both systems are based on similar Bayesian models, you can probably copy my parameters.

About the same questions again:

• Ok so although the paper chooses not to get such high precision, you're saying that it's possible using methods in the references. Would you somehow still get a Gaussian end result, or does it become necessary to store more complicated distributions?

• I understood how teams (or individuals) are split into segments of length $$$2\epsilon$$$, but there is often more than one way to do so. You can choose to make AB tied and CD tied, or you can make BC tied but put A and D into their own bands. And the band itself has some room to shift. If we view the round standings as an observation that the bands ended up a certain way, what's the likelihood?

In summary, it sounds to me like yes indeed arbitrarily precise computations are possible, and doing so would involve factor graphs, but that method is a bit more involved than what TrueSkill does. You'd have to endogenize the tie model to better match Codeforces (a nontrivial extension), and represent complicated non-Gaussian distributions.

Essentially, I'm arguing that both systems take some small shortcuts to make the math tractable. Elo-R (with Gaussians and no ties) can be thought of as an exact inference algorithm in the case where the number of contestants is practically infinite. I think this is actually pretty close to the truth on Codeforces. You can still draw the same factor graphs, but the result simplifies in the limit.

Yeah, $$$\epsilon$$$ being constant is exactly the assumption I'm talking about. On Codeforces, I might argue this is violated more severely than the assumption of highly populated rounds, though I don't know how much it matters in practice.

What's your concern about convergence? Both algorithms are Bayesian, so if the priors and assumptions were correct, they should produce the Bayesian "best possible ratings" at all times.

As for human-interpretability, I think the formulas on page 8 are pretty meaningful even without the Bayesian theory that was used to derive them. I provided my intuitions earlier in the paper. They may be a useful fallback if you don't fully believe the model.

A few questions about SPb TrueSkill:

• Are you saying the formulas are all exact? Page 4 contains the phrase "approximating the result with a normal distribution", suggesting that some intermediate results don't have a nice form.

• How exactly are the unobserved latents $$$l_i$$$ modelled probabilistically? It seems to me that the ratings $$$t_i$$$ don't fully determine which players are tied, so I didn't quite catch how the paper makes a Bayesian model of that.

Hey, sorry for the delay! To continue our discussion, most of the Elo-R system's approximations exist to deal with logistic distributions, whose heavier tails I preferred. If we instead use Gaussians, then Elo-R also comes close to being "mathematically perfect" in the Bayesian sense.

I believe our systems can compared by their respective modelling assumption: TrueSkill+ has a specific $$$\epsilon$$$-parametrized model for ties, whereas Elo-R assumes that individual rounds have a very large number of players. It remains to be seen just how much damage is done when either of these assumptions fails. We also found that Elo-R has simpler human-interpretable formulas, while on the other hand TrueSkill+ computations are an order of magnitude faster.

Hey I saw your new blog post, great work! Sorry that I haven't had much chance to examine your code or engage in the discussion. I moved on July 1 and the internet company still hasn't set up WiFi where I live :( so I'll be on and off the grid for just a little while longer...

Cool, it looks like TrueSkill doesn't need to compute the $$$N^2$$$ pairwise win probabilities! You can probably make it even faster using Rayon to parallelize as I did.

Today I reverted my code to use my simplest noising method. While the fancier methods are interesting for a variety of reasons, the simple one is more straightforwardly comparable with the current system on Codeforces.

Basically, it approximates the posterior, which is the most intractable part, by a Gaussian, while still using logistic distributions in other places. This method has no $$$NM$$$ term nor a saved history, so it satisfies the same monotonicity properties as Codeforces. It also results in the simplest versions of my formulas (see page 8 of the paper as of today). The rating distribution might converge more slowly with this method, but it seems to end up in the same place.

Wow 2 minutes! I'd like to see. If each contestant recalls $$$M$$$ rounds of history, then a round with $$$N$$$ contestants should take $$$O(N^2\log\frac{1}{\epsilon} + NM\log^2\frac{1}{\epsilon})$$$ using binary searches, with the log factors reduced if Newton's method is used instead.

The $$$NM$$$ term only applies to certain versions of my "noising step", but the $$$N^2$$$ term seems common to all the programming contest algorithms that compute pairwise win probabilities.

Sure, use whatever you need!

I derive the formulas in the paper: in short, I cheated in a few places to make the formulas tractable. As a result, I have human-interpretable formulas that approximately follow the Bayesian theory. In other words, my system can be interpreted in two ways: the Bayesian way, or as an exponentially weighted average of recent performances with reduced weight on outliers.

I do add noise. The "lower bound" you're seeing is simply the limiting value of $$$\sigma$$$ if the noise and measurement error per contest are constant. Actually, the noising calculation is where I had the toughest time sticking to the Bayesian derivation. In the end, I came up with four methods, each with different pros and cons which I'd be happy to discuss further.

Cool. It's definitely worth doing more tests! The improved TrueSkill from St. Petersburg looks like a good alternative. Nonetheless, I want to reply to your latest points:

• What exactly is your CLT-based argument? Are skills and performances the sum of very small contributions? Top players seem more spread-out than a normal distribution would predict, and all players seem to have more days that are very good or very bad, compared to normal draws. The logistic causes my model to put less weight on these unusual performances. We could try to measure the true distribution.

• The problem with ties is that there is no fixed $$$\epsilon$$$ that works. The most obvious example are the massive ties at $$$0$$$ points, whereas performances drawn from logistic or normal distributions would have no such bias. Maybe that's ok in practice: without human-interpretable formulas, it's hard for me to guess, just as it was hard to foresee problems with the original TrueSkill model of ties.

• In Elo-like systems, rating differences are based on win probabilities, not percentiles. As far as I can tell, TrueSkill doesn't enforce percentiles either: it merely suggests them in the prior, just as Elo-R does.

• Fixing the average rating reduces our control over the inflationary and deflationary forces I mentioned. But now I have a question. It seems to me that fixing the average rating is inconsistent with non-constant $$$\sigma$$$, because users with large $$$\sigma$$$ would gain/lose more points than their opponent loses/gains. Are you saying that TrueSkill manage to have both, and how?

Maybe I should write an explicit comparison with TrueSkill, after studying the Gaussian density filtering algorithm more closely to understand its properties. The models are similar, but I'll point out differences:

• My model uses logistic distributions instead of Gaussians: a major theme of my paper is to look at the implications of this.

• TrueSkill has a model for draws, which I think is inaccurate for programming contests. Elo-R doesn't model draws, but instead treats them as half a win + half a loss, similar to Elo. Actually, if we model draws as nearly-equal performances, the Elo-R math gives a result equivalent to 1 win + 1 loss, but it seemed strange to me to give draws double the weight...

• I appeal to the limit of large numbers of contestants to allow for an efficient and easy computation of performance. As a result, I get formulas that are more Elo-like and human-interpretable. Many properties of Elo-R can be deduced just by looking at the formulas, even without the theoretical model! (The formulas give reasonable results for small numbers of contestants too, although the theory no longer justifies this.)

Mean rating is the average "true rating" among all users, including inactive ones.

My system is most directly inspired by Glicko. It can be made more Elo-like by keeping $$$\sigma$$$ constant, as happens to be the case in my $$$\sigma=100$$$ experiment. In that case, the mean rating stayed very close to $$$1500$$$, drifting $$$11$$$ points off due to the approximations involved. I believe a system which preserves the mean will be inflationary: as Codeforces becomes more popular, it's likely to welcome a lot of weaker members, so we should want the average rating to decrease. Perhaps the top should be allowed to increase very slowly, as the state of the art improves.

I believe Elo-R can be extended to team matches. Thinking about it very briefly, we could compute performance scores for each team, by modeling team performance as a sum or max of random draws for each member (which amounts to one random draw per team, with a different distribution). Then, knowing the team performance, we have to reserve-engineer a measurement of each team member's skill.

For a very simple experiment, I just tried running my algorithm with an initial $$$\sigma$$$ of $$$250$$$ instead of $$$350$$$. This changed the mean true rating of all Codeforces users from $$$1311$$$ (when $$$\sigma=350$$$) to $$$1415$$$ (when $$$\sigma=250$$$). That's a big difference! Most of this seems to be due to the weakest members not having converged, since they participate less. Nonetheless, the top ratings also increased, by 14 to 19 points.

I suspect that two things are happening:

• When new users join, $$$1500$$$ is usually an overestimate of their skill, so they lose more than the system expects, giving everyone else extra rating points. This is an inflationary pressure.

• As users compete more, they usually improve and become better than their rating, so they win more than the system expects, taking away rating points from others. This is a deflationary pressure.

By using a high starting $$$\sigma$$$, we can drastically reduce the first effect, altering the balance between inflation and deflation.

Edit: with $$$\sigma=100$$$ (where it would stay fixed), we get a mean Codeforces rating of $$$1511$$$. The top ratings... are actually less than they were with $$$\sigma=350$$$! I suspect the population hasn't converged yet. A high starting $$$\sigma$$$ accelerates convergence of the population rating distribution by allowing it to spread right away, from Round #1. With low $$$\sigma$$$, my system might become even slower than others since it puts less weight on surprising performances (outliers).

The current CF system might have less inflation due to recent anti-inflationary measures, which I considered to be somewhat of a hack. Compared to the CF system without these measures, Elo-R seems to have less inflation based on looking at the rise of top-rated members over the years... but I admit this is not a rigorous experiment.

I suppose it would be helpful to create a testbed with various rating algorithms, so that we can easily compare them along each of the criteria you mention. I can't spend too much time on this project while working alone, but I might slowly try some of these things. It's open-source if others want to chime in with their own experiments. And since my system has a theoretical framework, we can change its assumptions to better match reality if needed.

Thanks for the discussion and experiment ideas!

FYI, I finally made a decent write-up of my contest rating algorithm (at least the first 8 pages of it): https://github.com/EbTech/EloR/blob/master/paper/EloR.pdf (2021 update: https://arxiv.org/abs/2101.00400)

Here's how everyone on Codeforces ranks according to it, including the performance and rating change of their most recent participation. Max ratings are in parentheses: https://raw.githubusercontent.com/EbTech/EloR/master/data/codeforces/CFratings.txt

The displayed rating is $$$1500 - 2(\sigma - 100)$$$, where $$$\sigma$$$ starts at $$$350$$$ and approaches $$$100$$$ as members become more experienced. So, the displaying rating is initially $$$1000$$$. That's a "penalty" of $$$500$$$, which shrinks to about $$$207.9$$$, $$$120.3$$$, $$$76.6$$$, $$$50.9$$$, $$$34.6$$$, $$$23.8$$$, $$$16.5$$$, $$$11.5$$$, $$$8.1$$$, and $$$5.7$$$ after competing ten times.

My system is a rigorous generalization of Elo/Glicko to the case of large numbers of simultaneous participants. It reduces inflation (but doesn't eliminate it), reduces the influence of new members, limits the size of rating jumps for experienced contestants, and produces (I believe) a more reasonable distribution of ratings (see the table here for a comparison). The math does all this naturally, without special hacks.

As a bonus, I recently optimized the implementation so that the entire history of Codeforces can be simulated on my laptop in 25 minutes. I haven't run many experiments or detailed comparisons, but I'd gladly assist anyone who wants to try!

I made the case for Rust in CP in a previous blog post. Obviously not everyone agrees: it takes a while to learn, and restricts you from doing unsafe things. On the other hand, I feel it expresses one's ideas very naturally, encourages good programming style, and it's surprisingly good at catching most bugs, while making the rest easier to spot! It's efficient, too.

I've probably written more Rust CP code than anyone, so feel free to use some of my more recent code as a template. At the very least, I proved that it's possible to perform at an orange level in Rust. Now let's see if someone can turn it up to red :P

Auto comment: topic has been updated by EbTech (previous revision, new revision, compare).

University of British California: ehnryx davidberard .rem

UBC O(1): keyvankhademi

I increased the thresholds at the top, for symmetry reasons and also to future-proof against the gradual rise at the top!

UPDATE (May 2020): 9 months later, the number of Elo-R IGMs remains the same, 6! I'm sure there will be more as the community gets stronger, but at least there doesn't seem to be rampant inflation. In fact, the mean rating is slowly decreasing. Having said that, it's tough to reliably compare the strengths of past vs present contestants...

Thanks for the paper! My system is a Bayesian approximation as well. Incremental systems are less accurate, but global updates compromise interpretability and consistency: we might not like to retroactively change players' rating histories based on recent contests they didn't participate in!

Elo-R takes advantage of some properties of programming contests to try to get the best of both. Most of my proposed improvements come from making more principled approximations with the logistic distribution, which help with convergence and outliers. Some of the issues noted in the paper have negligible impact on programming contests: for example, we don't have isolated cliques of competitors that only play against each other. Divisions are very large and overlap substantially, so estimates of performance within a round are fairly reliable without retroactive adjustments. However, the system does store many past performance scores per player, instead of just a rating and standard error.

Yep! My contest submissions are a bit abbreviated, but you can find my full Scanners here.

I had to use BufRead because interactive problems need to read line-by-line. Reading from Strings is still possible (see unit tests), meeting the BufRead requirement using either as_bytes or Cursor.

If by "real rating" you mean the center, yes. But since the belief distribution is so wide, we can't say with any confidence that their skill is "really" 1500. Microsoft's TrueSkill does this as well. The high starting sigma allows ratings to converge very quickly in the first few rounds.

Hmm perhaps, but you get more help in interviews, right? I don't know if it's different in India, but it seemed to me that Specialist students in Canada tend to place well in ICPC regionals and get nice internships in the Silicon Valley. Of course, their preparation wouldn't consist solely of contests.

Thanks! I'll have to properly explain Elo-R at a later date, but one modification is that displayed ratings are actually mu - 2*(sigma - sig_limit), where sigma starts at 350 and eventually approaches sig_limit = 80. Thus, unrated players are at 960 instead of 1500, rendering even the lower titles somewhat of an achievement :)

Congrats :D

I suppose I should get to that topic soon! I wrote a paper describing it in the linked repo, but I admit it's not very well-written right now.

UPDATE (May 2020): it's written now, I added the link!

It's easy to downplay the meaningfulness of Expert when Codeforces has so many titles above it, but I think it's important to put things into perspective: it's a skill the vast majority of professionals don't have even at Google, whose interview process is famously (or perhaps infamously, for those who disagree with the practice), contest-like! It's much more common to work on LeetCode or Hackerrank, where the problems are more standard, like something from a textbook rather than a contest. So, cheers to you!

Looks like my unsafe Scanner is now even faster than getchar()!

https://codeforces.me/contest/947/submission/55268770

Thanks for the discussion everyone. It took a while to get to this point, but I think Rust is seriously competitively viable now!!

Hey check this out! By avoiding the Vec<String> allocations, I made it almost as fast as yours! It's ugly though because it has to read line by line, passing around references to a String and a StdinLock. I commented the nicer version which, unfortunately, doesn't compile. Would you care to play against the lifetime checker to see if it can be made to work?

Edit: improved, but with an unsafe operation...

Edit2: and the really unsafe dark arts version! It's as fast as you could ever want, I think, and generic so you can use it with any FromStr type.

I don't know how to profile properly, but my unscientific measurements suggest the Scanner<StdinLock> (maybe even without the lock) is at most twice as slow as FastInput, which is probably good enough!

More data would be nice though.

Thanks. Alright, time to bring this to the attention of the Rust community: https://stackoverflow.com/questions/56449027

Gosh I had never been active on sites like Quora, Reddit, Stackoverflow before...

What I'd like to know is which part of Scanner<StdinLock> makes it slower, and what can we do to get optimal performance while being generic in T: FromStr?

Could it be that read_line reads too little at a time? But it seems wrapping the StdinLock in a BufReader doesn't help much...

Is it the fact that Scanner reads to a String, which must be checked to be valid UTF-8? If so, that's a waste since it seems the source code for parse::<i64>() ends up calling .as_bytes() anyway.

Is it because I'm allocating new Strings for each word and storing them in a Vec? If so, maybe we can use the SplitWhitespace object directly without the allocations.

Is the parse() method itself much slower than your custom digit multiplication? It shouldn't be, since the implementation seems similar, just with a few extra checks for the sign and such.

The Rust version on Codeforces is 1.31, which is exactly the release of 2018 edition!

Just for fun, I re-submitted your solution with my Scanner. It seems to work well enough, though indeed yours is faster: https://codeforces.me/contest/1151/submission/55073106

I got word from Mike, we use: rustc -O -C link-args=/STACK:268435456 --cfg ONLINE_JUDGE %1

The inner loop should only run 300,000 * floor(19/2) * ceil(19/2) = 27 million times, so it's still puzzling that my solution is so slow.

Edit: I figured it out! Unfortunately, it turns out stdout is line-buffered, so it's slow if you print a lot of newlines, such as using println!() or print!("\n").

Here's a passing submission using writeln!()

Are there many other programmers who compete in Rust?

My solution to 1168C seems similar to the editorial, but it times out and I don't know why.

Also, why isn't the i-j-k loop in the official solution n log^2 n?

Edit: locally, my code runs a lot faster if I use -O. What rustc compiler options does Codeforces use?

My Rust solution gets runtime error on the sample, even though it runs fine on my machine. Any idea as to what's going on?

Edit: never mind, I found out what's in common with the solutions failing B: primitive int arrays. Either Array.sort() is really bad at handling primitive ints as bodmas said, or the unwrapping when you cast Integer objects (from Integer.parseInt) to primitive ints is super slow. Wtf Java!

Seems relevant: http://codeforces.me/blog/entry/4827

Conservation of nutella

Nah I started with D, had a bug and eventually gave up to return to ABC. Then made another mistake on E.

Ouch, back to purple the same year I turned red!

Btw I updated the Elo-R ratings to reflect the end of 2015: https://raw.githubusercontent.com/EbTech/EloR/master/CFratings2015.txt (again, not totally precise because I don't know which events were unrated).

It's open source (root: https://github.com/EbTech/EloR) so if anyone plays with it and has questions, observations or suggestions, I'd be interested to hear them.

Have a wonderful 2016!

It's possible you're right; it just seems weird from a psychology angle. Keep in mind there are a lot of pairwise comparisons to be made on Codeforces, so unlikely events can happen. A lot of the similarities are very natural simplifying choices to make (i.e. low entropy). We should check for stylistic consistency with her other submissions; that might "explain away" some of the coincidences.

I'm just having trouble imagining someone with legit skills wanting to do this (especially when you're female so the whole world is watching you as sort of an example); even if it were, the code could have been disguised a lot better.

Edit: I didn't notice that now1 and now2 are unused :/ Damn whyyyyy

If we assume that cheating did take place, what happens next? It looks like you can get away with cheating if you have the skills and take effort to obfuscate the source. Will Demi and others just get better at it? Do many orange/red members already do it??? Deterrence is hard if people with actual skills cheat.

I'd wager coincidence! The programs are small, and it seems highly unlikely for someone in Demi's position to consider cheating. Sadly I also can't offer much towards improving cheat detection.

Edit: a friend of mine thinks the similarity is "clearly not a coincidence". Sigh... how does one reason about the probabilities involved here? Could be a scientific research question. Perhaps the users involved will make a statement, unclear what good that would do. I thought it better to give the benefit of the doubt, but hey at least we're not banning users.

How about the new star EvenImage?

Hm my top 10 list right now differs considerably from the official one...

For now the assumption is we keep the same mappings between colour and title. So the division boundary is 1750, and 2300+ (currently 150 users) are red. Although my system has less inflation, the number of GMs still more than doubled compared to CFratings2013.txt and will continue to increase as site activity grows.

Edit: oh I see what you mean. Yes my focus is on the rating algorithm; titles and colours just help to frame the picture.

I removed round 330 and a few others, but I'll need help to get a complete list of unrated and team events. CFratings.txt now shows 3 alternative sets of title bounds; my preference is the middle one.

For some reason, my automatically mined list has almost 2000 more users than http://codeforces.me/ratings/all/true. If a user changes their handle, do old scoreboards continue to show the old handle?

The scales are not directly comparable. My list has fewer reds, and you are still more than half-way from orange to red.

But actually now that I look more closely, the data shows a significant rating drop on your last contest, whereas real CF data says your last contest went great. The most likely explanation is that my program unfairly penalized you for an unrated contest. Do you remember if that was the case? If I could have the list of all rated events, the issue would be fixed.

Btw this algorithm also does a decent job of outlier reduction. For instance, Swistakk was understandably upset that he lost 140 points last round. My program gave him -57 instead. On the other hand, if you do very poorly (or very well) several times within a short span, the rating change accelerates as these data points cease to be treated as outliers.

You could have formed an M on the left from the boundary between black and white above the legs!

Hi everyone,

I'm currently developing a new Elo-based rating algorithm for large ranked matches such as programming contests, hopefully with a firmer statistical basis. Some goals are: faster convergence, no inflation, reduced sensitivity to unusual performances, and simplicity. The paper writeup is incomplete, but I've made the code available at https://github.com/EbTech/EloR

CFratings.txt contains everyone's Codeforces rating as computed by the algorithm, as well as the performance and delta of your most recent match. I assumed all events except the Educational rounds are rated, since I don't know where to find that information.

Ok I wrote up a draft! I plan to write more in the future, but for now just assume σ₁ < σ₂ and they are global constants.

https://github.com/EbTech/EloR

I conjecture that this system will have better properties than previous ranking-based update algorithms such as currently used by CF and TC.

Right, when σ₁, σ₂ are allowed to vary, my idea is essentially based on Glicko. When they are constant, it's closer to Elo but with a few distinctions:

1) A contestant's rank should not be treated as a sum of independent pairwise matchups. Instead, each p_i is drawn independently.

2) p_i is drawn from a logistic centered at s_i, whose prior is in turn logistic centered at r_i.

These should be sufficient to prevent unduly punishing a single bad round, without resorting to the geometric mean. After all, it's much less surprising to get one bad draw from a logistic distribution, than 100 bad draws from independent normals. And if it's still not enough, we can consider asymmetric distributions for p_i and s_i. Now it remains to derive some fast-computable formulas...

My thoughts parallel those of JohStraat below, though perhaps changing geometric to arithmetic mean is a bit of an overcorrection in terms of punishing bad performances. It seems to me the current rating system is a collection of hacks on Elo, designed to have some desired effect. It works fairly well but has some strange properties: for instance, if the number of contestants changed drastically, the relative meaning of geometric mean would change.

I would rather instead we build a rigorous statistical model. For example, how about we suppose a person's rating r is drawn from a distribution centered at their "true skill" s with variance σ₁². Their performance p in a specific contest is drawn from a distribution centered at s with variance σ₂². Player i beats Player j iff p_i > p_j. Now we should perform a Bayes update, changing each player's rating to the mean of their posterior marginal distribution for s (the prior has s independently drawn for each player from logistic(r, σ₁²)).

Technical issues: the Bayes update may require numerical integration. I believe many of the partial sums can be precomputed and shared, so it should be fast enough. In a basic implementation, σ₁ and σ₂ should be global constants. If we want to get fancier, σ₂ can be a function of certain factors that affect how accurately the contest measures skill; for instance, it makes sense to have σ₂ be inversely proportional to the square root of the contest length. σ₂ might also be higher for contestants who are much too strong or too weak for a given contest's difficulty. σ₁ can be a property of each contestant, subject to Bayes update jointly with r: normally each contest will decrease the uncertainty, so we should also increment σ₁² by a constant amount to account for the fact that people's skills change. Giving unrated coders a very high σ₁ also prevents them from giving or draining too many points from the system for inflation or deflation.

I don't know how feasible it is, but it would be nice to invent a formula that naturally preserves some invariant such as (or maybe something involving the $\sigma_1$s), as normal Elo does...

Wow, geometric mean. That explains why it's easier to go up than down.

Anyway thanks for making it open; community discussion can only help! I might have more detailed thoughts later.

You start at 1500, about the Codeforces average. That's just how Elo ratings work. You might find yourself green in the next few matches but it's ok, you can work your way back up. It takes a respectable amount of skill even to be "average" here. Some of us train years. Welcome :)

Hey, not everyone learns so quickly that they can feasibly compete in one month! Most CS undergraduates and professional software engineers would struggle. I suppose you're right that we're unqualified to teach novices; not necessarily because we're too good, but because most of us have insufficient experience working with or teaching average-skilled coders in person. Some have no ambitions of winning national olympiads, but still benefit from the learning experience.

And then there's the separate issue of people who have the potential to achieve 1900+ but get turned off our community without giving it much chance. This is common in minority demographics who have less reason to feel like they belong. I don't know what should be done about this, but it's worth thinking about as we try to grow the community in a way that benefits more people. We are not the most qualified to answer these questions, and yet we may have something unique to offer using our expertise!

Now that I think about it some more, I suspect the orange range was shortened as a provision to allow for just a tad more inflation, after the new rating formula converges once and for all. Perhaps IM, GM, IGM and LGM will move up to 2400, 2600, 2900 and 3200 respectively, without hurting our novice members. That would make a perfect spread. Note that higher colors would span monotonically wider ranges, which makes sense since they are less populated: 200 pts each up to cyan, then 300 pts for blue and purple, 400 pts for orange, and 600 pts for normal red.

Some people proposed that there be a Division 3. I think that would be a cool idea if, and only if, Codeforces wishes to expand its mission outside the usual competitive community. I mean the kid hackers and the average joes wanting to get better at their CS courses, technical job interviews, and programming jobs, who would be rated 800-1200 if they register on Codeforces.

Preparing creative problems is less of a concern at this level, since any simple problem can be an interesting challenge when you're relatively new to programming and algorithms. Instead, the purpose would be to provide an educational resource, and perhaps gently persuade this larger population that competitive programming is cool and worth a try. People often complain that our community (as well as CS in general) isn't diverse enough, or that math and competitions are scary; maybe we can do something about it. We could use some outsider perspectives to help us succeed in that regard.

Ah I posted in the wrong page. Sorry, please ignore...

Awesome! I suggested something similar here, but the current table is better. It makes sense:

• Div2 has long needed a new color. It was less fun for beginners when green represented a 300-point range.

• The number of users per color is more equitable, increasing the information content of seeing a user's color; the black letter is a nice touch.

• Div1, while less populated, represented a much bigger range in ratings than Div2. As a result, it was hard to make a good contest covering the spectrum: purple users would barely solve A, while IGMs would experience a sort of speed rush. Div1 might have fewer rated contests now, but that's fine; you can do div2 unrated, and look forward to higher challenges in div1.

• Psychologically, 1900 is a good boundary line. 2000 looks intimidating, almost unreachable, if you've always been in the 1000's. Likewise with 2900 at the top, though it's less important there.

• The one flaw is that two of the ranges span only 100 points, which seems silly. Still, I can see some justification for it: 2200 is a meaningful number to TopCoder members, 2200/2300/2400 roughly correspond to M/IM/GM in chess, and the two ranks do share a color. It seems Codeforces now sees E-to-CM and CM-to-M as the major milestones.

I look forward to seeing the new rating calculations! I hope the CF team looks at site statistics in detail to figure out how to control rating inflation, as well as phenomena such as div1 users gaining points from mixed-div contests (on TopCoder, I think mixed-div is actually bad for div1 users because they use a normal instead of logistic model). I also think the length and difficulty of a contest must be taken into account: contestants are more likely to perform at their true level (i.e. at lower variance) if (a) the contest is long, and (b) the contest is at their level, not too easy nor too hard.

| means "divides", so x_{i+1} is a multiple of x_i.

Your code is less scary because you don't do rotations. How then do you keep the x's in order? Doesn't this merge destroy the order?

It looks as though photo lottery is cancelled? I suppose it was too short notice to work anyhow.

Rust is shaping up to be a very nice modern successor to languages like C++ (more so than D or Go). The 1.0 beta came out today, so please if you're reading this Mike, this is a great time to add it! :-D

Alright, thanks for checking. I have never seen tall sizes be an option at special events, but I hope to see some eventually. Great contest! :)

I'll understand if this is asking too much, but is there any chance shirts could be offered in Tall sizes? Some stores have them, and they're basically two sizes longer. So a medium tall would be roughly M in width but XL in length.

I hate to say this right as I find myself approaching red but, with ratings gradually inflating, we might have to raise the thresholds to something like:

3300 International Grandmaster of Legend (royal red), alternatively: International Superstar Grandmaster
3000 International Grandmaster (royal red)
2700 Distinguished Grandmaster (red)
2400 Grandmaster (red)
2200 International Master (orange)
2000 Master (orange)
1800 Candidate Master (purple)
1600 Expert (blue)
1400 Specialist (turquoise)
1200 Senior Pupil (green)
1000 Junior Pupil (light green)
-infinity Newbie (grey)
Unranked (applies to coders of all ratings who competed less than 3 times)

Div 1 could start at 1600 or 1800. Adding colour variations in the lower ratings can make the prospect of ranking up more fun and approachable for newcomers.

We might also look for a way to make the rating distribution converge faster so that rewriting ranks doesn't become an annual tradition. Maybe a one-time increase in the parameter that makes it hard for a high-rated coder to rise and a low-rated coder to drop? Does the formula take into account how round length affects variance? CF rounds are longer than TC, so there would be less variability in the results, increasing the spread of ratings. I'd be interested in seeing the update formula if it were to be published for the sake of discussion.

Given that CF ratings start at 1500 (while TC starts at 1200), and assuming 2400 retains the prestige of TC's 2200 at convergence, then by linear extrapolation, CF 3300 would be equivalent to TC 3200, or top 8, i.e. the superstars whose names are known by all! Sorry for so many edits.

Nice round. One question about rating calculation: is the weight given to a new contest > 50%? The rating changes seem fairly drastic in some cases.

Nice feature! Standardizing names might be a little difficult, so let's discuss it here before things get messy. How should we shorten names of the form XYZ Institute of Technology or University of XYZ? Should I simply omit the final word in Carnegie Mellon University?

P.S. There's a layout glitch in country/city/organization view where the Friends Rating button overlaps with the drop-down list.

Since they said they intend to change it, I just registered...

The Codeforces Tutorial page is a good resource if you get stuck on a problem.

Edit: However, it's currently missing the most recent rounds. It would be nice to have them all collected somewhere.

[deleted]

Defeating the judge in 10 minutes is quite amazing ;)

It's nice to see a growing community around programming competitions; I still have lots to learn from all of you! (this was my first time coding MST)

Alright, someone explained the real solution so I went ahead and implemented it! The trick is to make a sparse version of the graph of vertices which have portals. The "edges" in the portal MST will be shortest paths between pairs of portals in the original graph. There could be n^2 of these, but we don't actually need them all. MST edges are always minimum weight among edges in some cut of the graph. This solution is guaranteed to include all such edges.

Actually, the set vs priority_queue issue might just be another vertex ordering problem in disguise. Submission 1801347 also fails case #39 even though the only change from the "modified RAVEman code" in my first post is changing the priority_queue< pl > to a priority_queue< pl, vector< pl >, greater< pl > >.

Thanks!! I'm surprised set vs priority_queue would make such a big difference. TopCoder's STL tutorial says "the difference is about ~%0.1 of time", yet RAVEman passed test case #39 in only 50 ms. When I tried his code with set 1798838, it failed case #39.

As for the other reason, it seems the problem is that non-portal vertices can be visited multiple times. I haven't thought of a solution for this yet...