Competitve Programming

Sep 7, 2021 18 min read #Cp#Cp#C++

Competitive Coding Resources

Here are some CP resources that I found useful.

Why did I write this blog?

  • Good question! There are plenty of resources out there on how to start competitive programming but what I found missing there were proper links to resources.
  • I also had selfish reasons:- I wanted a short description, which nevertheless contained the major ideas underlying the algorithms, a discussion of their relative strengths and weaknesses, with hints on what is known (and not known, but would be good to know) about these algorithms. If I succeeded, time will tell. Or, you can, by sending me an e-mail at sandeepskr1721@gmail.com

Abstract

Data structure is all about organising, retrieving, storing and managing data effectively, such that we can perform specific operation efficiently.
Whereas an Algorithms is a sequence of computational steps that transform the input into the output. Learning data structures and algorithms allow us to write efficient and optimized computer programs.

Motivation

Competitive Programming(CP) is very important if one aims to improve their overall programming skills. It not only increases your problem solving aptitude, speed and knowledge but also proves to be benefitical for interships and placements. With that said, many of us ignore CP or coding up until the tests start just coz we have a mindset that coding is hard and its not our cup of tea.

How to get started with the sport of competitive programming?

1. Pick a suitable programming language

You can do competitive programming in any programming language but it is recommended that you choose one of C/C++ or Java. C++ — Highly recommended! Why? Because it’s very fast. Implementing different algorithms takes little time because of STL which has Set, Map, Vectors etc. These can come very instrumental in solving certain kinds of problems. C++ is accepted in all competitions.

Learn C/C++ :

2. Choose a powerful code editor

To increase the speed and efficiency of your work, it is recommended that you write your code in a code editor. VS Code, Sublime Text 3 & Vim are some of the popular editors where you can use their cool features and practice your craft. Use STL, snippets, and templates whenever you can; it not only saves your code length but also decreases the time to write your code. Now you can focus mainly on solving the actual logic of the problems.

3. Choose a few platforms to practice and start participating in contests

  • Hackerrank

    • I recommend for beginners to start with Hackerrank. It has a good set of problems placed in a well-defined manner according to the tags & difficulty levels and undoubtedly has the best user interface & IDE.

  • https://codeforces.com/

    • Getting Started: Go to the problem set tab. Set difficulty(mid-right of your screen.) to 800-900. Select a question by clicking over it. Write code on the text editor on your laptop. Save your code in a .cpp file. Upload that file on the website through choose file option under Submit?. Couldn’t solve? See editorial solution by scrolling to the bottom of the page and selecting the editorial link. Increase difficulty by 100 once you solve 10-15 problems. Start giving contests after you reach 1100-1200 difficulty in practice.

  • GFG

    • For references around data structures and algorithms, consider GeeksforGeeks and original documentation like CPPreference .

  • AtCoder

  • https://codechef.com/

  • HackerEarth

  • Leetcode

4. Learn Data Structures and algorithms:

6. Practice more:

7. Practice DP:

Some other resources

There is so much more to tell about the same. I’ll be discussing them in detail on another day. Remember there is no shortcut for success. The harder the path, the better the fruit will be. Until then, practice, have fun, and learn a lot.

Basics and Ethics of Competitive Programming

Hello guys!

Many of you have been wondering why are we doing CP or what benefits will it provide. Maybe for some of you, it might not be cool as some other fields like AI or ML which fascinates most people or like developing a web app (A cool stuff for many people). The main objective of competitive programming isn’t to have you implement all the fancy algorithms and data structures from scratch. Rather, it is to develop problem-solving skills.

Well now is the time that we should focus on some of the key steps (like which language is best or which editor should we use) which we need to keep in mind to learn Competitive Programming.

Language to be chosen for Competitive Programming

You all have seen that there are various languages in which you can submit the solutions to a problem on all the platforms (Codeforces, Codechef, TopCoder, AtCoder). However, if you have noticed that almost all of the users submit their solution only in C++. This is because C++ has a very nice library STL(Standard Template Library) in which there are many in-build functions that we can directly use. So, it is recommended that if you use any other language than C++ then it is the time that you should switch to C++ and be comfortable in it. You can refer to this document to switch from C to C++.

Editor to be used for Competitive Programming

Some of you may have thought that which editor to be used for competitive programming. Well, some of the good editors for CP are Sublime Text (for both Linux and Windows), CodeBlocks (for Windows only), and Geany. However, if someone still uses online editor (GeeksForGeeks, Codeforces, Ideone, or CodeChef IDE) then switch to offline editors as soon as possible. Online editors should not be used during the contests because the site may crash at that time and you may lose the unsaved code. Also, if you are using Ideone or Pastebin then your code may get stolen and you might be caught in plagiarism.

Now talking about the offline editors, if you have Linux installed on your laptop then you can easily set up Sublime Text on it. (Installing Sublime Text on Linux , Set Up Sublime Text in Linux ). However, if you are using Windows then first try to set up Sublime Text (Sublime Text for Windows ). However, if it is giving any errors which you are not able to resolve then you can set up CodeBlocks easily on your system. You can also setup Geany on your Linux system if you want. (Here is a video of Errichto for Setting up Geany for Linux Environment )

P.S. The further blog will be in consideration that now you have switched to C++.

Templates and Snippets in Sublime Text

Now that you have begun coding in C++, let’s talk about the template which you will need (No-one wants to write the include and define statements every time in a fresh code). You all have seen that many of the users have a fixed set of lines that are present in every code they submit. A basic template which you can all use is :

Template Code

    #include <bits/stdc++.h>
    typedef long long int ll;
    #define ld long double
    #define pb push_back
    /* You may enter other macros defined by you */
    
    using namespace std;
    
    const int MOD = 1e9+7;
    const ld PI = acos(-1);
    const ld EPS = 1e-9;
    const ll INF = 1e18;
    
    /* You may enter some functions too if you find them important */
    
    void solve(){
    
    	
    
    	return;
    }
    	
    int main(){
    
    	ios::sync_with_stdio(0);
    	cin.tie(0); cout.tie(0);
    
    	int TC = 1,t = 0;
    	cin >> TC;
    	while(t++ < TC){
    		// cout << "Case #" << t << ": "; // For Google CodeJam and Kickstart
    		solve();
    		// cout << "/n";
    	}
    
    	cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
    
    	return 0; 
    }

Talking about the template, let’s first understand some of its important parts.

The starting part includes the header bits/stdc++.h. It is an implementation file for a precompiled header. It is a good idea to minimize the include. It actually includes a lot of files, which your program may not need, thus increase both compile-time and program size unnecessarily. But in contests, using this file is a good idea, when you want to reduce the time wasted in doing chores. It works in most online judges, programming contest environments, including ACM-ICPC (Sub-Regionals, Regionals, and World Finals) and many online judges. However, The disadvantages of it are that it increases the compilation time and uses an internal non-standard header file of the GNU C++ library, and so will not compile in MSVC, XCode, and many other compilers but however, it compiles in Sublime Text.

Next, we have some macros which can be used to reduce the time needed for writing the same piece of code every time in your solution. For example, #define pb push_back is the most commonly used macro because we generally have to use push_back many times in a problem where a new element has to be added to a vector at the end. However, by defining this macro, we only have to write pb instead of push_back. You can also define your own macros if you want to have. However, it is also not a rule to have the same macros as in the template provided. You may also change them if you want.

You may have noticed here that for long long int we have used typedef long long int ll; instead of define ll long long int because the typedef has the advantage that it obeys the scope rules. That means you can use the same name for the different types in different scopes. It can have file scope or block scope in which declare. In other words, #define does not follow the scope rule. You can read more about scope rules here .

Proceeding onwards, we define some of the most commonly used constants which we generally require in one or the other problem. The first of them is MOD which is always used whenever the answer exceeds the limit of long long int or int. The value of MOD may vary from question to question but the most commonly used values are 1000000007(1e9+7) and 998244353. The next used is PI which is used whenever dealing with a problem involving geometry or angles (Note — the angles for all the trigonometric functions have to be in radians and not degrees). The next const EPS is generally used whenever we deal with problems involving precision on real numbers (generally the case for Binary Search on real numbers). With this, we come to our last constant INF which is used for the problems where we want to print “NO/-1/0” if the number exceeds this number.

You can also add some common functions which are generally used in your templates like the function for modulo arithmetic or modulo inverse. (You may think of adding gcd function also but it is already present in STL and can be used directly as __gcd(int x, int y). Try to guess the complexity of this inbuild gcd function. However, if you are using C++17 or above then gcd(int x, int y) is also fine to work with).

You must have seen various problem statements saying: “Warning: Large I/O data, be careful with certain languages (though most should be OK if the algorithm is well designed)”. It is often recommended to use scanf/printf instead of cin/cout for fast input and output. (However, for C++17(64) printf is very slow as compared to cout. So, if you are using C++17(64) then you should never use printf in your code).However, you can still use cin/cout and achieve the same speed as scanf/printf by including the following two lines in your main() function:

ios::sync_with_stdio(0); <br>
cin.tie(0); cout.tie(0);

The first line toggles on or off the synchronization of all the C++ standard streams with their corresponding standard C streams if it is called before the program performs its first input or output operation. Adding ios_base::sync_with_stdio(false); (which is true by default) before any I/O operation avoids this synchronization. It is a static member of the function of std::ios_base. tie() is a method which simply guarantees the flushing of std::cout before std::cin accepts an input. This is useful for interactive console programs that require the console to be updated constantly but also slows down the program for large I/O.

You may have noticed that in the template there is a commented line cout << "\n". Some of you may have wondered why endl is not being used in this. It is because endl flushes the output buffer everytime it is called too along with printing a new line but \n only prints a new line. For interactive problems, it is always recommended that you should flush the output after printing every line and hence, you can always use endl instead of printing \n and then flushing the output buffer separately.

At last, we are now left with the cerr object. std::cerr is an object of class ostream that represents the standard error stream oriented to narrow characters (of type char). It corresponds to the C stream stderr. The standard error stream is a destination of characters determined by the environment. This line will print the total time needed for compiling and running your program for a specific test case in milliseconds.

Snippets in Sublime Text

This brings us to the end of our template. Now you may think that you should make a separate cpp file where you can save your template but Sublime Text offers another simpler solution to that. You can add your template as a snippet in Sublime Text. Adding Snippet in Sublime Text . You can also add snippets for some important data structures like Segment Tree.

Ethics of Competitive Programming

There might be points in time where some you would feel stuck with a problem within a contest and are frustrated to the core, or just lazy to go through with it anymore. Easy ways out? Possibly look at solutions for the problems if it’s a mashup/virtual contest, or during official contests, talk and start discussing about the problem(s) with friends and come up with a solution collectively / ask someone for the solution.

So should you opt for easy ways out ? I’ll let you figure that out. If your answer is “Yes” then, please, stop fooling yourself by giving yourself a fake sense of happiness by solving extra problem(s) in the contest/mashup/whatever. It’s definitely not worth it and completely useless. The main purpose of CP is to improve your problem solving skills, which is beaten by this.

However, it is not restricted to copy standard codes from some of the standard sites like CP-Algorithms, Codeforces, and GeeksForGeeks. However, if you copy a code from these sites or from another previously occurred similar problem then always mention the source of that code in the comments so that you can argue about it if your code is caught in plagiarism.

STL

Hey Guys!

I have compiled some very useful resources for our first topic — Standard Template Library.

The following resources are optional and I recommend you to go through these resources only after completing the above two links.

To overcome the issue of creating functions that perform the same operations but work with different data types, C++ provides a feature to create a single generic function instead of many. The collection of these genric classes and functions is called STL which includes many different kinds of algorithms to provide support to tasks such as initializing, searching, copying, sorting, and merging, Algorithms are implemented by template functions.

Standard Template Library provides us with many important trivial data structures and algorithms which generally take up a lot of time to implement by ourselves. In order to be a good Competitive Programmer, you must have a strong command over STL.

Go through these links, discuss among yourselves and ping the mentors with any doubts. In a few days, we will be adding a long contest with various types of problems for you to practice.

Happy Learning!

Binary Search

Hey Guys!

We have compiled some resources you might find useful to study the second topic we would be covering, Binary Search. You might be aware of most of what is discussed in them, but I would still advise you to go through them and practice problems concerning binary search. We would soon be hosting a long contest for the same as well.

Leetcode: Binary Search 101 (I found this article easy to understand. It has simulations as well for better concept clarity)

Topcoder: BS Topcoder (One of the better binary search tutorials out there)

(Optional) Errichto: Binary Search tutorial (C++ and Python) (Not a very big fan of this video, but covers an appreciable amount of basics)

BS SPOJ (Make sure you try hard, and not look at the solution for a long time, it’ll increase your appreciation of the binary search algorithm highly)

https://drive.google.com/file/d/0B1yhFrxtsDsyLTdDUTZMSUV6RzA/view (This seems like a good resource, but gives a lot of answers directly and is not advised to be used as a primary resource)

You should perceive binary search as more of an idea than an exact sequence of steps where you memorize the code and reproduce it (This causes fatal errors in code and irritating one-offs). There are multiple ways to code it, and the resources show their own favorite version, feel free to use any, as long as you’re comfortable with it.

UPD: You guys can also refer to Codeforces EDU section where pashka has explained binary search in great detail.(Link: ITMO Academy: pilot course )

Cheers and Happy Programming!!

Basics of Number Theory

Hey Guys!

The next topic is Basics of Number Theory. If you have been participating in contests regularly, probably you are quite familiar with Number Theory that you would be needing for competitive programming. We have listed some topics that we think you should know and also compiled some resources that you might find useful.

  1. Euclidean Algorithm to find GCD of two numbers : The algorithm basically states gcd(a,b)=gcd(b,a%b)gcd(a,b)=gcd(b,a%b) . This can be computed recursively and in O(loga+logb)O(log?a+log?b) time. You should try to implement it yourself.

  2. Bezout’s identity : Bezout’s identity states that if d=gcd(a,b)d=gcd(a,b) , then there exist integers xx and yy , such that ax+by=dax+by=d (Try and prove that dd is the minimum positive integer that can be expressed as a linear combination of aa and bb .

  3. Extended Euclidean Algorithm : Now that you are aware of the fact that gcd(a,b)gcd(a,b)can be expressed as a linear combination of aa and bb , the coefficients xx and yy can be found using this algorithm. You can check out the algorithm and a detailed explanation at https://brilliant.org/wiki/extended-euclidean-algorithm/ and you find the implementation at https://www.geeksforgeeks.org/euclidean-algorithms-basic-and-extended/ .

  4. Sieve of Erastothenes : This is an extremely useful algorithm and you will find the need to use it time and again. The idea behind the sieve is that you can iterate through multiples of each prime i,1?i?ni,1?i?n which are less than nn , in O(nlognlogn)O(nlog?nlog?n) (The complexity of this has to do with the sum of reciprocals of first nn natural numbers (or nn th Harmonic number)). The sieve not only allows you to find the prime factors in a range, it also allows you to find the smallest (or largest) prime factor of all numbers in a range, and in turn you can find the factorisation of a number mm in O(logm)O(log?m) . You can find a clean implementation and detailed explanation at https://cp-algorithms.com/algebra/sieve-of-eratosthenes.html

  5. Modular Arithmetic : I hope you have encountered problems which require to find results modulo some constant M. Modular Arithmetic is nothing but performing basic arithmetical operations modulo some constant, and there are some basic properties you need to keep note of. More often than not you will have to work with a prime as the Modulo base (like 1e9+71e9+7 ), which makes life much easier :). The most important theorem in this context would be Euler’s theorem, which states that a?(m)?1?1 mod ma?(m)?1?1 mod m , where gcd(a,m)=1gcd(a,m)=1 . Now, if mm is a prime then the equation becomes am?1?1 mod mam?1?1 mod m , which is Fermat’s Little theorem, and this is useful in finding inverse of aa modulo mm which would be am?2 mod mam?2 mod m . You can read more about modular inverse at https://cp-algorithms.com/algebra/module-inverse.html . Definitely check out this blog to know more about modulo arithmetic and where it is used.

  6. Linear Sieve and Multiplicative Functions: Linear sieve is used to calculate some really useful number-theoretic functions like phi function, totient function. A really great tutorial — https://codeforces.com/blog/entry/54090

  7. Chinese Remainder Theorem: A fairly popular algorithm which you might have heard of. A detailed explanation can be found here — https://codeforces.com/blog/entry/61290

In some of the links above, we have added a link of the website cp-algorithms . This is a great website in general to check out many theorems and algos that are useful in competitive programming. Some practice questions are also added at the end of the tutorials there, do try to solve those so that you get a good grasp of the algorithm and on how to implement it.

It’s very important in CP that you be familiar with the first 55

algorithms, so make very sure you understand the underlying concept that goes in them and practice enough problems.

Finally, do checkout the following links as aggregate resources:

https://www.codechef.com/wiki/tutorial-number-theory

https://artofproblemsolving.com/community/c90633h1291397

https://www.hackerearth.com/practice/notes/number-theory-1/

Graphs

Hey Guys!

The next topic which will be covered is Graphs. The initial topics which we have planned to cover are DFS/BFS. We have compiled some resources for it which you may find helpful. We will be hosting a contest soon on BFS/DFS.

Basic Graph Introduction and BFS/DFS: https://slides.com/nikhilag/introduction-to-graphs-2d26ce#/

Codeforces: https://codeforces.com/blog/entry/16221 (It contains some advanced topics too. You may read them also if you want.)

CP-Algorithms (DFS): https://cp-algorithms.com/graph/depth-first-search.html

CP-Algorithms (BFS): https://cp-algorithms.com/graph/breadth-first-search.html

You can find some problems for practice on CP-Algorithms.

You should always try to write code for BFS/DFS and not memorize it or insert into your template.

Feel free to have a discussion.

Bonus : Tutorial on Bitwise Operations — https://www.topcoder.com/community/competitive-programming/tutorials/a-bit-of-fun-fun-with-bits/ (May come handy in future)

Cheers and Happy Programming!!

Related Posts

comments powered by Disqus