Hi all!
Several months ago I decided to write down all the algorithms I know (and don't know) in one Visual Studio project for reusing, remembering, preparing to the interviews and easy learning of new algorithms and compose them in the one big library.
I have implemented some part of this library, but before going deeper I want to provide some examples of library current usages:
Example
For example, you can compute Fibonacci n-th element using matrix exponentiation by writing the following code:
#include <iostream>
#include <Math/Math.h>
using namespace std;
int main()
{
algo::Matrix<int> mat{ {1, 1}, { 1, 0 } };
algo::Matrix<int> neutral{ {1, 0}, { 0, 1 } };
algo::Matrix<int> fib { {1, 1} };
mat = algo::bin_pow(mat, 7, neutral, algo::matrix_mul<int>);
fib = algo::matrix_mul(fib, mat);
cout << fib[0][0]; // prints 34
}
After this code compiles another file is generated that do not contain any of repo headers and this file you can submit to any online judge:
Postprocessed code
#include <iostream>
#pragma once
#include<iostream>
#pragma once
#include<algorithm>
#include<iostream>
#include<vector>
#include<string>
#include<cassert>
#include<queue>
#include<set>
#include<map>
namespace algo
{
const int Inf = INT_MAX;
const long long LInf = LLONG_MAX;
template<typename T, typename... Others>
T max(T first, Others... others);
template<typename T>
T max(T first);
template<typename T, typename... Others>
T min(T first, Others... others);
template<typename T>
T min(T first);
template<typename Container>
void input_container(std::istream& in,
int& n,
Container& container);
template<typename Container>
void output_container(std::ostream& out,
const Container& container,
const std::string& delimiter = " ");
template<typename Container, typename T>
void sum_container(const Container& container, T& sum);
template <typename T>
using Matrix = std::vector<std::vector<T>>;
template <typename T>
Matrix<T> CreateMatrix(size_t n, T etalon = T());
template <typename T>
Matrix<T> CreateMatrix(size_t n, size_t m, T etalon = T());
template <typename T>
void CreateMatrix(Matrix<T>& matrix, size_t n, T etalon = T());
template <typename T>
void CreateMatrix(Matrix<T>& matrix, size_t n, size_t m, T etalon = T());
double random(double min, double max);
}
#pragma once
#include<algorithm>
#include<random>
namespace algo
{
template<typename T, typename... Others>
inline T max(T first, Others... others)
{
return std::max(first, max<T>(others...));
}
template<typename T>
inline T max(T first)
{
return first;
}
template<typename T, typename... Others>
inline T min(T first, Others... others)
{
return std::min(first, min(others...));
}
template<typename T>
inline T min(T first)
{
return first;
}
template<typename Container, typename T>
inline void sum_container(const Container& container, T& sum)
{
for (auto& elem : container)
{
sum += elem;
}
}
template<typename T>
inline Matrix<T> CreateMatrix(size_t n, T etalon)
{
return Matrix<T>(n, std::vector<T>(n, etalon));
}
template<typename T>
inline Matrix<T> CreateMatrix(size_t n, size_t m, T etalon)
{
return Matrix<T>(n, std::vector<T>(m, etalon));
}
template<typename T>
inline void CreateMatrix(Matrix<T>& matrix, size_t n, T etalon)
{
matrix = Matrix<T>(n, std::vector<T>(n, etalon));
}
template<typename T>
inline void CreateMatrix(Matrix<T>& matrix, size_t n, size_t m, T etalon)
{
matrix = Matrix<T>(n, std::vector<T>(m, etalon));
}
inline double random(double min, double max)
{
std::random_device rd;
std::mt19937 mt(rd());
std::uniform_real_distribution<double> dist(min, max);
return dist(mt);
}
template<typename Container>
inline void input_container(std::istream& in,
int& n,
Container& container)
{
in >> n;
container.resize(n);
for (auto& elem : container)
{
in >> elem;
}
}
template<typename Container>
inline void output_container(std::ostream& out,
const Container& container,
const std::string& delimiter)
{
for (auto& elem : container)
{
out << elem << delimiter;
}
}
}
#include<functional>
// TODO check math
namespace algo
{
template<typename T>
T gcd(T a, T b)
{
return b ? a : gcd(b, a % b);
}
template<typename T>
T lcm(T a, T b)
{
return a / gcd(a, b) * b;
}
int euler_function(int n)
{
int ans = 0;
for (int i = 1; i <= n; ++i)
{
ans += gcd(i, n) == 1;
}
return ans;
}
template<typename T, typename Func>
T bin_pow(T elem, int n, T neutral_element,
Func mul = std::multiplies<T>())
{
T ans = neutral_element;
while (n)
{
if (n & 1)
{
ans = mul(ans, elem);
}
elem = mul(elem, elem);
n >>= 1;
}
return ans;
}
template<typename T, typename Func>
T bin_pow(T elem, int n, int mod, T neutral_element,
Func mul = std::multiplies<T>(),
Func modulus = std::modulus<T>())
{
T ans = neutral_element;
while (n)
{
if (n & 1)
{
ans = mul(ans, elem);
ans = modulus(ans, mod);
}
elem = mul(elem, elem);
elem = modulus(elem, mod);
n >>= 1;
}
return ans;
}
template<typename T>
algo::Matrix<T> matrix_mul(const algo::Matrix<T>& l,
const algo::Matrix<T>& r)
{
if (l[0].size() != r.size())
{
throw std::runtime_error("Matrix dimensions must be equal");
}
algo::Matrix<T> matrix = CreateMatrix(l.size(), r[0].size(), 0);
for (int i = 0; i < l.size(); ++i)
for (int j = 0; j < r.size(); ++j)
for (int k = 0; k < l[i].size(); ++k)
matrix[i][j] += l[i][k] * r[k][j];
return matrix;
}
template<typename T>
algo::Matrix<T> matrix_mod(algo::Matrix<T> matrix, int mod)
{
for (int i = 0; i < matrix.size(); ++i)
for (int j = 0; j < matrix[i].size(); ++j)
matrix[i][j] %= mod;
return matrix;
}
std::vector<int> sieve_of_eratosthenes(int n)
{
std::vector<int> primes(1, 2);
std::vector<char> used(n, false);
for (int i = 2; i < used.size(); i += 2)
used[i] = true;
for (int i = 3; i < used.size(); i += 2)
{
if (!used[i])
{
primes.push_back(i);
for (int j = i * i; j < used.size(); j += i)
{
used[j] = true;
}
}
}
return primes;
}
int extended_euclidean(int a, int b, int& x, int& y)
{
if (a == 0)
{
x = 0, y = 1;
return b;
}
int x1, y1;
int gcd = extended_euclidean(b % a, a, x1, y1);
x = y1 - b / a * x1;
y = x1;
return gcd;
}
}
namespace algo
{
int euler_function(int n)
{
int ans = 0;
for (int i = 1; i <= n; ++i)
{
ans += gcd(i, n) == 1;
}
return ans;
}
}
using namespace std;
int main()
{
algo::Matrix<int> mat{ {1, 1}, { 1, 0 } };
algo::Matrix<int> neutral{ {1, 0}, { 0, 1 } };
algo::Matrix<int> fib { {1, 1} };
mat = algo::bin_pow(mat, 7, neutral, algo::matrix_mul<int>);
fib = algo::matrix_mul(fib, mat);
cout << fib[0][0]; // prints 34
}
Another example
For another example, I tested my repo on this problem. Here is the code I wrote in my IDE:
#include <iostream>
#include <DataStructures/SegmentTree.h>
using namespace std;
int main()
{
int n;
cin >> n;
algo::SegmentTree<int> tree(std::vector<int>(40000, 0), // initial array
std::plus<int>(), // operation (function or lambda or functor)
0, // neutral element of operation above
algo::SegmentTree<int>::UpdateType::Sum); // update type (assigning, product or sum for now)
vector<int> ans(n);
for (int i = 0; i < n; i++)
{
int x, y;
cin >> x >> y;
ans[tree.query(0, x)]++;
tree.update(x, 1);
}
for (int i = 0; i < n; i++)
{
cout << ans[i] << endl;
}
}
The following code is generated after compiling, which you can submit to the timus and get your AC :) (Here is my submission):
Full code to submit
#include <iostream>
#pragma once
#include<vector>
#include<functional>
#include<algorithm>
namespace algo
{
template<typename T>
class SegmentTree
{
public:
static T min(T a, T b)
{
return a < b ? a : b;
}
static T max(T a, T b)
{
return a > b ? a : b;
}
enum class UpdateType
{
Assign,
Sum,
Product
};
private:
std::vector<T> m_vec;
std::vector<T> m_tree;
std::vector<T> m_lazy_prop;
std::function<T(T, T)> m_tree_logic;
int m_neutral_element;
UpdateType m_upd_type;
void build_tree(int v, int l, int r);
void update(int pos, T elem, int v, int l, int r);
// void update(int pos_l, int pos_r, T elem, int v, int l, int r);
T query(int from, int to, int v, int l, int r) const;
static int left(int v);
static int right(int v);
static int mid(int l, int r);
void update_one(int& a, int b);
public:
SegmentTree(const std::vector<T>& vec,
const std::function<T(T, T)>& tree_logic,
int neutral_element,
UpdateType upd_type = UpdateType::Assign);
void build_tree();
void update(int pos, T elem);
// void update(int pos_l, int pos_r, T elem);
T query(int from, int to) const;
int size() const;
};
}
namespace algo
{
template<typename T>
inline void SegmentTree<T>::build_tree(int v, int l, int r)
{
if (l == r)
{
m_tree[v] = m_vec[l];
}
else
{
int m = mid(l, r);
build_tree(left(v), l, m);
build_tree(right(v), m + 1, r);
m_tree[v] = m_tree_logic(m_tree[left(v)], m_tree[right(v)]);
}
}
template<typename T>
inline void SegmentTree<T>::update(int pos, T elem, int v, int l, int r)
{
if (l == r)
{
update_one(m_tree[v], elem);
update_one(m_vec[pos], elem);
}
else
{
int m = mid(l, r);
if (pos <= m)
{
update(pos, elem, left(v), l, m);
}
else
{
update(pos, elem, right(v), m + 1, r);
}
m_tree[v] = m_tree_logic(m_tree[left(v)], m_tree[right(v)]);
}
}
/*template<typename T>
inline void SegmentTree<T>::update(int pos_l,
int pos_r,
T elem,
int v,
int l,
int r)
{
if (pos_l == l && pos_r == r)
{
m_lazy_prop = elem;
}
}*/
template<typename T>
inline T SegmentTree<T>::query(int from, int to, int v, int l, int r) const
{
if (from > to)
{
return m_neutral_element;
}
if (from == l && to == r)
{
return m_tree[v];
}
else
{
int m = mid(l, r);
int left_ans = query(from, std::min(m, to), left(v), l, m);
int right_ans = query(std::max(from, m+1), to, right(v), m + 1, r);
return m_tree_logic(left_ans, right_ans);
}
}
template<typename T>
inline int SegmentTree<T>::left(int v)
{
return v << 1;
}
template<typename T>
inline int SegmentTree<T>::right(int v)
{
return (v << 1) + 1;
}
template<typename T>
inline int SegmentTree<T>::mid(int l, int r)
{
return (l + r) >> 1;
}
template<typename T>
inline void SegmentTree<T>::update_one(int& a, int b)
{
switch (m_upd_type)
{
case UpdateType::Assign:
a = b;
break;
case UpdateType::Sum:
a += b;
break;
case UpdateType::Product:
a *= b;
break;
default:
break;
}
}
template<typename T>
SegmentTree<T>::SegmentTree(const std::vector<T>& vec,
const std::function<T(T, T)>& tree_logic,
int neutral_element,
UpdateType upd_type)
: m_vec(vec)
, m_tree_logic(tree_logic)
, m_neutral_element(neutral_element)
, m_upd_type(upd_type)
{
m_tree.resize(m_vec.size() << 2);
}
template<typename T>
inline void SegmentTree<T>::build_tree()
{
build_tree(1, 0, m_vec.size() - 1);
}
template<typename T>
inline void SegmentTree<T>::update(int pos, T elem)
{
update(pos, elem, 1, 0, m_vec.size() - 1);
}
/*template<typename T>
inline void SegmentTree<T>::update(int pos_l, int pos_r, T elem)
{
if (m_lazy_prop.empty())
{
m_lazy_prop.resize(m_tree.size());
}
update(pos_l, pos_r, elem, 1, 0, m_vec.size() - 1);
}*/
template<typename T>
inline T SegmentTree<T>::query(int from, int to) const
{
return query(from, to, 1, 0, m_vec.size() - 1);
}
template<typename T>
inline int SegmentTree<T>::size() const
{
return m_vec.size();
}
}
using namespace std;
int main()
{
int n;
cin >> n;
algo::SegmentTree<int> tree(std::vector<int>(40000, 0),
std::plus<int>(),
0,
algo::SegmentTree<int>::UpdateType::Sum);
vector<int> ans(n);
for (int i = 0; i < n; i++)
{
int x, y;
cin >> x >> y;
ans[tree.query(0, x)]++;
tree.update(x, 1);
}
for (int i = 0; i < n; i++)
{
cout << ans[i] << endl;
}
}
And there are a lot of other examples.
This is very comfortably and useful so I'm planning to add a lot of algorithms here.
Repo is on GitHub, and here is the link. You can find the themes (like Graphs, Strings, Cryptography etc.) I planned to cover on the Projects tab, and you can there see which algorithms are already implemented and tested. I use Windows, C++14/17, and my repo is a Visual Studio 2019 project by itself. All algorithms are implemented in namespace named "algo", and for each algorithm I have created separate class, and divided it in header and it's implementation file.
Also I have implemented "preprocessor" for parsing my own header files. This is to generate file that can be sent to online judge for checking.
Anyone here is welcomed to use this repo for problem solving. And I will be very happy if anyone will use my library and, why not, contribute to it by adding a new algorithms, fixing bugs and doing other github stuff!
Thank you for reading!
