DOCSEARCHbyAlgolia
Submit Docs

csd.io Algorithm and Mathematics Documentation

website·Indexed 30 days ago

https://justincsd.github.io/csd.io/

A comprehensive collection of mathematical and algorithmic notes covering number theory (Meissel–Lehmer, CRT, Euler's totient function, Bézout's lemma), linear algebra (eigenvalues, eigenvectors, inner products), calculus (limits, derivatives, integrals), game theory (Nim and Anti-Nim), and probability (Union Bound, Markov inequality). It also includes guides on bitwise operations, binary set operations, and numerical methods like Newton's method and Lagrange interpolation.

Tokens
191.9K
Snippets
563
Records
1.3K
Agent score
74%

What's inside csd.io

  1. Overview of Chinese Informatics Olympiad (OI) Advanced Competitions

    Following the initial stages of CSP and NOIP, high-level Chinese OI competitions include:

    • WC (Winter Camp): Includes training and an exam used to select the National Candidate Team (15 people) from the National Training Team (50 people). High-performing NOIP and CSP-S participants may also attend.
    • APIO (Asia-Pacific Informatics Olympiad): A regional competition for students in the Asia-Pacific. China holds a mirror competition in early May.
    • CTS (China Team Selection Competition): Used to select the final National Team (4 regulars, 2 alternates) from the Candidate Team to compete in the IOI.
    • NOI (National Olympiad in Informatics): The primary national competition.
    • IOI (International Olympiad in Informatics): The global annual competition. Each country sends four participants. Problems typically feature subtasks with partial scoring.

  2. Overview of Informatics Olympiad (OI) competitions

    The Informatics Olympiad (OI) is a subject competition for middle and high school students focusing on algorithms, data structures, and mathematical knowledge to solve practical problems via computer programming. In China, the primary language permitted is C++. Competition problems typically include traditional problems (file-based input/output) and non-traditional problems (interactive, code completion, or answer-only submissions).

  3. Overview of Mathematics for Competitive Programming (OI)

    In algorithm competitions, mathematics is primarily focused on discrete and concrete areas such as number theory, permutations and combinations, probability/expectation, and polynomials. These concepts are often used to optimize other algorithms and data structures. Examples of application include:

    • Using polynomials to optimize convolution-style knapsack problems for string-related tasks.
    • Using generating functions and FFT-based divide-and-conquer algorithms to solve recurrence problems based on permutations, combinations, or probability.
    • Utilizing modular arithmetic and cycle analysis to determine possible weight sums of non-simple paths on graphs, maintained via weighted Disjoint Set Union (DSU).

  5. Overview of the 'Catching People' game rules

    The 'Catching People' game is a social activity for students based on honesty and integrity. It is played primarily within school grounds, with a designated 'Catching People Day' on September 21st annually. The game relies on player honesty as there are no monitoring devices used.

  6. Overview of International Informatics Olympiads and Training

    Various countries and regions host their own OI competitions, often used for practice by competitive programmers:

    • USACO (USA): Monthly online contests from winter to early spring. Divided into four tiers: Bronze (beginners), Silver (basic algorithms/DS), Gold (complex algorithms/DP), and Platinum (advanced design). Popularly hosted on Luogu in China.
    • POI (Poland): Consists of three rounds and the ONTAK training camp. Often found on BZOJ.
    • COCI (Croatia): Wide range of difficulty. Problems, data, and solutions are periodically updated.
    • JOI (Japan): Includes Preliminaries, Finals, Spring Camp (JOISC), and Open Contests. Most problems are available on AtCoder.
    • ROI (Russia): Municipal, Regional, and Final stages. Some problems are available on Codeforces.
    • CCC & CCO (Canada): CCC Junior/Senior align with NOIP levels; CCO Gold requires NOI Silver level proficiency. Available on DMOJ.
    • NOI SG (Singapore): Consists of an Online Qualification and a Final Contest. Materials are available on their official GitHub.
    • Regional Olympiads: BalticOI, BalkanOI, and CEOI are high-difficulty competitions for their respective European regions.

  10. Overview of Mathematics for Competitive Programming (OI)

    In algorithm competitions (OI), mathematics is heavily focused on discrete and concrete areas such as number theory, permutations and combinations, probability/expectation, and polynomials. These mathematical concepts are often used to optimize other algorithms and data structures. Examples of application include:

    • Using polynomials to optimize convolution-style knapsack problems for string-related tasks.
    • Using generating functions and FFT-based divide-and-conquer algorithms to solve recurrence problems based on combinatorics or probability.
    • Utilizing modular arithmetic and cycle analysis to determine possible weight sums of non-simple paths on graphs, maintained via weighted Disjoint Set Union (DSU).

  11. Overview of International Informatics Olympiads by Region

    Various countries and regions host their own OI competitions, often used as training or qualification for the IOI:

    • Poland (POI): Consists of three rounds (online/open, then two formal rounds) and the ONTAK training camp.
    • Croatia (COCI): Wide range of difficulty from beginner to advanced.
    • Japan (JOI): Includes Preliminaries, Finals, Spring Camp (JOISC), and the JOI Open Contest. Many problems are available on AtCoder.
    • Russia (ROI): Progresses through Municipal, Regional, and Final stages. Some problems are available on Codeforces.
    • Canada (CCC & CCO): CCC Junior/Senior align with NOIP levels; CCO requires higher proficiency (NOI Silver level for gold medals).
    • Singapore (NOI SG): Consists of an Online Qualification Contest and a Final Contest.
    • Taiwan: Includes Regional and National competitions and the TOI (Information Study Camp).
    • Regional Olympiads: BalticOI (Baltic states), BalkanOI (Balkan region), and CEOI (Central European Olympiad) are known for high difficulty.