DOCSEARCHbyAlgolia
Submit Docs

0xcjy's Blog and OI Tutorials

website·Indexed 31 days ago

https://0xcjy.github.io

A personal technical blog and resource hub featuring comprehensive Olympiad in Informatics (OI) tutorials on graph theory, dynamic programming, and tree structures (LCA, Heavy-Light Decomposition). It includes a code template collection, an HTML reference manual, and various developer tools such as a memory calculator, bubble sort visualizer, and the UmaDecryptor project.

Tokens
21.9K
Snippets
47
Records
109
Agent score
75%

What's inside 0xcjy

  1. Overview of Graph Theory concepts and algorithms

    Graph theory focuses on the relationship between vertices and edges. Graphs are categorized by direction (Directed Graphs, such as DAGs, and Undirected Graphs) and by weight (Weighted Graphs, used in network flow, and Unweighted Graphs).

    Key algorithmic categories include:

    • Traversal: DFS and BFS, which form the basis for topological sorting and connected component analysis.
    • Shortest Path: Dijkstra (for graphs without negative edges), Bellman-Ford (includes negative edge detection), and Floyd-Warshall (for all-pairs shortest paths).
    • Minimum Spanning Tree (MST): Prim's and Kruskal's algorithms, typically used for network cabling/layout problems.
    • Connectivity: Tarjan's algorithm for Strongly Connected Components (SCC) and algorithms for Biconnected Components (identifying articulation points and bridges).
    • Advanced Topics: Network Flow (Max-Flow Min-Cut Theorem), Bipartite Matching (Hungarian algorithm), and Eulerian Circuits (Hierholzer's algorithm).

  2. Overview of Mathematical Topics for Competitive Programming

    Mathematical requirements in competitive programming primarily focus on Number Theory, Combinatorics, and Computational Geometry. Key areas include:

    • Number Theory: Prime sieves (Eratosthenes, Linear Sieve), Congruence Theory (Fermat's Little Theorem, Extended Euclidean Algorithm), and Discrete Logarithms (BSGS algorithm).
    • Combinatorics: Permutations and combinations counting (Inclusion-Exclusion Principle, Catalan numbers), Probability and Expectation (Markov chains), and Game Theory (SG function).
    • Algebraic Tools: Matrix Fast Exponentiation for accelerating recurrences and Gaussian Elimination for solving systems of linear equations.
    • Computational Geometry: Vector cross products (Graham scan for convex hulls), Plane sweeping (closest pair of points), and circle intersection determination.
    • Numerical Analysis: Newton's method for root-finding and Fast Fourier Transform (FFT) for polynomial multiplication to reduce time complexity.

  3. Overview of common data structures for competitive programming

    Data structures are the foundation of algorithm implementation and are categorized into three main types: linear, tree-based, and hash structures. Key structures include:

    • Linear: Arrays, Linked Lists, Stacks (LIFO), and Queues (FIFO) which support DFS/BFS.
    • Tree-based: Binary Trees, Heaps (Priority Queues) used for fast extreme value queries in Dijkstra's algorithm.
    • Hash Structures: Hash Tables providing O(1) lookup via hash functions, requiring collision handling (Open Addressing or Chaining).
    • Specialized/Advanced Structures:
      • Disjoint Set Union (DSU): Solves set merging and connectivity (e.g., Kruskal's algorithm).
      • Fenwick Tree (Binary Indexed Tree): Optimized for single-point updates and prefix sums.
      • Segment Tree: Optimized for range modifications and range queries.
      • Hybrid/Modified structures: Skip Lists and Blocked Linked Lists.

  4. Overview of UmaDecryptor

    UmaDecryptor is a decryption tool for AssetBundle resources from the game Umamusume (Japanese Windows version). It uses decryption logic derived from UmaViewer to crack encrypted assets so they can be loaded into the Unity engine. The tool is available in Python and C++ versions, with the C++ version generally offering faster performance.

  5. Overview of Search Algorithms in Competitive Programming

    Search algorithms are a core area of competitive programming, categorized into blind search and heuristic search.

    • Blind Search: Includes Depth-First Search (DFS) and Breadth-First Search (BFS).
    • Heuristic Search: Includes A* and IDA* search, which use evaluation functions (e.g., Manhattan distance) to guide the search direction for complex problems like the 15-puzzle.

    Key techniques to manage exponential complexity include:

    • Pruning: Pre-determining invalid paths to reduce computation (e.g., constraint propagation in Sudoku).
    • State Compression: Using bitwise operations to represent states.
    • Memoization: Storing previously computed results to avoid redundant calculations.

  6. Overview of the Informatics Olympiad (OI) Competition

    The Informatics Olympiad (OI) is a global computer science competition for secondary school students focusing on algorithm design, programming skills, and computational thinking. Key areas of study include:

    • Core Algorithms: Dynamic Programming, Search, Graph Theory, and Data Structures.
    • Mathematical Modeling: Number Theory, Combinatorics, and Probability/Statistics.
    • Technical Requirements: Proficiency in languages like C++ and Python, and familiarity with tools such as the Standard Template Library (STL) and Binary Indexed Trees (Fenwick Trees).

    The competition hierarchy typically consists of provincial leagues (NOIP), national finals (NOI), and international competitions (IOI).

  7. Overview of Heavy-Light Decomposition (HLD)

    Heavy-Light Decomposition (HLD) is a technique used to partition a tree into several chains to efficiently maintain and query information along paths or within subtrees. By decomposing the tree, any path between two nodes can be represented as a set of at most O(log n) continuous chains. Because nodes on these chains have contiguous DFS orders, sequence-based data structures like Segment Trees can be used to perform path modifications, path queries, subtree modifications, and subtree queries. Typical time complexity for these operations is O(log² n), though it can be O(log n) with advanced data structures. HLD can also be used to find the Lowest Common Ancestor (LCA) in O(log n) time with a small constant factor.

  8. Overview of Heavy-Light Decomposition (HLD)

    Heavy-Light Decomposition (HLD) is a technique used to flatten a tree structure into a linear sequence. This allows developers to use efficient linear data structures (like Segment Trees or Fenwick Trees) to perform path queries (e.g., sum, max, min) and path updates on a tree. The core idea is to decompose the tree into 'heavy chains' such that any path from the root to a leaf crosses at most O(log n) light edges, ensuring that path operations can be completed in O(log² n) time.

  9. Overview of common string algorithms and their use cases

    String algorithms primarily focus on matching, storage, and transformation. Key algorithms include:

    • KMP Algorithm: Uses a partial match table to achieve O(n) pattern matching; often used for determining cycle periods.
    • Trie Tree: Organizes string sets to support efficient prefix retrieval.
    • AC Automaton: Combines Trie and KMP to handle multi-pattern matching (e.g., sensitive word filtering).
    • Suffix Array (SA): Constructed via the doubling method; used for problems like finding the longest repeated substring.
    • Hashing Techniques: Rolling hashes and double hashing are used for fast substring similarity comparisons.
    • Manacher's Algorithm: Specifically used to find the longest palindromic substring.
    • Sequence Automaton: Used to judge the existence of subsequences.
    • Suffix Automaton (SAM): Highly efficient for processing complex substring problems.

  10. Overview of Heavy-Light Decomposition (HLD)

    Heavy-Light Decomposition (HLD) is used to handle path and subtree queries/updates on a tree by transforming the tree structure into a linear structure. This allows the use of segment trees or Fenwick trees to reduce the time complexity of path operations from O(n) to O(log²n) and subtree operations to O(log n).

    Key Concepts:

    • Node Size: The number of nodes in the subtree rooted at that node.
    • Heavy Child: The child node with the largest subtree size.
    • Heavy Edge: The edge connecting a node to its heavy child.
    • Light Edge: Any edge connecting a node to a child that is not the heavy child.
    • Heavy Chain: A path consisting of continuous heavy edges. The node with the minimum depth in a heavy chain is called the Chain Head (top).

  11. Overview of the Advanced Color Previewer

    The Advanced Color Previewer is a tool for intuitively previewing and adjusting Hex, RGBA, and gradient colors. It provides real-time visual feedback and generates the corresponding code for use in projects.

  12. Understand Dynamic Programming (DP) core concepts and patterns

    Dynamic Programming is a method for solving complex problems by breaking them down into overlapping subproblems and storing intermediate results to avoid redundant calculations. There are two primary implementation patterns:

    1. Top-Down (Memoization): A recursive approach that stores the results of function calls.
    2. Bottom-Up (Iterative/Tabulation): An iterative approach that fills a table (DP array) from the smallest subproblems up to the target solution.

    The core of DP is designing the state transition equation (e.g., defining dp[i][j] to represent the minimum operations to transform the first i characters of string A to the first j characters of string B in the Edit Distance problem).