EbTech's blog

By EbTech, 7 weeks ago, In English,

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-R, 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 players who've competed on Codeforces in the past 6 months, as of August 18, 2019, rated according to the Elo-R system which I use with the UBC team. Full data and source code are accessible here. Official Codeforces statistics are similar, and accessible here.

Elo-R Range Codeforces Equiv Codeforces Range Title Division Number
3000+ 3336+ 3000+ Legendary Grandmaster 1 4
2700-2999 2900-3316 2600-2999 International Grandmaster 1 25
2400-2699 2570-2889 2400-2599 Grandmaster 1 126
2200-2399 2311-2570 2300-2399 International Master 1 338
2000-2199 2091-2310 2100-2299 Master 1 1336
1800-1999 1833-2091 1900-2099 Candidate Master 1 or 2 2779
1600-1799 1629-1833 1600-1899 Expert 2 5131
1400-1599 1462-1629 1400-1599 Specialist 2 or 3 7978
1200-1399 1374-1462 N/A Apprentice 2 or 3 10898
1000-1199 1238-1374 1200-1399 Pupil 2 or 3 14224
Up to 999 Up to 1238 Up to 1199 Newbie 2 or 3 12526

Codeforces equivalents were obtained by finding which Codeforces ratings correspond to the same world ranks as the Elo-R ratings in the first column.

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!

Read more »

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

By EbTech, history, 3 months ago, In English,

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!

Read more »

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