Construct Quad Tree

A quadtree is a tree data structure in which each internal node has exactly four children. Given a n * n matrix grid of 0's and 1's only. We want to represent the grid with a Quad-Tree. Return the root of the Quad-Tree representing the grid. Notice that you can assign the value of a node to True or False when isLeaf is False, and both are accepted in the answer. Definition for a QuadTree node. ```cpp class Node { public: bool val; bool isLeaf; Node* topLeft; Node* topRight; Node* bottomLeft; Node* bottomRight; Node() { val = false; isLeaf = false; topLeft = NULL; topRight = NULL; bottomLeft = NULL; bottomRight = NULL; } Node(bool _val, bool _isLeaf) { val = _val; isLeaf = _isLeaf; topLeft = NULL; topRight = NULL; bottomLeft = NULL; bottomRight = NULL; } Node(bool _val, bool _isLeaf, Node* _topLeft, Node* _topRight, Node* _bottomLeft, Node* _bottomRight) { val = _val; isLeaf = _isLeaf; topLeft = _topLeft; topRight = _topRight; bottomLeft = _bottomLeft; bottomRight = _bottomRight; } }; ``` We can construct a Quad-Tree from a two-dimensional area using the following steps: If the current grid has the same value (i.e all 1's or all 0's) set isLeaf True and set val to the value of the grid and set the four children to Null and stop. If the current grid has different values, set isLeaf to False and set val to any value and divide the current grid into four sub-grids as shown in the photo. Recurse for each of the children with the proper sub-grid. If you want to know more about the Quad-Tree, you can refer to the wiki. Quad-Tree format: The output represents the serialized format of a Quad-Tree using level order traversal, where null signifies a path terminator where no node exists below. It is very similar to the serialization of the binary tree. The only difference is that the node is represented as a list [isLeaf, val]. If the value of isLeaf or val is True we represent it as 1 in the list [isLeaf, val] and if the value of isLeaf or val is False we represent it as 0. Example: ```cpp Input: grid = [[0,1],[1,0]] Output: [[0,1],[1,0],[1,1],[1,1],[1,0]] ``` Solution: Recursively divide the grid by four and check if it is the leaf and its value is same as the other three. ```cpp Node* construct(vector>& grid) { int n = (int) grid.size(); return build(grid, 0, 0, n); } Node* build(vector>& grid, int i, int j, int n) { if(n == 1) return new Node(grid[i][j], true); Node* res = new Node(0, false, build(grid, i, j, n / 2), build(grid, i, j + n / 2, n / 2), build(grid, i + n / 2, j, n / 2), build(grid, i + n / 2, j + n / 2, n / 2)); if( res->topLeft->isLeaf && res->topRight->isLeaf && res->bottomLeft->isLeaf && res->bottomRight->isLeaf && res->topLeft->val == res->topRight->val && res->topLeft->val == res->bottomLeft->val && res->topLeft->val == res->bottomRight->val ) { res->val = res->topLeft->val; res->isLeaf = true; delete res->topLeft; delete res->topRight; delete res->bottomLeft; delete res->bottomRight; res->topLeft = NULL; res->topRight = NULL; res->bottomLeft = NULL; res->bottomRight = NULL; } return res; } ```

Same GCD?

Find the number of x that satisfies $ gcd(a, m) = gcd(a + x, m) $ where $ 0 <= x < m $. For example, if $ a = 4 $ and $ m = 9 $, there would be 6 $x$ which are $0, 1, 3, 4, 6, 7$. From Euclidean algorithm, we know that $ gcd(a, b) = gcd(a \bmod b, b) $. For example, if $ a = 4 $ and $ b = 8 $, we know that $ gcd(12, 8) = gcd(12 \bmod 8, 8)$, in this case, which is $4$. Back to our question, we know that $ 0 <= x < m $, which means that the range of $ a + x $ would be $ a .. m + a $, it can be divided by $ m $. Let $ k $ be $ (a + x) \bmod m $, the range of $ k $ is $ 0 .. m $. Now we can rewrite it to $ gcd(a, m) = gcd(k, m) $. Let's say $ gcd(a, m) = gcd(k, m) = g $, it then can be rewritten as $ gcd(\frac{k}{g}, \frac{m}{g}) = 1 $. In this case, we can use Euler's totient function to find out how many numbers from $ 1 $ to $ \frac{k}{g} $ are co-prime to $ \frac{k}{g} $. The function is defined as $$ \varphi(n) = n \displaystyle \prod_{n= p | n}^{} (1 - \frac{1}{p}) $$ For example, for $\varphi(36)$, it can be factoralized as $\varphi(2^2 * 3^2)$ = $36 * (1 - \frac{1}{2}) * (1 - \frac{1}{3}) = 12 $. Those 12 numbers are $1, 5, 7, 11, 13, 17, 19, 23, 25, 29, 31$ and $ 35$. Here's the implementation of Euler's totient function in C++. ``` long long phi(long long n) { long long result = n; for (long long i = 2; i * i <= n; i++) { if (n % i == 0) { while (n % i == 0) n /= i; result -= result / i; } } if (n > 1) result -= result / n; return result; } ``` Therefore, back to our question, the solution is relatively simple. ``` long long a, m; cin >> a >> m; cout << phi(m / gcd(a, m)) << endl; ```

