Skip to content

Latest commit

 

History

History
333 lines (269 loc) · 9.18 KB

README.md

File metadata and controls

333 lines (269 loc) · 9.18 KB
Raw

Competitive Programming Syllabus for IOI/ ICPC Training

1. Basic Concepts

  1. Introduction to Competitive Programming

    • Overview of competitive programming.
    • Setting up the environment (IDE, compilers).

  2. Basic Input/Output

    • Handling standard input and output.
    • Using files for input and output.

  3. Basic Data Structures

    • Arrays.
    • Strings.
    • Linked Lists.

  4. Basic Algorithms

    • Sorting (Bubble Sort, Selection Sort, Insertion Sort).
    • Searching (Linear Search, Binary Search).
    • Introduction to complexity analysis (Big O notation).

  5. Basic Math

    • Number theory (GCD, LCM, prime numbers).
    • Basic combinatorics (factorials, combinations, permutations).

2. Intermediate Concepts

  1. Advanced Data Structures

    • Stacks and Queues.
    • Hash Tables and Hashing.
    • Heaps and Priority Queues.
    • Trees (Binary Trees, Binary Search Trees).

  2. Graph Theory

    • Graph representations (adjacency matrix, adjacency list).
    • Breadth-First Search (BFS).
    • Depth-First Search (DFS).
    • Shortest Path Algorithms (Dijkstra’s, Bellman-Ford).

  3. Dynamic Programming

    • Basic concepts and state transition.
    • Memoization vs Tabulation.
    • Common DP problems (Knapsack, Longest Increasing Subsequence, etc.).

  4. Greedy Algorithms

    • Concept of greedy choice.
    • Common greedy problems (Activity Selection, Huffman Coding).

  5. Advanced Math

    • Modular arithmetic.
    • Matrix exponentiation.
    • Probability and combinatorics.

3. Advanced Concepts

  1. Advanced Data Structures

    • Segment Trees.
    • Fenwick Trees (Binary Indexed Trees).
    • Disjoint Set Union (Union-Find).
    • Suffix Arrays and Suffix Trees.
    • Tries.

  2. Advanced Graph Theory

    • Minimum Spanning Trees (Kruskal’s, Prim’s).
    • Network Flow (Ford-Fulkerson, Edmonds-Karp).
    • Strongly Connected Components (Kosaraju’s, Tarjan’s).
    • Topological Sorting.
    • Eulerian and Hamiltonian Paths.

  3. Advanced Dynamic Programming

    • DP on Trees.
    • DP with Bitmasks.
    • DP on Graphs.

  4. String Algorithms

    • String Matching (Knuth-Morris-Pratt, Rabin-Karp).
    • Z Algorithm.
    • Suffix Arrays and LCP Array.
    • Manacher’s Algorithm for Palindromes.

  5. Geometry

    • Basic geometry (points, lines, polygons).
    • Convex Hull (Graham’s Scan, Andrew’s Algorithm).
    • Line Intersection.
    • Closest Pair of Points.
    • Computational Geometry algorithms.

4. Expert Level Concepts

  1. Game Theory

    • Grundy Numbers.
    • Nim Game.
    • Minimax algorithm.

  2. Advanced Number Theory

    • Sieve of Eratosthenes.
    • Extended Euclidean Algorithm.
    • Chinese Remainder Theorem.
    • Fermat’s Little Theorem.
    • Fast Exponentiation.
    • Pollard’s Rho Algorithm for Prime Factorization.

  3. Advanced Graph Theory

    • Planar Graphs.
    • Graph Coloring.
    • Graph Isomorphism.

  4. Advanced Techniques

    • Mo’s Algorithm.
    • Heavy Light Decomposition.
    • Dynamic Trees (Link-Cut Trees).
    • Persistent Data Structures.

5. Problem-Solving Strategies

  1. Problem-Solving Techniques

    • Breaking down complex problems.
    • Identifying patterns.
    • Simplifying problems.

  2. Competitive Programming Practices

    • Participating in online contests.
    • Practicing previous IOI problems.
    • Time management during contests.

  3. Optimization Techniques

    • Reducing time complexity.
    • Reducing space complexity.
    • Trade-offs and approximations.

6. Advanced Topics for ICPC Training

1. Advanced Data Structures

  1. Advanced Trees

    • AVL Trees, Red-Black Trees.
    • Splay Trees.
    • Treaps.
    • K-D Trees.
    • Interval Trees.
    • Segment Trees with Lazy Propagation.
    • Persistent Segment Trees.
    • Heavy-Light Decomposition.
    • Dynamic Trees (Link-Cut Trees).

  2. Advanced Heaps

    • Fibonacci Heaps.
    • Pairing Heaps.
    • Binomial Heaps.

  3. Persistent Data Structures

    • Persistent Arrays.
    • Persistent Stacks and Queues.
    • Persistent Segment Trees.

  4. Sparse Tables

    • Range Minimum Query (RMQ).
    • Least Common Ancestor (LCA).

