Awesome Competitive Coding

A Curated list of Topic wise Theory and Questions to Get You Started On Competitive Coding.

Inspired by the awesome list thing. You might also like to read complete awesome-list.

Contributing

Kindly Go Through Contribution Guidelines First.

Topics

• Binary and Ternary Search
• Dynamic Programming
• Game Theory
• Graphs
• Greedy
• Maths
• Matrix Exponentiation
• Miscellaneous
• Prefix and Suffix Trees
• Segment Trees
• Trees

Binary and Ternary Search

Binary Search : The process of exploiting the property of an array of being sorted to arrive at answers of questions in non linear time.

Ternary Search : The process of exploiting the property of a function having double diffrential of a constant sign to arrive to results in non linear time.

• Theory

  • Hackerearth - Power of Binary search by Aman Goel (Easy).
  • Topcoder - Binary Search by lovro (Hard).
  • Ternary Search - Blog Post on Ternary Search.

• Questions on

  • Codeforces
  • A20j
  • Codechef

Dynamic Programming

Used to solve questions which can be broken down into smaller sub problems.

• Theory

  • Topcoder
  • Codechef

• Questions on

  • Hackerrank
  • spoj
  • More Problems on SPOJ
  • A2oj
  • Codeforces

Game Theory

Used to solve problems involving mathematical modelling of conflict and cooperation among rational players.

• Theory

  • Stanford - PDF on Combinatorial Games.
  • Wikipedia - Introduction to Nim Games.
  • Book - Composite Mathematical Games.
  • Book - Game Theory By Thomas S. Ferguson.

• Questions on

  • A2oj

Graphs

A graph consists of nodes and the interconnection between them.The problems involve finding shortest distance, connectivity and flow.

• Theory

  • Topcoder
    • Identifying a graph on Topcoder
    • Searching in a Graph
    • Path Algorithms
  • Codeforces - Important Graph Algorithms by PrinceOfPersia
  • Codechef - Tutorial on Graph Theory - part 1

• Questions on

  • Codeforces
  • Codechef
  • A2oj

Greedy

Greedy problems involve solving a problem statement considering the most greedy, i.e. most optimal solution at the given time without taking into consideration the future effects of it.

• Theory

  • Topcoder - Greedy is Good.
  • Stackoverflow. - Tutorial on how to spot a greedy algorithm.
  • Hackerearth - Tutorial on greedy algorithms by Akash Sharma.

• Questions on

  • Codeforces
  • A2oj

Maths

Problem related to mathematics are quite common in the domain of competitive programming.It involved topics like geometry, algebra, discrete mathematics and probability.

• Theory

  • Stanford - Stanford's Guide on Introduction To Competitive Programming.
  • Aduni - Course Guide to Discrete Mathematics.
  • Topcoder - Understanding Probability.

• Questions on

  • A20j
  • Codechef - Basic
  • Codechef - Advanced

Matrix Exponentiation

Used to solve problems which involve finding a solution to a given series by using exponentiation property on multiplication of matrices.The complexity is thus reduced to logrithmic from linear.

• Theory

  • zobayer - Introduction to Matrix exponentiations
  • Quora - Solving Dynamic Programming with Matrix Exponentiation.

• Questions on

  • A2oj

Miscellaneous

• Mo's Algorithm
  • Blog Post By Anudeep Nekkanti
  • Hackerearth
  • DQUERY on Spoj
  • FREQUENT on Spoj
• Persistant Segment Trees
  • Blog Post By Anudeep Nekkanti
  • MKTHNUM on Spoj
• Mobius Function
  • Dance With Mobius Function by Surya Kiran
• Treaps
  • Codeforces
  • Wikipedia
  • TREAP on Spoj
• Bit Manipulation
  • Hackerearth - Tutorial on Bit Manipulation by Prateek Garg.
  • Hackerrank - Questions On Hackerrank on but manipulation.
• Other Resources
  • Data Structures - A guide to high level data structures by PrinceOfPersia

Prefix and Suffix Trees

Tries are some kind of rooted trees in which each edge has a character on it.

• Theory

  • Wikipedia - Introduction to Tries.
  • Marknelson - Tutorial on prefix and suffix trees by Sartaj Sahni
  • Marknelson - Suffix Trees Explained.

• Questions on

  • Codechef
  • Another problem on Codechef
  • A2oj

Segment Trees

Segment tree is a tree for which each of it's nodes belongs to an interval.

• Theory

  • Hackerearth - Segment trees for Beginners by Ayush Agrawal.
  • Codeforces - Everything about Segment trees by PrinceOfPersia
  • Lazy Propogation - Segment Trees and Lazy propogation.Solving problems related to updation of segment tree in logrithmic time.

• Questions on

  • Codechef
  • A2oj

Trees

A tree is a data structure made up of nodes or vertices and edges without having any cycle.

• Theory

  • Hackerearth - Baisc introduction to trees and terminologies related to it by Anuj Garg
  • Wikipedia - Tree (data structure)

• Questions on

  • Hackerrank
  • Codechef
  • A2oj
  • Codeforces