Intro to competitive programming

Introduction

Competitive programming (CP) is a mental sport where participants compete by solving programming problems under specific time and memory constraints. The contests mainly combines two topics: (1) Design of algorithms (2) Implementation of algorithms. This video by William Lin gives a very good overview to intro to CP.

This guide will mainly contain pseudo code that resembles C++ as it is the programming language of choice. You can use python, java, other languages to attempt the problems given in this guide too. Here is a guide to download and set up C++ and VScode (IDE) on your local machine.

Basic C++

Example of a typical C++ template:

        #include <bits/stdc++.h>
        using namespace std;
        int main() {
            ios::sync_with_stdio(0);
            cin.tie(0);
            // solution comes here
        }
    

The first two lines in main make input and output more efficient.

The #include line at the beginning is for including standard c++ libraries. <bits/stdc++.h> is a library that contains all necessary functions that you will use in CP. It is used by all competitive programmers that use C++.

Chapter 2 and 3 of this book explains input, output and time complexities in detail.

Important Macros and TypeDefs

Macros: are a feature of C++ that allow text substitution before complilation process
Typedefs: are used to create alias for an existing data type. It does not create a new datatype.

Macros and typedefs significantly speed up the speed at which you can write your code and should be a part of your template. Following basic macros and typedefs are used by us:

        #define rep(i,a,b) for (int i = int(a); i < int(b); i++)
        #define ff first
        #define ss second
        #define yes cout<<"YES\n";
        #define no cout<<"NO\n";
        #define sqr(a) ((a)*(a))
        #define pb push_back
        typedef vector<long long> vi;
        typedef pair<long long, long long> pi;
        typedef long long ll;
        const int inf = 1e9;
        const int llinf = 4e18;
    

For complete utilization of this guide we recommend you to make an account in the following website:

• CodeForces
• Kattis
• Leetcode
• Uva online judge

It is important to type code fast to place higher in competitive programming contest. KeyBr is a good website to practice typing to get faster.

Output Formating

Many times in a contest you will be required to output numbers uptill a specific decimal places. For example, if you are required to output a number upto 6 decimal places, you can use the following code:

In competitive programming contests, you may often need to format numbers to a specific number of decimal places. For instance, if you are required to output a number up to 6 decimal places or output till n significant digits. For this we introduce setprecision.
For giving output with a specific number of decimal places, you can use the following code:
cout << fixed << setprecision(6) << x; (code for outputting a number x with 6 decimal places)
cout << setprecision(3) << x; (code for outputting a number with 3 significant digits)

It's important to understand the difference between cin and getline in C++:

• cin stops reading input at the first whitespace character (such as a space ' ' or newline '\n'). It also leaves the whitespace character (like '\n') in the input stream, which can cause issues if not handled properly.
• getline, on the other hand, reads input until it encounters a newline character '\n'. It consumes and removes the newline from the input stream, allowing you to safely read full lines of text, including spaces.

Generally, this behavior is not a problem. However, when using getline after cin, cin leaves the '\n' character in the input stream. As a result, getline interprets it as an empty line. To avoid this, we use cin.ignore() to remove the leftover '\n' before calling getline().

There will be excersizes on the bottom of every page for your reference. Happy CPing :)