01 CP Templates - broyda/cp-lib GitHub Wiki

C++ pointer note

*p 
&p

means value at p
ampersand means address of p (if used on RHS). If ampersand is used on LHS, then it is reference (and not "address of")

arr is really arr + 0. Therefore, the end element happens to be arr + (n - 1) end() is really the nth element e.g. the element after end of the array, so that works as exclusive in operations such as search/find etc.

**Array pointers (iterators) **
rend() -1th index
begin() 0th index
rbegin (n-1)th index
end() nth index (beyond the array)

& changes values inside the vector (without the ampersand, the vector will not be effected

    vector<int> a = {1,2,4,13};
    for (int &x: a){
      if (x > 3) {
        x = 3;
      }
    }
    for (int x: a) {
      cout << x << " ";
    }

Output:
1 2 3 3

(1) Perform two operations on return statement

Refer to union find code with path compression

return parent[i] = findParent(parent[i]);

1. Rain water problem

O(n) solution if we create two arrays storing the max heights uptill an index - one traversing from the left and another traversing from the right

2. Clone a vector

vector<int> a = {1, 3, 2};
vector<int> b(a); // Populate vector b from vector a

(2) Read and populate a 2D n * m matrix

void readMatrixInto2DArray() {
    int n, m;
    cin >> n >> m;
    int a[n][m];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cin >> a[i][j];           
        }        
    }
}

(2.1) Print a n * m matrix

void print2DMatrix() {
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            cout << a[i][j] << " ";           
        }
        cout << endl;
    }
}

(3) Huge 2-D array

A 10000 * 10000 2-D array takes huge space. So don't use them and find an alternative way

4. Cardinality technique

For example, in a m * n grid with towers which can guard all cells vertically and horizontally, the number of unguarded rectangles is based on the two diff arrays (x-diff and y-diff). The count of xdiffs was 4 and counts of ydiffs was 3 and the number of unguarded rectangles is really all the possible xdiff and ydiff combinations.

5 Max function

if (x < 0) {
   x = 0;
} else {
  x = x;
}

use

x = max(0, x);

6 Read the ith row of an n * m matrix

TODO

7 Read the ith column of an n * m matrix

TODO

Strings

Convert character to int

int j = ch - '0'; 
int k = ch - 'a';

Convert string to int

char x = num + 'a'; // If you've used int k = ch - 'a'; for the encoding

Convert string to int

stoi(str);
stol(str);

Convert string to uppercase or lowercase

transform(s.begin(), s.end(), s.begin(), ::toupper);

Run a while loop with a check for the size of the data structure

while (q.size()) {

   // Do something

}

Check if an int is greater than 0

if (a/2) {
    a.insert(a/2);
}

String contains() function in C++

 if (s.find("H") != string::npos) {
    // Do something
} 
// or
if (s.find(c) < s.length()) {	
     // Do something	
}

