Table of Contents
- About
- Lessons
- 1. Number Theory: Factorization and Sieve of Eratosthenes
- 2. Number Theory: GCD, LCM, Extended Euclidean Algorithm
- 3. Trees: Minimum Spanning Trees
- 4. Trees: Tree Center and Diameter
- 5. DP - Warm Up
- 6. DP - Table Method and Patterns
- 7. DP - Tricks and Masks
- 8. Segment Tree
- 9. Trees - Binary Lifting, K'th Ancestor, Lowest Common Ancestor
The basics covered in this training:
https://github.com/MohamedAfifii/ProblemSolving--Arabic
Lessons will usually contain:
- Resources covering the specified topic
- Extra notes (either videos or text) on points not covered by the resources
- Problems
Problems will usually be divided to:
- Basic problems: These are the problems that you should not skip. If you struggle with a basic problem, go read the solution to get the idea, then implement the solution on your own.
- Extra problems: These are usually harder problems. Feel free to skip these and get back to them later when you finish the training if you need more practice on a certain topic.
- Refresh problems: These problems are not related to the topic covered by the lesson, they will usually be
- Problems on older topics
- Ad-hock or greedy problems
Problems are sorted according to difficulty.
I will put the source code used in the videos that I record there.
This directory contains documented solutions for the training problems. If the solution isn't straightforward, you will find an explanation above the main function.
It is highly recommended that you read through the solutions even if you solve the problem, as you may find useful tricks there!
Read these two short PDFs:
Watch these two videos by Mustafa Saad:
Watch this video that highlights important points that were not highlighted by the resources above:
The code in the last video can be easily modified to generate all the divisors (not only the prime divisors) for all numbers from 1 to N.
int n = 10;
vector<vector<int>> divisors(n+1);
//i starts from 1
//All numbers (not only prime numbers) will visit their multiples
for(int i = 1; i <= n; i++)
{
for(int j = i; j <= n; j += i)
{
divisors[j].push_back(i);
}
}The complexity of this algorithm is O(NlogN) (assuming that push_back is O(1) for simplicity). The proof is similar to the proof mentioned in Codility's PDF, except that the summation is now over all numbers from 1 to N. See this interesting derivation if you want to know why the upper bound for the summation is indeed O(logN) (feel free to skip the proof).
As this is an extremely important topic that frequently appears on programming contests, please solve all the following problems:
- Codility - CountFactors
- Codility - MinPerimeterRectangle
- SPOJ - Prime Count
- SPOJ - Almost Prime Numbers
- Codeforces - Sherlock and his girlfriend
- Codility - CountSemiprimes
- Codility - CountNonDivisible
- Codeforces - Easy Number Challenge
- Codeforces - Bear and Prime Numbers
Extra
If the above problems were easy for you and you want to go fancier, read this link about Segment Sieve, then give the following problems a try:
- https://codility.com/media/train/10-Gcd.pdf
Skip section 12.3 - https://www.youtube.com/watch?v=YklnFXpq0ZE
Skip the parts of the video that are not related to GCD, LCM (they will be covered later). - https://www.youtube.com/watch?v=2k0TPnZyobY
- Hackerrank - Sherlock and GCD
- Codeforces - Modified GCD
- Codility - Chocolates by Numbers
- Codeforces - LCM
- Codeforces - Alarm Clocks Everywhere
- Codeforces - Alice and Bob
Note that problems that involve using the Extended Euclidean Algorithm are usually hard problems, so don't get disappointed if you struggle with them. I will try to provide easy to read solutions so that you can understand the solution if you get stuck!
- Codeforces - Neko does Math
- Codeforces - The Beatles
This problem is a harder version of Codility's Chocolates by Numbers.
Watch these two videos by Mustafa Saad:
- Graph Theory - DFS (Arabic)
- Graph Theory - BFS (Arabic)
- SPOJ - BUGLIFE (Graph coloring, Testing bipartiteness)
- UVA 852 - Deciding victory in Go (DFS on grid)
- Codeforces - 558C (BFS on implicit graph)
- Codeforces - 767C (DFS, imporant!)
- https://www.youtube.com/watch?v=TNgPT91sn90&t=121s (Introduction + how to print the optimal solution)
Read this lesson from Codility
Watch these 3 videos by Mustafa Saad
- https://www.youtube.com/watch?v=gFdP6X4CyKU
- https://www.youtube.com/watch?v=gFdP6X4CyKU
- https://www.youtube.com/watch?v=vAqaki1BhS0
- Codeforces - 35D (Knapsack-like)
- Codeforces - 189A (Reduced version of the Coin Change problem)
- ECPC2016 H
- Codeforces - 761C
- SPOJ ELIS (LIS, no need to memoize)
- SPOJ TLCS (LCS + printing output)
- Codeforces - 2B (Printing output, good one)
- Mustaf Saad's video for table method
https://www.youtube.com/watch?v=PrXbn8-zw14 - Another video explaining table method (and some other stuff) in a better way
https://www.youtube.com/watch?v=34Drti_iMsg - DP patterns
- ICPC archive - 2675
- UVA 10003
- UVA 348
- UVA 10739
- Codeforces 245H
- Codeforces 835D
- IEEExtreme11 - Gotta Catch 'Em All
- Codeforces 1107E
- DP Tricks - Subarrays (Arabic)
- DP Tricks - State Graphs (Arabic)
- DP Tricks - Consider One Element (Arabic)
- Dynamic Programming - Masks - 1 (Arabic)
- Dynamic Programming - Masks - 2 (Arabic)
- SPOJ DBALLZ
- UVA 562
- Codeforces 837D
- Codility MinAbsSum (Hard, see the solution if you get stuck)
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent