Training path for Competitive Programming

Training path

We want to establish a knowledge base of unprecedented! We want this page to contain a more complete list of what needs to know an Olympic success. helps us and you!
Another list http://www.scribd.com/doc/58361421/Programming-Camp-Syllabus

Data Structures

• Lists, stacks, queues
• Deque
• Hash tables
  • Cuckoo hashing
• Bloom filters
• Skiplists

• Indexed binary trees
  • Educational Application Archive
• Priority queues
  • Heap sites
  • Mergeable heaps (heaps maxophobic are the simplest)
  • For small integer costs an array of lists

• Structures disjoint sets
• Trees intervals
• Tries
• Binary search tree ( Treapuri , AVL, red-black trees)
• Orthogonal searches. Quad trees, kd-trees

Algorithms and programming techniques

Mathematics

• Mathematical induction
• Euclid's Algorithm
• Binary GCD
• Sieve of Erathostene
• Gray code
• Solving modular linear equations
• Fermat's little theorem
• Chinese Theorem debris
  • Problems: eval scrap gears in action
• Big numbers: addition, subtraction, multiplication, division, radical
• Recurrent and rapid exponential matrices (+ rapid assessment logarithmic expressions using exponential time), the k-th Fibonacci term
• The principle of inclusion and exclusion
  • Issues cowfood , indep , frac
• Systems of linear equations (Gauss)
  • Theory:
    • Gaussian elimination
    • Row echelon form
  • Issues SGU To 275 or not to xor xor . champion Xor SGU 260 Puzzle UVa 10808 UVa 326 UVa 10014 BColor Laser XOR ing TC TC Escape the Jail Register CEOI 2003 horror tunnel SGU 200 TC CoinGame
• Simplex
• Floyd's cycle finding
• Combinatorics
  • Generating permutations , permutations with repetition, arrangements, combinations , Stirling , Catalan, Bell, Fibonacci
  • Transition from combination / permutation to index them and vice versa
  • Prüfer code. Counting trees

Geometry

Computer Graphics FAQ
courses after Computational Geometry: Algorithms and Applications, Mark de Berg, M. van Krefeld, M. Overmars, O. Schwarzkopf

• Intersection of two segments
• The closest points of the plan
• Point inside a polygon
  • http://geometryalgorithms.com/Archive/algorithm_0103/algorithm_0103.htm
  • http://tog.acm.org/editors/erich/ptinpoly/
• Point in convex polygon in O (log n)
  • http://geometryalgorithms.com/Archive/algorithm_0103/algorithm_0103.htm # Monotone% 20Polygons
• Pick's Theorem
  • problem trees
