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, andi64
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 traitFromStr
.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 toflush()
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 allocating space for n
elements as with 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 String
s 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 bool
s 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 HashSet
s 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!