2. Advanced Algorithms

  1. Graph Algorithms

    • Centroid Decomposition.
    • Articulation Points and Bridges.
    • 2-SAT Problem.
    • Planarity Testing.
    • Tree Isomorphism.
    • Blossom Algorithm for Maximum Matching.
    • Dynamic Connectivity.

  2. Dynamic Programming on Trees and Graphs

    • Tree DP.
    • DP on DAGs.
    • Knuth’s Optimization.
    • Divide and Conquer DP.
    • Slope Trick.

  3. Advanced String Algorithms

    • Aho-Corasick Algorithm.
    • Suffix Automaton.
    • Suffix Trees.
    • Exponential Search.
    • Sparse Dynamic Programming.

  4. Geometry

    • Convex Hull Trick.
    • Sweep Line Algorithm.
    • Voronoi Diagrams.
    • Delaunay Triangulation.
    • Rotating Calipers.
    • 3D Geometry.

  5. Approximation Algorithms

    • Greedy Algorithms.
    • Local Search Algorithms.
    • PTAS and FPTAS.

3. Numerical Methods and Algebra

  1. Number Theory

    • Euler’s Totient Function.
    • Modular Inverse.
    • Integer Factorization.
    • Discrete Logarithm Problem.
    • Elliptic Curve Cryptography.

  2. Polynomial Algorithms

    • Fast Fourier Transform (FFT).
    • Number Theoretic Transform (NTT).
    • Polynomial Multiplication and Division.
    • Multipoint Evaluation.
    • Interpolation.

  3. Matrix Algorithms

    • Strassen’s Algorithm.
    • Matrix Exponentiation.
    • Rank and Inversion of Matrices.
    • Determinants and Applications.

4. Game Theory and Combinatorial Optimization

  1. Game Theory

    • Combinatorial Game Theory.
    • Sprague-Grundy Theorem.
    • Impartial and Partisan Games.
    • Alpha-Beta Pruning.

  2. Advanced Combinatorics

    • Inclusion-Exclusion Principle.
    • Pigeonhole Principle.
    • Generating Functions.
    • Burnside's Lemma.
    • Polya’s Enumeration Theorem.

  3. Network Flow

    • Dinic’s Algorithm.
    • Push-Relabel Algorithm.
    • Min-Cost Max Flow.
    • Bipartite Graph Matching.
    • Flow with Demands.

5. Advanced Problem-Solving Techniques

  1. Heuristics

    • Simulated Annealing.
    • Genetic Algorithms.
    • Ant Colony Optimization.

  2. Advanced Search Techniques

    • Beam Search.
    • Iterative Deepening.
    • Bidirectional Search.
    • A* Algorithm.

  3. Meta-Programming

    • Bit Manipulation Tricks.
    • Template Metaprogramming in C++.
    • Efficient Use of STL and Boost Libraries.

  4. Parallel Algorithms

    • Parallel Sorting Algorithms.
    • Parallel Dynamic Programming.
    • Use of OpenMP and MPI for Parallelism.

7. Resources for Training

  1. Books

    • "Introduction to Algorithms" by Cormen, Leiserson, Rivest, and Stein.
    • "Competitive Programming" by Steven Halim.
    • "Algorithm Design Manual" by Steven Skiena.
    • "The Art of Computer Programming" by Donald Knuth.
    • "Advanced Data Structures" by Peter Brass.
    • "Approximation Algorithms" by Vijay V. Vazirani.
    • "Computational Geometry: Algorithms and Applications" by Mark de Berg.

  2. Online Courses and Lectures

    • MIT OpenCourseWare (OCW).
    • Coursera (Algorithms Specializations).
    • edX (Algorithmic Design and Techniques).
    • TopCoder University.

  3. Competitive Programming Websites

    • Codeforces.
    • TopCoder.
    • AtCoder.
    • CodeChef.
    • HackerRank.
    • LeetCode.
    • SPOJ.

  4. Practice Contests and Platforms

    • ICPC Live Archive.
    • Kattis.
    • Timus Online Judge.
    • Google Code Jam Archives.
    • Facebook Hacker Cup Archives.
    • UVa Online Judge.
    • CodeChef.
    • CSES Problem Set.

8. Recommended Practices

  1. Regular Participation in Contests

    • Participate in regular online contests on platforms like Codeforces, AtCoder, and CodeChef.
    • Engage in virtual contests to simulate the ICPC environment.

  2. Group Study and Discussions

    • Form study groups to discuss problems and solutions.
    • Participate in mock contests and team problem-solving sessions.

  3. Deep Dive into Problem Analysis

    • Analyze previous ICPC problems and their solutions.
    • Study the problem-solving techniques used by top coders.

  4. Personal Projects

    • Develop small projects to implement and visualize algorithms.
    • Contribute to open-source projects related to algorithm implementations.

  5. Review and Refactor Code

    • Regularly review and optimize your code.
    • Learn to write clean, efficient, and bug-free code.

This comprehensive syllabus aims to provide a structured path for ICPC training, covering advanced topics and problem-solving techniques necessary for excelling in the competition.