C++ Tricks for Competitive Programming
If you are interested in Computer science or Information technology, you must have heard about competitive programming. Competitive programming is a way to improve your problem-solving skills. There are various competitive programming platforms available nowadays. In competitive programming, you have to solve problems on your merit. But it is also true that in every place, there are some tricks used to solve problems in a short time. These tricks provide some features that take less time to solve problems. So, if you know the tricks, you will surely get the advantage. In this article, we will discuss some tricks which are available in the C++ language, especially in C++ 11.
1. Include all standard libraries
We use many standard libraries to insert different things in our code. These libraries are as follows:
#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <stack>
#include <set>
#include <queue>
#include <map>
Instead of including each standard library individually, use #include <bits/stdc++.h> to include all of them in your project. This would be particularly helpful in a programming contest where speed is of concern. There are numerous header files in <bits/stdc++.h> that you might not need for your project. The time required for compilation may increase as a result.
2. Using range-based for loop
C++ 11 runs for loop across a number of values. It is used as a more readable alternative to the classic for loop that operates over a range of values, such as all of the container's elements. If you wish to iterate sequentially from beginning to end, this C++11 feature is the best. Below the given code is an example of the implementation of the above-said feature.
#include <iostream>
#include <map>
#include <vector>
int main()
{
std::vector<int> v = { 0, 1, 2, 3, 4, 5 };
for (auto i : v)
std::cout << i << ' ';
std::cout << '\n';
for (int n : { 0, 1, 2, 3, 4, 5 })
std::cout << n << ' ';
std::cout << '\n';
int a[] = { 0, 1, 2, 3, 4, 5 };
for (int n : a)
std::cout << n << ' ';
std::cout << '\n';
for (int n : a)
std::cout << "hello world" << ' ';
std::cout << '\n';
std::string str = "earth";
for (char c : str)
std::cout << c << ' ';
std::cout << '\n';
std::map<int, int> MAP(
{ { 1, 1 }, { 2, 2 }, { 3, 3 } });
for (auto i : MAP)
std::cout << '{' << i.first << ", " << i.second
<< "}\n";
}
Output:
3. Use auto to omit the data type of a variable
The auto keyword indicates that the type of the variable being defined will be deduced automatically from its initialiser. When it comes to functions, a return type expression will be used at runtime to determine whether the return type is auto. When generating iterators for containers, it is a good idea to utilise auto to minimise lengthy initialisations. If a variable containing the auto keyword is not initialised at the time of declaration, a compile time error will be occurred. Below the given code is an example of the implementation of the above-said feature.
//First program:
#include <bits/stdc++.h>
using namespace std;
int main()
{
auto x = 4;
auto y = 3.37;
auto ptr = &x;
auto a = 'a';
auto t = true;
cout << typeid(x).name() << endl
<< typeid(y).name() << endl
<< typeid(ptr).name() << endl;
return 0;
}
//Second program:
#include <bits/stdc++.h>
using namespace std;
int main()
{
set<string> st;
st.insert({ "world", "is", "very", "nice" });
for (auto it = st.begin(); it != st.end(); it++)
cout << *it << " ";
return 0;
}
Output:
4. Checking if the number is even or odd without using the % operator
Although utilising the % operator is still preferable, this method can still be useful in certain circumstances (with large numbers). The goal is to determine whether or not the number's final bit is set. The number is odd if the last bit is set; otherwise even. We know that in bitwise and operation, the answer will be 1 if and only if both the bits are 1. We use this technique only. Below the given code is an example of the implementation of the above-said features.
Code using % operator:
#include <iostream>
using namespace std;
bool isEven(int n)
{
If ( n%2 == 0 )
return true;
else
return false;
}
int main()
{
int n = 101;
isEven(n)
? cout << "Even"
: cout << "Odd";
return 0;
}
Output:
Code using & operator:
#include <iostream>
using namespace std;
bool isEven(int n)
{
return (!(n & 1));
}
int main()
{
int n = 101;
isEven(n)
? cout << "Even"
: cout << "Odd";
return 0;
}Output:
5. Use of ternary operator instead of if else statement
It is often seen that we have to use conditional statement in many places. We mainly use if else statements to apply conditions. We use this very frequently because it is easy to use this type of conditional statement in our code. But just think about competitive programming. You have to increase your speed in that situation. So for every conditional case, if you use if-else statement then it will take time to complete your code. But ternary operator can be use as the replacement of if else statement. See the following code to understand how if else statements increase your time and decrease the speed.
Code using if-else statement:
#include <iostream>
using namespace std;
int fun(int n)
{
If ( n > 100 )
{
return 1;
}
else
{
return 0;
}
}
int main()
{
int n = 50;
if ( n < 0 )
{
return 0;
}
else
{
cout<< fun(n);
}
return 0;
}
Output:
As you can see, we have spent lot of time for completing this if else statements but if we use ternary operator in same code we will surely get benefit. Let’s see the below code to get more clear idea.
Code using ternary operator:
#include <iostream>
using namespace std;
int fun(int n)
{
int x;
n > 100 ? x= 1: x= 0;
return x;
}
int main()
{
int n = 50;
n < 0 ? cout<< 0 : cout << fun( n );
return 0;
}Output:
6. Two variables swapping without use of third variable
Swapping is a very common process in programming problems. Many famous sorting algorithms need swapping as a basic process. So, you can see the importance of swapping. In this process, mainly the values of two variables are interchanged. If we have to swap two numbers then it is necessary to take one more variable to store value. But just think about a big set of data which is to be sorted. Now you have to swap. For every swapping you have to take one extra variable. This thing will surely increase the time complexity. You can reduce this extra complexity by doing xor operation on two variables.
Code using extra variable:
#include <iostream>
using namespace std;
int main()
{
int a = 50;
int b = 10;
cout << a<< endl;
cout << b<< endl;
int c = a;
a = b;
b = c;
cout << a<< endl;
cout << b<< endl;
return 0;
}Output:
As you can see, we have declared one new variable to swap the variable. BY using the XOR operation we can do it more efficiently. Let’s see the below code to get more clear idea.
Code using ternary operator:
#include <iostream>
using namespace std;
int main()
{
int a = 50;
int b = 10;
cout << a<<endl;
cout << b<< endl;
a ^= b;
b ^= a;
a ^= b;
cout << a<< endl;
cout << b<< endl;
return 0;
}
Output:
7. Multiplication by 2 and division by 2 easy method
Division by 2 and multiplication by 2 are very common operations which are used in many problems. It is very easy thing to multiply or divide. But just think about the situation when you have to multiply in a loop and the number is very big. The same thing can happen in the case of division. For this reason we can use right shift and left shift operations instead of multiplication and division.
Code using normal multiplication and division:
#include <iostream>
using namespace std;
int main()
{
int a = 5;
int b = 1;
for ( int I = 0; I < a; I++ )
{
cout << b<< endl;
b = b*2;
}
for ( int I = 0; I < a; I++ )
{
cout << b<< endl;
b = b/2;
}
return 0;
}Output:
As you can see, the time complexity increases automatically. But if we use shift operations we will surely get benefit. Let’s see the below code to get more clear idea.
Code using shift operator:
#include <iostream>
using namespace std;
int main()
{
int a = 50;
int b = 10;
for ( int I = 0; I < a; I++ )
{
cout << b;
//multiplication with 2
b = b << 1;
}
for ( int I = 0; I < a; I++ )
{
cout << b;
// division by 2
b = b >> 1;
}
return 0;
}
Output:
