Saturday, September 30, 2017

Codechef Expert Certification

Expert
This level is intended to test that the candidate is an expert in algorithms and data structures, and has a deep understanding of the topics. Candidates can expect problems from the following topics to come in the exam.

Syllabus:

The syllabus for Expert Level is open-ended. Everything in Advanced Level will be included, along with:
  • Treaps
  • Persistent Data Structures
  • HLD
  • Centroid Decomposition
  • Computational Geometry
  • Fast Fourier Transforms
  • Game Theory
  • Gaussian Elimination
  • Dynamic Programming Optimizations
  • Advanced String algorithms (Tries, KMP, Aho-Corasik, Suffix arrays, Suffix trees)
  • Flows (Max-Flow, Min Cost Max Flow)

Learning Resources:

  • Coming Soon

Mock Test:

  • Coming Soon

Codechef Advanced Certification

Advanced
This level is intended to test that the candidate has a very good grasp of algorithms and data structures, and can solve most problems that arise in practice. Candidates can expect problems from the following topics to come in the exam.

Syllabus:

Everything in the Foundation Level, along with:
  • Heaps (priority queue)
  • Disjoint Set Union
  • Segment Trees
  • Binary Index Tree (Fenwick tree)
  • Trees (traversals, tree dynamic programming)
  • Finding Lowest Common Ancestors (O(log N) solution where N is number of nodes).
  • Graph Algorithms:
    • Finding connected components and transitive closures.
    • Shortest-path algorithms (Dijkstra, Bellman-Ford, Floyd-Warshall)
    • Minimum spanning tree (Prim and Kruskal algorithms)
    • Biconnectivity in undirected graphs (bridges, articulation points)
    • Strongly connected components in directed graphs
    • Topological Sorting
    • Euler path, tour/cycle.
  • Modular arithmetic including division, inverse
  • Amortized Analysis
  • Divide and Conquer
  • Advanced Dynamic Programming problems (excluding the dp optimizations which are added in expert level)
  • Sieve of Eratosthenes

Learning Resources:

Mock Test: