Readers of my Codeforces blog may recall that inutard and I have been experimenting with rating systems for quite some time. Last year, we demonstrated how to break the Topcoder system, and published our findings at the World Wide Web 2021 research conference. There, we derived a new Bayesian rating system from first principles. This system was specifically motivated by sport programming, though it may in theory be applied to any sport that ranks lots of contestants. Recently, it was adopted by the Canadian contest judge, DMOJ.

Now, in collaboration with the CodeChef admins, we are pleased to announce that upon the completion of July Lunchtime, the Elo-MMR rating system goes live on CodeChef.com! While recognizing that any rating system migration will be disruptive, we hope that you’ll find the advantages worthwhile. Let’s briefly go over them. Elo-MMR is:

1. Principled: using rigorous, peer-reviewed, Bayesian derivations.

2. Incentive-compatible: it’s never beneficial to score fewer points.

3. Robust: players will never lose too much rating for a single bad day.

4. Open: the algorithm and its implementation are available under open licenses.

5. Fast: on a modern PC, CodeChef’s entire history is processed in under 30 minutes; using close approximations, we’ve further reduced it to under 30 seconds. In addition, Elo-MMR offers:

6. A better rating distribution: CodeChef and Codeforces have a high spread at the top: for instance, tourist / gennady.korotkevich has a 1000+ point lead over CodeChef’s other top users, whereas Elo-MMR brings the gap below 150 points. Conversely, the old systems provide less spread in the low-to-median percentiles, compared to the wider numerical range that Elo-MMR allocates for the majority of users to progress through.

7. Conservative ratings / newcomer boost: Similarly to Microsoft’s TrueSkill, the publicly displayed rating will be a high-confidence lower bound on the player’s actual skill. As a result, rather than starting at the median and moving down, newcomers will start near the bottom and move up as the system becomes more confident in their skills. This provides a sense of progression and achievement.

8. Faster convergence for experts: Compared to the previous rating system, Elo-MMR awards a much higher increase to users who do well in their first CodeChef rounds.

It’s worth noting that no special hacks were taken to ensure these properties: they emerge naturally from the mathematical derivation. For details, please see the latest revision of our research article.

To demonstrate the difference in rating distributions, let’s plot them for CodeChef users, using both the old and new (Elo-MMR) rating systems. The latter’s parameters were chosen in such a way as to make the two rating scales approximately comparable. We see that although the original CodeChef ratings take up a wider range overall, gennady.korotkevich alone occupies a big chunk at the upper end! Elo-MMR, on the other hand, spreads the bottom 80% of the population over a wider range.

So, how are we handling the migration to Elo-MMR ratings? One option we considered is to simply take the current ratings and apply Elo-MMR updates from now on. This is not ideal, since rating systems can take a long time to converge: for example, consider the rating distribution of any programming contest site in its first year of operation. At the opposite extreme, we can retroactively recompute all contests in CodeChef’s history using Elo-MMR. DMOJ took this approach; it better leverages the site’s history, but the resulting transition is very sharp.

To smooth it out, CodeChef retroactively computed everyone’s current Elo-MMR ratings in the backend, but will continue to show the original CodeChef rating. Every time you compete, your backend Elo-MMR (MM) rating will be updated, and then your public CodeChef (CC) rating will be pulled closer to your MM rating according to the formula:

where $$$n$$$ is the number of rounds in which you’ve taken part. Thus, new players, who do not yet have a solidified CC rating, are transitioned into the new system more rapidly. The most experienced players are pulled one-fourth of the way each time they compete.

Having examined the population, we might also ask how much the ratings of specific individuals change between the two systems. To find out, we first eliminate the noisiest data: players who have been caught cheating, and newcomers with at most 10 lifetime contest participations. For all remaining users, we compare their original CodeChef rating to their retroactively computed Elo-MMR ratings. The statistics are summarized as follows:

• World champion gennady.korotkevich is the main outlier, with $$$CC - MM = 1079$$$. Thus, over the next 10 or so contests that it will take for the new ratings to come into effect, he is expected to lose about $$$1000$$$ points. Thanks Gennady, for understanding and being fine with this!

• Less than 800 additional users have $$$CC - MM > 200$$$, and none of these are over $$$500$$$. Nonetheless, these users’ ratings will most likely decrease over their next few contests.

• Around 8000 users have $$$MM - CC > 200$$$, the highest of them being $$$630$$$. These players will experience a rating boost over their next few contests.

• All other users have $$$|MM - CC| \le 200$$$, so they will experience minimal disruptions.

For the next few months, the day after every rated contest, we will update everyone's hidden Elo-MMR rating in this drive (warning: it might be too large to view online). This way, interested users can investigate their "true" rating trajectories. Within a year, CodeChef will retire the migration plan and simply assign all users their full Elo-MMR rating.

We welcome any questions and will do our best to answer them all!

It's long been known that certain rating systems, namely Glicko-2 and Topcoder, are not monotonic. In other words, there are cases where losing can eventually result in a higher rating. We wanted to know just how severe the issue can be. In joint work with inutard at WWW 2021, we computed how tourist's rating would evolve according to both Topcoder and our custom rating system. The dataset consists of Codeforces rounds up to Looksery Cup 2015, accessed via the Codeforces API. Here, we see that tourist's Topcoder rating is 3284, but could have been as high as 3807 if he were willing to lose on purpose!

More details on the adversarial strategy: for his first 45 rounds, we simulate tourist playing normally, following historical data. In the next 45 rounds, he purposely becomes last place whenever his Topcoder rating is above 2975, but plays normally otherwise. Then finally, he returns to playing normally for an additional 15 rounds.

A similar strategy recently broke the Pokemon Go Battle League rankings, which seem to be based on Glicko-2: https://www.reddit.com/r/TheSilphRoad/comments/hwff2d/farming_volatility_how_a_major_flaw_in_a/.

UPDATE: the new rating system paper will appear in the Web Conference 2021!

Last year, I published ratings using a contest rating system that I had developed at the end of 2015. Back then, I promised to eventually write in detail about the system's inner workings.

Over the past week, I've cleaned up and optimized the code: it now takes 24 minutes to process the entire history of Codeforces on my small laptop!!!

More importantly, I cleaned up the paper. Please ignore the last sections for now, as they're incomplete, but the main sections that explain how the rating system was derived are now ready! I claim my Elo-MMR is a more principled extension of Elo/Glicko to the programming contest setting, with nicer properties than the systems that contest sites currently use.

The main work that remains to be done are quantitative empirical studies comparing the properties of the different ratings systems. Since this is just my hobby project, I might not have the time to do all of it alone. If anyone wants to help run experiments, let's chat about it!

This blog post outlines the design of a very general data structure for associative range queries, in the Rust programming language.

In the "real world", self-balancing binary search trees can be augmented to handle a variety of range queries. However, for contest problems, statically allocated variants are much easier to code and usually suffice. The contest community has come to know these data structures as segment trees. Here, I will generalize most of the segment trees that you can find in the wild into one polymorphic data structure, that can easily be copy-pasted during online competitions. I will call it an ARQ tree. ARQ is pronounced "arc", which has a similar meaning to "segment", but also stands for "Associative Range Query". It supports highly customizable range queries, the main requirement being that the aggregation operation must be associative.

Associativity and Semigroups

We begin with an array $$$a_0, a_1, a_2, \ldots, a_{n-1}$$$. Each $$$a_i$$$ belongs to a semigroup $$$(S, +)$$$; that is, a set $$$S$$$ together with an associative binary operation $$$+$$$. In formal notation:

Associative Law: $$$+: S \times S \rightarrow S$$$ satisfies $$$a + (b + c) = (a + b) + c$$$ for all $$$a, b, c \in S$$$.

Because $$$+$$$ is associative, we can drop the parentheses without ambiguity and talk about range aggregates in the form $$$a_l + a_{l+1} + \ldots + a_r$$$.

The ARQ Problem

In the Associative Range Query problem, we wish to support two types of queries:

• Given bounds $$$l$$$ and $$$r$$$, compute the aggregate $$$a_l + a_{l+1} + \ldots + a_r$$$.

• Given bounds $$$l$$$ and $$$r$$$, and a function $$$f: S \rightarrow S$$$, replace $$$a_i$$$ with $$$f(a_i)$$$ for all $$$l \le i \le r$$$.

In typical instances where computing $$$a + b$$$ or $$$f(a)$$$ take $$$O(1)$$$ time, we wish to support each query in $$$O(\log n)$$$ time.

Identity and Monoids

Perhaps you've heard of range queries over a monoid. A monoid is simply a semigroup with a special identity element:

Identity Law: $$$id\in S$$$ satisfies $$$a + id = id + a = a$$$ for all $$$a \in S$$$.

We represent Semigroup and Monoid using Rust traits. The Rust compiler will not verify the associative and identity laws, so it's the programmer's job to check them when implementing these functions:

trait Semigroup {
    fn op(&self, other: &Self) -> Self;
}

trait Monoid: Semigroup {
    fn identity() -> Self;
}

Equivalence

In practice, there is not much difference between a semigroup and a monoid, and either of the two would suffice for our purposes. This is because a semigroup can always be extended into a monoid by adding an identity element. In this Rust implementation, the Monoid's advantage is that it can clone (i.e., make copies of) elements, by applying its operation with the identity. Thus, the trait bound Monoid turns out to be equivalent to Semigroup + Clone. To illustrate, here is the conversion from Semigroup + Clone to Monoid, using Option<T> to denote "T or the identity":

impl<T: Semigroup + Clone> Semigroup for Option<T> {
    fn op(&self, other: &Self) -> Self {
        match self {
            Some(ref a) => match other {
                Some(ref b) => Some(a.op(b)),
                None => self.clone()
            },
            None => other.clone()
        }
    }
}

impl<T: Semigroup + Clone> Monoid for Option<T> {
    fn identity() -> Self {
        None
    }
}

Conversely, a Monoid is already a Semigroup and can implement Clone by operating with the identity element:

impl<T: Monoid> Clone for T {
    fn clone(&self) -> Self {
        self.op(T::identity())
    }
}

ARQ API v1: Point Updates

Now that we understand Semigroup + Clone as equivalent to Monoid, the choice between the two becomes an implementation detail, with tradeoffs in performance and ergonomics depending on the application. Personally, I found it easier to work with the Monoid trait. Our first API will not support full range updates, but only point updates:

pub struct ArqTree<T> {
    val: Vec<T>
}

impl<T: Monoid> ArqTree<T> {
    pub fn update(&mut self, pos: usize, f: &dyn Fn(&T) -> T) {
        // implement update
    }
    
    pub fn query(&self, l: usize, r: usize) -> T {
        // implement query
    }
}

I won't provide a full implementation: you may use other segment tree guides as a reference. In summary, we build a complete binary tree on top of our array. tree.update(pos, f) will replace $$$a_{pos}$$$ by $$$f(a_{pos})$$$, then recompute each of the ancestors of $$$a_{pos}$$$ by applying $$$+$$$ to its two children. This will work with no restrictions on the function $$$f$$$. Its time complexity is comprised of one application of $$$f$$$ and $$$O(\log n)$$$ applications of $$$+$$$.

Shortcomings of the v1 API

Our simple v1 API can't support efficient range updates! In order to update an entire range efficiently, we will need to apply $$$f$$$ lazily, storing it in internal nodes of the tree to eventually be pushed toward the leaves. If multiple updates are performed, we may have to store a composition of updates for postponed application. While one may implement a composition operation $$$f \circ g$$$ which simply first calls $$$g$$$ and then calls $$$f$$$, this makes the cost of function application no longer $$$O(1)$$$!

