Competitive Coding

One must have basic idea and clear concepts of Data Structures and Algorithms before diving into this sport called “Competitive Coding”.

Before getting started, have a look at this site: CP-Algorithms, a one stop solution for all competitive coders. This will be very helpful at later stages of this journey.

---

:pushpin: Dynamic Programming

• Dynamic Programming Notes Hackerearth
• DP Tutorial involving grids
• Divide and Conquer DP
• TopCoder Tutorial on DP
• Some classical problems:
  • Coin change problem
  • Rod Cutting problem
  • Unbounded Knapsack
  • 0-1 Knapsack problem
  • Longest common subsequence
• Practice 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

• AtCoder Educational DP Contest
• Codeforces DP Contest
• AtCoder DP contest
• CodeChef DP Contest

---

:pushpin: String Algorithms

• String manipulation(basics)
• Z algorithm & Z algorithm II
• Manachar’s algorithm & Manacher’s algorithm II
• String Hashing
• KMP algorithm
• Rabin-Karp and KMP TopCoder

(i) HackerEarth Problemset

☆	Problem Link	Finished
★☆☆	Compiler Version	<ul> <li> [ ] </li> </ul>
★★☆	Secrete Messages!	<ul> <li> [ ] </li> </ul>
★★☆	String Queries	<ul> <li> [ ] </li> </ul>
★★☆	Largest Lexicographical Rotation II	<ul> <li> [ ] </li> </ul>
★★☆	EasyPalindrome	<ul> <li> [ ] </li> </ul>
★★★	Statistics of strings	<ul> <li> [ ] </li> </ul>
★★★	Last Forever	<ul> <li> [ ] </li> </ul>

(ii) HackerRank Problemset

☆	Problem Link	Finished
★☆☆	Palindrome Index	<ul> <li> [ ] </li> </ul>
★☆☆	Weighted Uniform Strings	<ul> <li> [ ] </li> </ul>
★★☆	Sherlock and Anagrams	<ul> <li> [ ] </li> </ul>
★★☆	Bear and Steady Gene	<ul> <li> [ ] </li> </ul>
★★★	Circular Palindromes	<ul> <li> [ ] </li> </ul>

(iii) Codeforces Problemset

☆	Problem Link	Finished
★★☆	Another Problem on Strings	<ul> <li> [ ] </li> </ul>
★★☆	AB-string	<ul> <li> [ ] </li> </ul>
★★★	Prefixes and Suffixes	<ul> <li> [ ] </li> </ul>

(iv) SPOJ Problemset

• Word Puzzles

---

:pushpin: Trees

• Trees-Data Structures
• Binary Search Trees
• Balanced Search Trees
• Sqrt Tree

☆	Problem Link	Finished
★☆☆	Same Tree	<ul> <li> [ ] </li> </ul>
★☆☆	Invert Binary Tree	<ul> <li> [ ] </li> </ul>
★★☆	Binary Tree Longest Consecutive Sequence	<ul> <li> [ ] </li> </ul>
★★☆	Most Frequent Subtree Sum	<ul> <li> [ ] </li> </ul>
★★☆	Lowest Common Ancestor of a binary tree	<ul> <li> [ ] </li> </ul>
★★☆	N-ary Tree Level Order Traversal	<ul> <li> [ ] </li> </ul>
★★★	Sum of distances in tree	<ul> <li> [ ] </li> </ul>

---

:pushpin: Graphs

• Algorithm Gym :: Graph Algorithms
• Basic Graph Theory
• :movie_camera: Breadth-First Search(MIT OCW playlist-Youtube)
• :movie_camera: Depth-First Search, Topological Sort (MIT OCW playlist-Youtube)

☆	Problem Link	Finished
★☆☆	PPATH(SPOJ)	<ul> <li> [ ] </li> </ul>
★☆☆	Draughts(CodeChef)	<ul> <li> [ ] </li> </ul>
★★☆	Distant Relatives(CodeChef	<ul> <li> [ ] </li> </ul>

---

:pushpin: Shortest Path Algorithms

• Dijkstra
• Dijkstra Algorithm(CP-Algorithms)

• :movie_camera: Dijkstra’s Algorithm Single Source Shortest Path Graph Algorithm(Youtube)

• Bellman Ford
• Bellman-Ford Algorithm(CP-Algorithms)

• :movie_camera: Bellman-Ford Algorithm Single Source Shortest Path Graph Algorithm(Youtube)

• Floyd Warshall
• Floyd-Warshall Algorithm(CP-Algorithms)
• :movie_camera: Floyd Warshall Algorithm All Pair Shortest Path Graph Algorithm(Youtube)

☆	Problem Link	Finished
★★☆	Minimum Valid Path	<ul> <li> [ ] </li> </ul>
★★☆	Chef and Digit Jumps	<ul> <li> [ ] </li> </ul>
★★☆	Road Decoration	<ul> <li> [ ] </li> </ul>
★★☆	Mice and Maze	<ul> <li> [ ] </li> </ul>

---

:pushpin: Union Find (Aka Disjoint Set Union/Union Find Disjoint Sets)

• :movie_camera: Union Find (PU-CS : Youtube)
• Disjoint Set Union(CP-Algorithms)

☆	Problem Link	Finished
★☆☆	Marriage Problem	<ul> <li> [ ] </li> </ul>
★★☆	Roads not only in Berland	<ul> <li> [ ] </li> </ul>
★★☆	Lexicographically minimal string	<ul> <li> [ ] </li> </ul>
★★☆	Consecutive Letters	<ul> <li> [ ] </li> </ul>

---

:pushpin: Minimum Spanning Tree (Kruskal’s)

• :movie_camera: Kruskal’s algorithm Minimum Spanning Tree Graph Algorithm(Youtube)
• Minimum spanning tree - Kruskal with Disjoint Set Union(CP-Algorithms)

☆	Problem Link	Finished
★★☆	Bytelandian Blingors Network	<ul> <li> [ ] </li> </ul>
★★☆	Roads in HackerLand	<ul> <li> [ ] </li> </ul>
★★☆	MST Queries	<ul> <li> [ ] </li> </ul>
★★☆	Cost	<ul> <li> [ ] </li> </ul>

---

:pushpin: Binary Indexed Tree (Fenwick Tree)

• :movie_camera: Video, for better Understanding and Visualisation(Youtube)
• Blog, with Explanation, Implementation and Practice Problems(CP-Algorithms)

☆	Problem Link	Finished
★☆☆	Thor	<ul> <li> [ ] </li> </ul>
★☆☆	Zeros and Ones	<ul> <li> [ ] </li> </ul>
★★☆	Help Ashu	<ul> <li> [ ] </li> </ul>
★★☆	Distinct Digits II	<ul> <li> [ ] </li> </ul>
★★☆	Micro and Array Function	<ul> <li> [ ] </li> </ul>

---

We hope you now know the roadmap to being a professional Competitive Coder :v: