sanjit30/Get_Better_at_CP_in_2_Months

This contains the curriculum that I will follow to get better at Competitive Programming in 2 months.

Get_Better_CP_in_2_Months

Month 1

Week 1

Dynamic Programming

• [x ] 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
• Try to solve as much tasks as possible in this Educational DP contest on AtCoder
• More Contests - https://vjudge.net/contest/202878
• Find DP Contests here - https://codeforces.com/group/hK6hgc8x94/contests

---

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

---

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

• Solve as many problems as possible out of a total of 24, in the ZCO Practice Contest.

---

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.

How to use this list?

The Github markdown's task list feature is used to check progress.

Create a new branch so that you can check items like this, just put a x in the brackets: [x]

• One time steps:

1. Fork this repository.

2. Clone the forked repository.

   git clone https://github.com/your_user_name/Get_Better_at_CP_in_2_Months/

3. Create a new branch for tracking your progress. Let's name this your_user_name

   git checkout -b your_user_name

4. Add remote

   git remote add your_user_name https://github.com/your_user_name/Get_Better_at_CP_in_2_Months/

• Marking tasks as completed and pushing to your branch:

  git add .
  git commit -m "Completed tasks x and y"
  git rebase your_user_name/master
  git push --force
  

• Keeping your fork's list updated with the changes made here:

  git remote add upstream https://github.com/sahilbansal17/Get_Better_at_CP_in_2_Months.git
  git checkout master
  git pull upstream master
  git push your_user_name master
  

Refer to this for understanding more about Fork and PR workflow.