Thus, we must switch from function pointers to an implicit, composable representation for $$$f$$$. The composition of "add 5" and "add 7" is not "add 5 and then 7"; rather, it's "add 12": we should store the number 12 instead of the adding functions.

To recap, now we have a monoid $$$(S, +)$$$ of array elements, as well as a second monoid $$$(F, \circ)$$$ whose set $$$F \subset (S\rightarrow S)$$$ consists of the update functions that we're interested in. Why is $$$F$$$ a monoid? Well, it's easy to check that function composition is associative, making it at least a semigroup. And then, just as with $$$S$$$, we can choose whether to have F: Monoid or F: Semigroup + Clone. For $$$F$$$, I found the latter to be more ergonomic.

However, these are not simply two independent monoids! The sets $$$S$$$ and $$$F$$$ interact, with functions from $$$F$$$ acting on elements from $$$S$$$ to produce the newly updated elements of $$$S$$$. While we're at it, I'm actually not too happy with the Semigroup and Monoid traits. There's more than one way for a type, say 32-bit integers, to be a monoid: the operation could be addition, multiplication, minimum, maximum, leftmost non-identity value, etc. With this design, we'd have to wrap our i32s in distinct wrappers for each Monoid implementation, and that's ugly.

But remember that a struct is just a collection of data. A struct's impl block is a collection of functions (and possibly some associated types and constants). Typically, functions inside an impl block take a special self argument and are called methods, but this is not strictly necessary. So we can instead define a trait that packages the two types $$$S$$$ and $$$F$$$, alongside functions that act on these types!

ARQ API v2: Range Updates

We scrap the Semigroup and Monoid traits, and instead define:

pub trait ArqSpec {
    type S;
    type F: Clone;
    
    /// Require for all a,b,c: op(a, op(b, c)) = op(op(a, b), c)
    fn op(a: &Self::S, b: &Self::S) -> Self::S;
    /// Require for all a: op(a, identity()) = op(identity(), a) = a
    fn identity() -> Self::S;
    /// For eager updates, compose() can be unimplemented!(). For lazy updates:
    /// Require for all f,g,a: apply(compose(f, g), a) = apply(f, apply(g, a))
    fn compose(f: &Self::F, g: &Self::F) -> Self::F;
    /// For eager updates, apply() can assume to act on a leaf. For lazy updates:
    /// Require for all f,a,b: apply(f, op(a, b)) = op(apply(f, a), apply(f, b))
    fn apply(f: &Self::F, a: &Self::S) -> Self::S;
}

pub struct ArqTree<T: ArqSpec> {
    val: Vec<T::S>,
    app: Vec<Option<T::F>>,
}

impl<T: ArqSpec> ArqTree<T> {
    pub fn update(&mut self, l: usize, r: usize, f: &T::F) {
        // implement update
    }
    
    pub fn query(&mut self, l: usize, r: usize) -> T::S {
        // implement query
    }
}

This version still supports the previous setting of point updates. In that case, op() and identity() must satisfy their respective monoid laws, but apply() can apply any arbitrary function, and compose() can remain unimplemented or even crash because updates with l == r will never call compose().

However, if we plan to do range updates, i.e., with l < r, then we must be prepared to apply $$$f$$$ to internal nodes of the tree! To ensure consistency, we require two additional laws:

Composition Law: $$$(f \circ g)(a) = f(g(a))$$$ for all $$$f, g \in F$$$, $$$a \in S$$$

Distributive Law: $$$f(a + b) = f(a) + f(b)$$$ for all $$$f \in F$$$, $$$a, b \in S$$$

The composition law implies that $$$F$$$ is a semigroup, and the distributive law ensures consistent interactions between $$$S$$$ and $$$F$$$ throughout the tree!

Example: Range Minimum Query

To see how to specialize this API, let's use it to solve the following classical problem:

• Given bounds $$$l$$$ and $$$r$$$, compute the minimum of $$$a_l, a_{l+1}, \ldots, a_r$$$.

• Given bounds $$$l$$$ and $$$r$$$, and a number $$$f$$$, replace $$$a_i$$$ with $$$f + a_i$$$ for all $$$l \le i \le r$$$.

The first monoid $$$S$$$ consists of the numerical array elements with the minimum operation. The second monoid $$$F$$$ consists of functions which add a constant: their composition simply sums their respective constants. Thus, elements of $$$F$$$ are most conveniently represented by literally storing the constant in question. All four functions are one-liners:

pub enum RMQ {}
impl ArqSpec for RMQ {
    type S = i64;
    type F = i64;
    
    fn op(&a: &i64, &b: &i64) -> i64 {
        a.min(b)
    }
    fn identity() -> i64 {
        i64::max_value()
    }
    fn compose(&f: &i64, &g: i64) -> i64 {
        f + g
    }
    fn apply(&f: &i64, &a: i64) -> i64 {
        f + a
    }
}

// Instantiate with:
let mut rmq_tree = StaticArq::<RMQ>::new(&vec);

Note that the programmer must manually verify the four laws (only two if range updates are not used). In some cases, your operations may need access to the size or position of the subtree corresponding to the current node. This does not require an extension of the API: the monoid type $$$S$$$ can simply be made a tuple which contains this additional information. For examples of the ARQ tree in action, please see: ARQ tree example usage on Github

Static Implementation: ARQBIT

static_arq.rs

To keep this blog post focused on the abstraction and general API, I left the implementation details here as a GitHub link. Indeed, the key advantage of these abstractions is that I almost never have to think about segment tree code! I only have to worry about ensuring that my custom operations satisfy the four laws.

If you're interested in the details, this is a statically allocated binary-indexed ARQ tree with lazy propagation, which I like to call an ARQBIT. It's more heavy-weight than a standard BIT, but works on general semigroups. It's based on a very cool blog post by Al.Cash that you can check out for a better explanation!

Dynamic Implementation: Sparsity and Persistence

dynamic_arq.rs

A dynamically allocated version of this data structure can initialize its leaves (potentially more than $$$10^{18}$$$ of them!) to the identity in $$$O(1)$$$ time, using a lazy construction. It supports some splitting and merging operations, as well as persistence. Most of its methods require an ArqView parameter, which determines which node to treat as the root of the tree. When the is_persistent flag is turned on, previously generated ArqView objects remain valid and immutable, thus preserving access to all earlier states of the data structure. However, when the flag is turned on, only the more recently generated ArqView should be considered valid, while the others may be destroyed.

Advanced Usage with push() and pull()

Typically, the data structure is only updated (and new ArqViews generated) by calls to update(). However, advanced users may directly make use of push()/pull() to dig inside the tree. For example, suppose we want the first (i.e., leftmost) negative element in the array. One approach is to binary search down from the root of an RMQ tree. Example binary search functions are provided for each of the static and dynamic implementations above. Here, we focus on some general aspects of the dynamic implementation.

Since changes are lazily propagated, only the root node is valid for read/write access at first. We gain access to its subtrees as follows:

let (lchild_view, rchild_view) = arq_tree.push(root_view);
// If we make changes to either or both child subtrees, we must pull them before accessing the root again:
arq_tree.pull(root_view);

The static and dynamic implementation files above demonstrate how this works for the binary search example. Since these functions leave the underlying array unchanged, they don't need to pull().

Once in a while, you'll come across a problem where you need range updates but can't satisfy the distributive law, not even if you store additional information such as subtree size and position. You might need custom break/tag conditions with intricate runtime analyses. In such cases, the provided algorithms will no longer function as-is. You may have to implement your own version of query() and/or update(). Nonetheless, the push()/pull() API may reduce the amount of work you have to do.

Conclusions

This is a side project that I built in summer 2017, expanded upon in summer 2019, and only now in 2020 had the chance to write about. Please let me know if you'd like something to be explained in more detail :)

UPDATE: the new rating system paper will appear in the Web Conference 2021!

If you're new to competitive programming, you may be wondering: what are ratings and colors? What do they mean?

