So I made this listing for topic wise coding resources. It is open sourced here Thought of sharing it here too!

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
• Flow
• 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

- A2oj

- Codechef

Dynamic Programming

--- Used to solve questions which can be broken down into smaller sub problems.It involves the technique of saving the result of a problem for future reference.

• Theory

- Topcoder — Dynamic Programming from Novice to Advanced.

- Codechef — Tutorial on Dynamic Programming.

• Questions on

- Hackerrank

- spoj

- More Problems on SPOJ

- A2oj

- Codeforces

Flow

• Theory

- Topcoder — Max Flow Part 1

- Topcoder — Max Flow Part 2

• Questions

- spoj

- A2oj

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.
  • Wikipedia — Sprague Grundy Theorem.
  • Topcoder — Introduction to Algorithmic Games.

• 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

- A2oj

- 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 bit 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 node represents an interval.

• Theory

• Hackerearth — Segment trees for Beginners by Ayush Agrawal.

• Codeforces — Everything about Segment trees by PrinceOfPersia

• 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](https://www.hackerearth.com/users/

• Questions on

- Hackerrank

- Codechef

- A2oj

- Codeforces

Hey Codeforces! This is to inform you guys that I am working on an addition to the Awesome series for people who want to start Competitive Coding.

The repository can be found here.

It is in its grooming stage and is not yet added to the Awesome list.

I would invite everyone to please contribute to the list.

It still lacks links to some of the advanced topics.You can file directly for a pull request or post suggestions in the comments and I would be more than happy to add them to the list.

Thankyou

Happy Coding!

552A - Vanya and Table For each rectangle she adds ,the value of all the cells in that rectangle is increased by one. Hence it is obvious that if a rectangle of side n*m is added ,the ans increases by n*m

for each rectangle

scan(x1)

scan(y1)

scan(x2)

scan(y1)

ans=ans+(x2-x1+1)*(y2-y+11)

Time Complexity O(n)

My submission:: 11637017

552B - Vanya and Books By number of digits the question means the total number of digits.

Hence number of digits for 1=1

number of digits for 10=2

number of digits for 100=3

We need to write all numbers from 1-n We find the number of digits in n (lets call it k).

Ans=(the number of digits in all 1 digit numbers)+(number of digits in all 2 digit numbers)+...(number of digits in all k-1 digit numbers)+number of digits from 10^k to n.

As the number of p digit numbers = 9*pow(10,p-1)

for(i from 1 to k-1)

• ans=ans+i*(9*pow(10,k-1))

And finally ans=ans+(n-pow(10,k-1)+1)*k

My submission: O(log(n))

My submission :11639835

552C - Vanya and Scales The problem is a simple case of recursion.We have weights of the form w^k(0<k<100).

if there exists a combination of weights that forms the mass M , then

M=summation(w^k1)-summation(w*k2)

Hence M has to be of the form w*t+k (-1<=k<=1)

t also has to be of the form w*t1+k1 (-1<=k1<=1)

Hence the recursion continues . The base case is when t<w.The answer will be yes if t=w-1||t=1||t=0

Time Complexity O(log(M))

My submission:11644642

552D - Vanya and Triangles

The problem can be solved by a simple brute force for all the points in pairs of 3.If the area of a given pair of 3 triangles is not zero , then it is a possible triangle.

• for(i from 0,n-1)
• • for(j from i,n-1)
• • • for(k from j,n-1)
• • • • if (area (i,j,k)!=0)
• • • • ans++;

Time Complexity O(n^3)

The problem can however be solved in n^2 complexity.By iterating over all points in pairs of 2 , we can store their slopes in a map.

Then on iterating over the map we can find the number of triangles which wont contribute to the answer.

for(it in map)

• k += (it*(it-1)*(it-2)/6)

answer=n*(n-1)*(n-2)/6-k

Time Complexity O(n^2*log(n))

My submission: 11727314

552E - Vanya and Brackets

An easy analysis shows that the brackets must be placed adjacent to * sign since they wont have any effect next to a + sign.

We need to store the indexes of all the * in the string and iterate over all possible pairs. One thing to keep in mind is the maximum case may be one in which the brackets starts at the 0th index or the one in which it ends at the last index.

Time Complexity O((length of string)*15*15)

My submission: 11726590