This is a blog post meant to many people who have ever tried to start competitive programming, but didn't find where to go ahead and left in midway. And also to those who wonders where to start from.
Before talking about competitive programming I would like to talk about what is Competitive Programming?
Generally competitive programming is a mind sport where everyone showcase his/her skills of problem solving under various constraints(that force everyone to think deeply or efficiently). Anyone who does competitive programming can enhance his/her problem solving approaches.You will learn how to approach a problem with the best of the best possible ways, you will learn how to analytically think and solve a problem and analyze it's space and time complexity.
Key things required to be regular in Competitive programming:
Most important thing you need to learn is patience while doing the problems. Anyone who starts competitive programming as a beginner face impatience, and the reason behind this is that he/she is not getting the AC(the most awaited green sign) on some problems even after trying that problem since last 2 or more days, and this leads into the impatience. I have met many people who starts the competitive programming and left it just after a week, and the reason will surprise you, they all left the competitive programming because of impatience and they all used to say that we can't waste our time on a single problem for more than few hours.So please you need to patience and gradually you will surely feel the improvement in solving problems.
2. Do participate regularly in contest:
Please do participate regularly in as many as contest you can, why because participating in the contests you will learn many new topics and will get experienced how to fight with the programmers from across the globe.But please make sure as a beginner you will face some difficulties while solving the problems in any ongoing contest because there will be some pressure of getting ranked above your competitors.Sometimes you will also find decrement in your rating, but please don't get demotivated or discouraged everyone have gone through all these things to become a successful programmer,rating is just a matter of time as the time will pass and you will keep practicing,then you will see increment in your rating.
Key steps in learning Competitive programming:
1. Choose any well known programming language used for Competitive programming:
You can do competitive programming in any programming language but it is highly recommended that you choose one of C/C++ or Java. The reason being that the time of execution is a key factor in Competitive Programming and so, choosing a language whose time of execution is fast is surely going to give you a benefit. C/C++ and Java are relatively faster, particularly when compared to languages like Python. Python is slow as compared to C/C++ and JAVA,that's why very less number of programmers used to do Competitive Programming in Python due to its time factor which is highly prioritised in Competitive Programming.
2. Choose some platforms to practice Competitive programming and to participate in contest:
As per my personal experience if you are a beginner i will recommend everyone to start with HackerRank,it has really the best user interface and IDE. HackerRank has a good set of problems for beginners placed in well defined manner according the tags and difficulty levels.The main thing that HackerRank provide to the users is that if you get stuck on some problem from very long time and only passing some of the test cases, then you can download the test cases and you can review your logic to do some modifications,it will help in thought process to be able to think about corner test cases.But seeing the test cases is not always good, after some duration(about 2 or 3 months) you itself should be able to think that which test case might give WA(wrong answer). And after the practice of 2 or 3 months you can also start doing practice and participating in contests on some of these famous sites CodeChef,CodeForces,AtCoder. CodeChef is known for long challenge(10 days duration),CookOff(2.5 hrs),LunchTime(3 hrs). Codeforces is known for short duration contests of atmost 3hrs long.
3. Get your hands dirty in Data Structures:
Data Structures are something that helps you in making the program more efficient. Having good amount of knowledge in Data Structures will help you in selecting the optimal Data Structure for any problem. Anyone can learn Data Structures from GeeksForGeeks, it contains Data Structures tutorials and problems in rich amount.
4. Get your hands dirty in Algorithms:
Algorithms are something that use various data structures to implement the logic and then we get the result in form of output produced by the algorithm. You need to be very good in Algorithms, again GeeksForGeeks contains Algorithms in rich amount.
Time/Space Complexity: Every Algorithm has a Time and Space complexity which refers to the maximum amount of time an Algorithm will take and the maximum amount of memory an algorithm will require. While doing Competitive Programming these two will play a key role in determining the verdict of your solution.
Always try to think of the most optimal solution, that is, one which runs with least time complexity and occupies minimum space.
Sorting: You must have heard of a number of sorting techniques to sort but while doing Competitive Programming most of those techniques prove to be time-consuming hence the STL library comes to rescue, it offers a function sort() which sorts the array in the most optimal way.
5. Keep Practicing practicing …….. Practicing:
Always keep yourself motivated enough to solve the problem, it will help you in enhancing your problem solving skills. As now you have good knowledge of Data Structures and Algorithms you can do really well in world of Competitive programming if you keep practicing continuously.
Online course link to learn Competitive Programming by Coding Blocks
Some other useful links to learn Competitive programming:
- 1. Data Structures and Algorithms
- 2. Coding Blocks Competitive Programming Study Material
- 3. Good Collection of problems by Coding Blocks
- 4. Must known Algorithms for Competitive Programming
- 5. Introduction to Programming Contests(by Jaehyun Park (Stanford ACM-ICPC coach))
- 6. Collection of CP Algorithms
- 7. CodeMonk HackerEarth problems and tutorials
- 8. 10 Algorithms must known in order to learn CP
- 9. What algorithms and data structures should any software engineer know?
Some useful YouTube links for Competitive Programming:
- 1. Time Limit Exceeded (TLE) - Learn this trick to pass all testcases in Competitive Coding !
- 2. List of mandatory Competitive Programming videos by Prateek Narang Bhaiya
Try to do all the problems stated below if you are a beginner.
- Prime Check ( O(log n) also possible read about miller-rabbin ).
- Number of factors.
- Sum of factors.
- Generating Primes using sieve of eratosthenes.
- Bounds on number of primes till N.
- Euler's totient function.
- Try to solve these listed problems :
Basic Number Theory
- Number Theory
- Number Theory for Competitive Programming
- Basic Number Theory Every Programmer Should Know...
- Modulo operations and Inverse modulo
- How to compute (a ^ b) % p in O(log b), where p is prime
- Find Nth Fibonacci number modulo p using Matrix exponential method
- Euler theorem , Fermat's little theorem , Wilson theorem
- nCr % p (inverse modulo) ( read about extended euclid algorithm)
- Matrix Exponentiation
- Practice problems:
Power of BITS
** Tutorial Links:**
- Basics of Bit Manipulation
- Bit Twiddling Hacks By Sean Eron Anderson
- Bits manipulation (Important tactics)
- Practice problems:
- Read this for further knowledge
Understand the concept of binary search. Both left_binary_search and right_binary_search. Try to implement it on your own. Look at others implementation.
The Beauty of Standard Template Library of C++
- Vectors in one dimension and two dimensions
- solve : Compilers and parsers Try to solve using Stack and solve the following problem too. Alternating Current
- Priority Queue
Some Practice Problems Before you proceed further
- Chef and Strange Matrix
- Just Some Permutations 3
- Witua and Math
- SPCO - Gopu and Counting Bitwise Prime Numbers
- NDIVPHI - N DIV PHI_N
- HISTOGRA - Largest Rectangle in a Histogram
Try the following problems :
Breadth First Search/Traversal (BFS) (very important, master it as soon as possible)
- Application : Shortest path in unweight
Depth First Search/Traversal (DFS) [very very important, master it as soon as possible]
Greedy Algorithms are one of the most intuitive algorithms. Whenever we see a problem we first try to apply some greedy strategy to get the answer(we humans are greedy, aren't we ? ).
Readthis tutorial for further insight or you can directly attempt the problems most of the greedy approaches are quite simple and easy to understand/formulate.But many times the proving part might be difficult. But you should always try to prove your greedy approach because most the times it happens that you later realise that you solution does not give the optimal answer.
They are generally used in optimization problems and there exists an optimal substructure to the problem and solutions are generally O(n log n) (sorting) or O(n) (single pass).
Practice as many DP problems as much possible.
You must go throughthis topcoder tutorial and you must try to solve all the problems listed below in this doc.
- Largest contiguous subarray sum
- Dessert Wizard
- Pizza Delivery
- Little Elephant and Balloons
- IOIPALIN - Palindrome 2000
- COINS - Bytelandian gold coins
So to master the Competitive Programming you need dedication, patience and continuous practice to solve the problems as many as you can.I have provided a link of online Competitive Programming by Coding Blocks course above you can refer to that.
Code,sleep,eat and repeat.
~ By Ankush Sharma