All ways to split a string into two parts

         string x = b[i];
 
        for (int j = 1; j < x.length(); j++)
        {
            string m = x.substr(0, j);
            string n = x.substr(j);

Replace all occurances of a particular substring in a string

    size_t pos = 0;
    string x = "WUB";
    while (true)
    {
        pos = s.find(x, pos);
        if (pos == string::npos) { // npos - no positions matched the specified string
            break;
        } 
        s.erase(pos, x.length());
        if (s[pos - 1] != ' ') {
            s.insert(pos, " ");
        }
    }

Loop until it hits the minimum of n and m

while(i < min(m, n)) {
   // Do something
}

Use a pair<int, int> data structure

To solve problems wherein the initial index should be tracked throughout the solution. Refer to solution for problem 450A.cpp for an implementation.

vector<pair<int, int>> a(n);

    for (int i = 0; i < n; i++) {
        int x;
        cin >> x;
        auto m = make_pair(i + 1, x);
        a[i] = m;
    }
    // ---
    while (j < a.size()) {
        if (a[j].second > m) {
            a[j].second = a[j].second - m;
            a.push_back(a[j]);
        }
        j++;
    }
    cout << a[j - 1].first;

Fast data structures

Heaps (priority queue), unordered_set

Unordered set takes linear O(1) time for a lookup!

unordered_set<int> s;
s.insert(y);
if (s.find() != s.end() {

}

Multiset notes

A set cannot contain duplicates, but a multiset can.
Multisets contain ordered elements and the first element set.begin() contains the smallest element.

  1. Deleting all occurences of an element in multiset.
multiset<int> mset = {1,1,1,2,3,4}
mset.erase(1); // Deletes ALL occurances of '1'
mset.erase(mset.find(1)); // Delete first occurances of '1' (using the above line of code can cause subtle issues wherein all occurences of '1' are deleted). So choose the options correctly.
  1. Calling erase on an element that does not exist can cause runtime errors. So here's a defensive check:
if (!mset.empty() and mset.count(n) > 0)
   mset.erase(mset.find(n));
  1. Erase an element for which we have an iterator hook.
auto it = mset.upper_bound(x);
if (it != mset.end()) {
    mset.erase(it);
}

Time complexities of sets:
Insert (log n)
Erase/Find (log n)
Hence, m.erase(m.find(1)) will do the erase in O(log n) time complexity.

How to make a pair

make_pair(x, y);
or {x,y}

Array contains a certain element

// Example usage:
// Suppose int a[20]
// contains(a, 60)
template<typename C, typename T>
bool contains(C&& c, T e) { 
    return std::find(std::begin(c), std::end(c), e) != std::end(c);
};

template<typename C, typename T>
void check(C&& c, T e) {
    std::cout << e << (contains(c,e) ? "" : " not") <<  " found\n";
}

Nice debugging template

#ifndef ONLINE_JUDGE
#define pr(...)dbs(#__VA_ARGS__,__VA_ARGS__)
#define debarr(a,n)cerr<<#a<<":";for(int i=0;i<n;i++)cerr<<a[i]<<" ";cerr<<endl;
#define debmat(mat,row,col)cerr<<#mat<<":\n";for(int i=0;i<row;i++){for(int j=0;j<col;j++)cerr<<mat[i][j]<<" ";cerr<<endl;}

template<class S,class T>ostream &operator<<(ostream &os,const pair<S,T> &p){return os<<"("<<p.first<<","<<p.second<<")";}
template<class T>ostream &operator<<(ostream &os,const vector<T> &p){os<<"[";for(auto&it:p)os<<it<<" ";return os<<"]";}
template<class T>ostream &operator<<(ostream &os,const set<T>&p){os<<"[";for(auto&it:p)os<<it<<" ";return os<<"]";}
template<class T>ostream &operator<<(ostream &os,const multiset<T>&p){os<<"[";for(auto&it:p)os<<it<<" ";return os<<"]";}
template<class S,class T>ostream &operator<<(ostream &os,const map<S,T>&p){os<<"[";for(auto&it:p)os<<it<<" ";return os<<"]";}
template<class T>void dbs(string str,T t){cerr<<str<<":"<<t<<"\n";}
template<class T,class...S>void dbs(string str,T t,S... s){int idx=str.find(',');cerr<<str.substr(0,idx)<<":"<<t<<",";dbs(str.substr(idx+1),s...);}
#else
#define pr(...){}
#define debarr(a,n){}
#define debmat(mat,row,col){}
#endif

Modulus functions

#define ll long long int

int mod = 1e9 + 7;

inline ll add(ll a, ll b) {
  ll num = a + b;
  if (num >= mod) {
  	num -= mod;
  } else if (num < 0) {
  	num += mod;
  }
  return num;
}

inline ll sub(int a, int b) {
  ll num = a - b;
  if (num < 0) {
  	num += mod;
  }
  else if (num >= mod) {
  	num -= mod;
  }
  return num;
}

inline int mul(int a, int b) {
  return (int) ((long long) a * b % mod);
}

inline int power(int a, long long b) {
  int res = 1;
  while (b > 0) {
    if (b & 1) {
      res = mul(res, a);
    }
    a = mul(a, a);
    b >>= 1;
  }
  return res;
}

inline int inv(int a) {
  a %= mod;
  if (a < 0) a += mod;
  int b = mod, u = 0, v = 1;
  while (a) {
    int t = b / a;
    b -= t * a; swap(a, b);
    u -= t * v; swap(u, v);
  }
  assert(b == 1);
  if (u < 0) u += mod;
  return u;
}

int fact[N];

void pre() {
    fact[0] = 1;
    for(int i = 1; i < N; i++)
        fact[i] = mul(fact[i - 1], i);
    return;
}

Find nth element in a set

set<int> my_set;
////
////
int x = *std::next(my_set.begin(), n);

Shorthand for loops

Initialize to max of two values

for (int i = max(a,b); i < N; i++) {
    // Do something
}

next_permutation() example

Generate all permutations.

vector<int> a = {0,1,2,3,4,5,6,7,8,9}
do {
  cout << a << endl;
} while(next_permutation(v.begin(), v.end())

Using assert

To check if the solutions from two different implementations (with the same input passed in) results in the exact same output

int i = solve1(n);
int j = solve2(n);
pr(i == j)

Formatting result to certain decimal positions

double y = abs(x1 - x2) + abs(y1 - y2);
cout << fixed << setprecision(7) << sqrt(x) << " " << y << endl;







Deque


Supports random access too, in addition to insertion and deletion from the front/back.


Traverse cells up, down, left and right


int drows[] = {-1, 0, 1, 0};
int dcols[] = {0, 1, 0, -1};
for (int i = 0; i < 4; i++) {
    int nrow = row + drows[i];
    int ncol = col + dcols[i];
} 


Priority Queue (reverse sort)


Priority queues, by default, returns the max element. In order to return the minimum element instead, we insert by negating the number.


priority_queue<int> pq;
pq.insert(-data);




When to use priority queue?

If the use case deals with ONLY find minimum or find maximum and we do not really care of the order of anything else that's on the data structure, priority queue is the way to go.


Interesting usage of the swap function


Avoid writing multiple conditional logic for example if n > m { do this } and n <= m { do that }. Insead swap n and m. Arrays can be swapped too.


if (n > m) {
   swap(n, m);
   swap(arr_a, arr_b);
}


How big of arrays can be created?


Inside a function, 10^6 (stack)
In global scope, 10^8 (heap)


Note on STL find versus lower_bound functions


std::find() performs linear search, i.e., it goes element by element until it finds the value it's looking for. It is linear regardless of whether or not the collection is sorted.


If you have a sorted vector, you may want to consider performing binary search with std::lower_bound() instead. This will be logarithmic in the size of the vector.


int howmany(vector<long long> &a, int startIndex, int num) {
	auto last = upper_bound(a.begin() + startIndex, a.end(), num);
	auto first =  lower_bound(a.begin()  + startIndex , a.end(), num);
	int count = last - first;
	return count;
}


Handling -1 when array actually contains negative numbers


Create a separate done[n] array. So by cross referencing the done array, we know whether the cache array has a computed -1 or a default -1.


if (done[n]) {
   return cache[n];
}


Check stack size before calling stack.top() or such


if (!st.empty()) {
   st.top();
   st.pop();

}



Search techniques using lb and upperbounds


    

  • For <=, use upperbound
    • 

  • For <, use lowerbound
    • 



For the inequality m > y, this essentially becomes:
N - (# elements <= y)

Can be found using two approaches:


    

  • end() - upper bound(y) or
    • 

  • N - (upper bound(y) - begin())
    • 



For the problem STL App 5.1 Count how many intervals wherein a specific number lies, the key idea is to transform the intervals (wherein it is difficult to apply sorting on pairs) to a disjoint set argument e.g. count the number of elements in the complement set. E.g. we want to find

How many intervals wherein y >= Li AND y <= Ri

The complement is y < Li OR y > Ri

Transform this to a form upperbound and lowerbound functions can understand e.g.

Li > y OR Ri < y Count them individually and notice that they are disjoint sets so we can just sum them up to get the answer (after using some math for complement etc.)




⚠️ **GitHub.com Fallback** ⚠️