CSES Practice

This repository contains templates and test infrastructure for solving the CSES Problem Set locally in both C++ and Rust.

Features

• Dual Language Support: Solutions can be implemented in both C++ and Rust
• Comprehensive Test Suite: Each problem includes multiple test cases with expected outputs
• CMake Build System: C++ solutions use CMake with Catch2 testing framework
• Cargo Workspace: Rust solutions organized in a Cargo workspace with automated testing
• Dev Container: Pre-configured development environment with all dependencies

Project Structure

cses-practice/
├── s01_introductory_problems/     # Introductory problems
├── s02_sorting_and_searching/     # Sorting and searching  
├── s03_dynamic_programming/       # Dynamic programming
├── s04_graph_algorithms/          # Graph algorithms
├── s05_range_queries/             # Range queries
├── s06_tree_algorithms/           # Tree algorithms
├── s07_mathematics/               # Mathematics
├── s08_string_algorithms/         # String algorithms
├── s09_geometry/                  # Geometry
├── s10_advanced_techniques/       # Advanced techniques
├── s11_sliding_window_problems/   # Sliding window problems
├── Cargo.toml                    # Rust workspace configuration
├── CMakeLists.txt               # C++ project configuration
└── README.md

Each problem directory contains:

• main.cpp - C++ skeleton implementation
• mod.rs - Rust skeleton implementation
• *.in / *.out - Test input/output files
• Problem-specific test cases

Quick Start

Prerequisites

1. git clone --recurse-submodules git@github.com:gaurishg/cses-practice.git
2. cd cses-practice
3. git switch empty_problems
4. Install git-lfs: sudo apt install git-lfs
5. git lfs pull
6. Open in VSCode and accept devcontainer prompt

Development Workflow

C++ Development

# Build all C++ targets
cmake --build build 

# Build specific problem
cmake --build build --target p01_weird_algorithm

# Run C++ tests
cd build && ctest

# Run specific problem
./build/s01_introductory_problems/p01_weird_algorithm

Rust Development

# Check all Rust code
cargo check --workspace

# Test all Rust solutions
cargo test --workspace

# Test specific problem
cargo test -p s02_sorting_and_searching p02_apartments

# Run specific problem  
cargo run -p s01_introductory_problems --bin p01_weird_algorithm

Rust scaffold feature (s01–s11)

• What: a Cargo feature named scaffold to keep placeholder code warning-free while stubs are unimplemented.
• Where: enabled in crates s01–s11; select modules gate allows via cfg_attr(feature = "scaffold", allow(dead_code, unused_imports, unused_variables, unused_mut)).
• When: use it to get clean builds during scaffolding; disable it to see full linting.
• How:

cargo check --workspace --features scaffold
cargo test  --workspace --features scaffold

Optional for VS Code to align editor diagnostics:

• Add to .vscode/settings.json:
  • "rust-analyzer.cargo.features": ["scaffold"]
  • "rust-analyzer.cargo.allFeatures": false
  • "rust-analyzer.cargo.noDefaultFeatures": false

Implementation Guide

C++ Implementation

Each C++ problem follows this structure:

#include <iostream>
#include <vector>

int64_t f(/* parameters */) {
    // IMPLEMENT THIS FUNCTION
    return 0;
}

#ifndef MY_DEBUG
int main() {
    // Input parsing
    // Call f() with parsed input
    // Output result
}
#endif

#ifdef MY_DEBUG
#include <catch2/catch_test_macros.hpp>
// Test cases using filesystem-based testing
#endif

Rust Implementation

Each Rust problem follows this structure:

fn f(/* parameters */) -> ReturnType {
    unimplemented!("Implement this function")
}

pub fn main() {
    // Input parsing
    // Call f() with parsed input  
    // Output result
}

#[cfg(test)]
mod test {
    use super::f;
    
    #[test]
    fn test_example() {
        // Example test case
    }
    
    #[test] 
    fn test_all_filesystem() {
        // Comprehensive filesystem-based testing
    }
}

Testing

Test Structure

• Example Tests: Hand-written test cases for basic validation
• Filesystem Tests: Automated testing against all .in/.out files
• C++ Tests: Use Catch2 framework with catch_discover_tests
• Rust Tests: Use built-in Rust testing with cargo test

Adding New Tests

1. Add .in input files and corresponding .out expected output files
2. Tests are automatically discovered and run by the framework
3. Both C++ and Rust implementations test against the same files

Problem Categories

1. Introductory Problems: Basic algorithmic thinking
2. Sorting and Searching: Fundamental algorithms and data structures
3. Dynamic Programming: Optimization problems with overlapping subproblems
4. Graph Algorithms: Traversal, shortest paths, network flows
5. Range Queries: Efficient querying of array ranges
6. Tree Algorithms: Tree traversal, LCA, tree DP
7. Mathematics: Number theory, combinatorics, geometry
8. String Algorithms: Pattern matching, string processing
9. Geometry: Computational geometry problems
10. Advanced Techniques: Complex algorithmic techniques

Contributing

1. Implement the f function in both C++ and Rust
2. Ensure all tests pass: cargo test and ctest
3. Follow the established patterns for input/output handling
4. Add additional test cases if needed

Development Environment

The devcontainer includes:

• Rust: Latest stable with common tools
• C++: GCC with C++20 support
• CMake: Build system for C++ projects
• Catch2: C++ testing framework
• Git LFS: For managing large test files
• VS Code: Extensions for C++ and Rust development

Start coding and happy problem solving! 🚀