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

Codeforces Round #720 - 1521B. Nastia and a Good Array

This is an unofficial editorial for [Nastia and a Good Array](https://codeforces.com/contest/1521/problem/B). ## Problem Statement Nastia has received an array of n positive integers as a gift. She calls such an array a good that for all i ($ 2 <= i <= n $) takes place $ gcd(a_i − 1, a_i )$ = 1, where $ gcd(u, v) $ denotes the greatest common divisor (GCD) of integers u and v. You can perform the operation: select two different indices $i$, $j$ ($1 <= i, j <= n, i \neq j$) and two integers $x$, $y$ ($1 <= x,y <= 2 * 10^9$) so that $ min(a_i, a_j) = min(x, y)$. Then change $a_i$ to $x$ and $a_j$ to $y$. The girl asks you to make the array good using at most $n$ operations. It can be proven that this is always possible. ## Approach From the statement, we can have our first obversation which is $ a_i - 1 $ and $a_i$ are coprime, denoted by $ gcd(a_i − 1, a_i )$ = $1$. Two integers are coprime if the only positive integer that is a divisor of both of them is 1, mathematically $ gcd(a, b) = 1 $. Therefore, this question can be rephrased as "how to make a_i - 1 and a_i coprime using at most $n$ operations". ### Solution 1 We can use the fact that an integer $x$ and $ x \pm 1 $ are coprime. First let's find the min value $x$ and its position $pos$ in array $a$ as we have to use this value to perform the operations. For all integer $i$ where $ 1 <= i <= n $, we can perform $ (pos, i, x ,abs(pos - i)) $ to replace $a_i$ to $x$ + $abs(pos - i)$. For the first test case, we can make $ [9, 6, 3, 11, 15] $ to $ [5, 4, 3, 4, 5] $ using $ n - 1 $ operations. ### Solution 2 We can put a prime number, let's say $ 1e9 + 7$ on every odd index if the minimum value is on even index and vice versa. In this case, we just need $ (n + 1) / 2 $ operations to turn $ [9, 6, 3, 11, 15] $ to $ [9, 1e9 + 7, 3, 1e9 + 7, 15] $.

Nezzar and Symmetric Array

This is an unofficial editorial for [Nezzar and Symmetric Array](https://codeforces.com/problemset/problem/1478/C). ## Problem Statement Long time ago there was a symmetric array $a_1$, $a_2$, ... ,$a_{2n}$ consisting of $2n$ distinct integers. Array $a_1$, $a_2$, ... ,$a_{2n}$ is called symmetric if for each integer $1 <= i <= 2n$, there exists an integer $1 <= j <= 2n$ such that $a_i = -a_j$. For each integer $1<=i<=2n$, Nezzar wrote down an integer $d_i$ equal to the sum of absolute differences from $a_i$ to all integers in $a$, i. e. $d_i$ = $\sum_{j=1}^{2n} |a_i - a_j|$. Now a million years has passed and Nezzar can barely remember the array $d$ and totally forget $a$. Nezzar wonders if there exists any symmetric array 𝑎 consisting of $2n$ distinct integers that generates the array $d$. ## Input The first line contains a single integer $t$ ($1 <= t <= 10^5$) — the number of test cases. The first line of each test case contains a single integer 𝑛 ($1 <= n <= 10^5$). The second line of each test case contains $2n$ integers $d_1, d_2, ..., d_{2n}$ ($1 <= d_i <= 10^{12}$). It is guaranteed that the sum of 𝑛 over all test cases does not exceed $10^5$. ## Output For each test case, print "YES" in a single line if there exists a possible array 𝑎. Otherwise, print "NO". You can print letters in any case (upper or lower). ## Approach Here's the simulation of the first example. ``` a = [1 -3 -1 3] i = 0 : 0 + 4 + 2 + 2 = 8 i = 1 : 4 + 0 + 2 + 6 = 12 i = 2 : 2 + 2 + 0 + 4 = 8 i = 3 : 2 + 6 + 4 + 0 = 12 d = [8, 12, 8, 12] ``` Each element has a positive and negative value. Supposing the positive value is $ x $, and the absolute difference to $(y, -y)$ would be $| x - y | + | x + y | $. Similarly, for $ -x $, that would be $ |-x - y | + |-x + y |$, which is also $|x - y| + |x + y|$. Therefore, for each $ d[i] $, there would be a pair as well. For $|x - y| + |x + y|$, we have two different cases. For $x > y$, $|x - y| + |x + y|$ would be $ 2 * x $. For $x > y$, $|x - y| + |x + y|$ would be $ 2 * y $. Now we know that $|x - y| + |x + y|$ = $2 * max(x, y)$. For each $ d[i] $, it is the sum of each absolute differences from $a[i]$ to all integers. Combined with the previous finding, we got $$ d[i] = \sum_{j=1}^{2n} max(abs(a[i]), abs(a[j])) $$ Given the array $d$, how can we generate the array $a$ back? Supposing the maximum element in $a$ is called $max_1$, the corresponding $d[i]$ would be $max_1 * 2 * n$. Therefore, we now have $max_1 = d[i] / 2 / n$. For the second maximum element, let's say $max_2$, as there is only $max_1$ which is greater than $max_2$, all other $(n - 1)$ elements are less than or equal to $max2$. The sum of absolute differences to them would be $max_2 * 2 * (n - 1)$. As $max_2 < max_1$, we need to add $max_1 * 2$ back to $d[i]$. Similarly, we can do the same thing one by one to get the original array $a$ back. We can induce that $$ max_1 = d[i] / 2 / n $$ $$ max_2 = (d[i] - max_1 * 2) / 2 / (n - 1) $$ $$ max_3 = (d[i] - max_2 * 2) / 2 / (n - 2) $$ $$ max_4 = (d[i] - max_3 * 2) / 2 / (n - 3) $$ $$ \vdots $$ $$ max_m = (d[i] - max_{m - 1} * 2) / 2 / (n - k) $$ For each elelment $x$, we need to check the occurence of its absolute value. If $x$ is odd or its occurence is odd, then the answer is $NO$. Also, if $x$ appears more than 2 times, that would be also $NO$. For each $max_m$, we can verify that if we can retrieve an integer, i.e. $(d[i] - max_{m - 1} * 2) / 2 % (n - k) $ is $0$ or not. If not, that is also $NO$. if $(d[i] - max_{m - 1} * 2) / 2 / (n - k) $ appears before or it is less than or equal to $0$, that is also not a correct answer. Therefore, we have 6 cases to check in total. For other cases, that would be $YES$. ## Solution ``` void solve() { long long n; cin >> n; map<long long, long long> vis, m; for(int i = 0; i < 2 * n; i++) cin >> d[i], m[-d[i]]++; long long cur_sum = 0, k = 0; EACH(it, m) { long long abs_difference = -it.fi, occurrence = it.se; if(abs_difference % 2 || occurrence % 2 || occurrence > 2) { cout << "NO" << "\n"; return; } long long p = (abs_difference - cur_sum * 2) / 2; long long q = n - k; if(p % q) { cout << "NO" << "\n"; return; } p /= q; if(vis.count(p) || p <= 0) { cout << "NO" << "\n"; return; } vis[p] = 1, cur_sum += p, k++; } cout << "YES" << "\n"; } ```

Codeforces - Love-Hate - Deltix Round, Spring 2021

[Love-Hate](https://codeforces.com/contest/1523/problem/D) is one of my favourite questions in Deltix Round. ## Problem Statement William is hosting a party for 𝑛 of his trader friends. They started a discussion on various currencies they trade, but there's an issue: not all of his trader friends like every currency. They like some currencies, but not others. For each William's friend 𝑖 it is known whether he likes currency j. There are m currencies in total. It is also known that a trader may not like more than p currencies. Because friends need to have some common topic for discussions they need to find the largest by cardinality (possibly empty) subset of currencies, such that there are at least ⌈n / 2⌉ friends (rounded up) who like each currency in this subset. ### Input The first line contains three integers 𝑛,𝑚 and 𝑝 (1 <= n <= 2 * 10 ^ 5,1 <= p <= m <= 60,1 <= p <=15), which is the number of trader friends, the number of currencies, the maximum number of currencies each friend can like. Each of the next 𝑛 lines contain 𝑚 characters. The 𝑗-th character of 𝑖-th line is 1 if friend 𝑖 likes the currency 𝑗 and 0 otherwise. It is guaranteed that the number of ones in each line does not exceed 𝑝. ###Output Print a string of length 𝑚, which defines the subset of currencies of the maximum size, which are liked by at least half of all friends. Currencies belonging to this subset must be signified by the character 1. If there are multiple answers, print any.
# Approach Since the final answer will be a submask of one of ⌈n / 2⌉ friends, we can use a randomized solution. First we shuffle the all the friends and take N of them as the probability of failing is $ 1 : 2 ^ N$. We can take $ N = min(20, n) $ where $ n $ is the number of trader friends. To shuffle our input $ s $, we can use the built in function ``shuffle`` with ``rng``. ``` mt19937 rng((unsigned int) chrono::steady_clock::now().time_since_epoch().count()); shuffle(s.begin(), s.end(), rng); ``` Then we can "compress" each mask for each friend to a size no larger than $ p $ by only keeping those true bits which are also true in mask. For exmaple, if $s[it]$ is $ 11001$ then bits would be $[0, 1, 4]$. ```cpp for(int it = 0, it < min(20, (int) s.size())) { vector<int> bits; for(int b = 0; b < m; b++) { if(s[it][b] == '1') { bits.push_back(b); } } } ``` We can use ``exact_cnt[mask]`` to store the number of friends who like exactly the currency mask. Let's say we have $ K $ ones in ``b``, then we will have $ 2 ^ K $ possible masks. For example, if $ K = 2 $, then we will have $2 ^ 2 = 4$ masks which are $[00, 01, 10, 11]$. To find out all the counts, we can iterate each friend and build the mask based on the set bits of the first friend. ``` int K = bits.size(); vector<int> exact_cnt(1 << K, 0); for(auto x : s) { int mask = 0; for(int i = 0; i < K; i++) mask |= (x[bits[i]] - '0') << i; exact_cnt[mask]++; } ``` Then we use at_least_cnt[mask] to store the number of friends who like at least the currency mask. Given a mask, we need to find the sum of all its supermask in ``exact_cnt``. For example, $111$, $110$, $101$, and $100$ are the supermask of $100$ because the MSB is $1$. To convert from exact_cnt to at_least_cnt, we can adopt an [$O(3 ^ N) $ solution](https://cp-algorithms.com/algebra/all-submasks.html) or $O(N * 2 ^ N) $ using SOS DP and invert all the bitmasks. ``` template<typename T_out, typename T_in> vector submask_sums(int n, const vector &values) { assert(int(values.size()) == 1 << n); vector dp(values.begin(), values.end()); for (int i = 0; i < n; i++) for (int base = 0; base < 1 << n; base += 1 << (i + 1)) for (int mask = base; mask < base + (1 << i); mask++) dp[mask + (1 << i)] += dp[mask]; return dp; } template<typename T_out, typename T_in> vector supermask_sums(int n, vector values) { reverse(values.begin(), values.end()); vector result = submask_sums(n, values); reverse(result.begin(), result.end()); return result; } ``` After that, we can check each mask to see if it has at least ⌈n / 2⌉ friends (rounded up) who like each currency in this subset and checks if it is larger by cardinality subset of currencies. If so, we update our temp answer by decompressing back to the full mask. ``` for(int mask = 0; mask < (1 << K); i++) { if( 2 * at_least_cnt[mask] >= n && __builtin_popcount(mask) > __builtin_popcountll(best) ) { ll full_mask = 0; for(int i = 0; i < K; i++) full_mask |= (long long)(mask >> i & 1) << bits[i]; best = full_mask; } } ``` At the end, we output the ans in binary format.
``` for(int i = 0; i < m; i++) cout << (best >> i & 1); ``` The full solution can be found [here](https://github.com/wingkwong/competitive-programming/blob/master/codeforces/contests/1523/D.cpp).