Core Algorithms and Data Structures

Simulation and Mathematics

• High-precision arithmetic is critical for problems involving large integers, such as the "King's Game" or matrix selection problems.
• Number theory fundamentals include Fast Power (Exponentiation by Squaring), Prime Sieves (Sieve of Eratosthenes), Greatest Common Divisor (GCD), and Extended Euclidean Algorithm for solving linear congruences.
• Inclusion-Exclusion principles and permutation combinations are necessary for combinatorial counting problems.
• Problem-solving techniques for mathematical equations, such as the Qin Jiushao algorithm (Horner's method), are also relevant.

Search and Optimization

• Search algorithms require optimization techniques like pruning (e.g., in Mayan Puzzle), Iterative Deepening DFS (IDDFS), and Bidirectional BFS (e.g., for Sliding puzzles/Huarong Dao).
• Greedy algorithms are often used in conjunction with other methods, such as Binary Search + Greedy, Prefix Sums, or Dynamic Programming.

Dynamic Programming

• State transitions vary by problem structure, including环形, Tree DP, and Knapsack problems with divide and conquer strategies.
• Optimization techniques are vital to reduce time complexity: Prefix Sums, Monotone Queues, Heaps, Rolling Arrays, and two-array state updates.
• Advanced optimizations like Convex Hull Trick (Slope Optimization) may appear in complex scenarios.

Graph Theory

• Minimum Spanning Trees (MST) and their variants, including Second-best MST.
• Shortest Path algorithms (SPFA, Dijkstra) and problem transformation via graph modeling.
• Topological Sorting and DFS Order (Euler Tour / Timer entry-exit).
• Difference Constraints systems.

Strings and Trees

• String algorithms include KMP (focusing on the Next array logic) and String Hashing.
• Tree data structures involve Segment Trees, Binary Indexed Trees (Fenwick Trees), Sparse Tables (ST Table), and Binary Lifting for LCA.
• Tree Chain Decomposition offers an alternative method to Binary Lifting for path queries.
• Advanced connectivity algorithms include Point Divide and Conquer, Tarjan's algorithm (SCC/Articulation Points), and bitwise DP (State Compression DP).

Standard Library (STL)

• Efficient use of std::set and std::map (e.g., for simulating travel data).
• Stack and Queue implementations for specific logic like dual-stack sorting.
• Disjoint Set Union (DSU) for connectivity and cycle detection.
• Inversion pairs and base conversion are frequently required auxiliary utilities.

Time Complexity Estimation

Analyzing constraints is crucial for selecting the correct algorithm:

• N ≤ 20: Permutation-level complexity, suitable for search/DFS.
• N ≤ 100: O(N^3) feasible, such as Floyd-Warshall or simple search.
• N ≤ 1000: O(N^2) feasible, such as standard DP, SPFA, or MST.
• N ≤ 500,000: O(N log N) required, using Binary Search on answer, Sort, Segment Trees, ST Tables, or Tree Chain Decomposition. Note that naive DFS might stack overflow.
• N ≥ 1,000,000: O(N) or O(1) required, usually mathematical, greedy, or specialized DP.

Contest Strategy and Best Practices

Pre-Competition

• Configure the IDE environment immediately: set up code templates, include standard headers, and verify compiler functionality.
• Prepare standard algorithm snippets to avoid re-typing boilerplate.

Implementation Details

• Strictly check data types. Use long long for calculations involving large numbers, especially in Fast Power function parameters and accumulation.
• Use %lld format specifiers for 64-bit integers in C/C++.
• Prefer printf/scanf over cin/cout to avoid I/O timeouts, unless BigNum functionality is required.
• Construct the logic structure before coding. Define all required functions, inputs, and outputs. Estimate time and space complexity formally.
• Avoid keywords reserved by the system or standard libraries (e.g., variable names like time).
• Ensure recursive functions like DFS have proper return conditions and base cases.
• Be mindful of memset or memcpy usage inside loops, as they add linear overhead.
• Handle newline characters and input buffer flushing carefully.

Problem Solving Workflow

1. Analyze: Read data ranges and time limits carefully. Do not assume unstated constraints.
2. Verify: Prove the algorithm logic if possible. If not, test with edge cases and random small data.
3. Priority: Solve problems in order but check code for Problem 1 and 2 before moving to 3. If Problem 3 is not solved within 15 minutes, switch to writing a brute-force or partial score solution immediately.
4. Stability: Do not modify code in the last 15 minutes of the exam; errors introduced late are difficult to fix.
5. Consistency: Avoid peeking at others' answers. Focus on your own monitor and logic.
6. Review: Reserve at least 45 minutes for re-reading code, checking filenames (submitting brute-force instead of optimized solution), and final data testing.

Stress Testing (Duipai)

Always perform stress testing using a brute-force validator against the optimized solution. This is critical for catching logical errors missed by manual review.

Windows Scripting (Batch)

// data_generator.cpp
#include <cstdlib>
#include <ctime>

int main() {
    srand(time(0));
    // Generate random data logic here
    return 0;
}

@echo off
set LOOP=100
:loop
  data.exe > input.txt
  solution.exe < input.txt > sol_out.txt
  brute.exe < input.txt > brute_out.txt
  fc sol_out.txt brute_out.txt
  if errorlevel 1 goto break
  set /a LOOP-=1
  if %LOOP%==0 goto break
goto loop
:break
  echo Difference found!
pause

Linux Shell Scripting (NOI Linux)

#!/bin/bash
for i in {1..100}
do
    ./data_generator > input.txt
    ./optimized_solution < input.txt > output_opt.txt
    ./brute_solution < input.txt > output_brute.txt
    if ! diff output_opt.txt output_brute.txt > /dev/null ; then
        echo "Mismatch detected on iteration $i"
        break
    fi
done
echo "Stress test completed"