Yesterday YouKn0wWho posted a blog explaining common mistakes in competitive programming and how to avoid them. I was greatly inspired by that post so I decided to make my own.
I have compiled some of the mistakes that I didn't make in my early Competitive Programming phase. I also mentioned how to avoid them. Also, in most cases, I will give you a chance to find out what the bug is before I reveal the culprit as I tried to make this blog interactive. The codes that I have used in this blog have been written in Rust as it is the most beloved language for CP.
Mistake 1
Check out the following code:
Codefn main() {
let x: i32 = 1_000_000_000;
let y: i32 = 1_000_000_000;
println!("{}", x * y);
}
The output should be $$$10^{18}$$$. But if you run the code, you will get a different output. Why?
ReasonBecause it won't even compile.
error: this arithmetic operation will overflow
--> foo.rs:4:20
|
4 | println!("{}", x * y);
| ^^^^^ attempt to compute `1000000000_i32 * 1000000000_i32`, which would overflow
|
= note: `#[deny(arithmetic_overflow)]` on by default
error: aborting due to previous error
Overflow!
$$$10^9 \times 10^9$$$ does not fit inside the i32
type which can only hold numbers up to $$$2^{31}-1$$$. To store large numbers like $$$10^{18}$$$, you'll need bigger integer types like i64
.
Mistake 2
Check out the following code:
Codefn test(v: Vec<i32>) -> usize {
v.len()
}
fn main() {
const N: usize = 1_000_000;
let mut sum = 0;
let v = vec![0; N];
for _i in 1..=N {
sum += test(v);
}
println!("{}", sum);
}
Try to run this locally. What is the time complexity of this?
Is it $$$O(n)$$$?
ReasonYou guessed correctly! It won't compile.
error[E0382]: use of moved value: `v`
--> foo.rs:10:21
|
8 | let v = vec![0; N];
| - move occurs because `v` has type `Vec<i32>`, which does not implement the `Copy` trait
9 | for _i in 1..=N {
| --------------- inside of this loop
10 | sum += test(v);
| ^ value moved here, in previous iteration of loop
|
note: consider changing this parameter type in function `test` to borrow instead if owning the value isn't necessary
--> foo.rs:1:12
|
1 | fn test(v: Vec<i32>) -> usize {
| ---- ^^^^^^^^ this parameter takes ownership of the value
| |
| in this function
help: consider cloning the value if the performance cost is acceptable
|
10 | sum += test(v.clone());
| ++++++++
Types like Vec
don't have the Copy
trait to avoid accidental copying. So, it is moved into the test
function. As you can see from the extremely helpful compile error messages, you moved v
into a function during the first iteration of the loop, so you can't use it in the next iterations.
How to fix this? The compiler already told you the answer! You can either borrow the parameter (&Vec
instead of Vec
), or add .clone()
to get an owned version of v
. (And as the compiler message suggests, the second method will be slower.)
Mistake 3
Check out the following code:
Codeuse std::io::{stdin, BufRead};
const N: usize = 100_000;
fn main() {
let test_cases = 100_000;
for _i in 0..test_cases {
let a = vec![0; N];
let n = stdin().lock().lines().next().parse();
let mut sum: i32 = 0;
for i in 0..n {
sum += a[i];
}
println!("{}", sum);
}
// it is guaranteed that total sum of n is <= 100000
}
Notice that it is guaranteed that total sum of n is <= 100000
. So how many operations will the code take in the worst case?
ReasonYou guessed correctly again! It won't compile.
error[E0599]: no method named `parse` found for enum `Option` in the current scope
--> foo.rs:9:47
|
9 | let n = stdin().lock().lines().next().parse();
| ^^^^^ method not found in `Option<Result<String, std::io::Error>>`
This is because a BufRead
returns a Result<String, std::io::Error>
when you read a line. The lines()
method returns an iterator of lines. The first()
method returns the first value of an iterator, which can be None
. Its type is Option<Result<String, std::io::Error>>
. Finally, the parse()
method parses the string into a number, which may fail, so it returns a Result
.
The correct code is to get the "success" values inside Option
s and Result
s! You can do it with unwrap
(NOT RECOMMENDED). For example: let n = stdin().lock().lines().next().unwrap().unwrap().parse().unwrap();
.
However, this is considered bad pratice, as you should always handle the error and none values properly.
Mistake 4
What is happening in the following code?
Codefn main() {
const N: usize = 5;
let a = [0; N];
a.fill(1);
println!("{:?}", a);
}
The output is supposed to be [1, 1, 1, 1, 1]
. But it's not the case actually! Why?
ReasonBecause it won't compile.
error[E0596]: cannot borrow `a` as mutable, as it is not declared as mutable
--> foo.rs:4:5
|
3 | let a = [0; N];
| - help: consider changing this to be mutable: `mut a`
4 | a.fill(1);
| ^^^^^^^^^ cannot borrow as mutable
Since you modify a
, you need to declare it as mutable with let mut a = [0; N];
.
Mistake 5
Don't use endl
! If your code needs to print millions of newlines, then using endl
turns out to be really slower than using '\n'
. Why?
ReasonBecause endl
isn't a thing in Rust.
By the way, println!
is also quite slow. If you need to print many lines, consider using a BufWriter
or converting all lines to strings first, joining those strings with "\n"
then printing the joined string all at once.
Mistake 6
Use pow()
function for integer calculations.
Why?Rust has the functions pow()
, ilog()
, ilog2()
, etc. for integer types. These are pretty safe to use, since their results are either integers or rounded to integers so are precise. If you worry about overflowing, functions like checked_pow()
return Option
to help you check cases where integer overflows happen.
fn main() {
assert_eq!(5i32.pow(2), 25);
assert_eq!(69i32.ilog(3), 3);
}
Mistake 7
Run the following code
Codefn main() {
let v = Vec::<i32>::new();
println!("{}", v.len() - 1);
}
You might expect the output to be $$$-1$$$. But the output is actually not! Why?
ReasonBecause of integer overflow.
thread 'main' panicked at 'attempt to subtract with overflow', foo.rs:3:20
note: run with `RUST_BACKTRACE=1` environment variable to display a backtrace
v.len()
is an unsigned integer 0 and is the lowest number an unsigned type can represent. Attempting to subtract a positive value from it will result in an overflow.
Mistake 8
Using eprintln!
might be a good way to debug your code as it doesn't output to the standard output. But leaving the eprintln!
instances in your code while submitting in OJ might be one of the worst ways of getting TLE.
Smash me for more info.
Mistake 9
Look at the following code
Codefn main() {
let a = 1;
let b = 3;
// we want to take a + b and bitwise & it with 3
let result = a + b & 3;
println!("{}", result);
}
The output is $$$0$$$, which is correct. Why?
ReasonThe precedence of the +
operator is higher than the &
operator, so the operator + operates first, meaning a+b = 4
executes and then the &
operator comes into play, so 4&3
executes and the output is clearly 0
for this.
Check out this to learn more about Rust operator precedence.
Mistake 11
Consider the following code for calculating the maximum occurrence in an array.
Codeuse std::collections::HashMap;
use std::io::{stdin, BufRead};
fn main() {
const N: usize = 30_000;
let mut mp = HashMap::<i64, usize>::new();
for _i in 0..N {
let x = stdin().lock().lines().next().unwrap().unwrap().parse().unwrap();
*mp.entry(x).or_insert(0) += 1;
}
println!("{}", mp.values().max().unwrap())
}
This code seems like it can be hacked easily but in fact, for almost every valid input, it should get AC.
Why?Rust's HashMap
by default uses a cryptographic hash function, which is also seeded by secure random numbers. This means it is extremely difficult to generate a hash collision in advance that blows up its complexity.
Mistake 12
Run the following code:
Codeuse std::collections::HashMap;
fn main() {
let mut mp = HashMap::<i64, usize>::new();
// add 1 to 5 to the map
for k in 0..5 {
*mp.entry(k).or_insert(0) += 1;
}
let mut cnt: usize = 0;
// check how many numbers in the keys exist in the map
for k in mp.keys() {
if *mp.entry(*k).or_insert(0) != 0 {
cnt += 1;
}
}
// now print the size of the map
println!("{} {}", cnt, mp.len())
}
What will be the size of the map? $$$5$$$?
CheckWrong, it's actually compile error.
error[E0502]: cannot borrow `mp` as mutable because it is also borrowed as immutable
--> foo.rs:11:13
|
10 | for k in mp.keys() {
| ---------
| |
| immutable borrow occurs here
| immutable borrow later used here
11 | if *mp.entry(*k).or_insert(0) != 0 {
| ^^^^^^^^^^^^ mutable borrow occurs here
In Rust, when you have a mutable borrow of a variable, then you cannot have other references to that variable, even immutable ones. The borrow checker of Rust is an extremely powerful feature, as it prevents many bugs (usually data races) that are caused by accidentally changing values while using them. You can learn more about references and borrowing by smashing me.
Mistake 13
I forgot Mistake 10.
Mistake 14
Check this out.
Codefn main() {
const N: usize = 1_000_000;
let mut s = String::new();
for _i in 0..N {
s = s + "ゑ";
}
println!("{}", s)
}
What is the time complexity of this?
CheckIt's not $$$O(n^2)$$$! It's $$$O(n)$$$ actually.
This is because in Rust, the +
operator of Strings consumes the value on the left hand side, while the right hand side is used to extend the buffer of the left string. This means that s = s + "ゑ";
is equivalent to pushing a string to s
and then moving it to itself, without allocating a new String. This operation takes $$$O(1)$$$ amortized time.
More Mistakes and Non-Mistakes
- Do not
insert
or erase
from a container (Vec
, HashSet
etc) while traversing it using for x in s.iter()
like syntax at the same time. This is because the compiler won't let you do that. In Rust, you are not allowed to borrow a variable while it is also borrowed as mutable at the same time (e.g. when inserting). - Create variables only when you need them instead of just declaring
let a, b, c, d, e, f, g, h;
and 69 other variables at the beginning of your code! This is because Rust's grammar doesn't let you do that. - If you want to count the number of set bits in an
i64
number, then use the count_ones()
method instead of the __builtin_popcount
function. This is because there is no __builtin_popcount
function. - If you want to compute the square root of an
f64
number, then use the sqrt()
method instead of sqrt()
because sqrt()
function takes self
as input whereas sqrt()
takes self
. - Speaking of
Runtime Error
, the most likely case of getting Runtime Error
is when your code encounters an error while running. let x: i64 = 1 << 40;
will not overflow as Rust will try to deduce the types of integer literals if they're not specified. In this case, the compiler determines that 1
is i64
. - Don't accidently write your code in C++.
Thanks for reading the blog. Feel free to add more mistakes that are common in CP in the comment section.
See you on a later episode, friend blobheart!
P.S. Although this is mostly a joke post, I tried to be accurate about the facts and did not intentionally put incorrect information in it (which means you may treat it as a somewhat educational blog). It also aims to showcase some features of Rust that helps you avoid some common CP mistakes in languages like C++.
Thank you sir, definitely one of the blog posts of all time.
using rust
As a proud Rustacean and Ferris the Crab adorer, I regret to inform you that your taste in languages sucks. This is sad. You can do better. You know how easy package and dependancy management is with Cargo? Not to mention you don’t even need a Makefile. It’s great. Dynamically typed languages need to die. There’s no other option. They just do. If you like dynamic typing, you need some help. Seriously. By using a dynamically typed and interpreted language (which means its @#*!&!@ slow!!!), you are committing genocide and harming the environment more than gas cars. Rust is fast and uses clean, renewable energy through the magic of being a language compiled with LLVM. Tired of memory bugs? You should be. Shame on you for still having them when Rust exists. Tired of being bad? Time to go to Rust. Tired of being slow because you’re not smart and your friends laugh at you? Rust is quite speedy indeed (all thanks to the big brain of the compiler). Tired of not getting off the normal way? Match statements, loops, and the compiler for Rust give the best orgasms 10/10 (completely legit). Not to mention the superiority you get to feel when you show off your superior Rust code to your inferior “friends” still using some other language. Want to get rid of malware? Rust is safe, therefore malware is noware (also completely legit). You quite honestly will forget about any other language (including English because it’s slow and unsafe). You even get to add the Rust Book and its brothers to your Bible collection alongside the Arch and Gentoo Wikis. All hail Rust. TempleOS pales in religious comparison to the faith of Rustaceans. Graydon Hoare is Jesus. Amen.
I especially love it when the Rust compiler said "It's Rustin' time" and Rust'd all over the mistakes. Truly the pinnacle of Competitive Programming.
This suggests why you should choose a compiler that does most of the work for you while letting you focus on the core business in hand.
Looking at this blog, RUST seems great to learn in 2023.
I like this semi-troll style of writing you have!