As a contestant and now coach of the UBC team, I've taken enough interest in the subject to have developed my own rating system, Elo-MMR, which I might describe in a future blog post. For now, I want to talk about ratings more generally: what does it mean to achieve a certain rating or title? How concerned should you be with your rating and title? Might it be harmful to be concerned with them at all?

A Brief History of Contest Ratings

Contest rating systems can trace their heritage back to the Elo system. Elo was devised for 2-player games, with rating updates based on whether a player wins, loses or draws. Starting in 1960, it was adopted by the chess community to numerically estimate the skills of players based on whom they won or lost against.

The first major online venue for competitive programming, TopCoder, was founded in 2001. It generalized Elo to allow for matches in which an arbitrary number of players are ranked. Players would see their "handles" (a sort of nickname or username) colored according to rating ranges: 0-899 is grey, 900-1199 green, 1200-1499 blue, 1500-2199 yellow, and 2200+ receive the coveted red color. Players rated 3000+ get an additional white dot inside their red icon, like a bull's-eye, inspiring colloquial usage of the title "target" to refer to these dozen or so top programmers in the world.

The leading competitive programming site in modern times, Codeforces, arrived on the scene in 2010. Its rating system associated not only colors to numerical ranges, but also named titles. In the spirit of peaceful sportsmanship, the old militaristic titles were discarded in favor of chess-style titles in 2011's November Revolution of Colors and Titles, which received further updates in later years.

Rating Statistics

This table summarizes the present-day titles alongside some statistics. The numbers refer to subsets of the 99832 players who've competed on Codeforces in the past 6 months, as of May 30, 2021, rated according to the Elo-MMR system which I use with the UBC team. The full list of ratings and source code are accessible here. Official Codeforces rating statistics are similar, and accessible here. Using optimized parallel algorithms, it took about half an hour to simulate the entire history of Codeforces on a modest laptop; it can be made even faster if subsampling-based approximations are used.

Codeforces equivalents in the last column were obtained by finding which Codeforces ratings correspond to the same world ranks as the Elo-MMR ratings in the first column. Divisions are suggested ones using Elo-MMR.

One interesting finding is that the 1800-1999 Elo-MMR range (Candidate Master) corresponds to a wider Codeforces range than the levels either immediately above or below. While I haven't yet tested whether that's the case, it's suggestive that Divisions 1 and 2 might be better-separated in my system: that is, an in-between player's rating updates aren't unduly advantaged when competing in the weaker division.

Interpretations

Newbie

The start of everyone's journey. At this stage, you might be new to programming. You'll have to become familiar with the control structures and core libraries of your chosen programming language. You might wonder if it makes sense to participate in the competitive programming community at this stage. In my opinion, it's never too early to join!

You might start with sites such as LeetCode which are more oriented toward basic knowledge and professional development, rather than competition and problem solving. Nonetheless, with the introduction of Division 3 rounds, Codeforces is a welcoming environment as well. Some people enjoy learning a programming language by attempting small, self-contained problems.

Pupil

Now you know how to write working code, and perhaps you've taken your first data structures course. However, you don't often know when to apply standard library data structures, or algorithmic techniques such as dynamic programming.

It bears mentioning that the disciplines of computer science and software engineering are so vast, that it's quite possible to be a successful professional in your specialization while still being a Pupil on Codeforces. Contest skills which you may wish to develop include: algorithmic fundamentals, mathematical problem solving, and speed and precision of implementation. In my Pacific Northwest region, we prepare Division 2 contests (roughly equivalent to Division 3 on Codeforces) to provide a fun and educational experience for novices.

Apprentice

This is a new tier I added. To me, the word "Apprentice" suggests something between a student (aka Pupil) and a professional (aka Specialist). An Apprentice has completed enough basic training to apply their skills in the real world, with some help. With some additional mentorship, they will eventually become a self-sufficient specialist in their trade. At this level, you're comfortable with some basic techniques and looking to further extend your skills.

Specialist

