Collection of the common functions that I used during practice for competitive coding

competitive_snippets

A collection of implementations of the problems that I did during competitive coding.

bubble_sort_count_inversions.hpp

int count_inversions_bsort(int a[], int n) {
    bool swapped = true;
    int swaps = 0;
    while(swapped) {
        swapped = false;
        for(int i = 0; i < n - 1; i++) {
            if (a[i] > a[i+1]) {
                int temp = a[i];
                a[i] = a[i+1];
                a[i+1] = temp;
                swaps++;
                swapped = true;
            }
        }
    }
    return swaps;
}

merge_sort_count_inversions.hpp

int count_inversions_msort(int a[], int temp[], int n) {
    if (n == 1) {
        return 0;
    }

    int inversions = count_inversions_msort(a, temp, n / 2) +
                     count_inversions_msort(a + n / 2, temp, n - n / 2);
    int l = 0, r = n / 2;
    int k = 0;

    while(l < n / 2 && r < n) {
        if (a[l] <= a[r]) {
            temp[k++] = a[l++];
        } else {
            temp[k++] = a[r++];
            inversions += n / 2 - l;
        }
    }

    while(l < n / 2) {
        temp[k++] = a[l++];
    }

    while(r < n) {
        temp[k++] = a[r++];
    }

    for (int i = n - 1; i >= 0; i--) {
        a[i] = temp[i];
    }

    return inversions;
}

shortest_common_supersequence.hpp

#include <iostream>
#include <string>
#include <vector>
#include <functional>
#include <algorithm>

std::string scom_supsec(const std::string& a,
                        const std::string& b)
{
    int alen = a.size();
    int blen = b.size();
    std::vector<std::vector<int> > mat(alen + 1, std::vector<int>(blen + 1));
    std::function<int(const std::string&, const std::string&, int, int)> scss;

    scss = [&mat, &scss](const std::string& astr, const std::string& bstr,
                            int a_len, int b_len) -> int
    {
        if (a_len == 0) {
            mat[a_len][b_len] = b_len;
            return b_len;
        } else if (b_len == 0) {
            mat[a_len][b_len] = a_len;
            return a_len;
        } else if (astr[a_len - 1] == bstr[b_len - 1]) {
            if (mat[a_len][b_len] != 0) {
                return mat[a_len][b_len];
            } else {
                mat[a_len][b_len] = 1 + scss(astr, bstr, a_len - 1, b_len - 1);
                return mat[a_len][b_len];
            }
        } else {
            if (mat[a_len][b_len] != 0) {
                return mat[a_len][b_len];
            } else {
                mat[a_len][b_len] = 1 + std::min(scss(astr, bstr, a_len - 1, b_len),
                scss(astr, bstr, a_len, b_len - 1));
                return mat[a_len][b_len];
            }
        }
    };

    int scss_len = scss(a, b, alen, blen);
    std::string result;
    int i = alen, j = blen;

    while(i > 0 && j > 0) {
        if(a[i - 1] == b[j - 1]) {
            result.push_back(a[i - 1]);
            i--;
            j--;
        } else if (mat[i - 1][j] > mat[i][j - 1]) {
            result.push_back(b[j - 1]);
            j--;
        } else {
            result.push_back(a[i - 1]);
            i--;
        }
    }

    while (j > 0) {
        result.push_back(b[j - 1]);
        j--;
    }

    while (i > 0) {
        result.push_back(a[i - 1]);
        i--;
    }

    std::reverse(result.begin(), result.end());
    return result;
}