CP101

Introduction to Competitive Programming

Lecture - 01
What/Why Competitive Programming?

● You are given a set of problems, you need to write code to solve
these problems.

● The scoring depends contest to contest and you’ll get a hang of

it eventually.

● The code written needs to be efficient.

● Why CP ? Useful for placements/interns - not that important

right now, treat it as a game and enjoy it.

● What is Competitive Programming by William Lin

Requirements
● Decent Skills in any 1 common Programming knowledge
○ Order of Preference : C++ > Java >> Python
○ Python is good for projects but not very common in CP
○ Much easier to learn other languages after C++.
○ Buckys Playlist (till 40)
○ Nearly everyone at IITG uses C++. Easy to get help.
● Text Editor + Command Prompt / IDE
○ What is IDE ?
○ Ideone.com
○ Online C++ Compiler - online editor
○ repl.it
○ Codeblocks OR (VSCode / Sublime + Terminal)
Code Template
#include line:Allows us to include
entire standard library.
#include<bits/stdc++.h>
Thus it is not required to include
using namespace std; libraries like iostream,vector etc
separately.
int main(){
using line:used to include classes and
//CODE HERE:
functions of standard library
return 0; directly.

} Further Reading:

http://www.cplusplus.com/doc/tutorial/
program_structure/
Code Template
int main(): The main function which
gets executed by default when you run
#include<bits/stdc++.h>
the program.

using namespace std; return 0: Indicates that the main

function ran without any errors.
int main(){ Return value is non-zero if there is
//CODE HERE:
an error.

return 0; Further Reading:

} http://www.cplusplus.com/doc/tutorial/
program_structure/
Primitive Data Types

Keyword Data Type Example

int integer int a = 5;

bool logical true/false bool abc = true;

double double floating point double g = 4.90;

float floating point / decimal nos float h = 6.20;

char character char ch = ‘a’;

● double is more precise than float.

● signed, unsigned, long, short are data type modifiers.
● generally, long long is used in CP.
Sizes and Ranges

● Here size is in bytes

1 byte=8 bits

● String is another datatype which

is useful
eg : string lang = “C++”;

● Avoid overflow in smaller

datatypes

● Further Reading :
https://www.geeksforgeeks.org/c-d
ata-types/
Operators

Arithmetic Operators: +,-,*,/,%

Relational Operators: >, <, >=, <=, ==, !=

Logical Operators: &&, ||, !

Bitwise Operators: &, |, ^, >>, << (a bit advanced :p)

Operators

Modulo operator (%)

x mod m denotes the remainder when x is divided by m:
Eg : 17 mod 5 = 2 because 17 = 3*5 + 2
Obviously, 0 <= x mod m <= m - 1

Sometimes the problem has an answer which is too large to be

expressed in any data type, eg 1000!, in such cases, we are often
asked to express answer modulo some number N such as 10^9 + 7
(1000000007) or 998244353.
Modulo Properties
Some useful properties :
(a + b)mod m = (a mod m + b mod m ) mod m
(a - b)mod m = ((a mod m - b mod m ) + m) mod m
(a * b)mod m = (a mod m * b mod m ) mod m

Try these:
1. (100-84)%6
2. (84-100)%6 *
3. (76*91)%15
Operators

Relational and logical operators return a boolean value i.e.

true/false.
Eg :
5 > 3
4 <= 6
7 == 8
9 != 10
Operators

Relational operators return a boolean value i.e. true/false

Eg :
5 > 3 True
4 <= 6 True
7 == 8 False
9 != 10 True
Operators

Logical Operators (&&, ||, !) also return boolean values and are
extremely useful
Eg: AND (&&)
int myAge = 19;
bool eligible = (myAge >= 18);
bool hasCard = true;
bool canVote = (eligible && hasCard);
Operators

Eg: OR(||)
bool goUp = true;
bool goDown = false;
bool isActive = (goUp || goDown);
Operators