Eulerian path / Hierholzer's Algorithm

 ### Eulerian Trail / Path It is a trail in a finite graph that every edge will be visited exactly once. ### Eulerian Cycle / Circuit / Tour It is an Eulerian trail that starts and ends on the same vertex. ### Euler's Theorem A connected graph has an Euler cycle if and only if every vertex has even degree. ### Properties - An undirected graph has an Eulerian cycle if and only if every vertex has even degree, and all of its vertices with nonzero degree belong to a single connected component. - An undirected graph can be decomposed into edge-disjoint cycles if and only if all of its vertices have even degree. So, a graph has an Eulerian cycle if and only if it can be decomposed into edge-disjoint cycles and its nonzero-degree vertices belong to a single connected component. - An undirected graph has an Eulerian trail if and only if exactly zero or two vertices have odd degree, and all of its vertices with nonzero degree belong to a single connected component. - A directed graph has an Eulerian cycle if and only if every vertex has equal in degree and out degree, and all of its vertices with nonzero degree belong to a single strongly connected component. Equivalently, a directed graph has an Eulerian cycle if and only if it can be decomposed into edge-disjoint directed cycles and all of its vertices with nonzero degree belong to a single strongly connected component. - A directed graph has an Eulerian trail if and only if at most one vertex has (out-degree) − (in-degree) = 1, at most one vertex has (in-degree) − (out-degree) = 1, every other vertex has equal in-degree and out-degree, and all of its vertices with nonzero degree belong to a single connected component of the underlying undirected graph. ## Problem #1: LC2097 - Valid Arrangement of Pairs (Hard) You are given a 0-indexed 2D integer array pairs where $ pairs[i] = [start_i, end_i] $. An arrangement of pairs is valid if for every index i where 1 <= i < pairs.length, we have $end_i - 1 $ == $start_i$. Return any valid arrangement of pairs. Note: The inputs will be generated such that there exists a valid arrangement of pairs. ``` Input: pairs = [[5,1],[4,5],[11,9],[9,4]] Output: [[11,9],[9,4],[4,5],[5,1]] ``` ## Idea: Using Hierholzer's Alogorithm We can construct Eulerian trails and circuits using Fleury's algorithm or Hierholzer's algorithm. However, the latter one is more efficient than Fleury's algorithm. Here's the general idea. - Choose any starting vertex v, and follow a trail of edges from that vertex until returning to v. It is not possible to get stuck at any vertex other than v, because the even degree of all vertices ensures that, when the trail enters another vertex w there must be an unused edge leaving w. The tour formed in this way is a closed tour, but may not cover all the vertices and edges of the initial graph. - As long as there exists a vertex u that belongs to the current tour but that has adjacent edges not part of the tour, start another trail from u, following unused edges until returning to u, and join the tour formed in this way to the previous tour. - Since we assume the original graph is connected, repeating the previous step will exhaust all edges of the graph. ## Solution: - Search the starting point of an Eulerian Path, i.e. $ out[i] == in[i] + 1 $. If we got $ out[i] == in[i] $ for all $ i $, then we can start at any arbitrary node (the first node is chosen in this solution). - Perform ``euler``, a post-order dfs function` on the graph. Walk through an edge and erase the visited edge. - Push the ``src`` and ``nxt`` to ``paths``. ``` void euler(unordered_map<int, vector<int>>& g, int src, vector<vector<int>>& paths) { while(!g[src].empty()) { int nxt = g[src].back(); g[src].pop_back(); euler(g, nxt, paths); paths.push_back({src, nxt}); } } vector<vector<int>> validArrangement(vector<vector<int>>& pairs) { vector<vector<int>> ans; int n = (int) pairs.size(); unordered_map<<int, vector<int>> g; unordered_map<int, int> in, out; for(auto x : pairs) { g[x[0]].push_back(x[1]); in[x[1]]++; out[x[0]]++; } int src = -1; for(auto x : g) { int i = x.first; if(out[i] - in[i] == 1) { src = i; break; } } if(src == -1) { src = g.begin()->first; } euler(g, src, ans); reverse(ans.begin(), ans.end()); return ans; } ``` ## Problem #2: LC332 - Reconstruct Itinerary (Hard) You are given a list of airline tickets where tickets[i] = [fromi, toi] represent the departure and the arrival airports of one flight. Reconstruct the itinerary in order and return it. All of the tickets belong to a man who departs from "JFK", thus, the itinerary must begin with "JFK". If there are multiple valid itineraries, you should return the itinerary that has the smallest lexical order when read as a single string. For example, the itinerary ["JFK", "LGA"] has a smaller lexical order than ["JFK", "LGB"]. You may assume all tickets form at least one valid itinerary. You must use all the tickets once and only once.  ``` Input: tickets = [["MUC","LHR"],["JFK","MUC"],["SFO","SJC"],["LHR","SFO"]] Output: ["JFK","MUC","LHR","SFO","SJC"] ``` ## Idea: Using Hierholzer's Alogorithm Similar to LC2097, in this problem, we don't need to search for the starting point as the itinerary must begin with ``JFK``. The black edges represent unvisited edge, green edges are visited edges, and brown edges are backtrack edges.  ## Solution: - Sort tickets based on the destination so that it could get the smaller edge first. - Perform ``euler``, a post-order dfs function` on the graph. Walk through an edge and erase the visited edge. - Push node to ``ans`` when all its edges are processed. ``` void euler(unordered_map<string, queue<string>>& g, string src, vector<string>& ans) { while(!g[src].empty()) { string nxt = g[src].front(); g[src].pop(); euler(g, nxt, ans); } ans.push_back(src); } vector<string> findItinerary(vector<vector<string>>& tickets) { vector<string> ans; sort(tickets.begin(), tickets.end(), [&](const vector& x, const vector& y) { return x[1] < y[1]; }); unordered_map<string, queue<string>> g; for(auto x : tickets) { g[x[0]].push(x[1]); } string src = "JFK"; euler(g, src, ans); reverse(ans.begin(), ans.end()); return ans; } ``` ## Problem #3: CSES1691 - Mail Delivery Your task is to deliver mail to the inhabitants of a city. For this reason, you want to find a route whose starting and ending point are the post office, and that goes through every street exactly once. Input The first input line has two integers n and m: the number of crossings and streets. The crossings are numbered 1,2,…,n, and the post office is located at crossing 1. After that, there are m lines describing the streets. Each line has two integers a and b: there is a street between crossings a and b. All streets are two-way streets. Every street is between two different crossings, and there is at most one street between two crossings. Output Print all the crossings on the route in the order you will visit them. You can print any valid solution. If there are no solutions, print "IMPOSSIBLE". ## Solution: ``` vector ans; vector> g; const int mxN = 1e6 + 5; void euler(int src) { while(g[src].size()) { int nxt = *g[src].begin(); g[nxt].erase(src); g[src].erase(nxt); euler(nxt); } ans.push_back(src); } void solve() { int n, m; cin >> n >> m; g.resize(mxN); for(int i = 0; i < m; i++) { int a, b; cin >> a >> b; --a, --b; g[a].insert(b); g[b].insert(a); } for(int i = 0; i < n; i++) { if(g[i].size() & 1) { cout << "IMPOSSIBLE" << endl; return; } } euler(0); if(ans.size() != m + 1) { cout << "IMPOSSIBLE" << endl; return; } reverse(ans.begin(), ans.end()); for(int i = 0; i < m + 1; i++) { cout << ans[i] + 1 << " \n"[i == m]; } } ```

De Bruijn Sequence

De Bruijn Sequence is a binary sequence of order $ n $ of bits $b_i \in {0, 1} $ where $ b = {b_i, ..., b_{2^n}}$ such that every string of length $ n $ ${a_1, ..., a_n} \in $ {0, 1} $ ^ n $ occurs exactly once consecutively in $b$. To generate a De Bruijn Sequence, we need to get the Euler circuit for the graph for all $ n - 1 $ possible stringds. For example, given $ n = 4 $ & $ k = 2 $,  We would have a sequence of length $2 ^ 4 = 16$ using Eulerian $k$-D de Bruijn graph cycle where $k = n - 1$ which is 3 in this case. Each edge will be traversed exactly once to use each of the 16 4-digit sequences exactly once. The Eulerian path is $$ 000, 000, 001, 011, 111, 111, 110, 101, 011, 110, 100, 001, 010, 101, 010, 100, 000. $$ The de Bruijn sequence is $$ 0 0 0 0 1 1 1 1 0 1 1 0 0 1 0 1 $$ For output sequences of length $ k = 4 $, we got ``` {0 0 0 0} 1 1 1 1 0 1 1 0 0 1 0 1 0 {0 0 0 1} 1 1 1 0 1 1 0 0 1 0 1 0 0 {0 0 1 1} 1 1 0 1 1 0 0 1 0 1 0 0 0 {0 1 1 1} 1 0 1 1 0 0 1 0 1 0 0 0 0 {1 1 1 1} 0 1 1 0 0 1 0 1 0 0 0 0 1 {1 1 1 0} 1 1 0 0 1 0 1 0 0 0 0 1 1 {1 1 0 1} 1 0 0 1 0 1 0 0 0 0 1 1 1 {1 0 1 1} 0 0 1 0 1 0 0 0 0 1 1 1 1 {0 1 1 0} 0 1 0 1 0 0 0 0 1 1 1 1 0 {1 1 0 0} 1 0 1 0 0 0 0 1 1 1 1 0 1 {1 0 0 1} 0 1 0 0 0 0 1 1 1 1 0 1 1 {0 0 1 0} 1 0 0 0 0 1 1 1 1 0 1 1 0 {0 1 0 1} 0} 0 0 0 1 1 1 1 0 1 1 0 0 {1 0 1 ... ... 0 0} 0 0 1 1 1 1 0 1 1 0 0 1 {0 1 ... ... 0 0 0} 0 1 1 1 1 0 1 1 0 0 1 0 {1 ... ``` To find Euler circuit, we can use Hierholzer’s algorithm to get it in linear time. If we randomly traverse the graph without repeating edges, it will eventually end up on the same vertex but the path may not include all the edges. Therefore, we have to remove those visited edges from the graph, which will split into several components. All the components contain Euler Circuit. ## [Cracking the Safe (Hard)](https://leetcode.com/problems/cracking-the-safe/) There is a safe protected by a password. The password is a sequence of n digits where each digit can be in the range [0, k - 1]. The safe has a peculiar way of checking the password. When you enter in a sequence, it checks the most recent n digits that were entered each time you type a digit. For example, the correct password is "345" and you enter in "012345": After typing 0, the most recent 3 digits is "0", which is incorrect. After typing 1, the most recent 3 digits is "01", which is incorrect. After typing 2, the most recent 3 digits is "012", which is incorrect. After typing 3, the most recent 3 digits is "123", which is incorrect. After typing 4, the most recent 3 digits is "234", which is incorrect. After typing 5, the most recent 3 digits is "345", which is correct and the safe unlocks. What is the string of minimum length that will unlock the safe at some point of entering it? For example, $ n = 2, k = 2 $, one of the possible answers is $01100$ because we can type $01$ from the $1st$ digit, $11$ from the $2nd$ digit, $10$ from the $3rd$ digit, and $00$ from the $4th$ digit. ## Solution ```cpp class Solution { public: string ans; vector> vis; int n, k, v; void dfs(int u) { for(int i = 0; i < k; i++) { if(!vis[u][i]) { vis[u][i] = 1; dfs((u * k + i) % v); ans += '0' + i; } } } string crackSafe(int n, int k) { if(k == 1) return string(n, '0'); this->n = n, this->k = k; v = pow(k, n - 1); // vis[k ^ (n - 1)][k] vis.resize(v, vector(k)); dfs(0); return ans + ans.substr(0, n - 1); } }; ```

