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; } ```

1622C - Set or Decrease

Give an integer array $a_1, a_2, ..., a_n$ and an integer $k$. If you can either make $a_i = a_i - 1$ or $a_i = a_j$, what is the minimum number of steps you need to make the sum of array $\sum_{i=1}^n a_i <= k$? Let's do it in a greedy way. Sort the array in an non-deceasing order. Apply operation one on $a_1$ $x$ times and apply operation two from $a_n$ $y$ times. The final array would look like $(a_1 - x), a_2, a_3, ..., a_{n - y}, (a_1 - x), (a_1 - x), ..., (a_1 - x)$. So we need to minimize the value of $x + y$ and we need $(a_1 - x) * (y + 1) + pref(n - y) - a_1 <= k$ where $pref$ is the prefix sum which can be precomputed beforehand. Rearrange it to get the minimum possible $x$ by iterating $y$ , $$ x = a_1 - \lfloor \frac{k - pref(n - y) + a_1}{y + 1} \rfloor $$ Solution: ```cpp long long safe_floor(long long x, long long y) { long long res = x / y; while (res * y > x) res--; return res; } void solve() { long long n, k; cin >> n >> k; vector<long long> a(n); long long sum = 0; for (int i = 0; i < n; i++) { cin >> a[i]; } sort(a.begin(), a.end()); vector<long long> pref(n + 1); for (int i = 0; i < n; i++) { pref[i + 1] = pref[i] + a[i]; } long long ans = 9e18; for (int y = 0; y < n; y++) { long long x = a[0] - safe_floor(k - pref[n - y] + a[0], y + 1); x = max(0LL, x); ans = min(ans, x + y); } cout << ans << endl; } ```

CF1625C - Road Optimization

Problem : [Codeforces Round #765 (Div. 2) - C. Road Optimization](https://codeforces.com/contest/1625/problem/C)  let $dp[i][j]$ be the minimum time to move up to sign $i$ and $j$ signs where $j$ is $[1 .. i - 1]$ are removed. We can iterate all the stops, try all $k$ on each possible position $p$ where $p$ is the previous stops $1 .. p - 1$. For example, if we need to move from stop $p$ to sign $i$ directly, then all signs between these two stops has to be removed. The total time is simply $(d[i] - d[p]) * a[p]$. And we need to add the previous part $dp[p][j - (i - p - 1)]$. If we remove all signs from stop $p$ to $i$, so basically it is $i - p - 1$. There is a constraint that we cannot remove no more than $k$ signs, so we check if previous $j$ signs that have been removed is greater than $0$ or not. If so, then we can update take the minimum of $dp[i][j]$ and $dp[p][j - (i - p - 1)]$. ```cpp void solve() { long long n, l, k; cin >> n >> l >> k; vector<long long> d, a; for (int i = 0; i < n; i++) cin >> d[i]; for (int i = 0; i < n; i++) cin >> a[i]; d.push_back(l); vector<vector<long long>> dp(n + 1, vector<long long>(k + 1, 1e18)); dp[0][0] = 0; for (int i = 1; i <= n; i++) { for (int j = 0; j <= k; j++) { for (int p = i - 1; p >= 0; p--) { int old_j = j - (i - p - 1); if (old_j >= 0) { dp[i][j] = min(dp[i][j], dp[p][old_j] + (d[i] - d[p]) * a[p]); } } } } cout << *min_element(dp.back().begin(), dp.back().end()) << endl; } ```

A problem at which I stared for an hour

Problem: [LC2127 - Maximum Employees to Be Invited to a Meeting](https://leetcode.com/problems/maximum-employees-to-be-invited-to-a-meeting/) A company is organizing a meeting and has a list of n employees, waiting to be invited. They have arranged for a large circular table, capable of seating any number of employees. The employees are numbered from 0 to n - 1. Each employee has a favorite person and they will attend the meeting only if they can sit next to their favorite person at the table. The favorite person of an employee is not themself. Given a 0-indexed integer array favorite, where favorite[i] denotes the favorite person of the ith employee, return the maximum number of employees that can be invited to the meeting.  Example: ##Input: favorite = [2,2,1,2] ##Output: 3 ## Explanation: The above figure shows how the company can invite employees 0, 1, and 2, and seat them at the round table. All employees cannot be invited because employee 2 cannot sit beside employees 0, 1, and 3, simultaneously. Note that the company can also invite employees 1, 2, and 3, and give them their desired seats. The maximum number of employees that can be invited to the meeting is 3. ## Solution If an employee A has a favourite person, let's say employee B, and vice versa. Then we can put them together. Then we can put an employee, let's say C, whose favourite person is A on the left hand side of A. Then put an employee, let's say D, whose favourite person is C next to C. If we do the same thing for employee B, then we can have two ways to extend. Therefore, we can first look for the interdependent nodes, in this case, A & B. ``` if (a[a[i]] == i) { // TODO: calculate the left chain and the right chain } ``` Starting from node A and node B, we perform dfs to calculate the maximum nodes of the left chain and the right chain. Then we could invite $left + right + 2$ people. ``` function<int(int)> dfs = [&](int u) { if (depth[u] != -1) return depth[u]; int res = 0; for (int x : inv[u]) res = max(res, dfs(x)); return depth[u] = res + 1; }; ``` However, it would fail for the input [1,2,0] because it will output $0$ instead of $3$. In this case, we need to take care of the cyclic dependency. We need to run another dfs function for each node and check if there is a cyclic dependency. If the visited node is the entry node, then we know there is a cycle here. Then we could invite them also. ``` function<tuple<int, int, int>(int)> dfs2 = [&](int u)->tuple<int, int, int> { if (depth[u] != -1) { return { u, depth[u], 0 }; } depth[u] = 0; auto [entry, d, isCyclic] = dfs2(a[u]); if (isCyclic) { return { entry, d, 1 }; } depth[u] = d + 1; return { entry, depth[u], u == entry }; }; ``` The final answer is simple the maximum number of the result of case 1 and case 2. Here's the full solution. ``` class Solution { public: int maximumInvitations(vector<int>& a) { int n = a.size(); vector<int> depth(n, -1); vector<vector<int>> inv(n); for (int i = 0 ; i < n; i++) inv[a[i]].push_back(i); // check interdependent nodes + longest left & right chain function<int(int)> dfs = [&](int u) { if (depth[u] != -1) return depth[u]; int res = 0; for (int x : inv[u]) res = max(res, dfs(x)); return depth[u] = res + 1; }; int mx1 = 0, mx2 = 0; for (int i = 0; i < n; i++) { if (depth[i] != -1) continue; if (a[a[i]] == i) { depth[i] = depth[a[i]] = 0; int left = 0, right = 0; for (int x : inv[i]) if (x != a[i]) left = max(left, dfs(x)); for (int x : inv[a[i]]) if (x != a[i]) right = max(right, dfs(x)); mx1 += left + right + 2; } } // check cyclic dependency function<tuple<int, int, int>(int)> dfs2 = [&](int u)->tuple<int, int, int> { if (depth[u] != -1) { return { u, depth[u], 0 }; } depth[u] = 0; auto [entry, d, isCyclic] = dfs2(a[u]); if (isCyclic) { return { entry, d, 1 }; } depth[u] = d + 1; return { entry, depth[u], u == entry }; }; for (int i = 0; i < n; i++) { if (depth[i] != -1) continue; auto [entry, d, isCyclic] = dfs2(i); if (isCyclic) { mx2 = max(mx2, d); } } return max(mx1, mx2); } }; ```

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; ```