• The area of ​​a polygon
• Center of gravity of a polygon
• Polygon triangulation in O (n ^ 2)
• Intersection of two circles
• Minimal enclosing circle
• Convex hull
  • Educational Application Archive
  • http://www.algorithmist.com/index.php/Monotone_Chain_Convex_Hull
  • http://en.wikipedia.org/wiki/Gift_wrapping_algorithm
  • Application - onion peeling in O (n ²⁾
• Swing vertical / radial
  • radial sweep
    • Given a set S of n points in the plane. Determine the fixed circle of radius R that covers as many points of S. O (n ^ 2 log n)
    • Given a set S of n points in the plane. To find a line that passes through the maximal number of points in S. O (n ²⁾ with hashuri angles for O (n ^ 2 log n) with radial scanning.
    • Given a set S of n segments in the plan. To find a line that intersects the maximum number of segments in S. O (n ^ 2 log n) with radial scanning.
    • Building visibility graphics.
• Rotating calipers
  • problem rhubarb
  • problem popandai2
• Intersection of convex polygons
• Intersection of half-planes (without dualization)
  • problem room
• Dualize

• forum thread

Sorting and searching

• Shell sort, merge sort, heapsort, quicksort, counting sort, radix sort, sorting by comparison
• Order statistics
• Search binary / ternary and applications
• Hill climbing

Greedy

• Huffman
• Job scheduling

Dynamic programming

• DP Resource [MIT]
• Expression syntax optimal matrices
• The longest ascending subsequence O (N * log N)
• Knapsack
  • Bitwise Knapsack
• The longest common subsequence
• Distance editing 2 words
• Hamiltonian cycle in O (n ² * ^{2 n)}
  • problem adn , application in educational archive
• Dynamics in 3 ⁿ
  • explanation , problem
  • scara2
  • coloring
• Optimal search tree in O (n ^ 2)
• Dynamic trees
• Include the possibility of covering a table with dominoes
• Memoization (trading space for time)

Graphs

• Browse
  • DFS , BFS , BFS meet in the middle
  • Components biconexe
  • Hard-Related Components
  • Sort topological
  • Eulerian cycle

• Shortest paths
  • Dijkstra (with Heaps, with links set with IS NOT sites, with tail as TC - Cosmin know)
  • Dijkstra low costs ;) how to use the issue of car
  • A * has a lot of intuitive appeal for me. If you compare Dijkstra's round. A *, Dijkstra's is like a puddle of water flooding outwards on a flat floor, Whereas A * is expanding like the same puddle on the floor Toward bumpy and graded to drain (the target node) at the Lowest point in the floor. INSTEAD of spreading out evenly on all sides, the water seeks the path of Least Resistance, only trying new paths When Something Gets In its way. The heuristic function is what provides the 'degree' of the hypothetical floor.
    • A * is used a lot in the game industry, being a very fast algorithm in practice. An example where it is used is the strategy game Starcraft.
  • Floyd-Warshall
  • Bellman-Ford
    • Usually simpler to implement and about the same speed as Dijkstra with Heaps
    • System of inequalities
    • Minimum average cost cycle
• Flow
  • Edmonds-Karp
  • Minimum Cut
  • DINICA
  • Minimum cost maximum flow
  • Flow with lower capacity
  • Movement
  • Chinese postman problem
    • issue directions
• Trees
  • The diameter of a tree center
  • Test whether two trees are isomorphic
  • Prüfer code
• APM
  • First
  • Kruskal
  • The second APM
  • APM in directed graph
  • Kirchhoff's matrix tree theorem
• For bipartite graphs: maximum coupling , minimal support, plenty maximum independence
• LCA , RMQ , Level Ancestor, Tree decompositions
• Coloring of edges, complete graphic / bipartite / some (Vizing's theorem)
• Planar Graphs
  • problem count
• Graphs tour / Hamiltonian cycle
  • problem Ride
• Implication graph and 2-SAT

Strings

• Hashuri
• KMP
• Strings of suffixes
  • While linear
• Aho-Corasick .

Formal languages ​​and finite automata

• Evaluations of arithmetic expressions
• CYK
• Matching with wildcards
• Building a vending machine to accept a set of words
• Simplification of automatic
• Automatic equivalents
• forum thread

Game Theory

• Nim
• Sprague-Grundy numbers
• Min-max
• Alpha-beta

Various

STL (Standard Template Library)

• vector, deque, stack, list
• string
• set, map, hash_map
• peer
• sort
• priority_queue
• bitset
• iterators

Searches

• backtracking
• iterative deepening
• branch and bound

Optimizations

• Parsing
• Working with bits
• Brute force
  • dancing links

Working with memory

• Cacheuri memory
  • problem ancestry
• free lists
  • problem tube

Bulan

• Randomization (2 to 8, k-opt)
• Constants
• Interpolation Taylor / Gauss polynomial formula

Smenuri

• The trick 'of Cod (+ LCA in sqrt (n))
  • problems: skiing ,
• The trick 'of Mars
  • problem cubes
• Meet in the middle

Useful Books

• Ioan Tomescu
  • "Problems of Combinatorics and Graph Theory" (which was given to ONI or batch almost every year about a problem or more)
  • "Combinatorics and Graph Theory"
• John Cuculescu
  • "International Mathematical Olympiad of Students'
• EA Morozova, IS Petracov, VA Skvortova
  • "International Mathematics Olympiad"
• "Mathematical Problems KVANT translated from Soviet magazine"
• AM Iaglom, IM Iaglom
  • "Basic Problems treated neelementare"
• Thomas H. Cormen, Charles E. Leiserson, Ronald R. Rivest
  • "Introduction to Algorithms"
• DE Knuth
  • "The Art of Computer Programming" ("The Art of Computer Programming")
  • "Concrete Mathematics"
• Jon Bentley
  • "Programming Pearls"
• Steven Skien
  • "The Algorithm Design Manual"
• M. Crochemore and W. Rytter
  • Jewels of Stringology
• Mark de Berg
  • "Computational geometry"
• Emanuela Cerchez and Marinel Serban
  • "Programming in C / C + + for high volume 1,2,3"