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