61

How to Learn Competitive Programming

Before getting into competitive programming, let’s understand what it is?

Competitive Programming

It is a sport where coding skills are tested based on the problem-solving capability of a person. The better the problem solving, the better competitive programmer will be. There are different methods to solve a given situation but solving it efficiently is a good sign of a coder. During competitive programming, a person does mind exercises in thinking analytically, logically and solve a given set of questions.

Why competitive programming?

After understanding the basic idea of competitive programming, let us know why should it be learned and the reason for its popularity:

1. Growth in Career: Competitive programming makes you a perfect eligible candidate at big product-based companies like amazon, google, Microsoft, etc., because big product-based companies demand excellent problem-solving skills. Coding can shape your career. The persons with good problem-solving skills bag a fantastic offer and thus get placed.
   Furthermore, if the student is from a tier 3 college or university, can get referrals from employees if the coding skills are good.
2. Win coding competitions: There are several famous coding competitions like google hashcode, codejam, ACM ICPC, where students participate and get assured prizes. In addition to that, if a person secures a good rank in those competitions, there are high chances to get interview calls from product-based companies. For example, google hashcode’s excellent score holder is interviewed by google for a software engineer’s role.
3. Learn teamwork and promote networking: When participating in competitive coding hackathons, there is generally a team of 3 to 10 members. So, being in a group, a person can learn teamwork to work under pressure calmly. It boosts our networking, too, as we socialize with the mentors, the panel, etc., which acts as a booster in our career.
4. Learn to stay calm and focused: Competitive programming is not to be learned in some days or weeks. It takes years or months to become a well-ranked coder. This, in turn, demands a lot of patience as it can be stressful sometimes. Usually, people give up in between when they are not able to solve problems. The bright side is it teaches us how to rise from our failures.
5. Active community: The family of competitive programming is so vast that one can be flooded with numerous tutorials, doubt sessions, etc. Many free resources are available on YouTube and some websites where a beginner can learn and follow up to an advanced level. There are various websites to test your skills like CodeChef, codeforces, leetcode, atcoder, etc.
6. Long-term future security: With the rise of this computer and technologies era, coding will take a hike in the coming years. So the problem-solving capabilities won’t go to waste in the coming future. Instead, it will boost our careers and will provide security.

How to Start with Competitive Programming?

1. Choose a language: There are several languages in computer science like C, C++, Java, Python, JavaScript, rust, go, ruby, etc. Each language has different libraries, which helps in competitive programming as they are efficient and saves time. A programmer can choose their interested language to begin with competitive programming. Remember, once a language is chosen, make sure you stick to it until the end, as it may create a problem to switch in between.
2. Learn in-depth data structures and algorithms: To begin with competitive programming for this, we need to understand the basic concept of all the data structures and algorithms, time complexities, space complexities, etc. These will give us a base of what data structure will be used in a particular problem in an optimized manner. The execution time is based upon our data structure only as different data structures as other operation times. The data structure to be learned are as follows :
   • Arrays: An array is a linear data structure in which one variable store’s several elements in a linear fashion.
   • Stack: A stack is a data structure that uses the Last in first out the property (LIFO) to store the elements.
   • Queue: A queue is a data structure that uses a First in, first-out (FIFO) manner to keep the elements.
   • Link list: A link list is a data structure in which another element’s address is stored in the first element’s memory part.
   • Trees: A tree is a non-linear data structure in which elements are stored as the branches of a tree, and the first element is called the root node.
   • Graph: A graph is a non-linear data structure that contains nodes and edges. The difference between a graph and a tree is a graph can be termed as a cyclic tree.
   • Hash tables: This data structure can store data in an associative manner.

   In algorithms, one should have a deep knowledge of the algorithm concepts as follows:

   • Time complexity: It is the total time taken by a program until its completion. This factor is the most needed in competitive programming, as the less the time complexity, the higher the code is optimized. If a person applies a naive approach, the code runs perfectly but gives the Time limit exceeded (TLE). It only means either we have to change the data structure or the approach. For example, if a code runs in O (n*n) will take more time than a code running in O (n).
   • Space complexity: It is defined as the memory taken by our program for a given range of input. In competitive programming, there are given constraints in every problem. These constraints are a hint by which the data structure and the approach are to be decided. For example, any program can run for ten inputs perfectly but gives memory overflow for 200 inputs. These kinds of problems are handled by space complexity analysis.
3. Learn competitive programming algorithms: Some algorithms are helpful regarding time and space constraints. Further, they help in the logic building too. Some of them are listed below –
   • Sorting and searching algorithms: The sorting algorithms like merge sort, quick sort, etc., are very helpful in competitive programming. These algorithms are efficient and also have several advantages. The searching algorithm binary search is the most used algorithm when data is given in a sorted format. A brief study of string sorting algorithms like Rabin Karp, KMP algorithm, Z’s algorithm can help string sorting and manipulations.
   • Graph algorithms: Graph plays a significant role in competitive programming. This data structure is used in different ways like finding a path, shortest route to a track, etc. The famous graph algorithms are BFS, DFS, Dijkstra algorithm, Floyd Warshall algorithm, Prim’s algorithm articulation points, Johnson’s algorithm, find bridges in a graph, etc.
   • Dynamic programming algorithms: Dynamic programming means using the subproblems for further computations in a meaningful manner. The subproblems are solved optimally so that it gives optimized results. Dynamic programming is most excited in competitive programming. Some of the algorithms are longest common subsequence, longest increasing subsequence, knapsack problems, the optimal strategy in games, etc.
   • Number theory and mathematical algorithms: The number theory algorithms solve mathematical problems like prime number test, GCD of two numbers, etc., for an immense input value in the program. These algorithms calculate the results in lesser time complexity, so the code does not get TLE. Some of the most important are the Fermat method, Modularity algorithms, Miller Rabin, Segmented Sieve, Prime factorization algorithms, etc.
   • Bit manipulations: Working with bits is swift and competitive programming is all about it. There are some methods where we can use bit operators like (logical AND, OR, NOT, left shift and right shift) to make our work easier.
   • Geometric and network flow algorithms: These algorithms help in solving the 2-D and n-D problems. The graph topics like the intersection of two lines, the union of two lines, slope, etc., can be easily solved. Some are convex hull, Line intersection, Dinic’s algorithm, and Hop-croft Karch algorithm, etc.
   • Segment trees: The segment trees are used to solve range-based queries. The insertion, deletion, and updation time complexity are significantly less as they can be accessed instantaneously.
   • Binary indexed trees: It is also known as the Fenwick tree, which allows us to represent the array enabling prefix sum to be calculated efficiently.
4. Choose a platform for practice: There are several online websites where competitive coders practice it as a sport. Some of them are CodeChef, codeforces, Leetcode, atcoder, SPOJ, HackerEarth, hackerrank, etc. You may choose any one of them and start doing questions from these websites. The regular contest is held every month and in weeks. Some of them are timed, long challenges, etc. You can check your progress in these contests.
5. Practice: Coders are not born; they are made by regular practices, correcting their mistakes. Generally, people feel demotivated when not able to do the questions, but they are learning signs. So do not give up if not able to do any problem in any contest. Practice and patience will help you to reach the goal.
6. Participate in contest regularly: Contest comes and goes. People do not participate again once they fail in any battle. Develop the habit of rising from failures. Learn the tutorials and practice them later after the contest. You will understand your mistakes, and this will help you level up. Make a group of peers where you can discuss the problems and approaches. It will boost up the confidence and promote the approach explaining capability.

---