Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

How to Compete in Rust

Revision en8, by EbTech, 2019-06-04 03:06:30

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. So 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.

  • 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();

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| ...)
    ...
}

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

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

Or borrow its contents immutably:

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

You can also keep track of the index:

for (i, &elem) in v.iter().enumerate() {
    ...
}

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);

How did I learn 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!

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. 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.

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. Try it out!

As additional resources, check out my competitive programming codebook full of example code 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!

Tags rust, programing languages, quickstart

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en17 English EbTech 2019-07-03 21:50:21 19
en16 English EbTech 2019-06-25 12:31:38 122
en15 English EbTech 2019-06-05 20:42:16 182 Tiny change: ' major one.\n\n- A m' -> ' major one, and sufficient for contests.\n\n- A m'
en14 English EbTech 2019-06-04 11:20:54 99
en13 English EbTech 2019-06-04 09:50:28 80
en12 English EbTech 2019-06-04 09:29:22 249 Tiny change: ' time, we Copy elem by patter' -> ' time, we `Copy` `elem` by patter'
en11 English EbTech 2019-06-04 03:20:20 32
en10 English EbTech 2019-06-04 03:12:34 157 Tiny change: 'ubstantial, so it may no' -> 'ubstantial enough that it may no'
en9 English EbTech 2019-06-04 03:07:39 309
en8 English EbTech 2019-06-04 03:06:30 146
en7 English EbTech 2019-06-04 03:01:44 249 Tiny change: 'o must be explicit' -> 'o must be made explicit'
en6 English EbTech 2019-06-04 02:56:04 2 Tiny change: '~\nMy 1168D submissio' -> '~\nMy 1168C submissio'
en5 English EbTech 2019-06-04 02:55:14 1133 Tiny change: 'mplements `Iterator`, so I Goo' -> 'mplements the `Iterator` trait, so I Goo' (published)
en4 English EbTech 2019-06-04 02:28:35 1983 Tiny change: '4903799)\n[My solu' -> '4903799)\n\n[My solu'
en3 English EbTech 2019-06-04 01:35:51 1003
en2 English EbTech 2019-06-04 01:10:30 58
en1 English EbTech 2019-06-04 01:07:14 1742 Initial revision (saved to drafts)