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

Lagrange Interpolation

There are some well-known formulas $$ \sum_{i=1}^n i = 1 + 2 + \dots + n = \frac{n * (n + 1)}{2} $$ $$ \sum_{i=1}^n i^2 = 1^2 + 2^2 + \dots + n^2 = \frac{n * (n + 1) * (2n + 1)}{6} $$ $$ \sum_{i=1}^n i^3 = 1^3 + 2^3 + \dots + n^3 = (\frac{n * (n + 1)}{2}) ^ 2 $$ Then what is the value of the following sum of the k-th power? $$ \sum_{i=1}^n i^k = 1^k + 2^k + \dots + n^k \mod 10^9 + 7 $$ given $1 <= n <= 10^9$ and $0 <= k <= 10^6$ The target sum will be a degree $ (k + 1) $ polynomial and we can interpolate the answer with $ (k + 2) $ data points, i.e. $degree(f) + 1$ points. In order to find the data points, we need to calculate $f(0) = 0$, $f(x) = f(x - 1) + x ^ k$. If there is less than $k + 2$ data points, we can calculate the answer directly. ``` if (x <= k + 1) { int s = 0; for (int i = 1; i <= x; i++) { s = (s + qpow(i, k)) % mod; } return s; } ``` Otherwise, let's say $f(x_1) = y_1, f(x_2) = y_2, ..., f(x_n) = y_n$ and $f$ is the unique $(n - 1)$ degree polynomial and we are interested in $f(x) = \sum_{i=1}^n f_i(x)$ where $f_i(x) = y_i * \prod_{j=1, j!=i}^n \frac{x - x_j}{x_i - x_j} $. Therefore, we have our Lagrange interpolation as $ f(x) = \sum_{i=1}^n y^i \prod_{j=1, j!=i}^n \frac{x - x_j}{x_i - x_j} $. However, we need $O(n^2)$ to calculate $f(x)$. Let's substitute $x_i = i$ and $y_i = f(i)$ and we got $ f(x) = \sum_{i=1}^n f(i) \frac{\prod_{j=1, j!=i}^n x - j}{\prod_{j=1, j!=i}^n i - j} $. What can we do for numerator and denonminator here? For numerator, we can per-calculate the prefix and suffix product of $x$, for each $i$, we can calculate the nubmerator in $O(1)$. $$ \prod_{j=1, j!=i}^n x - x_j = [(x - 1)(x - 2)...(x-(i-1))] * [(x - (i + 1))*(x - (i + 2))...(x - n)] $$ ``` vector pre(k + 2), suf(k + 2); pre[0] = x; suf[k + 1] = x - (k + 1); for (int i = 1; i <= k; i++) pre[i] = pre[i - 1] * (x - i) % mod; for (int i = k; i >= 1; i--) suf[i] = suf[i + 1] * (x - i) % mod; ``` For denominator, we can precompute the factorials using their inverse in $O(1)$ also. $$ \prod_{j=1, j!=i}^n i - j = [(i - 1)(i - 2)(i - 3)...(i - (i - 1))] * [i - (i + 1)(i - (i + 2)...(i - n)] = (-1)^{n - i} (n - i)!(i - 1)! $$ ``` int qpow(int base, int exp) { int res = 1; while (exp) { if (exp & 1) res = (res * base) % mod; base = (base * base) % mod; exp >>= 1; } return res; } unordered_map<int, int> rv_m; int rv(int x) { if (rv_m.count(x)) { return rv_m[x]; } return rv_m[x] = qpow(x, mod - 2); } vector inv(k + 2); inv[0] = 1; for (int i = 1; i <= k + 1; i++) inv[i] = inv[i - 1] * rv(i) % mod; ``` Overall, we can calculate $f(x)$ in $O(n)$. Complete Code: ``` #include <bits/stdc++.h> using namespace std; #define int long long const int mod = 1e9 + 7; int qpow(int base, int exp) { int res = 1; while (exp) { if (exp & 1) res = (res * base) % mod; base = (base * base) % mod; exp >>= 1; } return res; } unordered_map<int, int> rv_m; int rv(int x) { if (rv_m.count(x)) { return rv_m[x]; } return rv_m[x] = qpow(x, mod - 2); } int lagrange_interpolate(int x, int k, bool bf = false) { if (k == 0) return x; // find 1 ^ k + 2 ^ k + ... + x ^ k // (k + 1) degree polynomial -> (k + 2) points if (x <= k + 1 || bf) { int s = 0; for (int i = 1; i <= x; i++) { s = (s + qpow(i, k)) % mod; } return s; } vector<int> pre(k + 2), suf(k + 2), inv(k + 2); inv[0] = 1, pre[0] = x; suf[k + 1] = x - (k + 1); for (int i = 1; i <= k; i++) pre[i] = pre[i - 1] * (x - i) % mod; for (int i = k; i >= 1; i--) suf[i] = suf[i + 1] * (x - i) % mod; for (int i = 1; i <= k + 1; i++) inv[i] = inv[i - 1] * rv(i) % mod; int ans = 0; int yi = 0; // 0 ^ k + ~ i ^ k int num, denom; for (int i = 0; i <= k + 1; i++) { yi = (yi + qpow(i, k)) % mod; // interpolate point: (i, yi) if (i == 0) num = suf[1]; else if (i == k + 1) num = pre[k]; else num = pre[i - 1] * suf[i + 1] % mod; // numerator denom = inv[i] * inv[k + 1 - i] % mod; // denominator if ((i + k) & 1) ans += (yi * num % mod) * denom % mod; else ans -= (yi * num % mod) * denom % mod; ans = (ans % mod + mod) % mod; } return ans; } void solve() { int n, k; cin >> n >> k; cout << lagrange_interpolate(n, k) << endl; } int32_t main() { ios_base::sync_with_stdio(false), cin.tie(nullptr); // int T; cin >> T; // while(T--) solve(); solve(); return 0; } ```

LeetCode - Weekly Contest 273 Editorial

## [Q1: A Number After a Double Reversal](https://leetcode.com/problems/a-number-after-a-double-reversal/) If you just do what it says, here's the code. ```cpp class Solution { public: bool isSameAfterReversals(int num) { if (num == 0) return 1; string s = to_string(num); int n = s.size(), j = 0; while (s[n - 1 - j] == '0') j++; string t = s.substr(0, n - j); return s == t; } }; ``` However, a better way to solve this is to check if there is any trailing zero. No matter how many zeros at the end, after removing them all, it won't be same if you reverse it. The only exceptional case is $num = 0$. ``` class Solution { public: bool isSameAfterReversals(int num) { return num == 0 || num % 10; } }; ``` ## [Q2: Execution of All Suffix Instructions Staying in a Grid](https://leetcode.com/problems/execution-of-all-suffix-instructions-staying-in-a-grid/) We can just simulate the whole process. For each $i-th$ instruction, we have max $ s.size() - i $ steps assuming $ i $ starts from $ 0 $. We keep updating the position $(x, y)$ and check if it is out of bound. If not, keep inceasing $cnt$ by 1. If there is no further move we can make, we can break the loop and push the result $cnt$ to $ans$. ``` class Solution { public: vector executeInstructions(int n, vector& startPos, string s) { int m = s.size(); vector ans; for (int i = 0; i < m; i++) { int x = startPos[0]; int y = startPos[1]; int cnt = 0; for (int j = i; j < m; j++) { if (s[j] == 'L') y--; if (s[j] == 'R') y++; if (s[j] == 'U') x--; if (s[j] == 'D') x++; if (0 <= x && x < n && 0 <= y && y < n) cnt++; else break; } ans.push_back(cnt); } return ans; } }; ``` However, the above brute-force solution gives $O(m^2)$ complexity. It works because $m$ is just limited to $1000$. There's a $O(m)$ solution. ``` class Solution { public: vector executeInstructions(int n, vector& startPos, string s) { int m = s.size(), h = m + n, v = m + n; vector hor((m + n) * 2, m), ver((m + n) * 2, m), ans(m); for (int i = m - 1; i >= 0; i--) { hor[h] = ver[v] = i; if (s[i] == 'L') h++; if (s[i] == 'R') h--; if (s[i] == 'U') v++; if (s[i] == 'D') v--; ans[i] = min({ m, hor[h - startPos[1] - 1], hor[h - startPos[1] + n], ver[v - startPos[0] - 1], ver[v + startPos[0] * -1 + n] }) - i; } return ans; } }; ``` ## [Intervals Between Identical Elements](intervals-between-identical-elements) First we need to know the indices for each number. We can easily construct it using ``unordered_map<int, vector<int>>``. Then it comes to the math part. Our goal is to calculate the absolute difference for numbers smaller than and greater than or equal to $k$ in linear time. Let's say the list is [1, 3, 5, 7, 9] and let $k$ be $7$. The absolute difference for numbers smaller than or equal to $7$ is $(7 - 1) + (7 - 3) + (7 - 5) - (7 - 7)$. We can arrange it to $ 7 * 4 - (1 - 3 - 5 - 7)$ which is same as $k * (i + 1) - pre[i + 1]$. Similarly, let $k$ be $3$ and we want to find out the absolute difference for numbers greater than or equal to $3$. $(3 - 3) + (3 - 5) + (3 - 7) + (3 - 9)$. We can arrange it to $3 * 4 - (3 + 5 + 7 + 9)$, which is same as $(pre[n] - pre[i]) - k * (n - i)$. Therefore, $ans[k]$ would be the sum of the left part and the right part. Prefix sum can be calculated as ``` for (int i = 0; i < n; i++) { pre[i + 1] = pre[i] + v[i]; } ``` ``` class Solution { public: vector<long long> getDistances(vector& arr) { unordered_map<int, vector<int>> m; vector<long long> ans(arr.size()); int n = arr.size(); for (int i = 0; i < n; i++) { m[arr[i]].push_back(i); } for (auto x : m) { vector v = x.second; int n = v.size(); vector<long long> pre(n + 1); for (int i = 0; i < n; i++) { pre[i + 1] = pre[i] + v[i]; } for (int i = 0; i < n; i++) { long long k = v[i]; ans[k] = (k * (i + 1) - pre[i + 1]) + (pre[n] - pre[i] - k * (n - i)); } } return ans; } }; ``` ## [Recover the Original Array](https://leetcode.com/problems/recover-the-original-array/) In short, we just need to try all possible $k$. If we sort $nums$, the smallest elelment must be in the lower array. It is easy to see $k$ can be $(nums[i] - nums[0]) / 2$. We try each $k$ to see if we can match all the pairs. If the size of lower array is same as that of higher array, then the ans would be $ans[j] = (l[j] + r[j]) / 2$. ``` class Solution { public: vector recoverArray(vector& nums) { int n = nums.size(); sort(nums.begin(), nums.end()); for (int i = 0; i < nums.size(); i++) { unordered_map<int, int> m; int d = nums[i] - nums.front(); if (d == 0 || d & 1) { continue; } vector l, r; for (int j = 0; j < n; j++) { if (m.count(nums[j] - d)) { r.push_back(nums[j]); if (--m[nums[j] - d] == 0) { m.erase(nums[j] - d); } } else { l.push_back(nums[j]); m[nums[j]]++; } } if (l.size() == r.size()) { vector ans; for (int j = 0; j < n / 2; j++) { ans.push_back((l[j] + r[j]) / 2); } return ans; } } return {}; } }; ```

The Easiest LeetCode Contest in 2021

This LeetCode contest is sponsored by Amazon Pay. Check out [Weekly Contest 272](https://leetcode.com/contest/weekly-contest-272) for the questions. ## Q1 - 2108. Find First Palindromic String in the Array Given an array of strings words, return the first palindromic string in the array. If there is no such string, return an empty string "". A string is palindromic if it reads the same forward and backward. ### Example 1: Input: words = ["abc","car","ada","racecar","cool"] Output: "ada" Explanation: The first string that is palindromic is "ada". Note that "racecar" is also palindromic, but it is not the first. ### Example 2: Input: words = ["notapalindrome","racecar"] Output: "racecar" Explanation: The first and only string that is palindromic is "racecar". ### Example 3: Input: words = ["def","ghi"] Output: "" Explanation: There are no palindromic strings, so the empty string is returned. ## Solution There are several ways to check if $s$ is a palindrome. ### Long and Efficient ```cpp bool isPalindrome(const string& s) { for (int i = 0; i < s.size() / 2; i++) { if (s[i] != s[s.size() - i - 1]) return false; } return true; } ``` ### Shorter but not efficient ```cpp bool isPalindrome(const string& s) { string t = s; reverse(t.begin(), t.end()); return s == t; } ``` ### Shortest but not efficient ```cpp bool isPalindrome(const string& s) { return s == string(s.rbegin(), s.rend()); } ``` ### Shortest but efficient ```cpp bool isPalindrome(const string &s) { return equal(s.begin(), s.begin() + s.size() / 2, s.rbegin()); } ``` We just need to iterate each string and check if the target $s$ is a palindrome, return the string if so. ``` class Solution { public: bool isPalindrome(const string& s) { return equal(s.begin(), s.begin() + s.size() / 2, s.rbegin()); } string firstPalindrome(vector& words) { for (auto s : words) { if (isPalindrome(s)) { return s; } } return ""; } }; ``` ## Q2 - 2109. Adding Spaces to a String You are given a 0-indexed string s and a 0-indexed integer array spaces that describes the indices in the original string where spaces will be added. Each space should be inserted before the character at the given index. For example, given s = "EnjoyYourCoffee" and spaces = [5, 9], we place spaces before 'Y' and 'C', which are at indices 5 and 9 respectively. Thus, we obtain "Enjoy Your Coffee". Return the modified string after the spaces have been added. ### Example 1: Input: s = "LeetcodeHelpsMeLearn", spaces = [8,13,15] Output: "Leetcode Helps Me Learn" Explanation: The indices 8, 13, and 15 correspond to the underlined characters in "LeetcodeHelpsMeLearn". We then place spaces before those characters. ### Example 2: Input: s = "icodeinpython", spaces = [1,5,7,9] Output: "i code in py thon" Explanation: The indices 1, 5, 7, and 9 correspond to the underlined characters in "icodeinpython". We then place spaces before those characters. ### Example 3: Input: s = "spacing", spaces = [0,1,2,3,4,5,6] Output: " s p a c i n g" Explanation: We are also able to place spaces before the first character of the string. ## Solution Two-pointer. i-th pointer is for string $s$ and j-th pointer is for spaces vector. Iterate string $s$, if $i$ matches $spaces[j]$, then add a space and increase $j$ by 1. ``` class Solution { public: string addSpaces(string s, vector& spaces) { string ans; int j = 0, m = spaces.size(); for (int i = 0; i < s.size(); i++) { if (j < m && i == spaces[j]) ans += " ", j++; ans += s[i]; } return ans; } }; ``` ## Q3 - 2110. Number of Smooth Descent Periods of a Stock You are given an integer array prices representing the daily price history of a stock, where prices[i] is the stock price on the ith day. A smooth descent period of a stock consists of one or more contiguous days such that the price on each day is lower than the price on the preceding day by exactly 1. The first day of the period is exempted from this rule. Return the number of smooth descent periods. ### Example 1: Input: prices = [3,2,1,4] Output: 7 Explanation: There are 7 smooth descent periods: [3], [2], [1], [4], [3,2], [2,1], and [3,2,1] Note that a period with one day is a smooth descent period by the definition. ### Example 2: Input: prices = [8,6,7,7] Output: 4 Explanation: There are 4 smooth descent periods: [8], [6], [7], and [7] Note that [8,6] is not a smooth descent period as 8 - 6 ≠ 1. ### Example 3: Input: prices = [1] Output: 1 Explanation: There is 1 smooth descent period: [1] ## Solution The first observation is each number is a smooth descent period. The final answer is at least $ n $ which is the size of the given vector. Therefore, the initial value for $dp[i]$ is $1$. The second observation is that we can add $dp[i - 1]$ to $dp[i]$ if $prices[i - 1] - prices[i] = 1$ starting from $i = 1$. ``` class Solution { public: long long getDescentPeriods(vector& prices) { int n = prices.size(); long long ans = 0; vector dp(n, 1); for (int i = 0; i < n; i++) { if (i > 0 && prices[i - 1] - prices[i] == 1) { dp[i] += dp[i - 1]; } ans += dp[i]; } return ans; } }; ``` ## Q4 - 2111. Minimum Operations to Make the Array K-Increasing You are given a 0-indexed array arr consisting of n positive integers, and a positive integer k. The array arr is called K-increasing if arr[i-k] <= arr[i] holds for every index i, where k <= i <= n-1. For example, arr = [4, 1, 5, 2, 6, 2] is K-increasing for k = 2 because: arr[0] <= arr[2] (4 <= 5) arr[1] <= arr[3] (1 <= 2) arr[2] <= arr[4] (5 <= 6) arr[3] <= arr[5] (2 <= 2) However, the same arr is not K-increasing for k = 1 (because arr[0] > arr[1]) or k = 3 (because arr[0] > arr[3]). In one operation, you can choose an index i and change arr[i] into any positive integer. Return the minimum number of operations required to make the array K-increasing for the given k. ### Example 1: Input: arr = [5,4,3,2,1], k = 1 Output: 4 Explanation: For k = 1, the resultant array has to be non-decreasing. Some of the K-increasing arrays that can be formed are [5,6,7,8,9], [1,1,1,1,1], [2,2,3,4,4]. All of them require 4 operations. It is suboptimal to change the array to, for example, [6,7,8,9,10] because it would take 5 operations. It can be shown that we cannot make the array K-increasing in less than 4 operations. ### Example 2: Input: arr = [4,1,5,2,6,2], k = 2 Output: 0 Explanation: This is the same example as the one in the problem description. Here, for every index i where 2 <= i <= 5, arr[i-2] <= arr[i]. Since the given array is already K-increasing, we do not need to perform any operations. ### Example 3: Input: arr = [4,1,5,2,6,2], k = 3 Output: 2 Explanation: Indices 3 and 5 are the only ones not satisfying arr[i-3] <= arr[i] for 3 <= i <= 5. One of the ways we can make the array K-increasing is by changing arr[3] to 4 and arr[5] to 5. The array will now be [4,1,5,4,6,5]. Note that there can be other ways to make the array K-increasing, but none of them require less than 2 operations. ## Solution We can break input vector into $k$ groups $a_i, a_{i + k}, a_{i + 2 * k}, ...$ for each $ i < k$. Calculate the LIS (Longest Increasing Subsequence) on each group and compare the length with the target size. We need to perform $a.size() - lengthOfLIS(a)$ operations to make it K-increasing. ``` class Solution { public: int lengthOfLIS(vector& nums) { int n = (int) nums.size(); vector lis; for(int i = 0; i < n; i++) { auto it = upper_bound(lis.begin(), lis.end(), nums[i]); if(it == lis.end()) lis.push_back(nums[i]); else *it = nums[i]; } return (int) lis.size(); } int kIncreasing(vector& arr, int k) { int ans = 0, n = arr.size(); for (int i = 0; i < k; i++) { vector a; for (int j = i; j < n; j += k) { a.push_back(arr[j]); } ans += a.size() - lengthOfLIS(a); } return ans; } }; ```

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

LeetCode - Paint House

These problems are basically same except the constraints. In the first question, ``k`` is always 3. If we solve the second problem, then we can also solve the first problem. Therefore, let's think about the case when ``k`` is not fixed. ## Paint House (Medium) [Paint House (Medium)](https://leetcode.com/problems/paint-house/) There is a row of n houses, where each house can be painted one of three colors: red, blue, or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color. The cost of painting each house with a certain color is represented by an n x 3 cost matrix costs. For example, costs[0][0] is the cost of painting house 0 with the color red; costs[1][2] is the cost of painting house 1 with color green, and so on... Return the minimum cost to paint all houses. ## Paint House II (Hard) [Paint House II (Hard)](https://leetcode.com/problems/paint-hous-ii/) There are a row of n houses, each house can be painted with one of the k colors. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color. The cost of painting each house with a certain color is represented by an n x k cost matrix costs. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on... Return the minimum cost to paint all houses. ## Solution 1 : Dynamic Programming Supposing we got 5 houses and 6 colors (red, green, blue, yellow, purple, orange). Starting from the second, we can only choose the different color from the previous row. For example, if costs[1][0] is selected, then the only possible color to be chosen from the previous row must be from column 1 to column 5 and pick the minimum costs[0][j] where $j \neq 0$ in this example.  Therefore, we iterate each color in the current row and compare it from the previous row to find the minimum cost. The following solution gives $O(n * k ^ 2)$ time complexity and $O(k)$ space complexity. ```python def minCostII(self, costs: List[List[int]]) -> int: n = len(costs) k = len(costs[0]) prev_row = costs[0] for house in range(1, n): cur_row = [0] * k for cur_color in range(k): prev_best = math.inf for prev_color in range(k): if cur_color == prev_color: continue prev_best = min(prev_best, prev_row[prev_color]) cur_row[cur_color] += prev_best + costs[house][cur_color] prev_row = cur_row return min(prev_row) ``` which can be written in a cleaner way. ```python def minCostII(self, costs: List[List[int]]) -> int: k = len(costs[0]) prev_row = [0] * k for cur_row in costs: prev_row = [cur_row[i] + min(prev_row[:i] + prev_row[i + 1:]) for i in range(k)] return min(prev_row) ``` ## Solution 2: Markov Chain If ``n`` and ``k`` are set to $500$, then Solution 1 will exceed time limit. Here's another solution using the idea of Markov Chain. Given that ``k`` states (colors) and ``n`` stages, we can update the matrix to find out the optimal value for each state at the current stage. The idea is to find out the first and the second minimum cost for each stage. For the next stage, we can update each cost by adding either the first minimum cost or the second one. The reason we need two minimum cost is that we cannot paint the same color. If the index of the first minimum cost from the previous stage is ``i`` and we have to use the second minimum cost for the current stage, and vice versa. ```python class Solution: def solve(self, matrix): n = len(matrix) k = len(matrix[0]) for house in range(1, n): first_mi_color = second_mi_color = None # find first & second min color for color in range(k): cost = matrix[house - 1][color] if first_mi_color is None or cost < matrix[house - 1][first_mi_color]: second_mi_color = first_mi_color first_mi_color = color elif second_mi_color is None or cost < matrix[house - 1][second_mi_color]: second_mi_color = color # update matrix for the current row for color in range(k): if color == first_mi_color: matrix[house][color] += matrix[house - 1][second_mi_color] else: matrix[house][color] += matrix[house - 1][first_mi_color] return min(matrix[-1]) ``` Here's the shorter version. ```python class Solution: def minCostII(self, costs: List[List[int]]) -> int: n, k = len(costs), len(costs[0]) for house in range(1, n): first_mi_cost = min(costs[house - 1]) idx = costs[house - 1].index(first_mi_cost) second_mi_cost = min(costs[house - 1][:idx] + costs[house - 1][idx + 1:]) for color in range(k): if color == idx: costs[house][color] += second_mi_cost else: costs[house][color] += first_mi_cost return min(costs[-1]) ```

Codeforces - Deltix Round, Summer 2021 - 1556D. Take a Guess

[https://codeforces.com/contest/1556/problem/D](https://codeforces.com/contest/1556/problem/D) ## Problem This is an interactive task William has a certain sequence of integers $a_1, a_2, ..., a_n $ in his mind, but due to security concerns, he does not want to reveal it to you completely. William is ready to respond to no more than 2⋅𝑛 of the following questions: What is the result of a bitwise AND of two items with indices 𝑖 and 𝑗 (𝑖≠𝑗) What is the result of a bitwise OR of two items with indices 𝑖 and 𝑗 (𝑖≠𝑗) You can ask William these questions and you need to find the 𝑘-th smallest number of the sequence. Formally the 𝑘-th smallest number is equal to the number at the 𝑘-th place in a 1-indexed array sorted in non-decreasing order. For example in array [5,3,3,10,1] 4th smallest number is equal to 5, and 2nd and 3rd are 3. ### Input It is guaranteed that for each element in a sequence the condition 0≤𝑎𝑖≤109 is satisfied. ### Interaction In the first line you will be given two integers 𝑛 and 𝑘 (3≤𝑛≤104,1≤𝑘≤𝑛), which are the number of items in the sequence 𝑎 and the number 𝑘. After that, you can ask no more than 2⋅𝑛 questions (not including the "finish" operation). Each line of your output may be of one of the following types: "or i j" (1≤𝑖,𝑗≤𝑛,𝑖≠𝑗), where 𝑖 and 𝑗 are indices of items for which you want to calculate the bitwise OR. "and i j" (1≤𝑖,𝑗≤𝑛,𝑖≠𝑗), where 𝑖 and 𝑗 are indices of items for which you want to calculate the bitwise AND. "finish res", where 𝑟𝑒𝑠 is the 𝑘th smallest number in the sequence. After outputting this line the program execution must conclude. In response to the first two types of queries, you will get an integer 𝑥, the result of the operation for the numbers you have selected. After outputting a line do not forget to output a new line character and flush the output buffer. Otherwise you will get the "Idleness limit exceeded". To flush the buffer use: fflush(stdout) in C++ System.out.flush() in Java stdout.flush() in Python flush(output) in Pascal for other languages refer to documentation If you perform an incorrect query the response will be −1. After receiving response −1 you must immediately halt your program in order to receive an "Incorrect answer" verdict. ## Explanation In short, we can retrieve the first 3 numbers first by asking 3 OR questions and 3 AND questions using the fact that $$ a + b = (a \lor b) + (a \land b) $$ After that we can fix the first number to find the rest of them. Once we have all the numbers, we sort the array and find the $k-th$ one. The first 3 numbers can be obtained by the following approach. First we - ask ``or 1 0`` and ``and 1 0`` to get $ a_{01} $ - ask ``or 1 2`` and ``and 1 2`` to get $ a_{12} $ - ask ``or 0 2`` and ``and 0 2`` to get $ a_{02} $ Now we know that $$ a_{01} = a_0 + a_1 $$ $$ a_{12} = a_1 + a_2 $$ $$ a_{02} = a_0 + a_2 $$ We can use these 3 numbers to obtain the first 3 numbers in the array. $$ a_0 = \frac{(a_{01} + a_{02} - a_{12})}{2} $$ $$ a_1 = \frac{(a_{01} + a_{12} - a_{02})}{2} $$ $$ a_2 = \frac{(a_{02} + a_{12} - a_{01})}{2} $$ Starting from $ i = 3 $, we can fix the first number to find out $a_i$. - ask ``or 0 i`` and ``and 0 i`` to get $ a_{0i} $ so that we will have $$ a_i = a_{0i} - a_0 $$ ## Solution ``` long long OR(int i, int j) { cout << "or " << i + 1 << " " << j + 1 << endl; long long x; cin >> x; return x; } long long AND(int i, int j) { cout << "and " << i + 1 << " " << j + 1 << endl; long long x; cin >> x; return x; } void solve() { long long n, k; cin >> n >> k; vector<long long> a(n); long long a_01 = OR(0, 1) + AND(0, 1); long long a_12 = OR(1, 2) + AND(1, 2); long long a_02 = OR(0, 2) + AND(0, 2); a[0] = (a_01 + a_02 - a_12) / 2; a[1] = (a_01 + a_12 - a_02) / 2; a[2] = (a_02 + a_12 - a_01) / 2; for(int i = 3; i < n; i++) { long long a_0i = OR(0, i) + AND(0, i); a[i] = a_0i - a[0]; } sort(a.begin(), a.end()); cout << "finish " << a[k - 1] << endl; } ```

BinarySearch - Set Bits

[https://binarysearch.com/problems/Set-Bits](https://binarysearch.com/problems/Set-Bits) ## Problem Given an integer n, return the total number of set bits in all integers between 1 and n inclusive. Constraints $ n ≤ 2 ^ {27} $ ## Solution The i-th least significant bit can be calculate as $$ (\frac{n}{2 ^ i}) * 2 ^{i - 1} + n \bmod 2 ^ {i} - (2 ^ {i - 1} - 1) $$ if and only if $$ n \bmod ( 2 ^ {i} ) >= (2 ^ {i - 1} - 1) $$ ``` int solve(int n) { int two = 2, ans = 0; int tmp = n; while (tmp) { ans += (n / two) * (two >> 1); if ((n & (two - 1)) > (two >> 1) - 1) ans += (n & (two - 1)) - (two >> 1) + 1; two <<= 1, tmp >>= 1; } return ans; } ```

BinarySearch - Increasing Subsequences of Size K

[https://binarysearch.com/problems/Increasing-Subsequences-of-Size-K](https://binarysearch.com/problems/Increasing-Subsequences-of-Size-K) ## Problem Given a list of integers nums and an integer k, return the number of subsequences of size k that are strictly increasing. Mod the result by 10 ** 9 + 7. Constraints 0 ≤ n ≤ 1,000 where n is the length of nums. 1 ≤ k ≤ 10 ## Solution Use Dynamic Programming. Define dp[i][j] to store the count of increasing subsequences of size i ending with element nums[j]. $dp[i][j] = 1$, where $i = 1$ and $1 <= j <= n $ $dp[i][j] = dp[i][j] + dp[i - 1][j]$, where $1 < i <= k$, $i <= j <= n$ and $nums[m] < nums[j]$ for $(i - 1) <= m < j$. Time Complexity: $O(k * n ^ 2)$ Space Complexity: $O(k * n)$ ``` int solve(vector& nums, int k) { int n = (int)nums.size(), dp[k][n], ans = 0, mod = 1e9 + 7; memset(dp, 0, sizeof(dp)); for (int i = 0; i < n; i++) dp[0][i] = 1; for (int l = 1; l < k; l++) { for (int i = l; i < n; i++) { dp[l][i] = 0; for (int j = l - 1; j < i; j++) { if (nums[j] < nums[i]) { dp[l][i] = (dp[l][i] + dp[l - 1][j]) % mod; } } } } for (int i = k - 1; i < n; i++) { ans = (ans + dp[k - 1][i]) % mod; } return ans; } ```

BinarySearch - Longest Increasing Path

[https://binarysearch.com/problems/Longest-Increasing-Path](https://binarysearch.com/problems/Longest-Increasing-Path) ## Problem Given a two-dimensional integer matrix, find the length of the longest strictly increasing path. You can move up, down, left, or right. Constraints n, m ≤ 500 where n and m are the number of rows and columns in matrix ## Solution DFS Approach. dp[i][j] means the length of longest increasing path starting from (i,j). Traverse four directions iff the next cell is in the bound and the value is greater than the current one. Calculate it recursively and store it back to dp[i][j]. If dp[i][j] has been calculated, return the cached result directly. ``` int m, n; vector> dp; int dfs(vector>& matrix, int i, int j) { if (dp[i][j]) return dp[i][j]; int v = 1; if (i + 1 < m && matrix[i + 1][j] > matrix[i][j]) v = max(v, 1 + dfs(matrix, i + 1, j)); if (i - 1 >= 0 && matrix[i - 1][j] > matrix[i][j]) v = max(v, 1 + dfs(matrix, i - 1, j)); if (j + 1 < n && matrix[i][j + 1] > matrix[i][j]) v = max(v, 1 + dfs(matrix, i, j + 1)); if (j - 1 >= 0 && matrix[i][j - 1] > matrix[i][j]) v = max(v, 1 + dfs(matrix, i, j - 1)); dp[i][j] = v; return dp[i][j]; } int solve(vector>& matrix) { m = matrix.size(), n = matrix[0].size(); dp = vector>(m, vector(n, 0)); int ans = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { ans = max(ans, dfs(matrix, i, j)); } } return ans; } ```

BinarySearch - One Edit Distance

[https://binarysearch.com/problems/One-Edit-Distance](https://binarysearch.com/problems/One-Edit-Distance) ## Problem Given two strings s0 and s1 determine whether they are one or zero edit distance away. An edit can be described as deleting a character, adding a character, or replacing a character with another character. Constraints n ≤ 100,000 where n is the length of s0. m ≤ 100,000 where m is the length of s1. ## Solution Short and clean. Find the first index i that s0[i] is not equal to s1[i] Based on the length of s0 and s1, compare the rest of the sub string are same or not. ``` bool solve(string s0, string s1) { int m = s0.size(), n = s1.size(); for (int i = 0; i < min(m, n); i++) { if (s0[i] != s1[i]) { if (m == n) return s0.substr(i + 1) == s1.substr(i + 1); else if (m < n) return s0.substr(i) == s1.substr(i + 1); else return s0.substr(i + 1) == s1.substr(i); } } return abs(m - n) <= 1; } ```

BinarySearch - Escape-Maze

[https://binarysearch.com/problems/Escape-Maze](https://binarysearch.com/problems/Escape-Maze) ## Problem You are given a two dimensional integer matrix, representing a maze where 0 is an empty cell, and 1 is a wall. Given that you start at matrix[0][0], return the minimum number of squares it would take to get to matrix[R - 1][C - 1] (where R and C are the number of rows and columns in the matrix). If it's not possible, return -1. Constraints n, m ≤ 250 where n and m are the number of rows and columns in matrix ## Solution Use standard BFS. Check if the matrix[0][0] and matrix[m-1][n-1] is 1 or not. If so, return -1. Then we need a queue to store the coordinates and the local count. Starting from (0,0), go for four directions and check if the target cell is valid or not. If so, update matrix[xx][yy] so that we won't visit it again and add it to the queue. If xx and yy reaches m-1 and n-1, check if the count is the minimal. ``` int ans = INT_MAX, m, n; int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, -1, 0, 1}; bool ok(int i, int j) { return !(i < 0 || i > m - 1 || j < 0 || j > n - 1); } int solve(vector>& matrix) { m = matrix.size(), n = matrix[0].size(); if (matrix[0][0] == 1 || matrix[m - 1][n - 1] == 1) return -1; queue, int>> q; // i, j, cnt q.push({{0, 0}, 1}); matrix[0][0] = 1; while (!q.empty()) { auto p = q.front(); q.pop(); int x = p.first.first, y = p.first.second, cnt = p.second; if (x == m - 1 && y == n - 1) ans = min(ans, cnt); for (int i = 0; i < 4; i++) { int xx = x + dx[i], yy = y + dy[i]; if (ok(xx, yy) && matrix[xx][yy] == 0) { matrix[xx][yy] = 1; q.push({{xx, yy}, cnt + 1}); } } } return ans == INT_MAX ? -1 : ans; } ```

BinarySearch - Sum of Two Numbers

[https://binarysearch.com/problems/Sum-of-Two-Numbers](https://binarysearch.com/problems/Sum-of-Two-Numbers) ## Problem Statement Given a list of numbers nums and a number k, return whether any two elements from the list add up to k. You may not use the same element twice. Note: Numbers can be negative or 0. Constraints n ≤ 100,000 where n is the length of nums ## Solution Use unordered_map to store the complement. If it is found, return true. If not, update m[nums[i]]. ``` bool solve(vector& nums, int k) { unordered_map m; for (int i = 0; i < nums.size(); i++) { if (m.count(k - nums[i])) return true; m[nums[i]] = i; } return false; } ```

BinarySearch - Largest Island Area

[https://binarysearch.com/problems/Largest-Island-Area](https://binarysearch.com/problems/Largest-Island-Area) ## Problem You are given a two-dimensional integer matrix of 1s and 0s. A 1 represents land and 0 represents water, so an island is a group of 1s that are neighboring whose perimeter is surrounded by water. You can assume that the edges of the matrix are surrounded by water. Return the area of the largest island in matrix. Constraints n, m ≤ 250 where n and m are the number of rows and columns in matrix ## Solution Textbook flood fill. Search the cell with value 1 to perform dfs. For each dfs, mark all visited cells to 0 so that it won't be visited again. Compare the return value with ans and take the max one. ``` int dfs(vector>& matrix, int i, int j) { if (i < 0 || i > matrix.size() - 1 || j < 0 || j > matrix[0].size() - 1 || matrix[i][j] == 0) return 0; matrix[i][j] = 0; return 1 + dfs(matrix, i + 1, j) + dfs(matrix, i - 1, j) + dfs(matrix, i, j + 1) + dfs(matrix, i, j - 1); } int solve(vector>& matrix) { int ans = 0; for (int i = 0; i < matrix.size(); i++) { for (int j = 0; j < matrix[i].size(); j++) { if (matrix[i][j] == 1) { ans = max(ans, dfs(matrix, i, j)); } } } return ans; } ```

LeetCode Weekly Contest 256 - Editorials

Here's the editorials for [LeetCode Weekly Contest 256](https://leetcode.com/contest/weekly-contest-256/) ## [Minimum Difference Between Highest and Lowest of K Scores (3 points)](https://leetcode.com/problems/minimum-difference-between-highest-and-lowest-of-k-scores/) The question can be rephrased as finding the minimum difference between the lowest and highest element of window of size ``k``. Therefore, we can first sort the array and check all the differences for each window. ```cpp class Solution { public: int minimumDifference(vector& nums, int k) { sort(nums.begin(), nums.end()); int ans = INT_MAX, n = nums.size(); for(int i = 0; i < n - k + 1; i++) { ans = min(ans, nums[i + k - 1] - nums[i]); } return ans; } }; ``` ## [Find the Kth Largest Integer in the Array (4 points)](https://leetcode.com/problems/find-the-kth-largest-integer-in-the-array/) If the input is integer, then we can sort the array and the answer would be $ nums[n - 1 - (k - 1)] $. However, this question gives an array of strings. Therefore, we just need to convert it to an array of integers first and perform the abovementioned logic. ```cpp class Solution { public: string kthLargestNumber(vector& nums, int k) { int n = nums.size(); sort(nums.begin(), nums.end(), [](string& s, string& t){ if(s.size() < t.size()) return true; if(t.size() < s.size()) return false; return s < t; }); return nums[n - k]; } }; ``` ## [Minimum Number of Work Sessions to Finish the Tasks (6 points)](https://leetcode.com/problems/minimum-number-of-work-sessions-to-finish-the-tasks/) Same question as [Elevator Rides](https://cses.fi/problemset/result/2762549/). Greedy approach won't work here. Here's the Bitmask DP approach. Let's define $ dp[i][j] $ where $i$ is the mask, $j$ is the minimum time for finishing the current tasks, and $dp[i][j]$ stores the minimum number of work sessions needed to finish all the tasks. We can run a dfs function to calculate each mask, if a task is not picked, we can set it as a new mask and check if adding this task would exceed sessionTime or not. If so, that means we need to create a new session and we can perform the next mask. Otherwise, we can just add this task to the current work session and try the next mask. ```cpp class Solution { public: int dp[1 << 14][20]; vector t; int time; int dfs(int m, int k) { int n = t.size(); if(m == (1 << n) - 1) return 1; if(dp[m][k] != -1) return dp[m][k]; int best = INT_MAX, new_mask; for(int i = 0; i < n; i++) { if(!(m & (1 << i))) { int new_mask = m | (1 << i); if(k + t[i] <= time) { best = min(best, dfs(new_mask, k + t[i])); } else { best = min(best, 1 + dfs(new_mask, t[i])); } } } return dp[m][k] = best; } int minSessions(vector& tasks, int sessionTime) { memset(dp, -1, sizeof(dp)); t = tasks, time = sessionTime; return dfs(0, 0); } }; ``` However, this method is not that efficient. Let's define $ dp[i] $ where $i$ is the mask and $dp[i]$ stores a pair of integers, with the first element as the minimum number of sessions and the second element as minimum time of the last session. After all tasks have been picked, that would be all 1s. Therefore, the answer is $dp[(1 << n) - 1]$. For each mask, we try to find the best pair, the logic is similar to the first approach. ```cpp class Solution { public: int minSessions(vector& tasks, int sessionTime) { int n = tasks.size(), INF = 1e9; // {min number of session, min time of last session} vector<pair<int, int>> dp(1 << n, {INF, INF}); dp[0].first = 0; for(int mask = 1; mask < (1 << n); mask++) { pair<int, int> best = {INF, INF}; for(int i = 0; i < n; i++) { if(mask & (1 << i)) { pair<int, int> cur = dp[mask ^ (1 << i)]; if(cur.second + tasks[i] > sessionTime) { cur = {cur.first + 1, tasks[i]}; } else { cur.second += tasks[i]; } best = min(best, cur); } } dp[mask] = best; } return dp[(1 << n) - 1].first; } }; ``` ## [Number of Unique Good Subsequences (7 points)](https://leetcode.com/problems/number-of-unique-good-subsequences/) The transition formula can be easily obtained by listing out some examples. We just need to count the number of subsequence that ends with 0 and 1, says $dp[0]$ and $dp[1]$. If $s[i] = 0$, we can append this $0$ to all existing subsequences, i.e. $dp[0] = dp[0] + dp[1]$. Simiarly, we can append $1$ to all the subsequences so that we got $dp[1] = dp[0] + dp[1] + 1$. We add $1$ here because $1$ is also a valid subsequence. $0$ is also a valid subsequence, but it will fail with something like $01$ or $00$. Therefore, we can simply add one at the end instead. The final answer is $dp[0] + dp[1]$ + $zero$ where $zero$ is either $1$ if there is at least one zero in the string, or $0$ otherwise. ```cpp class Solution { public: int numberOfUniqueGoodSubsequences(string binary) { int M = 1e9 + 7, dp[2] = {0, 0}; for(char& c: binary) dp[c - '0'] = (dp[0] + dp[1] + c - '0') % M; return (dp[0] + dp[1] + (binary.find("0") != string::npos)) % M; } }; ```

Codeforces Round #732 (Div. 2) - Unofficial Editorial (A - D)

# [A. AquaMoon and Two Arrays](https://codeforces.com/contest/1546/problem/A) We can calculate how many operations we need in order to make $ a_i $ to become $ b_i $ by increasing $a_i$ by 1 or decreasing $ a_i $ by 1 digit by digit. Since each operation requires two changes. Therefore we can store $ i $ in $ inc $ if $ a_i $ needs to be increased to be $ b_i $, and vice versa in $ dec $. If both size is not same, then there is no way to turn $ a $ to $ b $. Otherwise, we can iterate each $ i $ in $ inc $ and $ dec $ and print $ inc_i $ and $ dec_i $ as one operation. ``` void solve() { int n; cin >> n; vector a(n), b(n); for(int i = 0; i < n; i++) cin >> a[i]; for(int i = 0; i < n; i++) cin >> b[i]; vector inc, dec; for(int i = 0; i < n; i++) { if(a[i] < b[i]) for(int j = 0; j < b[i] - a[i]; j++) inc.push_back(i); else if(b[i] < a[i]) for(int j = 0; j < a[i] - b[i]; j++) dec.push_back(i); } if(inc.size() != dec.size()) { cout << -1 << "\n"; } else { cout << inc.size() << "\n"; for(int i = 0; i < inc.size(); i++) { cout << dec[i] + 1 << " " << inc[i] + 1 << "\n"; } } } ``` # [B. AquaMoon and Stolen String](https://codeforces.com/contest/1546/problem/B) After shuffling some characters, we should be able to find $ 2 * n - 2 $ pairs. However, we don't need to do that as we can solve it simply by the observation. We can notice that each character in stolen string must have an odd occurrence at every $j-th$ column. In this case, we can use a XOR bitwise trick to find out the expected character at $j-th$ column. This method works as each pair can cancel each other. Let's say we have 4 'a's and 1 'b'at the first column, we can know the the first character in the stolen string is $ a \oplus a \oplus a \oplus a \oplus b = b $. ``` void solve() { int n, m; cin >> n >> m; string ans(m, 0); for(int i = 0; i < n * 2 - 1; i++) { string s; cin >> s; for(int j = 0; j < m; j++) { ans[j] ^= s[j]; } } cout << ans << "\n"; } ``` # [C. AquaMoon and Strange Sort](https://codeforces.com/contest/1546/problem/C) In the beginning, the direction of each friend is right. At the end, we also need the direction to be right. Hence, for each digit, it can only move even number of times. We can calculate the occurrence of each digit in odd position and even position and compare with that after sorting $ a $. If either one requires odd nubmer of times to move, then it returns $NO$. ``` const int mxN = 1e5 + 5; void solve() { int n; cin >> n; vector a(n); vector> cnt(mxN, vector(2)); for(int i = 0; i < n; i++) { cin >> a[i]; cnt[a[i]][i % 2]++; } sort(a.begin(), a.end()); for(int i = 0; i < n; i++) cnt[a[i]][i % 2]--; for(int i = 0; i < n; i++) { if(cnt[a[i]][0] != 0 || cnt[a[i]][1] != 0) { cout << "NO" << "\n"; return; } } cout << "YES" << "\n"; } ``` # [D. AquaMoon and Chess](https://codeforces.com/contest/1546/problem/D) In each operation, basically we can only apply those $11$ groups. For example, if $ s = 11110001011010 $, we don't need to care about those 1s where $ s[i - 1] = 0 $ and $ s[i + 1] = 0 $ if applicable. Therefore, we can remove those unused 1s and rearranage it as $ s = 111111000000 $. Let a pair of '11' be $X$ and $0$ be $Y$, then we can have $ 111111000000 -> XXXYYYYYY$ at the beginning. Then try to perform the operation to see the pattern. $$ 111111000000 = XXXYYYYYY $$ $$ 111101100000 = XXYXYYYYY $$ $$ 111100110000 = XXYYXYYYY $$ $$ 111100011000 = XXYYYXYYY $$ $$ 111100001100 = XXYYYYXYY $$ $$ 111100000110 = XXYYYYYXY $$ $$ 111100000011 = XXYYYYYYX $$ $$ 110110000011 = XYXYYYYYX $$ $$ ... $$ We can notice that the answer is $ C(N + M, N)$ where $N$ is the number of $X$ and $M$ is that of $Y$. In other words, we can put $X$ at position $(N + M)th$ column. You can find the modint template [here](https://github.com/wingkwong/competitive-programming/blob/master/snippets/maths.md#modint). ``` void solve() { int n; cin >> n; string s; cin >> s; long long zero = 0, one = 0, sum = 0; for(int i = 0; i < n; i++) { if(s[i] == '0') zero++, one += sum / 2, sum = 0; else sum++; } one += sum / 2; mint N = one + zero; mint M = one; cout << N.nCr(M) << "\n"; } ```