Codeforces - 999E. Reachability from the Capital

Problem Link: [https://codeforces.com/contest/999/problem/E](https://codeforces.com/contest/999/problem/E) ## Problem There are n cities and m roads in Berland. Each road connects a pair of cities. The roads in Berland are one-way. What is the minimum number of new roads that need to be built to make all the cities reachable from the capital? New roads will also be one-way.  ## Input The first line of input consists of three integers n, m and s (1≤n≤5000,0≤m≤5000,1≤s≤n) — the number of cities, the number of roads and the index of the capital. Cities are indexed from 1 to n. The following m lines contain roads: road 𝑖 is given as a pair of cities u𝑖, v𝑖 (1≤u𝑖,v𝑖≤n, u𝑖≠v𝑖). For each pair of cities (u,v), there can be at most one road from u to v. Roads in opposite directions between a pair of cities are allowed (i.e. from u to v and from v to u). ## Output Print one integer — the minimum number of extra roads needed to make all the cities reachable from city s. If all the cities are already reachable from s, print 0. ## Example Input ``` 9 9 1 1 2 1 3 2 3 1 5 5 6 6 1 1 8 9 8 7 1 ``` Output ``` 3 ``` ## Solution 1 Firstly, let's store the possible paths for each city u[i]. ``` int N, M, S; cin >> N >> M >> S; --S; while(M--) { int U, V; cin >> U >> V; --U, --V; g[U].push_back(V); } ``` Secondly, we can perform a DFS function to mark all the reachable nodes from the given source. ``` void dfs(int from) { reachable[from] = 1; for(auto to : g[from]) { if(!reachable[to]) { dfs(to); } } } ``` Then, for each unreachable node, run a DFS function on it to count how far it can go. Here we only count those nodes that are not reachable and not visited. ``` vector> v; for(int i = 0; i < n; i++){ if(!reachable[i]) { cnt = 0; memset(vis, 0, sizeof(vis)); dfs2(i); v.push_back({cnt, i}); } } ``` After that we can sort the vector by ``cnt`` in non-increasing order. ``` sort(v.begin(), v.end()); reverse(v.begin(), v.end()); ``` We can greedily mark the unreachable nodes based on this order. If the node A has more to unreachable nodes to reach, then we just need to add one vertex to it to make them all connected, which is the minimum number of paths to be added. ``` int ans = 0; for(auto x : v) { if(!reachable[x.second]) { ans++; dfs(x.second); } } ``` ## Solution 2 We can also find all the Strongly Connected Components (SCC) and add a path to those with 0 in-degree. It will be able to reach the maximum number of nodes. First, let's read the input and prepare G. ``` while(M--) { int U, V; cin >> U >> V; --U, --V; G[U].push_back(V); } ``` Then we can use Tarjan's algorithm to find all the SCCs. ``` struct SCC : vector { vector> comps; vector S; SCC() {} SCC(vector>& G) : vector((int)G.size(), -1), S((int)G.size()) { for(int i = 0; i < (int)G.size(); i++) if(!S[i]) dfs(G, i); } int dfs(vector>& G, int v) { int low = S[v] = (int)S.size(); S.push_back(v); for(auto e : G[v]) if(at(e) < 0) low = min(low, S[e] ?: dfs(G, e)); if(low == S[v]) { comps.push_back({}); for(int i = S[v]; i < (int)S.size(); i++) { at(S[i]) = (int)comps.size() - 1; comps.back().push_back(S[i]); } S.resize(S[v]); } return low; } }; ``` We also need a ``vector`` to store the indegree for each SCC. ``` SCC scc(G); vector in((int)scc.comps.size()); ``` Iterate each node, if the ``i`` and ``j`` belong to different SCC, as they can be reachable each other, we increase the indegree of scc[j]. It is like making a SCC to a DAG. ``` for(int i = 0; i < N; i++) { for(auto j : G[i]) { if(scc[i] != scc[j]) { in[scc[j]]++; } } } ``` For those unreachable SCCs from the source SCC, their indegree must be 0. Hence, the answer is the number of those SCCs as we can add a path to each one to reach all the nodes within the SCC. ``` int ans = 0; for(int i = 0; i < (int)scc.comps.size(); i++) { ans += (in[i] == 0 && i != scc[S]); } cout << ans << endl; ```

Chinese Remainder Theorem

A linear congruence can be displayed as $$ ax \equiv b (\text{mod } m ) $$ By definition of congruence, $ ax \equiv b (\text{mod } m ) $ iff $ax - b$ is disible by $m$. According to Wikipedia, the earliest known statement of the Chinese Remainder Theorem is by the Chinese mathematician Sun-tzu in the Sun-tzu Suan-ching in the 3rd century AD. $$ 今有物不知其數，三三數之剩二，五五數之剩三，七七數之剩二，問物幾何？ $$ We can rewrite the above statement into below congruence equations. $$ x \equiv 2 (\text{mod } 3 ) $$ $$ x \equiv 3 (\text{mod } 5 ) $$ $$ x \equiv 2 (\text{mod } 7 ) $$ and the answer is $23$. In fact, this is the minimum possible solution. Starting from 23, you can get another possible answer by adding 105, i.e. $$ x = 23 + 105 * n $$ where $$ n \in {0, 1, 2, 3, \cdots} $$ Given a set of congruence equations, we are interested to find $a$ that produces the given remainders. $$ a \equiv a_1 (\text{mod } p_1 ) $$ $$ a \equiv a_2 (\text{mod } p_2 ) $$ $$ \cdots \\ $$ $$ a \equiv a_k (\text{mod } p_k ) $$ where every pair $p_i$ are pairwise coprime, $a_i$ are given constants.

## Problem: [Oversleeping](https://atcoder.jp/contests/abc193/tasks/abc193_e) In this problem, we are interested in finding the minimum non-negative integer t such that $$ X \le t \text{ mod } (2X + 2Y) \lt X + Y $$ $$ P \le t \text{ mod } (P + Q) \lt P + Q $$ We can solve this problem using Chinese Remainder Theorem. $$ t \equiv t_1 (\text{mod } 2X + 2Y ) $$ $$ t \equiv t_2 (\text{mod } P + Q ) $$ AtCoder has provided a crt library [here](https://github.com/atcoder/ac-library/blob/master/atcoder/math.hpp#L34), which makes the implementation relatively simple. ```cpp #include <atcoder/math> using namespace atcoder; const ll mx = numeric_limits<ll>::max(); void solve() { ll X, Y, P, Q; cin >> X >> Y >> P >> Q; ll ans = mx; for(ll t1 = X; t1 < X + Y; t1++) { for(ll t2 = P; t2 < P + Q; t2++) { auto [t, lcm] = crt( { t1, t2 }, // rem { 2 * X + 2 * Y, P + Q } // mod ); if(lcm == 0) { // no solution continue; } MIN(ans, t); } } if(ans == mx) OUT("infinity"); else OUT(ans); } ``` The full solution is available [here](https://github.com/wingkwong/competitive-programming/blob/master/atcoder/contests/abc193/E.cpp).

Solving Distinct Values Queries using Mo's Algorithm (Query SQRT Decomposition) with Hilbert Curve

## SQRT Decomposition Square Root Decomposition is an technique optimizating common operations in time complexity O(sqrt(N)). The idea of this technique is to decompose the array into small blocks of size [N / sqrt(N)] = [sqrt(N)]. ```cpp b[0] : x[0], x[1], ..., x[block_size - 1] b[1] : x[block_size], ..., x[2 * block_size - 1] ... b[block_size - 1] : x[(block_size - 1) * block_size], ..., x[N - 1] ``` and precompute the answer for all blocks. Example: precalculate the sum of elements in block k. ```cpp b[k] = min(N - 1, (k + 1) * block_size - 1) Σ i = k * block_size (x[i]) ``` To calculate the sum of elements in a range [l, r], we just need the sum of [l ... (k + 1) * s - 1], [p * s ... r], and b[i]. ```cpp r Σ i = l (x[i]) = (k + 1) * block_size - 1 Σ i = l (x[i]) + p - 1 Σ i = k + 1 (b[i]) + r Σ i = p * s (x[i]) ``` ## Problem - Distinct Values Queries You are given an array of n integers and q queries of the form: how many distinct values are there in a range [a,b]? Input: ``` 5 3 3 2 3 1 2 1 3 2 4 1 5 ``` Output: ``` 2 3 3 ``` ## Solution 1 - Using Mo's Algorithm We can answer the range queries offline in O((N + Q) * sqrt(N)) using the idea based on square root decomposition. We need to answer the queries in a special order - answer all queries with L value in block 0 first, then answer all queries with L value in block 1, and so on. If they are in the same block, we then sort it by their R value. ```cpp bool operator < (const mo &m) const { // different block - sort by block if(left / block_size != m.left / block_size) return left / block_size < m.left / block_size; // same block - sort by right value return right < m.right; } ``` Then we need two functions for updating the answer - ``add`` and ``remove`` and freq[x] to keep track the frequency of a number x. For add function, if freq[x] is 0, and if we add 1 to it then x is now a distinct value. Similarly, we do it in reverse in ``remove`` function. ```cpp void add(int x) { if(!freq[x]) ans++; freq[x]++; } void remove(int x) { freq[x]--; if(!freq[x]) ans--; } ``` For each query [L, R], we can combine the precomted answer of the blocks that lie in between [L, R] in the given array. For example, given an array a[0 .. N - 1], we are asked to find out the sum in a range [L, R]. We first calculate the sum in a range [0, N - 1], if a query is like [1, N - 1], we simply substract the first element a[0] from the sum. Therefore, in general we have four cases to consider. ### Case 1: cur_left < query_left We need to substract the sum from ``cur_left`` to ``query_left``. ``` [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] ^ cur_left ^ query_left ``` ### Case 2: cur_left > query_left We need to add the sum from ``cur_left`` to ``query_left``. ``` [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] ^ query_left ^ cur_left ``` ### Case 3: cur_right < query_right We need to add the sum from ``cur_right`` to ``query_right``. ``` [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] ^ cur_right ^ query_right ``` ### Case 4: cur_right > query_right We need to substract the sum from ``query_right`` to ``cur_right``. ``` [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20] ^query_right ^ cur_right ``` where - cur_left is the left pointer of the last query L - cur_right is the right pointer of the last query R - query_left is the left pointer of the query L - query_right is the right pointer of the query R ```cpp int cur_left = 0, cur_right = 0; REPN(i, q) { while(cur_left < Q[i].left) remove(x[cur_left++]); while(cur_left > Q[i].left) add(x[--cur_left]); while(cur_right < Q[i].right) add(x[++cur_right]); while(cur_right > Q[i].right) remove(x[cur_right--]); res[Q[i].idx] = ans; } ``` However, [this solution](https://cses.fi/paste/0670b45afd08a4401804dc/) only passes 3 out of 11 test cases. The verdict for the rest of them is RUNTIME ERROR.  The reason is that each element can go up to 10 ^ 9. We cannot use frequency array for that. We also cannot use ``unordered_map`` as it will time out due to high constant factor. Therefore, an alternative is to use coordinate compression to map the large values to smaller one in the range [1, N] as N at most can be 2 * 10 ^ 5. ```cpp int compressed = 1; map compress; REPN(i, n) { // read the input cin >> x[i]; // find the compressed value -> update x[i] if(compress.find(x[i]) != compress.end()) x[i] = compress[x[i]]; // not found -> compress it and update x[i] else compress[x[i]] = compressed, x[i] = compressed++; } ``` Now [the revised solution](https://cses.fi/paste/d8a09d857905de4a182310/) gives you 4 TIME LIMIT EXCEED verdicts.  Let's rethink of the time complexity. When we sort all the queries, it will take O(QlogQ). For add(x) and remove(x), let the block size be S, it takes O((N / S) * N) calls for all blocks. If S is around sqrt(N), it takes O((N + Q) * sqrt(N)) in total. The solution can be all passed by changing the block_size to 555 and even more. Therefore, we can conclude that S = sqrt(N) doesn't always give you the best runtime. Moreover, we should also use ``const`` to define the block size instead of computing it in runtime as division by constants is optimized by the compliers. Is there a way to achieve a faster sorting? Yes. We can do it in O(N * sqrt(Q)) with [Hilbert Curve](https://en.wikipedia.org/wiki/Hilbert_curve). ## Solution 2 - Using Mo's Algorithm with Hilbert Curve Hilbert Curve is a continuous fractal space-filling curve. Here's some examples. Hilbert Curve with order = 1 ``` |__| ``` Hilbert Curve with order = 2 ``` __ __ __| |__ | __ | |__| |__| ``` Hilbert Curve with order = 3 ``` __ __ __ __ |__| __| |__ |__| __ |__ __| __ | |__ __| |__ __| | |__ __ __ __ __| __| |__ __| |__ | __ | | __ | |__| |__| |__| |__| ``` For each order N > 1, it traces out a miniature order N - 1, connecting from the end of the mini curve in the lower-left to the start of the mini curve in the upper-left and from the upper-right down to the lower-right and flip the quadrant to make the connection shorter. The pattern continues like that for higher orders. If we have a point about the halfway in the frequency line in Snake Curve, the locations of the point can be different wildly as N increases. However, with Hilbert Curve, the given point moves around less and less as N increases. Therefore, we can revise our mo struct and the sorting compartor using Hilbert Order. ```cpp struct mo { int idx, left, right; int64_t ord; void set(int i, int l, int r) { idx = i, left = l, right = r, ord = hilbert_order(l, r, 21, 0); } }; inline bool operator<(const mo &a, const mo &b) { return a.ord < b.ord; } ``` Here's the implementation of Hilbert Order function. ```cpp inline int64_t hilbert_order(int x, int y, int pow, int rotate) { if (pow == 0) return 0; int hpow = 1 << (pow - 1); int seg = (x < hpow) ? ( (y < hpow) ? 0 : 3 ) : ( (y < hpow) ? 1 : 2 ); seg = (seg + rotate) & 3; const int rotate_delta[4] = {3, 0, 0, 1}; int nx = x & (x ^ hpow), ny = y & (y ^ hpow); int nrot = (rotate + rotate_delta[seg]) & 3; int64_t sub_square_size = int64_t(1) << (2 * pow - 2); int64_t ans = seg * sub_square_size, add = hilbert_order(nx, ny, pow - 1, nrot); ans += (seg == 1 || seg == 2) ? add : (sub_square_size - add - 1); return ans; } ``` We can see that [the final solution](https://cses.fi/paste/c16a9e1ae75872c6183147/) can pass all the test cases. With such technique, it works faster than the previous version, especially when N >> Q. Supposing we have a matrix with size 2 ^ k * 2 ^ k, if we divide it onto squares with size 2 ^ k - l * 2 ^ k - l, we need O(2 ^ k - l) time to travel between adjacent squares. We can process all queries in O(Q * 2 ^ k - l) = O(Q * N / sqrt(Q)) = O(N * sqrt(Q)).  At the end, it took me 74 attmepts to find out the most optimized solution.  ## Conclusion We can solve this problem using Mo's algorithm because it is an offline algorithm as we don't need to update the elements or the execution order of queries. We can utilize Hilbert Curve to speed up the program. It can also be solved using Segment Tree.

Finding Longest Palindrome in O(n) Using Manacher's Algorithm

You can practice the problem [here](https://cses.fi/problemset/task/1111/). Given a string, your task is to determine the longest palindromic substring of the string. For example, the longest palindrome in aybabtu is bab. A palindrome here is a string which reads the same backward as forward. We can use functions like ``reverse`` to check if the given string is a palindrome or not. ```cpp bool is_palindrome(string s) { string t = s; reverse(t.begin(), t.end()); return s == t; } ``` Or we can use two pointers. ```cpp bool is_palindrome(string s) { int l = 0, r = (int) s.size() - 1; while(l < r) { if(s[l] != s[r]) return false; else l++, r--; } return true; } ``` The first approach is brute force. ```cpp int n = (int) s.size(), start = 0, mx_len = 1; REP(i, n) { REP(j, i) { int ok = 1; REP(k, (j - i + 1) / 2) { if(s[i + k] != s[j - k]) ok = 0; } if(ok && (j - i + 1) > mx_len) { start = i; mx_len = j - i + 1; } } } OUT(s.substr(start, mx_len)); ``` However, the time complexity for this solution is O(n ^ 3) because we need three nested loops to find the longest palindromic substring. It only works when n is really small. The second approach is dynamic programming. The time complexity can be further reduced to O(n ^ 2). We use dp[i][j] to indicate if s[i] .. s[j] is a palindrome or not. Let's think about the transitions. 1. If i == j, that means s[i] == s[j], a single character is a palindrome. Example: a. 2. If i + 1 == j and s[i] == s[j], then s[i] .. s[j] is a palindrome. Example: aa. 3. If dp[i + 1][j - 1] and s[i] == s[j], then s[i] .. s[j] is a palindrome. Example: abba. As we can see, dp[i + 1][j] needs to be calculated before d[i][j]. Therefore, we iterate i from n - 1 to 0 and j from i + 1 to n. ```cpp int n = (int) s.size(); vvi dp(n, vi(n, 0)); string ans; int start = 0, len = 1; REP(i, n) dp[i][i] = 1; FORD(i, n - 1, 0) { FOR(j, i + 1, n) { if(s[i] == s[j]) { if(i + 1 == j || dp[i + 1][j - 1]) { dp[i][j] = 1; if(len < j - i + 1) { start = i; len = j - i + 1; } } } } } OUT(s.substr(start, len)); ``` With dynamic programming, the time cplexity and auxiliary space are O(n ^ 2). However, we can solve the problem in linear time using Manacher's algorithm. As a palindrome has a symmetric property at the center position, it could help us to reduce some unnecessary computations. If there is a palindrome of length N centered at position P, we can avoid the comparisions after position P as we already calculated longest palindromic substring at position before P. However, an even palidrome has two centers, which makes the calculate a little bit different than the one calculating for an odd palindrome. Here's the implementation in C++. ```cpp string manacher(string s) { int n = (int) s.size(); // d1[i]: the number of palindromes accordingly with odd lengths with centers in the position i. // d2[i]: the number of palindromes accordingly with even lengths with centers in the position i. vector d1(n), d2(n); int l1 = 0, r1 = -1, l2 = 0, r2 = -1, mx_len = 0, start = 0; for (int i = 0; i < n; i++) { // ---------------------- // calculate d1[i] // ---------------------- int k = (i > r1) ? 1 : min(d1[l1 + r1 - i], r1 - i + 1); while (0 <= i - k && i + k < n && s[i - k] == s[i + k]) k++; d1[i] = k--; if (i + k > r1) l1 = i - k, r1 = i + k; if(d1[i] * 2 > mx_len) start = i - k, mx_len = d1[i] * 2 - 1; // ---------------------- // calculate d2[i] // ---------------------- k = (i > r2) ? 0 : min(d2[l2 + r2 - i + 1], r2 - i + 1); while (0 <= i - k - 1 && i + k < n && s[i - k - 1] == s[i + k]) k++; d2[i] = k--; if (i + k > r2) l2 = i - k - 1, r2 = i + k; if(d2[i] * 2 > mx_len) start = i - k - 1, mx_len = d2[i] * 2; } // return the longest palindrome return s.substr(start, mx_len); } ``` If you want to count how many palindromic substrings in the given string, simply sum d1[i] and d2[i] where i = 0 .. n - 1. ```cpp int cnt = 0; for(int i = 0; i < n; i++) cnt += d1[i] + d2[i]; ``` This problem can also be solved using fast LCA in O(n) or String Hashing O(nlogn). These methods will not be discussed in this post. You can find the whole solution [here](https://github.com/wingkwong/competitive-programming/blob/09531f2fbfbf03393ba3e744cb77858134463e29/cses/string-algorithms/1111-longest-palindrome.cpp).

Finding all occurrences of a pattern in a given string in linear time using Z Algorithm

Given a string S and a pattern P, find all occurences of P in S. Supposing the length of S is m and that of P is n, we can find the answer using Z Algorithm in linear time. First, we need to construct a Z array where Z[i] is the length of longest common prefix between S and the suffix starting from S[i]. If Z[i] = 0, it means that S[0] != S[i] and the first element of Z is generally not defined. ``` vector<int> z_function(string s) { int n = (int) s.length(); vector<int> z(n); for (int i = 1, l = 0, r = 0; i < n; ++i) { if (i <= r) z[i] = min (r - i + 1, z[i - l]); while (i + z[i] < n && s[z[i]] == s[i + z[i]]) ++z[i]; if (i + z[i] - 1 > r) l = i, r = i + z[i] - 1; } return z; } ``` For this standard string match problem, we can use Z Algorithm to solve it in O(m + n) on the string P + (something won't be matched in both string) + S. If there is an indice i with Z[i] = n, then we find one occurence. Example: S = zabcabdabc P = abc m = 10 n = 3 Let K = P + (something won't be matched in both string) + S K = P + $ + S = abc$zabcabdabc Z would be {0, 0, 0, 0, 3, 0, 0, 2, 0, 0, 3, 0, 0} There are 2 indices ``i`` with Z[i] = n. Hence, there are 2 occurences of a pattern P in S. Here's the code implemented in C++. ``` void solve() { string p, s; cin >> p >> s; string k = p + "$" + s; vector z = z_function(k); int n = p.size(), m = k.size(), cnt = 0; REP(i, m) if(z[i] == n) cnt++; OUT(cnt); } ```

Finding All Pairs Shortest Path Using Floyd–Warshall Algorithm

Floyd–Warshall Algorithm is an algorithm for finding shortest paths in a weighted graph with positive or negative edge weights (but with no negative cycles). Let's say we have 4 nodes and given the 2D array ``edges`` containing three values - {from, to, weight} representing a bidirectional and weighted edges between nodes ``from`` and ``to``. Supposing we have a distance threshold ``k`` and we would like to find out the smallest number of nodes that are reachable through some path whose the distance is at most ``k``.  The pseudocode for Floyd–Warshall algorithm is ``` let dist be a |V| × |V| array of minimum distances initialized to ∞ (infinity) for each edge (u, v) do dist[u][v] ← w(u, v) // The weight of the edge (u, v) for each vertex v do dist[v][v] ← 0 for k from 1 to |V| for i from 1 to |V| for j from 1 to |V| if dist[i][j] > dist[i][k] + dist[k][j] dist[i][j] ← dist[i][k] + dist[k][j] end if ``` To implement in C++, we first define ``dist``. As dist[i][j] stores the distance between two points, we can initialised the maximum value of ``k``. Let's say the constraint is ``1 <= k <= 10^4``. We can initialise any values which is greater than 10^4. ``` vector<vector<int>> dist(n, vector<int>(n, 10005)); ``` Then we need to reset the left diagonal to zero ``` for(int i = 0; i < n; i++) dist[i][i] = 0; ``` so that we can build the dist[i][j]. Let's say the edge is bidirectional. ``` for(auto e : edges) dist[e[0]][e[1]] = dist[e[1]][e[0]] = e[2]; ``` Calculate the distance for each pair with Time Complexity: O(n ^ 3) ``` for(int k = 0; k < n; k++) { for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]); } } } ``` If dist[i][j] is storing a boolean value, we can use ``` dist[i][j] = dist[i][j] || dist[i][k] && dist[k][j]; ``` Once we got dist[i][j], we can easily find out the answer. ``` int ans = 0, mi = n; for(int i = 0; i < n; i++) { int cnt = 0; for(int j = 0; j < n; j++) { cnt += dist[i][j] <= k; } if(cnt <= mi) { mi = cnt; ans = i; } } ``` Here are some practice problems. - [743. Network Delay Time](https://leetcode.com/problems/network-delay-time/) - [1334. Find the City With the Smallest Number of Neighbors at a Threshold Distance](https://leetcode.com/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/) - [1462. Course Schedule IV](https://leetcode.com/problems/course-schedule-iv/)

Breadth First Search (BFS)

Breadth First Search (BFS) can be used to explore nodes in different layers, compute shortest paths and connected components of undirected graph. The run time complexity is in linear time O(|V| + |E|) where |V| is the number of vertices and |E| is the number of edges in the graph. Initally all nodes are not visited, starting from vertex 1 in a graph G, mark 1 as visited. Let ``q`` be a FIFO queue, initialized with 1. While ``q`` is not empty, remove the first node of ``q`` called ``v``. For each edge ``u``, if ``u`` is not visited, mark it visited and add it to ``q.`` ```cpp memset(vis, 0, sizeof(vis)); queue<int> q; q.push(1); vis[1] = 1; while(!q.empty()) { int v = q.front(); q.pop(); for(auto u : g[v]) { if(!vis[u]) { vis[u] = 1; q.push(u); } } } ``` If vis[x] is 1, we can say that G has a path from 1 to x. Applications: - Shortest Paths ``` dist[v] = 0 if v = s, else INT_MAX for edge (v, u) if v is not visited set dist[u] = dist[v] + 1 ``` The shortets path result is stored in ``dist[u]``. - Connected Components via BFS ``` for i = 1 to n if not visited bfs(g, i) ```