Skip to content

Competitive_Programming.md

Latest commit

 

History

History
57 lines (50 loc) · 6.11 KB

Competitive_Programming.md

File metadata and controls

57 lines (50 loc) · 6.11 KB

Track - II - Competitive Coders

TL;DR One stop bookmark for Competitive Programming
You are in the jungle. You have a pocket-knife. Someone asks you to kill a mountain lion.

Years of training has taught you well. You use your knife to sharpen a stick. You cut vines to lash sharp stones on one end. Maybe you're from a top university, and you've learned to extract essential ingredients from plant and insect life around you to fashion a poison to tip your weapon with.

Convinced that you have an effective and efficient way to kill the lion, you set forth to accomplish your task. Maybe your stick is too short, or your poisons don't work. It's okay - you live to refine your method and try again another day.

That's "real-life" programming.

In competitive programming, you start out with the same resources (a pocket-knife), except you have 2 minutes to kill the lion. Source

1. World of competitive programming

What is ACM ICPC:
The ACM ICPC is considered as the “Olympics of Programming Competitions”. It is quite simply, the oldest, largest, and most prestigious programming contest in the world. https://www.geeksforgeeks.org/how-to-prepare-for-acm-icpc/

2. Algorithms and how to learn them

Well, Introduction to Algorithm by CLRS is considered as the bible for Algorithms.

3. Mathematics for coding

Just revise Linear Algebra, Combinatorics (Kenneth's DMS) and every 1 out of 2 will require atleast high school maths to solve.

4. Standard Template Library in C++

Resources:

Below content is taken from CS755, CSE, IIT B Description Course Content :

  1. Revision of Basic Geometry/Euclidean Geometry/Coordfinate Geometry/ [3-D variants of everything].
  2. Revision of Data Structures (Basic): (i) Arrays/Stacks/Queues, (ii) Singly/Doubly Linked List : Hash Tables, Circular linked list / queue, Binary/nary Trees, Heaps
  3. Data Structures (Advanced): i) Trie (Keyword tree) ii) Segment Trees iii) Fenwick(Binary Indexed) trees, iv) Disjoint Union data structure, Range minimum Query(RMQ), Customized interval/segment trees (Augmented DS)
  4. Dynamic Programming
  5. String Algorithms: i) KnuthMorrisPratt algorithm, ii) Aho Corasick algorithm, iii) Suffix Arrays iv) Suffix Trees vii) Manachar’s algorithm to find Length of palindromic substring of a string centered at a position for each position in the string. Runtime -> O(n) ix) Multi-dimensional pattern matching. x) Problems on Strings [can be solved with a variety of techniques]
  6. Basic Graphs [beginner]: Representation of graphs as adjacency list, adjacency matrix, incidence matrix and edge list and uses of different representations in different scenarios, i) Basic Graph algorithms ii) Breadth First Search. iii) Depth First Search. iv) Strongly Connected Components. v) Biconnected Components, Finding articulation points and bridges vi) Shortest path algorithms, vii) Floyd Warshall algorithm - viii) Minimum Spanning Tree ix) Flood-fill algorithm x) Topological sort xi) Bellman-Ford algorithm. xii) Euler Tour/Path.
  7. Flow networks/ matching etc etc. [Intermediate/Advanced]: i) Maximum flow using Ford Fulkerson Method. ii) Maximum flow using Dinics Algorithm.
  8. Counting: i) Basic principles - Pigeon hole principle, addition, multiplication rules, ii) Inclusion-exclusion, iii) Special numbers iv) Advanced counting techniques - Polya counting, burnsides lemma
  9. Computational Geometry: (i) Graham Scan algorithm for Convex Hull O(n * log(n)), (ii) Online construction of 3-D convex hull in O(n^2), (iii) Bentley Ottmann algorithm to list all intersection points of n line segments in O((n + I) * logn). (iv) Rotating Calipers Technique (v) Line Sweep/Plane Sweep algorithms -Area of Union of Circles, Delayunay Triangulation of n points in O(n * logn), Voronoi Diagrams of n points in O(n * logn) using Fortunes algorithm, Point in a polygon problem, Problems on computational geometry
  10. Combinatorial Games and Basics of Game theory: i) Basic principles and Nim game, Hackenbush,
  11. Linear Algebra, Matrix Operations, Polynomials, Permutation cycles, Group Theory, Generating functions,
  12. Search Techniques/Bruteforce writing techniques/Randomized algorithms: Backtracking - [Beginner], Dancing Links and Algorithm X given by Knuth - [Advanced], Binary Search - [Beginner], Ternary Search - [Intermediate], Meet in the middle [Intermediate], Hill Climbing [Advanced], Regular Iteration to reach a fixed point [Advanced], Randomized Algorithms [Intermediate]
  13. General programming issues in contests: Arithmetic Precision - [Beginner], Representing sets with bitmasks and manipulating bitmasks - [Beginner].

References Texts / References :

  1. Halim, Steven and Halim, Felix, Competitive Programming 3, 2013. Ebook available at lulu.com. Site associate with with the book is http://cpbook.net
  2. Knuth, Donald E. The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison Wesley, 1973.
  3. Weiss, Mark Allen. Data structure and algorithm analysis in C++, 4th Ed, Pearson, 2014.
  4. Herstein, Israel N. Topics in algebra. John Wiley & Sons, 2006.
  5. Cormen, Thomas H., Leiserson, C. E., Rivest, R. L., & Stein, C. Introduction to algorithms (Vol. 6). Cambridge: MIT press. 2001.
  6. Knuth, Donald E., Graham, Ronald L., and Patashnik, Oren. Concrete mathematics. Adison Wesley. 1989.
  7. Dasgupta, Sanjoy, Papadimitriou, Christos H., and Vazirani, Umesh, Algorithms. McGraw-Hill, Inc., 2006.
  8. Topcoder tutorials - https://www.topcoder.com/community/data-science/data-science-tutorials/
  9. Nite Nimajneb’s site - http://comscigate.com/Books/contests/icpc.pdf
  10. Slides from a Stanford Course - http://web.stanford.edu/class/cs97si/