website·Indexed 31 days ago
https://rustp.org/A comprehensive resource for competitive programming using the Rust language. It provides implementations and tutorials on data structures (vectors, segment trees), number theory (GCD, LCM, Sieve of Eratosthenes, modular arithmetic), combinatorics, dynamic programming (0/1 Knapsack, Coin Change), and array algorithms like Kadane’s Algorithm and Prefix Sum Arrays, along with Codeforces problem solutions and basic I/O templates.
Number Theory in the context of competitive programming involves the study and application of integers and integral value functions. Key areas of focus include:
Data structures are categorized by how they organize data:
Rust vectors are contiguous growable arrays. They often allocate more memory than currently needed to avoid frequent reallocations.
When a vector's size exceeds its capacity, Rust reallocates a new chunk of memory (typically doubling the previous capacity) and copies the existing elements to the new location.
fn main() {
// Create a vector of length 5, with all elements as 0
let mut vecky = vec![0; 5];
println!("Size: {}, Capacity: {}", vecky.len(), vecky.capacity()); // Size: 5, Capacity: 5
vecky.push(0);
println!("Size: {}, Capacity: {}", vecky.len(), vecky.capacity()); // Size: 6, Capacity: 10
}i128 and u128, which store up to approximately 10^38). To prevent overflow and maintain efficiency, results are typically computed modulo a large prime number, commonly 10^9 + 7 (1,000,000,007).unsafe option to bypass some of these safety checks.A Prefix Sum Array p is derived from an array a such that each index i in p contains the sum of all elements in a from index 0 up to index i (p[i] = a[0] + ... + a[i]).
Key properties include:
i is calculated as p[i] = a[i] + p[i-1] for i > 0.n with respect to p is a natural number x (where 1 ≤ x < p) such that (n * x) mod p = 1. This is used in modular arithmetic to replace the division operation. The inverse exists if and only if n and p are coprime (gcd(n, p) = 1). Common use cases include competitive programming for fractional results, calculating large permutations/combinations, and RSA cryptography.To solve the 'Colorful Table' problem, the goal is to find the smallest square that contains all occurrences of a specific color, given that all colors smaller than the current one have already been removed from the set of available indices.
Algorithm:
BTreeSet containing all currently available indices (initially all indices from $0$ to $n-1$).BTreeSet plus one: 1 + last_index - first_index.BTreeSet before moving to the next color.Complexity:
use std::collections::BTreeSet;
use std::io::stdin;
fn solve() {
// Read n (length) and k (number of colors)
let n_k = take_vector();
let n = n_k[0];
let k = n_k[1];
let arr = take_vector();
// Store indices of each color
let mut indices = vec![Vec::new(); k + 1];
for i in 0..n {
indices[arr[i]].push(i);
}
// BTreeSet to track available indices
let mut minimum = BTreeSet::new();
for i in 0..n {
minimum.insert(i);
}
for i in 1..=k {
if indices[i].is_empty() {
print!("0 ");
continue;
}
// The square edge is defined by the current min and max indices in the set
let first = *minimum.first().unwrap();
let last = *minimum.last().unwrap();
print!("{} ", 2 * (1 + last - first));
// Remove indices of the current color for the next iteration
for j in &indices[i] {
minimum.remove(j);
}
}
println!();
}
// Helper to read space-separated integers
fn take_vector() -> Vec<usize> {
let mut input = String::new();
stdin().read_line(&mut input).unwrap();
input.trim().split_whitespace().map(|x| x.parse().unwrap()).collect()
}
pub fn main() {
let t = take_int();
for _ in 0..t { solve(); }
}
fn take_int() -> usize {
let mut input = String::new();
stdin().read_line(&mut input).unwrap();
input.trim().parse().unwrap()
}