Competetive Programming Guide

Month 1

Week 1

Dynamic Programming

• Read Dynamic Programming Notes Hackerearth
• Read DP Tutorial involving grids
• Read TopCoder Tutorial on DP
• Solve the following classical problems:
  • Coin change problem
  • Unbounded Knapsack
  • Longest common subsequence
• Solve the following MISC problems:
  • Cutting
  • The Great Julya Calendar
  • Shashlik Cooking
  • Divisibility by Eight
  • Bishwock
  • Functions again
  • An impassioned circulation of affection
  • Color Stripe
  • Prime XOR
  • HackerRank City

Contests

• Educational DP contest on AtCoder
• DSA Learning Series: Week 7 - DP By CodeChef
• Marathon DP - 01
• V Planet DP - 2
• V Planet DP - 3
• V Planet DP Week 5

---

Week 2

Trees & Graphs

Trees

☆	Problem Link	Finished
★☆☆	Diameter of a Binary Tree
★☆☆	Path Sum
★★☆	K-th smallest element in a BST
★★☆	Find duplicate subtrees
★★☆	Lowest Common Ancestor of a binary tree
★★★	Sum of distances in tree

Graphs

BFS and DFS

• Ones and Zeroes
• Prime Path

Strongly Connected Components

• The Bottom of a Graph
• Fake Tournament

Biconnected Components, Shortest Path and MST

Reading Material

• 🎥Finding Bridges in Graphs
• 🎥Articulation Points
• 🎥Dijkstra's Shortest path
• Bellman Ford algorithm
• 🎥Floyd Warshall's algorithm
• 🎥Kruska's Minimum Spanning Tree
• 🎥Prim's MST Algorithm

Problems: Biconnected Components

• UVa 00315: Network (finding articulation points)
• UVa 00796: Critical Links (finding bridges)
• CF 193A: Cutting Figure

Problems: Shortest Path

• HE: Minimum Valid Path
• CC: DIGJUMP
• CC: AMR14B
• SPOJ: Mice and Maze

Problems: Minimum Spanning Tree

• SPOJ: BLINNET
• HR: Roads in HackerLand
• CC: MST Queries
• SPOJ: KOICOST

Contests

• DSA Learning Series: Week 8 - Graphs By CodeChef

---

Week 3

String Algorithms

1. Reading material

• Basics of String manipulation
• KMP algorithm
• Z algorithm
• Z algorithm II
• Manachar's algorithm
• Manacher's algorithm II
• Rabin-Karp and KMP TopCoder

2. Problems on HackerEarth

☆	Problem Link	Finished
★★☆	Find the substrings
★★☆	The Cheapest Palindrome
★★☆	Largest Lexicographical Rotation II
★★☆	Monk and Monster
★★★	Prefix Number
★★★	Last Forever

3. Problems on HackerRank

☆	Problem Link	Finished
★☆☆	Sherlock and the Valid String
★☆☆	Highest Value Palindrome
★★☆	Sherlock and Anagrams
★★☆	Common Child
★★★	Build a Palindrome

4. Problems on Codeforces

☆	Problem Link	Finished
★☆☆	Petya and Exam
★★☆	Password
★★★	Prefixes and Suffixes

5. Problems on Codechef

• Kira Loves Palindromes

5. Problems on SPOJ

• Word Puzzles

---

Week 4: Practice Contest

• ZCO Practice Contest
• INOI Problems
• IARCS OPC Judge Problems

---

Week 5

Data Structures

Sparse Table

1. Reading Material

• 🎥Tutorial
• Blog post

2. Problems

• B. Maximum of Maximums of Minimums
• CGCDSSQ
• D. R2D2 and Droid Army

Disjoint Set Union

1. Reading Material

• 🎥Tutorial

2. Problems

• D. Roads not only in Berland
• HackerEarth CodeMonk: DSU

---

Week 6

Square Root Decomposition

1. Reading Material

• Tutorial 1: Base Concept + Mo's algorithm
• Tutorial 2
• Tutorial 3 : Read the comments
• Tutorial 4 : Video Lecture, find slides in video description
• Tutorial 5 : Exhaustive PDF
• Tutorial 6 : Mo's Algorithm

2. Problems

• CHEFXQ
• RACETIME
• GIVEAWAY
• 13E
• 342E
• DQUERY
• 375D
• 840D
• 86D
• 398D
• GERALD07
• MKTHNUM

---

Week 7

Segment Tree

1. Reading Material

• Tutorial
• [ ]

2. Problems

• D. Distinct Characters Queries
• A. Knight Tournament
• F. Ant colony
• E. Drazil and Park
• C. DZY Loves Fibonacci Numbers

---

Week 8

Fenwick Tree

1. Reading Material

• Tutorial

2. Problems

• E. Little Artem and Time Machine
• E. Hanoi Factory
• C. Subsequences
• D. Ball
• E. Garlands

---

Why use this list?

Since getting better at competitive programming takes a lot of effort, you need to keep practicing a lot of problems. This list will keep you focussed and you will have a target with you that you need to finish atleast these many problems before moving on. It can help you organize your practice.