Knapsack
Knapsack Fractional knapsack greedy, sort items by value/wt and pick max ones 0/1 Knapsack - O(nw) time and O(nw) space variant def: f(w) ⇒ max value s.t.
Archive
DP
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
CSES Graph Problems Graphs Aim here is to implement whatever multiple approaches and use this as reference for programming style for future.
Trees
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...
Array Deque
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 ...
Binary Search Tree
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,...
Disjoint Set Union
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...
Dynamic Array
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...
Fenwick Tree
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...
Hash Map
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::...