Creativity, Teaching & Engineering

Digit DP refers to a DP technique that solves problems that involve digits. The general style of said problems are: How many integers in the range from [L, R] satisfy some condition. Notice that L, R will always be huge (L,R <= 1e18) in order to prevent naive looping. To solve these problems, we need…

There is a shop with N items, each with a different weight W and value V. We want to select some subset of these N items such that the sum of their values V is maximized and the sum of their weights W does not exceed some threshold C.  0/1 Knapsack: There exists only 1…

BFS is one of the main graph traversal algorithms. In DFS, we recursively travel as deep as possible to find paths, while in BFS we explore the graph layer by layer. We can imagine BFS as a fire spreading from the start node. Initially it is only at the start, at second 1 it spreads…

The longest increasing subsequence (LIS) problem is one of the most common in competitive programming. Given a sequence A, we want to find some sequence A_1, A_2 … A_k such that A_1 < A_2 < A_3 < A_k, hence a strictly increasing subsequence. Additionally, we want to find the subsequence with the maximum possible length. …

DFS is one of the main graph search algorithms. The idea of DFS is to start a vertex, then recursively visit each adjacent unvisited vertex in order.  vector<vector<int>> adj; vector<bool> vis; void dfs(int v){    vis[v] = true;    for(int u : adj[v]){        if(!vis[u]){    dfs(u);        }} DFS can…

Given a weighted undirected or directed graph with non-negative weights, you want to solve the Single Source Shortest Path problem. From a start vertex v, you want to find the shortest path from v to every other node in the graph, hence why it is called single source shortest path.  Dijkstra’s algorithm is the most…