Dynamic Programming Dice Combinations way to make sum n by using a(i) repeatedly → what is f? defn: f(i) = no of throws to make i base: f(⇐0) = 1 trans: f(i) = sum over throw in 1..6 : f(i-throw) Min Coins min number of a(i) needed ( rep ) to make sum n Problem is framed as coins def: min no of coin...
CSES Graph Problems Graphs Aim here is to implement whatever multiple approaches and use this as reference for programming style for future.
Trees Company Queries // problem: go up k levels // tag: bin lift #include <bits/stdc++.h> using namespace std; int main() { #define int long long int n, q; cin >> n >> q; vector<vector<int>> g(n + 1); for (int i = 2; i <= n; i++) { int u; cin >> u; g[u].push_b...
Implementations C++ #include <cstddef> #include <memory> template <typename T> class ArrayDeque { private: std::allocator<T> alloc_; T *array_ = nullptr; std::size_t start_ = 0; // WARN: end_ is not needed and you CANNOT do it without a size_ // end can be computed from size ...
Implementations C++ #include <cstddef> #include <iterator> #include <memory> #include <ranges> #include <type_traits> #include <utility> #include <vector> template <typename T> class BST { private: struct Node { T val; std::unique_ptr<Node> left,...
Implementations C++ // for the single array holds size and par trick // you need a signed int as the array elem type // since the par too must be same as the elem type // you need int as type // templating here is kind of wasteful #include <vector> class DSU { private: std::vector<int> p...
Implementations C #include <stddef.h> #include <stdlib.h> #include <string.h> typedef struct { unsigned char *data; size_t size; size_t capacity; size_t elem_size; } Array; /// initialise void array_init(Array *array, size_t elem_size) { *array = (Array){.data = NULL, .size = 0, .c...
Implementations C++ #include <concepts> #include <cstddef> #include <vector> template <typename T> concept Group = requires(T a, T b) { // INFO: you need to use other std::concepts in rhs here // so can't do std::is_same_v, need std::is_same_as // alternative is to add a...
Implementations C++ #include <concepts> #include <cstdint> #include <cstdio> #include <functional> #include <string> #include <type_traits> #include <utility> #include <vector> template <typename T> concept HashableKey = requires(T key) { { std::...
Implementations C++ #include <cstddef> #include <vector> template <typename T, typename Cmp = std::less<T>> class Heap { private: std::vector<T> array_; Cmp comp_; // INFO: you don't need a size // INFO: it's complete b tree in the sense that you FILL the // r...