You've made it! You are applying algorithms and data structures at a professional and competitive level. If your motivation was professional development or job interview preparation, this range might be your ultimate goal. When it comes to algorithmic software engineering interviews, you'll be a strong candidate, even at some of the most prestigious technology companies.

Expert

You have algorithmic expertise exceeding that of a typical professional. As such, students and colleagues may refer to you for guidance. In some local circles, you might be considered an algorithms guru of sorts. On the other hand, your ambition may have driven you to surround yourself with even stronger algorithmists! Perhaps you're thinking seriously about competing internationally, at events such as the IOI or the ICPC World Finals. In that case, your journey has only just begun...

Candidate Master

Welcome to Division 1! As a pre-requisite to the esteemed title of Master, you are deemed eligible to prove yourself by competing alongside the best of the best, on the toughest problem sets that Codeforces offers. Professional whiteboard interviews cease to scare or even challenge you; now they're just an opportunity for you to flex over interesting problem discussions.

Master

Congratulations! At this point, Division 2 contests are no longer rated for you, and probably not that interesting to you either. To signify the magnitude of your achievement, there's a sharp transition from the bottom of the rainbow toward the fiery colors at the top. You are a formidable competitor in your region. In most regions of the world, you have a strong chance of advancing to the IOI or the ICPC World Finals.

International Master

Similar to Master, only that you're considered formidable even on the international stage.

Grandmaster

The coveted red color comes with considerable respect, even fame, in the competitive programming community. Other competitors, total strangers to you, may recognize your handle and come to you for advice. People aspire to know even a fraction of what you know. Your fast wit is awe-inspiring. You might try to win a medal at the ICPC World Finals.

International Grandmaster

Similar to Grandmaster, only now your fame extends internationally. Your handle is familiar to the entire competitive programming community. A team of IGMs would be slated among the favorites to win ICPC outright.

Legendary Grandmaster

Similar to Grandmaster, only now your fame extends internationally and across time as well. Your achievements are of historic importance to the community, pushing the limits of what's thought to be possible. Colloquially, your color is a variant of red called "nutella": analogous to the "targets" of TopCoder, the white bull's-eye is substituted by a black first letter in the style of the Nutella logo.

This is another title that I once suggested, and was eventually added. We really just needed a shorthand for "programmers who stand a chance against tourist" :P

Concluding Remarks

So, should you be concerned with your rating? I suggest to relax a bit. If you worry too much about losing points on a bad day, you might decide to skip contests on any day in which your mental preparation is less than perfectly optimal. While this may rescue your rating in the short-term, such an attitude will slow your progress in the long-term. The obsession to optimize one's rating can be counter-productive and cause hurt feelings.

Having said that, having your rating on the line can be a good motivator during a contest, simulating some of the pressure of a major event such as an ICPC regional. In addition, now that you understand what the titles mean, ratings are a nice way to track your progress and feel good about the cumulative effect of your training. You've earned it! Just as in long-term stock investment, resist the urge to react to daily fluctuations: focus on the big picture!

Finally, keep track of your motivations, whatever it is that you hope to get out of the experience: be it to prepare for whiteboard interviews, to be exposed to ideas for computer science research, to play a competitive mental sport, to meet other problem solvers, or just to keep your mind active with fresh puzzles. Ratings may correlate with these things, but of course they're not everything. For good or ill, we tend to rank people a lot in our schools and workplaces. At least here, we all know that this is fundamentally a game we're playing, and the criteria and methods for success are well-publicized. Good luck and have fun!

Having spent a number of Codeforces rounds practicing the ins and outs of Rust, I think it's finally safe to encourage wider participation in the language! This guide is intended primarily for C++ programmers who may have taken interest in Rust, but had doubts regarding its feasibility in timed contests. On Quora, I summarized why I think Rust is suitable for contests in 2019 onward. Granted, the learning curve is substantial enough that it may not seem that way at first. To make the transition easier, for anyone who's interested, here I'll go over some aspects of my Codeforces submissions in more detail, with some tips along the way.

My solution to 1168C: And Reachability

My solution to 1158D: Winding polygonal line

Right away, you'll notice certain characteristics:

• The only global variable is a compile-time constant. By scoping things appropriately, I don't have to worry about accidentally forgetting to reset data.

• Very few mutable variables. This makes code easier to reason about, and mistakes less likely.

• Very strict type-checking. For example, I might use the usize type for array indices, and i64 for geometric coordinates. Conversions between the two must be made explicit. This seems annoying at first, but it caught quite a few of my bugs.

• A polymorphic Scanner.next() method. It can read space-separated tokens of any type that implements the trait FromStr.

• Output via BufWriter. This is needed for speed, if you want to write a large number of lines. BufWriter flushes automatically when it goes out of scope, but you'll probably want to flush() manually on interactive problems. Further I/O optimizations are possible (see comments section), but this is the major one and is sufficient for contests.

• A mix of imperative-style and functional-style constructions, depending on which is clearer.

In Rust, you can read a Vec (i.e., vector in C++, ArrayList in Java) of floats from standard input in imperative style:

let mut v = Vec::with_capacity(n);
for _ in 0..n {
    let elem = scan.next::<f64>();
    v.push(elem)
}

Or you can do it in functional style, rendering the result immutable:

let v: Vec<f64> = (0..n).map(|_| scan.next()).collect();

Both versions are very efficient: the Vec initially allocates space for n elements, similar to v.reserve(n) in C++!

You can "consume" (i.e., move) a Vec if you won't need it anymore:

for elem in v { // equivalent to v.into_iter().for_each(|elem| ...)
    // do something with elem
}

Or borrow its contents mutably, to change some of its elements:

for elem in &mut v { // equivalent to v.iter_mut().for_each(|elem| ...)
    // do something with *elem
}

Or borrow its contents immutably:

for elem in &v { // equivalent to v.iter().for_each(|elem| ...)
    // do something with *elem
}

If the elements implement Copy, the dereference can be copied into the variable elem by pattern matching. This time, let's also keep track of the index:

for (i, &elem) in v.iter().enumerate() {
    // do something with elem
}

Rust Strings are UTF-8. To get random access, you'll have to convert them to .bytes() or .chars(). And if you're reading a String made entirely of 0s and 1s? Convert them to bools as follows:

let s: String = scan.next();
let v: Vec<bool> = s.chars().map(|ch| ch == ‘1’).collect();

My 1168C submission features the following rather magical line:

let (zero_bits, one_bits): (Vec<usize>, Vec<usize>) =
                (0..BITS).partition(|b| (ai & (1usize << b)) == 0);

Where did I get the idea to do this? Well, I wanted to know which positions of the binary number ai contain a 0, and which contain a 1. I knew that the Range object 0..BITS implements the Iterator trait, so I Googled "rust iterator", landed on a doc page, and browsed through the list of methods. (0..BITS).filter().collect() seems close to what I wanted: it selects the bits which satisfy a given condition. However, (0..BITS).partition() does more, giving both the passing and the failing bits! Note that collect() and partition() are polymorphic, so I could just as easily have obtained HashSets instead.

As you can see, the language is very expressive, and the standard library quite flexible. One very interesting finding from my experience with Rust is that "production-quality" code and "quick hacky" code look much more alike than they do in C++. This is because Rust not only makes it harder to do things the wrong way, but also makes it much easier to do things the right way. As a result, I naturally find myself coding in a clearer style, even under time pressure.

Overall, my solutions attain much fewer WA verdicts in Rust than they did in C++. Development time is sometimes more, sometimes less, but it gets better with practice. Best of all, I now find coding to be a less paranoid experience: I can have fun with problems instead of being hyper-alert to programming errors. Try it out and see!

As additional resources, feel free to check out my past submissions on Codeforces, my competitive programming codebook full of algorithms and data structures you can use, and Rust's new dbg!() macro for a more informative way to inspect run-time values. Leave your competitive Rust questions in the comments, and good luck!