<!-- <style> .markdown-body { background-color: #AAAAF4; color: black; } </style> --> ![PCLUB_logo](https://hackmd.io/_uploads/ryCPQvXvA.png) # Roadmap <br> Competitive Programming (CP) ### Contents : ```markmap # [Section 0 : Introduction](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#Section-0-Introduction-) # [Section 1 : Basic Theory](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#Section-1-Basic-Theory) # [Section 2 : Intermediate](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#Section-2-Intermediate) # [Section 3 : Advanced](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#Section-3-Advanced) ``` | Section 0 : Introduction | Section 1 : Basic Theory | Section 2 : Intermediate | Section 3 : Advanced | | ------------------------------ | ------------------------------ | ----------------------------- | ----------------------------- | | Introduction | Number Theory | Advanced Maths | String Hashing | | Getting Started | Two Pointers / Sliding Windows | Range Update Queries | Directed Graphs | | basic prob solving | Range Queries | Graph Theory Basics | Range Update | | Time Complexity | Divide and Conquer | DSU + MST | Sparse Table | | Intro To STL | Intro to Greedy Algorithms | Shortest path | Tree Algorithm | | Sorting | Dynamic Programming | | | | Binary Search | Interactive Problems | | | | Bit Operations | | | | | Number Theory | | | | | Recursion | | | | | Complete Search | | | | # Section 0: Introduction : ```markmap # SECTION 0 part 1 ## [Getting Started](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#%E2%9E%A1%EF%B8%8FGetting-Started) ## [basic prob solving](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#%E2%9E%A1%EF%B8%8FBasic-Problem-Solving) ## [Time Complexity](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#%E2%9E%A1%EF%B8%8FTime-Complexity) ## [Intro To STL](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#%E2%9E%A1%EF%B8%8FIntro-to-STL) # SECTION 0 part 2 ## [Sorting](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#%E2%9E%A1%EF%B8%8FSorting) ### [Binary Search](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#%E2%9E%A1%EF%B8%8FBinary-Search) ## [Bit Operations](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#%E2%9E%A1%EF%B8%8FBit-Operations) ### [Primary Number Theory](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#%E2%9E%A1%EF%B8%8FPrimary-Number-Theory) ## [Recursion](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#%E2%9E%A1%EF%B8%8FRecursion) ### [Complete Search](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#%E2%9E%A1%EF%B8%8FComplete-Search) ``` ### What is CP and Why do it? - It's a mind-sport where you are given a problem and have to come up with optimized solutions for the given constraints with your problem-solving skills and implement with your coding skills. - We do it because it helps us in building our logical and analytical thinking skills and also in enhancing our knowledge. But most importantly, because it’s a lot of fun! (and it helps get a job 👀) - Some Popular CP Platforms are | - [Codeforces](https://codeforces.com/) <br> - [Codechef](https://www.codechef.com/) <br> - [Topcoder](https://www.topcoder.com/) | - [Atcoder](https://atcoder.jp/) <br> - [Leetcode](https://leetcode.com/) <br>- [Hackerrank](https://www.hackerrank.com/) | | -------- | -------- | We will look into them further as we go on! ## ➡️Getting Started ### Learn C++ : - If you have already gone through ESC112( any Coding Course in C) then you may follow this article for a smooth transition : [Moving from C to C++](https://saiankit.medium.com/moving-from-c-to-c-b38b13d04682) - If you have no prior coding experience , you can follow : * For youtube fans :(They also have a guide to setup) 1. [Bro Code](https://youtu.be/-TkoO8Z07hI?si=dg18FC3M85T2-Owu) : [first 5 hours] OR 2. [Free Code Camp](https://www.youtube.com/watch?v=vLnPwxZdW4Y) : [first 3 hours] * If you prefer to read, then : 1. [USACO : PAPS](https://usaco.guide/PAPS.pdf#page=29)(book Chapter 2) OR 2. [Learn C++](https://www.w3schools.com/cpp/default.asp) (Just the intro and functions parts) - Register on the domain [CodeChef](https://www.codechef.com/dashboard) ; and then solve the given problems : >- [ ] [Codechef - GDTURN](https://www.codechef.com/problems/GDTURN) >- [ ] [Codechef - TAXES](https://www.codechef.com/problems/TAXES) - In the end, you truly learn the language after you have sufficient experience. Try out as many problems from these links : >- [Beginner Problems | Codechef](https://www.codechef.com/practice/logical-problems) ### Setting Up Environment : We prefer VS CODE because of obvious reasons :eyes: , still feel free to use any other usable Code Editor like : sublime text , codeblocks , etc. - **Windows** : you can watch the [same video from above](https://youtu.be/-TkoO8Z07hI?si=MBam0S02pNlGpdVu&t=87) from [0:1:27] to [0:8:40] :::warning Currently you will be able to work fine with #include<iostream> , but in future if you’re facing issues with #include<bits/stdc++.h> on VS code then [watch this video](https://www.youtube.com/watch?v=pyn0TjUnf18). ::: - **Mac** : Download and install VS Code from [https://code.visualstudio.com/](https://code.visualstudio.com/) and then [Set it up for C++](https://www.youtube.com/watch?v=Qw5qjRNlC-Y). After this, it is best to change your compiler to gcc. You can follow [this tutorial](https://www.youtube.com/watch?v=0z-fCNNqfEg) to install gcc. ## ➡️Basic Problem Solving - :maple_leaf: ***Your first problem on Codeforces*** :::info Starting with a less interactive platform like CodeForces can be difficult, but don't worry we got your back : : 1. start by registering yourself on ==https://codeforces.com/== : 2. Here's ==[Everyone's First Problem](https://codeforces.com/problemset/problem/4/A)==, have a look : 3. Head to your local IDE : 4. When you pass the sample inputs locally, click on Submit. : 5. You can paste your entire code to the Source Code section (OR upload your solution.cpp file) and press Submit. PS : We recommend enrolling yourself in the ***"ITMO Academy: pilot course"*** on ==[Courses - Codeforces](https://codeforces.com/edu/courses)==. It contains great problems as well as theory which we'll cover as we move forward. By the end of the roadmap, you can independently finish it ! ::: - :maple_leaf: ***More problems from CodeForces*** >- [ ] [CF - A+B?](https://codeforces.com/problemset/problem/1772/A) >- [ ] [CF - Triangular Numbers](https://codeforces.com/problemset/problem/47/A) >- [ ] [CF - Morning](https://codeforces.com/problemset/problem/1883/A) - :maple_leaf: ***Your first problem on CSES*** :::info ***CSES is a problem set :*** ==[***register yourself***](https://cses.fi/register/)== : 1. Link : ==[Problem 1](https://cses.fi/problemset/task/1068/)== ; here you can only submit the solution as a file. Head to your local IDE and write up a 'solution.cpp' : 2. Run locally and check the code : 3. Press on the Submit tab and Upload the code file. The results of Online Judge will be displayed in some time. : 4. Make sure to use long long int ;) ::: - :maple_leaf: ***Your first problem on*** ==[***SPOJ.com*** : Problem TEST](https://www.spoj.com/problems/TEST/)== :::success ### Fast I/O (optional for now): What it is : * [Significance of fast I/O - Stack Overflow](https://stackoverflow.com/questions/31162367/significance-of-ios-basesync-with-stdiofalse-cin-tienull) OR * [Fast IO in C++ for Competitive Programming! (and when to not use it)](https://www.youtube.com/watch?v=aNF4DEluWnI) Try this problem with Fast I/O : >- [ ] [Enormous Input and Output Test - SPOJ INOUTEST - Virtual Judge](https://vjudge.net/problem/SPOJ-INOUTEST) ::: - :maple_leaf: ***Your First Problem on USACO*** :::info About USACO : 1. USACO has problems revolving around Farmer John's Farm and (mostly) His Cows. 2. Make a new account here. Whenever you go to a problem, you can press the 'Overview' tab to head to the same page for logins. 3. You can only submit the solution as a file; apart from that you might be required to get input from a file , output your answer to a file (all that will be processed on server). 4. Ex : mixmilk.in for input and mixmilk.out for output. Then you need to add these lines at the start of your code: ```cpp freopen("mixmilk.in", "r", stdin); freopen("mixmilk.out", "w", stdout); ``` ::: ([know more about it here](https://www.programiz.com/cpp-programming/library-function/cstdio/freopen) / [official page](https://en.cppreference.com/w/cpp/io/c/freopen) ) Or you may make your template for USACO problems like : :::spoiler Template - (Fast I/O included) ```cpp #include <iostream> #include <string> #include <vector> using namespace std; void setIO(string s){ ios_base::sync_with_stdio(0); cin.tie(0); freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); } int main(){ setIO("mixmilk"); return 0; } ``` ::: :::info First Problem 1. Link : ==[Mixing Milk](https://usaco.org/index.php?page=viewproblem2&cpid=855)== ; Head to your local IDE and write up a solution.cpp. 2. Create mixmilk.in locally in the same folder as your solution.cpp; enter sample input in it (treat .in and .out as .txt files). 3. Run locally and check the code. 4. Upload the file, Select C++11, Submit. The results of Online Judge will be displayed in some time. ::: - :maple_leaf: ***More problems on USACO :*** >- [ ] [Shell Game](https://usaco.org/index.php?page=viewproblem2&cpid=891) >- [ ] [The Bovine Shuffle](https://usaco.org/index.php?page=viewproblem2&cpid=760) ### Basic Math Problems >- [ ] [CF - Panoramix's Prediction](https://codeforces.com/problemset/problem/80/A) >- [ ] [CF - System of Equations](https://codeforces.com/problemset/problem/214/A) >- [ ] [CF - GCD vs LCM](https://codeforces.com/problemset/problem/1665/A) >- [ ] [CodeChef - Two equations](https://www.codechef.com/problems/NT01) <br> ### Some suggestions from the Makers : :::success - We believe that a lot of practice is what shapes you in CP ; apart from the questions found here , it is suggested to practice more problems whenever you feel. ::: :::success - It is sometimes okay to look up the solution / editorial (for codeforces). Don't fret if you're not able to solve a problem, you'll get it with practice. ::: :::success - The ":star: Expected time" is the amount of time you will need to give to prepare the theory in a heading before practicing. ::: :::success - Take your time to understand things and implement them. The expected time is suggestive and varies from person to person, but do not spend too much time on a single topic. ::: :::success - Consistency is very important in CP. It is highly recommended that you keep practicing it at your own pace daily, rather than doing it all at once. It is a skill that develops over time. ::: <br> ## ➡️Time Complexity >:star: Expected time : 40 - 50 minutes * [Why you need to know about it](https://codeaccepted.wordpress.com/category/theory/) * [CPH Ch 2](https://cses.fi/book/book.pdf#page=27) * [Watch this for more examples](https://www.youtube.com/watch?v=zUUkiEllHG0) Solve these in O(n) : >- [ ] [CSES : Missing Number](https://cses.fi/problemset/task/1083) >- [ ] [CodeChef - Magician versus Chef](https://www.codechef.com/problems/MAGICHF) >- [ ] [CSES : Increasing Array](https://cses.fi/problemset/task/1094) ~~Make sure to use long long int ;)~~ >- [ ] [CSES : Permutations](https://cses.fi/problemset/task/1070) ## ➡️Intro to STL >:star: Expected time : 40 - 60 minutes * [Complete C++ STL in 1 Video | Time Complexity and Notes](https://www.youtube.com/watch?v=RRVYpIET_RU) Watch till 35:57. >OR * [The Complete Practical Guide to C++ STL(Standard Template Library) | by Abhishek Rathore | Medium](https://abhiarrathore.medium.com/the-magic-of-c-stl-standard-template-library-e910f43379ea) ### Basic Array / Vectors Problems >- [ ] [CF - Team](https://codeforces.com/problemset/problem/231/A) >- [ ] [CF - Series of Crimes](https://codeforces.com/problemset/problem/181/A) >- [ ] [CF - Beautiful Matrix](https://codeforces.com/problemset/problem/263/A) >- [ ] [CF - I Wanna Be the Guy](https://codeforces.com/problemset/problem/469/A) >- [ ] [CF - Game Outcome](https://codeforces.com/problemset/problem/157/A) ### Basic String Problems * Your intro to strings : [C++ Strings (With Examples)](https://www.programiz.com/cpp-programming/strings) >- [ ] [CF - Boy or Girl](https://codeforces.com/problemset/problem/236/A) >- [ ] [CF - LLPS](https://codeforces.com/problemset/problem/202/A) >- [ ] [SPOJ.com - Transform the Expression](https://www.spoj.com/problems/ONP/) >- [ ] [CF - Phone Code](https://codeforces.com/problemset/problem/172/A) ( use vector&lt;string> 👀) * Basic Stack Problems >- [ ] [LeetCode - Valid Parentheses](https://leetcode.com/problems/valid-parentheses/description/) >- [ ] [CSES : Nearest Smaller Values](https://cses.fi/problemset/task/1645) >- [ ] [CF - YetnotherrokenKeoard](https://codeforces.com/problemset/problem/1907/B) ## ➡️Sorting >:star: Expected time : 2 - 2.5 hours * [CPH page 25](https://cses.fi/book/book.pdf#page=35) Read Chapter 3 from ‘Competitive Programmer’s Handout’ * [Sorting Algorithms | LeetCode The Hard Way](https://leetcodethehardway.com/tutorials/category/sorting) (optional) * [Tutorial with Visualisation](https://csacademy.com/lesson/sorting) - ***problems :*** >- [ ] [CSES : Apartments](https://cses.fi/problemset/task/1084) >- [ ] [CF - Assembly via Minimums](https://codeforces.com/problemset/problem/1857/C) >- [ ] [CF - Progressive Square](https://codeforces.com/problemset/problem/1955/B) >- [ ] [CF - XOUR](https://codeforces.com/contest/1971/problem/G) - A bit on the mathematical side, think about using map&lt;int,vector&lt;int>> . >- [ ] [CSES : Collecting Numbers ](https://cses.fi/problemset/task/2216) >- [ ] [CSES : Tasks and Deadlines ](https://cses.fi/problemset/task/1630) ### More on STL >:star: Expected time : 40 - 60 minutes <br> * Continue from 35:58 : [Complete C++ STL in 1 Video | Time Complexity and Notes](https://www.youtube.com/watch?v=RRVYpIET_RU&t=2158s) * Basic Set / Multiset Problems >- [ ] [CSES : Distinct Numbers](https://cses.fi/problemset/task/1621) >- [ ] [Problem - 1712C - Codeforces](https://codeforces.com/problemset/problem/1712/C) >- [ ] [Problem - 44A - Codeforces](https://codeforces.com/contest/44/problem/A) >>:::spoiler Hint >>(Using set&lt;pair&lt;string,string>> would make it very easy) >>::: >- [ ] [CSES : Concert Tickets](https://cses.fi/problemset/task/1091) >- [ ] [D - Querying Multiset](https://atcoder.jp/contests/abc212/tasks/abc212_d) * Basic Map Problems >- [ ] [CF - Radio Station](https://codeforces.com/contest/918/problem/B) >- [ ] [CSES - Sum of Two Values](https://cses.fi/problemset/task/1640) >- [ ] [CF - Boxes Packing](https://codeforces.com/contest/903/problem/C) >- [ ] [CSES - Playlist](https://cses.fi/problemset/task/1141) * Custom comparator >- [ ] [CF - Lamps](https://codeforces.com/problemset/problem/1839/B) >- [ ] [CF - Monsters](https://codeforces.com/contest/1849/problem/B) Each Data Structure in STL has its own strengths and weaknesses. Try to think what to use according to the problems. ## ➡️Binary Search >:star: Expected time : 40 - 60 minutes * [Tutorial with Visualisation](https://csacademy.com/lesson/binary_search) * [Binary Search | Code Accepted](https://codeaccepted.wordpress.com/2014/01/18/binary-search-and-its-relatives/) >- [ ] [ITMO - First Implementation](https://codeforces.com/edu/course/2/lesson/6/1/practice/contest/283911/problem/A) >- [ ] [CF - Cat, Fox and the Lonely Array](https://codeforces.com/problemset/problem/1973/B) >- [ ] [ITMO : Application on real numbers](https://codeforces.com/edu/course/2/lesson/6/2/practice/contest/283932/problem/E) >- [ ] [CSES - Array Division](https://cses.fi/problemset/task/1085) (Minmax concept) >- [ ] [CF - Maximum Median](https://codeforces.com/contest/1201/problem/C) >>:::spoiler Alternative Soln Link >>[Binary Search · USACO Guide](https://usaco.guide/silver/binary-search?lang=cpp#example---maximum-median) >>::: * ***Additional Practice*** >- [ ] [Codechef - WAV2](https://www.codechef.com/problems/WAV2) >- [ ] [Aizu Online Judge - Range Search (kD Tree)](https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_C) >- [ ] [CSES - Factory Machines](https://cses.fi/problemset/task/1620) >- [ ] [ITMO - Packing Rectangles](https://codeforces.com/edu/course/2/lesson/6/2/practice/contest/283932/problem/A) >- [ ] [SPOJ.com - Aggressive cows](https://www.spoj.com/problems/AGGRCOW/) ## ➡️Bit Operations >:star: Expected time : 1 - 1.5 hours * [Bit Manipulation | LeetCode The Hard Way](https://leetcodethehardway.com/tutorials/math/bit-manipulation) * [CPH Bit Manipulation](https://usaco.guide/CPH.pdf#page=105) (extra) * [Bit manipulation - CP Algorithms](https://cp-algorithms.com/algebra/bit-manipulation.html) - ***Problems :*** >- [ ] [CF - Raising Bacteria](https://codeforces.com/problemset/problem/579/A) >- [ ] [Virtual Judge - Little Elephant and Bits](https://vjudge.net/problem/CodeForces-258A) >- [ ] [Virtual Judge - Maximizing Xor](https://vjudge.net/problem/HackerRank-maximizing-xor) >- [ ] [CF - Preparing Olympiad](https://codeforces.com/problemset/problem/550/B) >- [ ] [Virtual Judge - Red Scarf](https://vjudge.net/problem/AtCoder-abc171_e) ## ➡️Primary Number Theory >:star: Expected time : 1 - 1.5 hours * [Elementary Number Theory](https://darrenyao.com/usacobook/cpp.pdf#page=68) * [“Output the answer modulo 10^9 + 7” | Code Accepted](https://codeaccepted.wordpress.com/2014/02/15/output-the-answer-modulo-109-7/) * [[Blog] Modular Arithmetic for Beginners - Codeforces](https://codeforces.com/blog/entry/72527) ### Binary Exponentiation >:star: Expected time : 20 - 30 minutes - [Binary Exponentiation | Code Accepted](https://codeaccepted.wordpress.com/2014/06/01/algorithm-11-binary-exponentiation/) or - [Binary exponentiation | AlgorithmClear Blog](https://algorithmclear.blog/blog/binary-exponentiation) or - [Binary Exponentiation - Faster way to calculate Pow(x,n) [Python] | Medium](https://medium.com/geekculture/binary-exponentiation-faster-way-to-calculate-pow-x-n-python-52bf4fcf42d1) >- [ ] [CSES : Bit Strings](https://cses.fi/problemset/task/1617/) >- [ ] [CSES : Exponentiation](https://cses.fi/problemset/task/1095) >- [ ] [SPOJ.com - Magic of the locker](https://www.spoj.com/problems/LOCKER/) ### Factorisation [till O(rootN)] >:star: Expected time : 20 - 30 minutes * [Primality Testing | Code Accepted](https://codeaccepted.wordpress.com/2013/08/25/algorithm-2-primality-testing/) :::warning we’ll cover Sieve of Eratosthenes later* ::: * [Trial division](https://cp-algorithms.com/algebra/factorization.html#trial-division) >- [ ] [Aizu Online Judge - Prime Factorization](https://onlinejudge.u-aizu.ac.jp/courses/library/6/NTL/1/NTL_1_A) >- [ ] [Atcoder - D Div Game](https://atcoder.jp/contests/abc169/tasks/abc169_d) >- [ ] [LeetCode - Four Divisors](https://leetcode.com/problems/four-divisors/description/) ### Gcd >:star: Expected time : 20 - 30 minutes * [Greatest Common Divisor | Code Accepted](https://codeaccepted.wordpress.com/2013/09/01/algorithm-3-gcd/) * [Gcd](https://cp-algorithms.com/algebra/euclid-algorithm.html) >- [ ] [CF - Common Divisors](https://codeforces.com/problemset/problem/1203/C) >- [ ] [CF - Minimum LCM](https://codeforces.com/problemset/problem/1765/M) >- [ ] [Codechef - Subset GCD](https://www.codechef.com/problems/GCDPERM) >- [ ] [Codechef - GCD and LCM](https://www.codechef.com/problems/GCDLM) * ***More Practice*** >- [ ] [Codechef - Hello Equation](https://www.codechef.com/problems/HLEQN) >- [ ] [Codechef - Bitwise Equation](https://www.codechef.com/problems/BITEQU) ## ➡️Recursion >:star: Expected time : 1.5 - 2 hours * [C++ Recursion (With Example)](https://www.programiz.com/cpp-programming/recursion) * The classic recursion problem : [Tower of hanoi](https://www.tutorialspoint.com/data_structures_algorithms/tower_of_hanoi.htm) or [Video](https://youtu.be/rf6uf3jNjbo?si=miZPq2VZdqe2jgvh) * Read [this](https://www.hackerearth.com/practice/basic-programming/recursion/recursion-and-backtracking/tutorial/) article on recursion (you may skip the introduction ) . [CSES : Chessboard and Queens](https://www.hackerearth.com/practice/basic-programming/recursion/recursion-and-backtracking/tutorial/) try this question which is an extension of the N Queens Problem . - ***Basic Recursion problems***: >- [ ] [CSES : Weird Algorithm](https://cses.fi/problemset/task/1068) >- [ ] [CSES : Elimination Game](https://leetcode.com/problems/elimination-game/description/) >- [ ] [CSES : Apple Division](https://cses.fi/problemset/task/1623) >- [ ] [CSES : Creating Strings ](https://cses.fi/problemset/task/1622) - Try generating all possible permutations using recursion ## ➡️Complete Search >:star: Expected time : 1.5 - 2 hours * [CPH ch 5](https://usaco.guide/CPH.pdf#page=57) * [Bit Masking | Code Accepted](https://codeaccepted.wordpress.com/2014/01/14/algorithm-4-bit-masking/) * [Backtracking | Code Accepted](https://codeaccepted.wordpress.com/2014/02/04/algorithm-6-backtracking/) - ***Problems***: >- [ ] [Creating Strings](https://cses.fi/problemset/task/1622) - try without using next_permutation() ;) >- [ ] [Virtual Judge - Bars](https://vjudge.net/problem/UVA-12455) >- [ ] [CF - Creating Expression1](https://codeforces.com/group/gA8A93jony/contest/270592/problem/E) >- [ ] [CF - 2D Traveling](https://codeforces.com/problemset/problem/1869/B) >- [ ] [USACO - Air Cownditioning II](https://usaco.org/index.php?page=viewproblem2&cpid=1276) >- [ ] [CF - Reverse String](https://codeforces.com/contest/1553/problem/B) :::success By now, you may have realized that debugging your code efficiently is very important. For a few tips on debugging, you can go through ==[this article](https://usaco.guide/general/basic-debugging?lang=cpp)== / ==[this video](https://www.youtube.com/watch?v=8ymiMHQPgZY)==. ::: ## ➡️Section 0 Additional Practice: >- [ ] [SPOJ.com - Factorial](https://www.spoj.com/problems/FCTRL/) >- [ ] [SPOJ.com - Small factorials](https://www.spoj.com/problems/FCTRL2/) `sometimes one has to use python in CP :)` >- [ ] [SPOJ.com - Transform the Expression](https://www.spoj.com/problems/ONP/) >- [ ] [CF - Turtle and an Infinite Sequence](https://codeforces.com/problemset/problem/1981/B) >- [ ] [CSES : Sum of Three Values](https://cses.fi/problemset/task/1642) >- [ ] [CF - Chat Order](https://codeforces.com/problemset/problem/637/B) >- [ ] [CF - Cellular Network](https://codeforces.com/contest/702/problem/C) # Section 1: Basic Theory ```markmap # SECTION 1 ## [Number Theory](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#%E2%9E%A1%EF%B8%8FNumber-Theory) ## [Two Pointers / Sliding Windows](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#%E2%9E%A1%EF%B8%8FTwo-Pointers--Sliding-Windows) ## [Range Queries](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#%E2%9E%A1%EF%B8%8FRange-Queries) ## [Divide and Conquer](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#%E2%9E%A1%EF%B8%8FDivide-and-Conquer) ## [Intro to Greedy Algorithms](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#%E2%9E%A1%EF%B8%8FIntro-to-Greedy-Algorithms) ## [Dynamic Programming](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#%E2%9E%A1%EF%B8%8FDynamic-Programming) ## [Interactive Problems](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#%E2%9E%A1%EF%B8%8FInteractive-Problems) ``` ## ➡️Number Theory ### Number Sieve >:star: Expected time : 1 - 1.5 hours * ([Sieve of Eratosthenes - Wikipedia](https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes)) or * ([Sieve of Eratosthenes - CpAlgorithms](https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html) ) >- [ ] [Count Primes - LeetCode](https://leetcode.com/problems/count-primes/description/) >- [ ] [SPOJ.com - Problem NFACTOR](https://www.spoj.com/problems/NFACTOR/) * Faster Prime Factorisation :::info * ==[CSES : Counting Divisors](https://cses.fi/problemset/task/1713)== : attempt it and have a look at this ==[solution](https://usaco.guide/gold/divisibility?lang=cpp#solution---counting-divisors)== or * ==[Prime Factors in Log(N) Tutorial | LeetCode The Hard Way](https://leetcodethehardway.com/tutorials/math/prime-factors)== ::: - Problems : >- [ ] [SPOJ.com - Amazing Prime Sequence](https://www.spoj.com/problems/APS/) >- [ ] [Virtual Judge - A Different Kind of Sorting](https://vjudge.net/problem/UVA-11353) >- [ ] [SPOJ.com - Printing some primes](https://www.spoj.com/problems/TDPRIMES/) >- [ ] [SPOJ.com - Bazinga!](https://www.spoj.com/problems/DCEPC505/) ### Modular Multiplicative Inverse >:star: Expected time : 20 - 30 minutes - [Modular Multiplicative Inverse | forthright48](https://forthright48.com/modular-multiplicative-inverse/) >- [ ] [Virtual Judge - Modular division](https://vjudge.net/problem/EOlymp-9606) >- [ ] [CSES : Exponentiation II](https://cses.fi/problemset/task/1712) ### Additional Practice : >- [ ] [Codechef - GCD of Prefixes](https://www.codechef.com/problems/GCDPRF) >- [ ] [SPOJ.com - Distinct Primes](https://www.spoj.com/problems/AMR11E/) >- [ ] [Codechef - Modular GCD](https://www.codechef.com/problems/GCDMOD) (you might wanna use (__int128_t)) >- [ ] [CSES : Divisor Analysis](https://cses.fi/problemset/task/2182) >- [ ] [CF - Orac and LCM](https://codeforces.com/problemset/problem/1349/A) >- [ ] [CF - k-LCM (hard version)](https://codeforces.com/problemset/problem/1497/C2?locale=en) >- [ ] [CF - Santa's Bot](https://codeforces.com/problemset/problem/1279/D) >- [ ] [Codechef - Chef and Riffles](https://www.codechef.com/problems/RIFFLES) (Here’s a challenging problem to practice binary exponentiation) >>:::spoiler Hint >>In essence, you need to apply the permutation U = (1, 3, 5 … N - 1, 2 , 4 …. N) to your initial array K times which is the same as composing f with You can use binary exponentiation). ::: ## ➡️Two Pointers / Sliding Windows >:star: Expected time : 30 - 40 minutes * [CPH](https://usaco.guide/CPH.pdf#page=87) * [video](https://www.youtube.com/watch?v=On03HWe2tZM) * ***Problems*** >- [ ] [CSES : Subarray Sum](https://cses.fi/problemset/task/1660) >- [ ] [ITMO - Big Sum](https://codeforces.com/edu/course/2/lesson/9/2/practice/contest/307093/problem/B) >- [ ] [ITMO - Number of small sum segments](https://codeforces.com/edu/course/2/lesson/9/2/practice/contest/307093/problem/C) >- [ ] [ITMO - Knapsack on a segment](https://codeforces.com/edu/course/2/lesson/9/3/practice/contest/307094/problem/E) >- [ ] [CF - Cellular network](https://codeforces.com/contest/702/problem/C) * ***Additional problems*** >- [ ] [CSES : Subarray Distinct Values](https://cses.fi/problemset/task/2428) >- [ ] [CSES : Sum of 4 values](https://cses.fi/problemset/task/1642) >- [ ] [CF - Quiz Master](https://codeforces.com/contest/1777/problem/C)(try coming back to this question after you learn about sieve method) ## ➡️Range Queries `Prefix Sums are Intensively Used in other problems to reduce Time Complexity of Solution.` >:star: Expected time : 40 - 50 minutes * [CPH Range Queries](https://cses.fi/book/book.pdf#page=93) (before Binary Indexed Tree) * [USACOBOOK ch11 Prefix Sums](https://darrenyao.com/usacobook/cpp.pdf#page=60) * [Solved Examples Leetcode](https://leetcodethehardway.com/tutorials/basic-topics/prefix-sum) two solved illustrations; more problems to solve. * [Maximum Sum Subsection](https://www.iarcs.org.in/inoi/online-study-material/topics/prefix-sums-maximum-sum-subsection.php) - Problems : >- [ ] [CSES : Sum Queries](https://cses.fi/problemset/task/1646) , [Xor Queries](https://cses.fi/problemset/task/1650) >- [ ] [CF - Playing in a Casino](https://codeforces.com/problemset/problem/1808/B) >- [ ] [CSES : Subarray Sums II](https://cses.fi/problemset/task/1661/) >- [ ] [Codechef : GCD Discount](https://www.codechef.com/problems/GCDISCOUNT) - - [ ] [CSES : Maximum Subarray Sum](https://cses.fi/problemset/task/1643) : :::spoiler Hint search for ***Kadane’s Algorithm*** ::: * ***2 D Prefix Sum*** >* [Ramu's Mango Trees](https://www.iarcs.org.in/inoi/online-study-material/topics/prefix-sums-ramus-mango-trees.php) >- [ ] [CSES : Forest Queries](https://cses.fi/problemset/task/1652) >- [ ] [Aizu Online Judge - Maximum Number of Overlaps](https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/5/DSL_5_B) ### Additional Practice >- [ ] [USACO - Subsequences Summing to Sevens](https://usaco.org/index.php?page=viewproblem2&cpid=595) >- [ ] [CF - Data Structures Fan](https://codeforces.com/contest/1872/problem/E) >- [ ] [CSES : Subarray Divisibility](https://cses.fi/problemset/task/1662/) ## ➡️Divide and Conquer >:star: Expected time : 20 - 30 minutes Read [this](https://www.programiz.com/dsa/divide-and-conquer) to know what divide and conquer is. Watch this [video](https://www.youtube.com/watch?v=ib4BHvr5-Ao) to get more insight into this topic >- [ ] [CF - Lost numbers](https://codeforces.com/problemset/problem/1167/B) >- [ ] [CF - Print the pattern](https://vjudge.net/problem/SPOJ-ABACABA) >- [ ] [CF - Permutation Transformation](https://codeforces.com/contest/1490/problem/D) >- [ ] [CF - Maximum Crossings](https://codeforces.com/problemset/problem/1676/H2) >- [ ] [CF - Greetings](https://codeforces.com/problemset/problem/1915/F) ## ➡️Intro to Greedy Algorithms >:star: Expected time : 1.5 - 2 hours `Moving in the direction which gives the most optimal solution at every step is a major characteristic of these algorithms.` * Read [Greedy Algorithms - CPH ](https://cses.fi/book/book.pdf#page=67) and [Job Scheduling ](https://cp-algorithms.com/schedules/schedule-with-completion-duration.html) to get a better idea of these algorithms . [Greedy | LeetCode The Hard Way](https://leetcodethehardway.com/tutorials/basic-topics/greedy) * Alternatively, you may go through [this](https://www.youtube.com/watch?v=bC7o8P_Ste4) video. Here are some questions : >- [ ] [CF - Studying algorithms](https://codeforces.com/gym/102951/problem/B) - An easy problem to start with >- [ ] [Optimal Merge Pattern ](https://www.geeksforgeeks.org/optimal-file-merge-patterns/)- Involves the use of multiset/priority queue ### **SELF ASSESSMENT** : >- [ ] [CF -Heavy Intervals ](https://codeforces.com/problemset/problem/1909/C) >- [ ] [CF - Contrast Values](https://codeforces.com/problemset/problem/1832/C) >- [ ] [CF - Grid Reconstruction ](https://codeforces.com/problemset/problem/1816/B) >- [ ] [CSES - Ferris Wheel ](https://cses.fi/problemset/task/1090) >- [ ] [CSES - Movie festival](https://cses.fi/problemset/task/1629) >- [ ] [CSES - Towers](https://cses.fi/problemset/task/1073) >- [ ] [CSES - Movie festival 2](https://cses.fi/problemset/task/1632) ## ➡️Dynamic Programming ### **Basic Concepts :** `Dynamic Programming , more famously known as DP is a technique in which we calculate and store subproblems in a particular problem.` There are two methods to apply dp in your code : recursion and iteration . >:star: Expected time : 1.5 - 2 hours * [This video](https://www.youtube.com/watch?v=YBSt1jYwVfU&list=PLl0KD3g-oDOGJUdmhFk19LaPgrfmAGQfo&index=1) explains the difference between the two implementations for _fibonacci numbers_, then try this problem : >- [ ] [CSES : Dice Combinations](https://cses.fi/problemset/task/1633) * Read [Chapter - 7 CPH](https://cses.fi/book/book.pdf#page=75) * [Classic Solved Illustrations](https://www.iarcs.org.in/inoi/online-study-material/topics/dp-classics.php) - After completing above resources for DP , you can now do the following standard problems : >- [ ] [Longest Increasing Subsequence - LeetCode](https://leetcode.com/problems/longest-increasing-subsequence/description/) >>:::spoiler Video Solution >>[Youtube](https://youtu.be/4fQJGoeW5VE?si=faWSyyc0KmdP9GEO) >>::: >- [ ] [Longest Common Subsequence - LeetCode](https://leetcode.com/problems/longest-common-subsequence/description/) >>:::spoiler Video Solution >>[Youtube](https://youtu.be/Wv1y45iqsbk?si=RpyyYGOV4E0nZnL9) >>::: >- [ ] [Longest Palindromic substring - LeetCode](https://leetcode.com/problems/longest-palindromic-substring/description/) >- [ ] [CSES : Edit Distance](https://cses.fi/problemset/task/1639) >- [ ] [Atcoder - Knapsack 1](https://atcoder.jp/contests/dp/tasks/dp_d) ### **DP on Grids :** [This tutorial ](https://atcoder.jp/contests/dp/tasks/dp_d)has some generic problems which will develop your understanding about grids . >- [ ] [CSES : Grid Paths ](https://cses.fi/problemset/task/1638)( A tougher version of counting number of paths from one corner to another ) >- [ ] [Superjump in a grid](https://www.hackerearth.com/practice/algorithms/dynamic-programming/2-dimensional/practice-problems/algorithm/superjump-in-a-grid-773f1e31/)- Another variant of path counting problem >- [ ] [LeetCode - Cherry Pickup-2 ](https://leetcode.com/problems/cherry-pickup-ii/description/?envType=problem-list-v2&envId=50izszui)( Here we have 2 sources , different as compared to other questions , think about dp-states) [TOUGH QUESTION] ### **DP Bitmask :** >:star: Expected time : 1.5 - 2 hours * Read this [blog ](https://codeforces.com/blog/entry/18169)( it is based on the CP book of Felix & Halim ) to begin with bitmasking . Follow this [tutorial ](https://www.hackerearth.com/practice/algorithms/dynamic-programming/bit-masking/tutorial/)for further understanding . * More resources - [Advanced DP concepts](https://www.youtube.com/watch?v=JvNHdmxTc74) (you may follow up to 45:00 ) * ***Some Problems :*** >- [ ] [CF - Vampiric Powers, anyone?](https://codeforces.com/contest/1847/problem/C) >- [ ] [CSES : Counting Tilings](https://cses.fi/problemset/task/2181) >- [ ] [CSES : Elevator Rides](https://cses.fi/problemset/task/1653) `DP is a topic which can be mastered only through practice.` - Some resources for practice : - [AtCoder DP Contest ](https://atcoder.jp/contests/dp) - [CF Problemset ](https://codeforces.com/problemset)(Use tag=dp in filters ) - [CSES Problem Set](https://cses.fi/problemset/) (DP section) ### **SELF-ASSESSMENT ( Topic : DP )** >- [ ] [CF - Nikita and String ](https://codeforces.com/problemset/problem/877/B) >- [ ] [CSES : Coin Combinations - 1 ](https://cses.fi/problemset/task/1635)( You can also try Coin combinations-2 on CSES ) >- [ ] [CF - Counting Rectangles](https://codeforces.com/problemset/problem/1722/E) >- [ ] [CF - Marvalo Gaunt's Ring ](https://codeforces.com/problemset/problem/855/B) >- [ ] [CSES : Rectangle Cutting](https://cses.fi/problemset/task/1744) >- [ ] [CF - Woodcutters](https://codeforces.com/problemset/problem/545/C) >- [ ] [CF - Tetrahedron ](https://codeforces.com/problemset/problem/166/E) >:::spoiler Extra >There exist both dp and math based solutions , the math solution can be found if you know about recursive relations and how to find their solutions using quadratic equations , this solution has a time complexity of _O(log(n))_ and uses binary exponentiation >::: >- [ ] [CF - Long Path](https://codeforces.com/problemset/problem/407/B) >:::spoiler Extra >There are two dp solutions one having O(n) time complexity and the other being O(n^2) .. which one were you able to spot >::: - ***Some Question on Dp + Probability and expected values :*** >- [ ] [CF - Bad Luck Island](https://codeforces.com/problemset/problem/540/D) >- [ ] [CF - Jeff and Furik](https://codeforces.com/problemset/problem/351/B) >>:::spoiler >>Interestingly you can solve this question even without dp but this solution still demands generalizing the solution , can you spot this >>::: >- [ ] [Atcoder - Sushi](https://atcoder.jp/contests/dp/tasks/dp_j) ## ➡️Interactive Problems >:star: Expected time : 15 - 20 minutes [Here](https://codeforces.com/blog/entry/45307) is a tutorial on how to solve interactive problems . ### Here are some questions : >- [ ] [CF - Interview](https://codeforces.com/problemset/problem/1807/E) >- [ ] [CF - Guess The Array](https://codeforces.com/contest/727/problem/C) >- [ ] [CF - Bit Guessing game ](https://codeforces.com/contest/1780/problem/D)(Involves bit manipulations ) :::success Some more tools to help you in your journey : * ==[Diffchecker](https://www.diffchecker.com/text-compare/)== - some problems have large output files. Use this tool to compare your generated output and problem's expected output. CodeForces Chrome Extensions : * ==[CF Analytics](https://chrome.google.com/webstore/detail/cf-analytics/hhljbjodjdbjbggddjaidojnlmaobcpo)== - improves the Codeforces profile webpage to include statistics of problems solved by the user. * ==[CodeForces Enhancer](https://chromewebstore.google.com/detail/codeforces-enhancer/ocmandagmgmkcplckgnfgaokpgkfenmp?hl=en)== - multiple ratings graph, adds "Hide/Show solved problems" link to Problemset page * ==[Carrot](https://chrome.google.com/webstore/detail/carrot/gakohpplicjdhhfllilcjpfildodfnnn)== - predicts actual performance in the contest, how many rating points you will gain after the contest, etc. * ==[Conding Dude](https://chromewebstore.google.com/detail/codingdude-contest-remind/gceicoplhhmgcoanpkbnopdccpghbngk)== - Contest Reminder ::: ## ➡️Section 1 Additional Practice: >- [ ] [CodeChef - Mathison and the Dynamo shuffle](https://www.codechef.com/problems/MATDYS) >- [ ] [CF - Long Multiplication](https://codeforces.com/problemset/problem/1954/C) >- [ ] [SPOJ.com - Eko](https://www.spoj.com/problems/EKO/cstart=20) >- [ ] [LeetCode : Container with Most Water](https://leetcode.com/problems/container-with-most-water/description/) >- [ ] [CF - Final Boss](https://codeforces.com/problemset/problem/1985/F) >- [ ] [SPOJ.com - ABCDEF](https://www.spoj.com/problems/ABCDEF/) >- [ ] [CF - Update Queries](https://codeforces.com/contest/1986/problem/C) >- [ ] [CF - Forming Triangles](https://codeforces.com/problemset/problem/1922/B) >- [ ] [CF - Binary Search ](https://codeforces.com/contest/1945/problem/E) >- [ ] [CF - Inaccurate Subsequence Search](https://codeforces.com/contest/1955/problem/D) # Section 2: Intermediate ```markmap # SECTION 2 ## [Advanced Maths](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#%E2%9E%A1%EF%B8%8FAdvanced-Maths) ## [Range Update Queries](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#%E2%9E%A1%EF%B8%8FRange-Update-Queries) ## [Graph Theory Basics](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#%E2%9E%A1%EF%B8%8FGraph-Theory-Basics) ### [DSU + MST](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#%E2%9E%A1%EF%B8%8FDSU--MST) ### [Shortest Path Algorithms](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#%E2%9E%A1%EF%B8%8FShortest-Path-Algorithms---Dijkstra-Floyd-Warshall-Bellman-Ford) ``` ## ➡️Advanced Maths ### :maple_leaf: **Combinatorics** >:star: Expected time : 15 - 20 minutes * Read the following topics : [Binomial Coefficients](https://cp-algorithms.com/combinatorics/binomial-coefficients.html) , [Catalan Numbers ](https://codeforces.com/blog/entry/87585) * Refer [CPH Ch 22 ](https://cses.fi/book/book.pdf#page=217)for further reading * Some questions : >- [ ] [DPL_5 &lt; Library &lt; Courses | Aizu Online Judge](https://onlinejudge.u-aizu.ac.jp/courses/library/7/DPL/5) (all 12 types of cases) >- [ ] [Virtual Judge - One Unit Machine](https://vjudge.net/problem/UVA-11904) >- [ ] [CSES : Christmas Party](https://cses.fi/problemset/task/1717) >- [ ] [CF - Secret Box](https://codeforces.com/problemset/problem/1985/E) * Some additional Problems: >- [ ] [CF - Earning on Bets](https://codeforces.com/problemset/problem/1979/C) >- [ ] [CF - How does the rook move?](https://codeforces.com/problemset/problem/1957/C)(try using your DP skills here) >- [ ] [CF - Blueprint for Seating](https://codeforces.com/problemset/problem/1912/B) >:::spoiler Hint >This may be tough but if you can, try thinking about all the valid permutations. Trust me you’ll be very happy if you figure the answer out ;-) >::: ### :maple_leaf: **Matrices** >:star: Expected time : 1 - 1.5 hours * For learning about the implementation of basic operations on matrices read [CPH Ch23](https://cses.fi/book/book.pdf#page=227). * A few ad hoc problems based on matrices- >- [ ] [CF - Weird Sum](https://codeforces.com/problemset/problem/1648/A) >- [ ] [CF - Permutation on rows and columns](https://codeforces.com/problemset/problem/1980/E) * Read this [Blog | CodeForces ](https://codeforces.com/blog/entry/67776) or [Matrix Exponentiation | Code Accepted](https://codeaccepted.wordpress.com/2014/06/01/algorithm-12-matrix-exponentiation/) , it would help to solve recurrence based questions using matrices . * [Matrix Exponentiation tutorial + training contest | CodeForces](https://codeforces.com/blog/entry/80195) * Some problems on Matrix Exponentiation: >- [ ] [CSES : Fibonacci Numbers](https://cses.fi/problemset/task/1722) >- [ ] [CF - Random Mood](https://codeforces.com/gym/102644/problem/A) >- { the following problems require basic graph theory } : >>- [ ] [CSES : Graph Paths I](https://cses.fi/problemset/task/1723) ; you may refer [this](https://cp-algorithms.com/graph/fixed_length_paths.html) for a hint. >>- [ ] [AtCoder - Walk](https://atcoder.jp/contests/dp/tasks/dp_r) >>- [ ] [CSES : Graph Paths II](https://cses.fi/problemset/task/1724) ### :maple_leaf: **Probability** >:star: Expected time : 1 - 1.5 hours * Read [CPH Ch 24](https://cses.fi/book/book.pdf#page=235) * Read [blog/video](https://codeforces.com/blog/entry/62792) * Problems - >- [ ] [CF - Archer](https://codeforces.com/problemset/problem/312/B) >- [ ] [CF - Little Pony and Expected Maximum](https://codeforces.com/problemset/problem/453/A) >- [ ] [CF - Random Events](https://codeforces.com/problemset/problem/1461/C) >- [ ] [CF - Andrey and Problem](https://codeforces.com/problemset/problem/442/B) >- [ ] [CF - Bag of mice](https://codeforces.com/problemset/problem/148/D) ### :maple_leaf: **Extra Number Theory** >:star: Expected time : 1 - 1.5 hours * [CPH Ch 21](https://cses.fi/book/book.pdf#page=207) * [Solving system of congruences | AlgorithmClear Blog](https://algorithmclear.blog/blog/system-of-congruences) * Some more problems : >- [ ] [SPOJ.com - Euler Totient Function Depth](https://www.spoj.com/problems/ETFD/) ## ➡️Range Update Queries >:star: Expected time : 1.5 - 2 hours * [CPH Range Queries](https://cses.fi/book/book.pdf#page=93) (may skip Fenwick Tree, as Segment Tree is able to do anything one can do with Fenwick Tree) * Segment Trees * [CS Academy Tutorial](https://csacademy.com/lesson/segment_trees) OR * [CP Algorithms Tutorial](https://cp-algorithms.com/data_structures/segment_tree.html) (only read Simplest form of a Segment Tree for now) * Fenwick Trees (optional ; may read just for knowledge) * [CS Academy Tutorial](https://csacademy.com/lesson/fenwick_trees) OR * [CP Algorithms Tutorial](https://cp-algorithms.com/data_structures/fenwick.html) - Let’s get started with practice : * [ITMO step 1 theory](https://codeforces.com/edu/course/2/lesson/4/1) read the article below / watch videos 1,3 for the same content >- [ ] [ITMO - Segment Tree for the Sum](https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/problem/A) for solution : watch a video with the title ‘CODE 1’ on [above link](https://codeforces.com/edu/course/2/lesson/4/1) >- [ ] [CSES - Segment Tree for the Minimum](https://cses.fi/problemset/task/1649) >- [ ] [ITMO - Number of Minimums on a Segment](https://codeforces.com/edu/course/2/lesson/4/1/practice/contest/273169/problem/C) soln : CODE 2 on [above link](https://codeforces.com/edu/course/2/lesson/4/1) >- [ ] [SPOJ.com - Range Sum](https://www.spoj.com/problems/RANGESUM/) >- [ ] [CF - Thor](https://codeforces.com/problemset/problem/704/A) - [ITMO step 3](https://codeforces.com/edu/course/2/lesson/4/3) go through theory , problems , solutions in order; then solve : ## ➡️Graph Theory Basics >:star:Expected time : 40 - 60 minutes * Here is a brief [intro to graphs ](https://csacademy.com/lesson/introduction_to_graphs)and its [representation](https://csacademy.com/lesson/graph_representation). * You may also refer [Representation of Graphs | Code Accepted](https://codeaccepted.wordpress.com/2014/03/17/representation-of-graphs/), then solve this problem : - [ ] [Spoj - ROADNET](https://www.spoj.com/problems/ROADNET/) * Here’s a video if you prefer those : [Introduction to Graph Theory: A Computer Science Perspective](https://www.youtube.com/watch?v=LFKZLXVO-Dg) ### :maple_leaf: BFS and DFS >:star: Expected time : 30 - 40 minutes * There are two basic (and extremely useful) algorithms for graph traversal : BFS and DFS. * To understand them, read page number 117 to 122 from this [handbook](https://usaco.guide/CPH.pdf#page=127). * Or we recommend watching these videos : * [Depth First Search (DFS) Explained: Algorithm, Examples, and Code](https://www.youtube.com/watch?v=PMMc4VsIacU) * [Breadth First Search (BFS): Visualized and Explained](https://www.youtube.com/watch?v=xlVX7dXLS64) (Also has the flood fill problem!) * Here are some problems : >- [ ] [CSES - Message Route](https://cses.fi/problemset/task/1667/) >- [ ] [CF - Two Buttons](https://codeforces.com/problemset/problem/520/B) >- [ ] [USACO - Moocast](https://usaco.org/index.php?page=viewproblem2&cpid=668) >- [ ] [CF - Kefa and Park](https://codeforces.com/problemset/problem/580/C) >- [ ] [CF - Round Dance](https://codeforces.com/contest/1833/problem/E) >- [ ] [CSES - Building Teams](https://cses.fi/problemset/task/1668) (Question on bipartiteness) ### :maple_leaf: Cycles Detection >:star: Expected time : 20 - 30 minutes * [This](https://cp-algorithms.com/graph/finding-cycle.html) and [This](https://www.tutorialspoint.com/print-all-the-cycles-in-an-undirected-graph-in-cplusplus) article will help you understand how to find cycles. * Problems : >- [ ] [CSES : Round Trip](https://cses.fi/problemset/task/1669) >- [ ] [CSES : Round Trip II](https://cses.fi/problemset/task/1678/) * Other problems for bidirectional graphs : >- [ ] [SPOJ.com - Cactus](https://www.spoj.com/problems/CAC/) : use unsigned long long int ;) >- [ ] [CF - Forest Program](https://codeforces.com/gym/102361/problem/F) ### :maple_leaf: Bridges in Graphs >:star: Expected time : 30 - 40 minutes * [[Tutorial] DFS TREE | CodeForces](https://codeforces.com/blog/entry/68138) * Problems : >- [ ] [Critical Edges](https://www.spoj.com/problems/EC_P/) >- [ ] [Bertown roads](https://codeforces.com/contest/118/problem/E) ### :maple_leaf: Flood Fill >:star: Expected time : 15 - 20 minutes * To understand flood fill, you can go through [this](https://usaco.guide/silver/flood-fill?lang=cpp) article. It was also covered in the video above. * Problems: >- [ ] [LeetCode : Flood Fill](https://leetcode.com/problems/flood-fill/description/) >- [ ] [CSES : Counting Rooms](https://cses.fi/problemset/task/1192) ### :maple_leaf: Topological Sort `Sorting nodes of a directed graph in an order in which they can appear in a path.` Note : we can only find topological sorting for an acyclic directed graph. >:star: Expected time : 40 - 60 minutes * You can read [this](https://leetcode.com/discuss/study-guide/4252467/TopoLogical-Sorting-On-Graph/) or watch [this](https://youtu.be/eL-KzMXSXXI?si=k0rwm1m2O8BaAct1) to understand topological sort. * [CPH 16.1](https://usaco.guide/CPH.pdf#page=159) * There is also [Kahn's Algorithm](https://youtu.be/cIBFEhD77b4?si=Ka0xzsnkin2MOE59) * Here are some problems: >- [ ] [CSES : Course Schedule](https://cses.fi/problemset/task/1679) >- [ ] [SPOJ.com - Answer the boss!](https://www.spoj.com/problems/RPLA/) >- [ ] [CF : Fox and Names](https://codeforces.com/problemset/problem/510/C) >- [ ] [AtCoder - Find Permutation](https://atcoder.jp/contests/abc291/tasks/abc291_e) :::warning Number of topological sortings for a directed tree is discussed in Section 3 Tree Algorithms : :maple_leaf: DP on Trees ::: ### :maple_leaf: Subtree/DFS Problems * try these problems >- [ ] [CSES : Subordinates](https://cses.fi/problemset/task/1674) >- [ ] [CF - Journey](https://codeforces.com/contest/839/problem/C) >- [ ] [LeetCode - Binary Tree Maximum Path Sum](https://leetcode.com/problems/binary-tree-maximum-path-sum/description/) >- [ ] [Codechef : Chef and Subtree MEXs](https://www.codechef.com/problems/SUBMEXS) (hint : Problem [Subordinates](https://cses.fi/problemset/task/1674)) ## ➡️DSU + MST ### Disjoint Set Union >:star: Expected time : 1.5 - 2 hours * DSU is a data structure that allows us to combine two sets, find out which set a particular element belongs to and allows us to create a set from a new element. * [This](https://youtu.be/vq5u09x2Kzo?si=7Ft_za0F8qD6lA7j) video lecture will help you understand it well! >- [ ] [CSES - Road Construction](https://cses.fi/problemset/task/1676/) >- [ ] [ITMO - Cutting a graph](https://codeforces.com/edu/course/2/lesson/7/1/practice/contest/289390/problem/D) >- [ ] [CF - Unforgivable Curse (hard version)](https://codeforces.com/problemset/problem/1800/E2) >- [ ] [CF - Roads not only in Berland](https://codeforces.com/contest/25/problem/D) >- [ ] [USACO - Wormhole Sort](https://usaco.org/index.php?page=viewproblem2&cpid=992) ### Minimum Spanning Trees >:star: Expected time : 1 - 1.5 hours 1. [PAPS Section 12.4](https://usaco.guide/PAPS.pdf#page=215) 2. [How Do You Calculate a Minimum Spanning Tree?](https://www.youtube.com/watch?v=Yldkh0aOEcg) 3. [CPH](https://usaco.guide/CPH.pdf#page=151) OR 3. Read these articles : [Kruskal](https://cp-algorithms.com/graph/mst_kruskal.html) , [Kruskal DSU](https://cp-algorithms.com/graph/mst_kruskal_with_dsu.html) , [Prim's Algo](https://cp-algorithms.com/graph/mst_prim.html) OR 3. Go through these videos : [Kruskal using DSU](https://youtu.be/5xosHRdxqHA?si=k-DdsiPoBlkV6hfx) , [Prim's Algo](https://youtu.be/z1L3rMzG1_A?si=OXHdZ3G2Fs6ew0sG) * Practice : >- [ ] [CSES - Road Reparation](https://cses.fi/problemset/task/1675) >- [ ] [SPOJ.com - BMW](https://www.spoj.com/problems/MARYBMW/) >- [ ] [ITMO : Dense Spanning Tree](https://codeforces.com/edu/course/2/lesson/7/2/practice/contest/289391/problem/F) ([Hint - Wikipedia](https://en.wikipedia.org/wiki/Minimum_bottleneck_spanning_tree#Properties)) >- [ ] [Codechef - Chefland and Electricity](https://www.codechef.com/problems/CHEFELEC) >- [ ] [Atcoder - Choose Two and Eat One](https://atcoder.jp/contests/abc282/tasks/abc282_e) ## ➡️Shortest Path Algorithms - Dijkstra, Floyd Warshall, Bellman Ford >:star: Expected time : 1 - 1.5 hours * You can go through Ch - 13 of [this](https://usaco.guide/CPH.pdf#page=133) book for better understanding or if video lectures are more up your alley, you can watch these : [Dijkstra](https://www.youtube.com/watch?v=pSqmAO-m7Lk), [Bellman Ford](https://www.youtube.com/watch?v=lyw4FaxrwHg), [Floyd Warshall](https://www.youtube.com/watch?v=4NQ3HnhyNfQ). * Problems : >- [ ] [CSES : Shortest Routes I](https://cses.fi/problemset/task/1671) (Djikstra) >- [ ] [CSES : Shortest Routes II](https://cses.fi/problemset/task/1672/) (Floyd Warshall) >- [ ] [CSES : Flight Discount](https://cses.fi/problemset/task/1195/) >- [ ] [CSES : Cycle Finding ](https://cses.fi/problemset/task/1197/)(Bellman Ford) >- [ ] [LeetCode - Path with Maximum Probability](https://leetcode.com/problems/path-with-maximum-probability/editorial/) >- [ ] [USACO : Milk Pumping](https://usaco.org/index.php?page=viewproblem2&cpid=969) ## ➡️Section 2 Additional Practice: >- [ ] [CSES : Distributing Apples](https://cses.fi/problemset/task/1716) >- [ ] [CSES - Prime Multiples](https://cses.fi/problemset/task/2185) >- [ ] [CSES : Graph Girth](https://cses.fi/problemset/task/1707/) >- [ ] [CF - Labyrinth](https://codeforces.com/contest/1064/problem/D) (you can use [0-1 BFS](https://cp-algorithms.com/graph/01_bfs.html)) >- [ ] [CF - Cyclic Components](https://codeforces.com/contest/977/problem/E) >- [ ] [CF - Number of Simple Paths](https://codeforces.com/contest/1454/problem/E) >- [ ] [CF - Arrayland's Challenge](https://codeforces.com/problemset/gymProblem/105164/A) - On the tougher side >- [ ] [CF - Lonely Mountain Dungeons ](https://codeforces.com/problemset/problem/1928/D) >- [ ] [SPOJ.com - Fibonacci Sum](https://www.spoj.com/problems/FIBOSUM/) >- [ ] [CF - Turtle Mission: Robot and the Earthquake](https://codeforces.com/problemset/problem/1933/F) >- [ ] [CF - Friendly Spiders](https://codeforces.com/problemset/problem/1775/D) >- [ ] [CF - GCD and MST](https://codeforces.com/problemset/problem/1513/D) >- [ ] [CF - Split Into Two Sets](https://codeforces.com/problemset/problem/1702/E) Optional : * [Bacterial Sampling ](https://codeforces.com/gym/105164/problem/B)- Find the Z matrix of the recursion - Time complexity O(log(n)) with a constant of 20*20 # Section 3: Advanced ```markmap # SECTION 3 ## [String Hashing](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#%E2%9E%A1%EF%B8%8FString-Hashing) ## [Directed Graphs](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#%E2%9E%A1%EF%B8%8FDirected-Graphs) ## [Range Update](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#%E2%9E%A1%EF%B8%8FRange-Update-Queries-continued%E2%80%A6) ## [Sparse Table](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#%E2%9E%A1%EF%B8%8F-Sparse-Table) ## [Tree Algorithm](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#%E2%9E%A1%EF%B8%8FTree-Algorithm-Problems) ``` ## ➡️String Hashing >:star: Expected time : 2 - 2.5 hours * Read [ch 26](https://usaco.guide/CPH.pdf#page=253) to get an overview of string algorithms like hashing, z-algorithm and trie structure. * Refer to [this video](https://youtu.be/6t_1eRO-Cqo?si=ub0-_G8fkybx-xQs) for a detailed explanation. It also explains algorithms like Knuth-Morris-Pratt (KMP) algorithm. * [This](https://cp-algorithms.com/string/aho_corasick.html) article covers Aho-Corasick algorithm * Problems : >- [ ] [CSES - Finding Borders](https://cses.fi/problemset/task/1732) >- [ ] [CF - Password](https://codeforces.com/problemset/problem/126/B) >- [ ] [CF - Compress Words](https://codeforces.com/contest/1200/problem/E) >- [ ] [CSES - Word Combinations](https://cses.fi/problemset/task/1731) >- [ ] [CSES - Finding Patterns](https://cses.fi/problemset/task/2102) >- [ ] [CF - Tavas and Malekas](https://codeforces.com/problemset/problem/535/D) ## ➡️Directed Graphs >:star: Expected time : 1.5 - 2 hours * A directed graph is a graph where the edges have a direction. * Theory on Directed Graphs : [CPH Ch 16](https://usaco.guide/CPH.pdf#page=159) >- [ ] [Codechef - MaxEdges](https://www.codechef.com/practice/course/3-star-difficulty-problems/DIFF1700/problems/MAXEDGES?tab=statement) >- [ ] [LeetCode - Minimum Number of Vertices to Reach All Nodes](https://leetcode.com/problems/minimum-number-of-vertices-to-reach-all-nodes/description/) ### :maple_leaf: Cycles in Directed graphs #### Functional Graphs * Graphs where each node has exactly one outgoing edge (outdegree = 1) >- [ ] [CSES - Planet Queries I](https://cses.fi/problemset/task/1750) , use : [CPH 16.3](https://usaco.guide/CPH.pdf#page=164) * *Cycle Finding :* 1. We can use [Floyd's Cycle Finding Algorithm](https://cp-algorithms.com/others/tortoise_and_hare.html) + [Visualization](https://visualgo.net/en/cyclefinding?slide=1) also known as Tortoise and Hare Algorithm 2. We can also use Kahn's algorithm :::info In Kahn's Algorithm : If all nodes in the graph are not removed as zero degree -> it implies that there must be cycles. ::: * Solve the following problems involving cycles: (a graph with vertices = n and edges >= n will have atleast one cycle) >- [ ] [USACO - The Bovine Shuffle](https://usaco.org/index.php?page=viewproblem2&cpid=764) >- [ ] [USACO - Visits](https://usaco.org/index.php?page=viewproblem2&cpid=1230) >:::success >- [ ] [ CSES - Planets Cycles ](https://cses.fi/problemset/task/1751) >**or** >- [ ] [ Atcoder - Reachability in Functional Graph ](https://atcoder.jp/contests/abc357/tasks/abc357_e) >{both problems have the same answer} >::: >- [ ] [CF - Secret Santa](https://codeforces.com/contest/1530/problem/D) ### :maple_leaf: Strongly Connected Components : A part of graph (component) is said to be strongly connected if there is a path from any node to all other nodes in the component. In Function Graphs : Every cycle alone is a SCC; Generally : if two cycles share a vertex they both come under the same SCC. * Start with [CPH Ch 17](https://usaco.guide/CPH.pdf#page=167) ; Learn any of these algorithms to solve problems 1. Kosaraju's Algorithm + [Techdose - Youtube](https://youtu.be/Rs6DXyWpWrI?si=htI10iYGvFmaUp83) + [CP Algos Article](https://cp-algorithms.com/graph/strongly-connected-components.html) 2. Tarjan's Algorithm + [William Fiset - Youtube](https://www.youtube.com/watch?v=wUgWX0nc4NY) + [Tutorial | CodeForces](https://codeforces.com/blog/entry/131187) * Try these problems : >- [ ] [CSES - Flight Routes Check](https://cses.fi/problemset/task/1682) >- [ ] [CSES - Planets and Kingdoms](https://cses.fi/problemset/task/1683) >- [ ] [CF - Checkposts](https://codeforces.com/contest/427/problem/C) :::info If you make disjoint sets of vertices within a SCC and join edges connecting SCCs; you get a **Condensation Graph**. This graph does not contain cycles as in that case they would form another SCC. Thus it's a Directed Acyclic Graph. ::: * Problems involving more ideas like condensation , topological sort : >- [ ] [CSES - Coin Collector](https://cses.fi/problemset/task/1686) >- [ ] [SPOJ.com - Good Travels](https://www.spoj.com/problems/GOODA/) >- [ ] [CF - Scheme](https://codeforces.com/contest/22/problem/E) ### :maple_leaf: 2-SAT * Go through one of these + [CPH 17.2](https://usaco.guide/CPH.pdf#page=170) + [Blog | CodeForces](https://codeforces.com/blog/entry/92977) + [CP Algorithms Article](https://cp-algorithms.com/graph/2SAT.html) + [Algorithms Live! | Youtube](https://www.youtube.com/watch?v=0nNYy3rltgA) * Attempt these problems >- [ ] [Kattis - Illumination](https://open.kattis.com/problems/illumination) >- [ ] [UVA - Rectangles](https://vjudge.net/problem/UVA-11930) >- [ ] [CSES : Giant Pizza](https://cses.fi/problemset/task/1684) >- [ ] [CF - Problem H +-1](https://codeforces.com/contest/1971/problem/H) ### :maple_leaf: DP on DAGs DAGs stands for Directed Acyclic Graphs, Trees are a particular kind of DAG. 1. Try this simple problem to start with : - [ ] [AtCoder - Longest Path](https://atcoder.jp/contests/dp/tasks/dp_g) 2. Then read [CPH 16.2](https://usaco.guide/CPH.pdf#page=161) and [DP on Trees and Graphs | CSE 421](https://courses.cs.washington.edu/courses/cse421/23wi/lecture/15-dp-graphs.pdf) 3. If you prefer to watch some videos : * [MultiStage Graph | Abdul Bari - Youtube](https://www.youtube.com/watch?v=9iE9Mj4m8jk&list=PLJULIlvhz0rE83NKhnq7acXYIeA0o1dXb&index=2) * [Shortest/Longest path on a DAG - WilliamFiset | Youtube](https://www.youtube.com/watch?v=TXkDpqjDMHA) 4. Problems : >- [ ] [CF - Pashmak and Graph](https://codeforces.com/problemset/problem/459/E) >- [ ] [CSES : Game Routes](https://cses.fi/problemset/task/1681) - video solution : [Codenzyme | Youtube](https://www.youtube.com/watch?v=0qQItpKVzdU&list=PLUpzFxGnjRcvRupvAGyUC1DUhVGM_C-fa&index=10) >- [ ] [LeetCode - All Ancestors of a Node in a Directed Acyclic Graph](https://leetcode.com/problems/all-ancestors-of-a-node-in-a-directed-acyclic-graph/description/) >- [ ] [SPOJ.com - Counting in a DAG](https://www.spoj.com/problems/DAGCNT2/) >- [ ] [CSES - Investigation](https://cses.fi/problemset/task/1202) 5. [DP on Trees](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#-Tree-Queries) ## ➡️Range Update Queries (continued)... >:star: Expected time : 1.5 - 2 hours This topic is continued from the previous section. * Try this problem : [CF - Xenia and Bit Operations](https://codeforces.com/problemset/problem/339/D) * [More Complex Queries](https://cp-algorithms.com/data_structures/segment_tree.html#more-complex-queries) ( Continued from earlier CP - Algos article) * [ITMO Step 2](https://codeforces.com/edu/course/2/lesson/4/2) - Go through theory, problems, solutions in order then solve : >- [ ] [CSES : Hotel Queries](https://cses.fi/problemset/task/1143) >- [ ] [CF - Merge Equals](https://codeforces.com/problemset/problem/962/D) >- [ ] [CSES : List Removals](https://cses.fi/problemset/task/1749/) >- [ ] [CSES : Bit Inversions](https://cses.fi/problemset/task/1188/) >- [ ] [CSES : Range Update Queries](https://cses.fi/problemset/task/1651) (hint : [CPH](https://cses.fi/book/book.pdf#page=103)) >- [ ] [CF - Distinct Characters Queries](https://codeforces.com/problemset/problem/1234/D) ### :maple_leaf: Additional (optional) : * [ITMO step 4 ](https://codeforces.com/edu/course/2/lesson/4/4/practice)(no video solutions) >- [ ] [CSES - Increasing Subsequence II](https://cses.fi/problemset/task/1748/) (hint : step 3) * [Range Update Seg Tree](https://www.iarcs.org.in/inoi/online-study-material/topics/range-queries-interval-updates-point-queries.php) , [ITMO step 5](https://codeforces.com/edu/course/2/lesson/5/1) * Range Queries in two Dimensions * Read [CP Algorithms article](https://cp-algorithms.com/data_structures/fenwick.html#finding-sum-in-two-dimensional-array) / [TopCoder article](https://www.topcoder.com/thrive/articles/Binary%20Indexed%20Trees#2d) >- [ ] [SPOJ.com - Matrix Summation](https://www.spoj.com/problems/MATSUM/) >- [ ] [CSES - Forest Queries II](https://cses.fi/problemset/task/1739) * [Number of distinct integers in O(log N) - Stack Overflow](https://stackoverflow.com/questions/39787455/is-it-possible-to-query-number-of-distinct-integers-in-a-range-in-olg-n) >- [ ] [CSES - Distinct Values Queries](https://cses.fi/problemset/task/1734) (unique problem) * [Longest increasing subsequence - CPAlgorithms](https://cp-algorithms.com/sequences/longest_increasing_subsequence.html) solution with data structures ## ➡️ Sparse Table >:star: Expected time : 1 - 1.5 hours * [Video](https://www.youtube.com/watch?v=c5O7E_PDO4U) / [Theory](https://cp-algorithms.com/data_structures/sparse-table.html) * Problems : >- [ ] [CSES - Static range minimum query](https://cses.fi/problemset/task/1647) >- [ ] [CF - Ant colony](https://codeforces.com/contest/474/problem/F)(maybe slightly tough) >- [ ] [CF - Longest Regular Bracket Sequence](https://codeforces.com/contest/5/problem/C) >- [ ] [CF - CGCDSSQ](https://codeforces.com/contest/475/problem/D) >- [ ] [CF - Turn off the TV](https://codeforces.com/contest/863/problem/E) * The same idea can be applied for 2D Range minimum queries as well. [Here](https://codeforces.com/blog/entry/45485) is a blog that explains it. ## ➡️Tree Algorithm Problems >:star: Expected time : 2 - 2.5 hours * [CPH Ch 14](https://usaco.guide/CPH.pdf#page=143) / [Tree Algorithms - YouTube](https://www.youtube.com/playlist?list=PLDV1Zeh2NRsDfGc8rbQ0_58oEZQVtvoIc) / [AlgorithmsThread 8: Tree Basics](https://www.youtube.com/watch?v=MOy4UDjN8DM) ### :maple_leaf: Tree Diameter * You can go through this [Article](https://www.altcademy.com/blog/compute-the-diameter-of-a-tree-solved/) / this [Blog (CodeForces)](https://codeforces.com/blog/entry/101271) >- [ ] [CSES - Tree Diameter](https://cses.fi/problemset/task/1131) >- [ ] [CF - Gym Problem 1](https://codeforces.com/gym/102694/problem/A) ( video solutions for Gym : [Tree Basics Solutions](https://www.youtube.com/watch?v=5ZZELkqmGOo) ) >- [ ] [CSES - Tree Distances I](https://cses.fi/problemset/task/1132) >- [ ] [CF - Gym Problem 2](https://codeforces.com/gym/102694/problem/B) >- [ ] [CF - Minimize the Diameter](https://codeforces.com/gym/104536/problem/F) ### :maple_leaf: DP on Trees (this section builds on from [DP on DAGs](https://hackmd.io/HRwfKhYyS4KwGPqihlGNIw?view#-DP-on-DAGs)) * Here’s a blog on [DP on Trees](https://codeforces.com/blog/entry/20935) * Here are some specific problems on Trees : >- [ ] [AtCoder - Independent Set](https://atcoder.jp/contests/dp/tasks/dp_p) >- [ ] [AtCoder - Subtree](https://atcoder.jp/contests/dp/tasks/dp_v) >- [ ] [CF - Distance in Tree](https://codeforces.com/contest/161/problem/D) >- [ ] [CF - Anton and Tree](https://codeforces.com/problemset/problem/734/E) >- [ ] [CF - Berland Federalization](https://codeforces.com/contest/440/problem/D) * Number of Topological Sorting : >- [[Blog] Number of Topological Orderings of a Directed Tree | Codeforces](https://codeforces.com/blog/entry/75627) >- [ ] [CodeChef - Build Towers ](https://www.codechef.com/problems/BUILDT) ### :maple_leaf: Tree Queries * [CPH 18.1 Finding Ancestors](https://usaco.guide/CPH.pdf#page=173) + [Binary Lifting - CPAlgorithms](https://cp-algorithms.com/graph/lca_binary_lifting.html) >- [ ] [CSES - Company Queries I](https://cses.fi/problemset/task/1687) >- [ ] [CF - Gym Problem 3](https://codeforces.com/gym/102694/problem/C) >- [ ] [USACO - Luxury River Cruise](https://usaco.org/index.php?page=viewproblem2&cpid=284) * [CPH 18.2 Subtree and Path Queries](https://usaco.guide/CPH.pdf#page=174) / Euler Tour >- [ ] [CSES - Subtree Queries](https://cses.fi/problemset/task/1137) >- [ ] [Codechef - Subtree Summation](https://www.codechef.com/problems/CODEFT07) >- [ ] [Atcoder - Count Descendants](https://atcoder.jp/contests/abc202/tasks/abc202_e) >- [ ] [CSES - Path Queries](https://cses.fi/problemset/task/1138) * [CPH 18.3 Lowest common ancestor](https://usaco.guide/CPH.pdf#page=177) + [Lowest Common Ancestor - CP Algorithms](https://cp-algorithms.com/graph/lca.html) + [WilliamFiset | Youtube](https://www.youtube.com/watch?v=sD1IoalFomA&list=PLDV1Zeh2NRsDfGc8rbQ0_58oEZQVtvoIc&index=7&pp=iAQB) >- [ ] [SPOJ.com - Lowest Common Ancestor](https://www.spoj.com/problems/LCA/) >- [ ] [CSES - Distance Queries](https://cses.fi/problemset/task/1135) >- [ ] [AtCoder - Distance Queries on a Tree](https://atcoder.jp/contests/abc294/tasks/abc294_g) * More Problems: >- [ ] [SPOJ.com - Query on a tree II](https://www.spoj.com/problems/QTREE2/) >- [ ] [Optimal Connectivity](https://www.hackerearth.com/practice/algorithms/graphs/graph-representation/practice-problems/algorithm/optimal-connectivity-c6ae79ca/) try with binary lifting ;) ## ➡️Section 3 Additional Practice: >- [ ] [CSES - Pizzeria Queries](https://cses.fi/problemset/task/2206) >- [ ] [CSES - Salary Queries](https://cses.fi/problemset/task/1144) >- [ ] [CSES - Planet Queries II](https://cses.fi/problemset/task/1160) >- [ ] [CSES - Tree Distances II](https://cses.fi/problemset/task/1133) >- [ ] [CSES - Counting Paths](https://cses.fi/problemset/task/1136) >- [ ] [CF - Shuffling Songs](https://codeforces.com/problemset/problem/1950/G) >- [ ] [CF - Sasha and Array](https://codeforces.com/problemset/problem/718/C) >- [ ] [CF - Analysis of Pathes in Functional Graph](https://codeforces.com/problemset/problem/702/E) >- [ ] [CF - Count Paths Queries](https://codeforces.com/gym/102644/problem/I) >- [ ] [CF - Civilization](https://codeforces.com/contest/456/problem/E) >- [ ] [LeetCode - Binary Tree Cameras](https://leetcode.com/problems/binary-tree-cameras/description/) >- [ ] [SPOJ.com - Cost](https://www.spoj.com/problems/KOICOST/) # Additional Topics Convex Hull Trick, Square Root Decomposition, DP Optimizations (Knuth, Aliens, Divide and Conquer, CHT), LiChao Tree, Mo’s Algorithm, Digit DP, Broken Profile DP, Connected Components DP, DP on Trees, Sparse Segment Trees, Persistent Data Structures, Slope Trick, FFT, Suffix Array, Tries, Heavy Light Decomposition, Centroid Decomposition NOTE : For the topics we covered above there still exist a lot of variations which might be missed out by us or were not possible in the scope of this Roadmap. Continue your jouney in CP with self exploration ! **➡️ Some More Resources -** ✧ **Books** - * [Competitive Programmer's HandBook / CPH](https://cses.fi/book/book.pdf) * [AN INTRODUCTION TO THE USA COMPUTING OLYMPIAD](https://darrenyao.com/usacobook/cpp.pdf) * [Principles of Algorithmic Problem Solving](https://www.csc.kth.se/~jsannemo/slask/main.pdf) * [Competitive Programming 2](https://www.comp.nus.edu.sg/~stevenha/myteaching/competitive_programming/cp2.pdf) * [Guide to Competitive Programming | Springer](https://drive.google.com/file/d/1-_qgdODciPQgzi8NciMtjYj01Dydq385/view) ✧ **Problem Sets and Resources** - * ==[ITMO Academy: pilot course - Codeforces](https://codeforces.com/edu/course/2)== (Recommended) * ==[USACO Guide](https://usaco.guide/dashboard)== (Recommended) * ==[The Ultimate Topic List](https://youkn0wwho.academy/topic-list)== * [CSES Problem Set](https://cses.fi/problemset/) * [A2OJ Ladders](https://earthshakira.github.io/a2oj-clientside/server/Ladders.html) * [AtCoder Problems](https://kenkoooo.com/atcoder#/table//) * ==[CP-Algorithms](https://cp-algorithms.com/)== * [KACTL CP Templates C++](https://github.com/kth-competitive-programming/kactl) * [T-414-ÁFLV: A Competitive Programming Course](https://github.com/SuprDewd/T-414-AFLV) * [Archived Problems - Project Euler](https://projecteuler.net/archives) (if you’re into math ; improves problem solving) * [Number Theory Articles | Brilliant](https://brilliant.org/number-theory/) ✧ **Blogs** - * [An awesome list for competitive programming! - Codeforces](https://codeforces.com/blog/entry/23054) * [Prepare — NOI.PH - Philippine Programming Contest](https://noi.ph/prepare/) * [All the good tutorials found for Competitive Programming - Codeforces](https://codeforces.com/blog/entry/57282) * [75 LeetCode Questions to save your time](https://www.teamblind.com/post/New-Year-Gift---Curated-List-of-Top-75-LeetCode-Questions-to-Save-Your-Time-OaM1orEU) ✧ **YouTube Channels and Playlists** - * [Pavel Mavrin : A&DS English Course - YouTube](https://www.youtube.com/playlist?list=PLrS21S1jm43igE57Ye_edwds_iL7ZOAG4) * [Gaurav Sen : Competitive Programming A-Z - YouTube](https://www.youtube.com/playlist?list=PLMCXHnjXnTnucEu8lYMatA23OOi_De3Zp) * [Errichto Algorithms](https://www.youtube.com/@Errichto) * [Colin Galen](https://www.youtube.com/@ColinGalen) * [AlgorithmsThread - YouTube](https://www.youtube.com/playlist?list=PLZU0kmvryb_HZpDW2yfn-H-RxAu_ts6xq) * [WilliamFiset - YouTube](https://www.youtube.com/@WilliamFiset-videos/playlists) * [William Lin](https://www.youtube.com/@tmwilliamlin168) --- This roadmap could never be possible without the inspiration and background support of the **Makers of the Previous Roadmap** : * Sanat Goel * Vipul Chanchlani * Goutam Das * Rishi Agarwal * Varun Tokas * Shivam Mishra * Chayan Kumawat * Prerak Agarwal * Sankul **Contributors** - Tattwa Shiwani | tattwash23@iitk.ac.in Khushi Ranawat | rkhushi23@iitk.ac.in Arnav Gupta | arnavgupta23@iitk.ac.in Yatharth Dangi | yatharth23@iitk.ac.in Rohit Somani | rohitvs23@iitk.ac.in