Eg: NOT
int marks = 55;
bool passed = !(marks<33);
equivalent to (marks>=33);
Operators

Eg:
bool hasLicense = true;
bool isDrunk = false;
bool canDrive = true;
Operators

Eg:
bool hasLicense = true;
bool isDrunk = false;
bool canDrive = (hasLicense && !isDrunk);
Input and Output

Standard streams are used for reading input and writing output
In C++, the standard streams are cin for input and cout for
output.
The input for the program usually consists of numbers and strings
that are separated with spaces and newlines.

int a, b;
string x;
cin >> a >> b >> x;
int a, b;
string x;
cin >> a >> b >> x;

10380 8090 CSEA 10920 10920 8090

8090 CSEA
CSEA

All of the above inputs will be read properly, i.e. spaces

and newlines(enter) are accounted for.
Output (cout) stream
int a = 234, b = 89;

string s = "CSEA";

cout << a << " " << endl << b << " " << s;

endl: Used to insert a linebreak in output

Output :
cin, cout vs scanf, printf

Often cin and cout are slow and less efficient than C
counterpart scanf and printf
Hence to make code efficient, we add the following lines in
the beginning which makes the program execution much faster.

ios::sync_with_stdio(0);
cin.tie(0);
cin doesn’t ignore white spaces so in case when want to read
a string with whitespaces then we have to use the getline
function

string a; string a;
getline(cin,a); cin>>a;
cout<<a; cout<<a;

Further Reading :
http://www.cplusplus.com/doc/tutorial/basic_io/
Conditional statements

if(condition){ if(condition1){
// do thing 1
//Do something ...
} }
else if(condition2){
// do thing 2
...
}else if(condition3){
if(condition1){ // do thing 3
// do thing 1 ...
} }else{
else{ // optional
// optional ...
} }
switch statements

switch(var){
case n1 : // code if var == n1
break;
case n2 : // code if var == n2
break;
case n3 : // code if var == n3
break;
default : //~else
}

Further reading : https://www.w3schools.in/cplusplus-tutorial/decision-making/

Coding Platforms

● Level -1 : Learn a language, preferably C++

● Level 0: Hackerrank
○ Language Proficiency : 2-3 stars
○ Problem Solving : 3-4 stars
● Level 1: Atcoder Beginner Contests (ABCs), Codechef Starters,
Codeforces Div 3
○ ABC’s first 2-3 problems are very easy.
○ Starters is aimed at beginners. Good video editorials.
○ Div 3 can be tough or easy at times, but easiest on CF.
● Level 2: Codeforces Div 2
○ A level above Div 3. You can try solving only A for now and
after sometime B and C.
Useful Resources

● CP Handbook (https://cses.fi/book/book.pdf)
● thenewboston (youtube channel) for basic c++
● cplusplus.com for advanced c++ , keep googling the things you
don’t know
● geeksforgeeks.com, DSA Articles and implementations, may or
may not be 100% correct so verify once
● cp-algorithms.com : Implementations and to the point theory
● CLRS : for deep study of DSA, part of syllabus in 3rd sem CSE.
Some problems

1)Solve Me First | HackerRank

2)Conditional Statements | HackerRank
3)Input and Output | HackerRank
4)Problem - 1154A - Codeforces
Homework

● Set up C++
○ Use Codeblocks IDE (from Bucky’s tutorial)
○ Use VSCode and GCC-compiler (https://youtu.be/jvg4VtYEhKU) or
(https://www.geeksforgeeks.org/how-to-setup-competitive-programming-i
n-visual-studio-code-for-c/ )
● Solve problems on Hackerrank Problem Solving section
(here) and C++(here)
● Ask doubts on the Teams chat if you face any.
● Create accounts on Hackerrank, Codechef, Atcoder and
Codeforces. Fill the form which will be floated.
 That’s all
You can ask your doubts on the Teams chat
anytime.