LeetCode Weekly Contest 256 - Editorials

Here's the editorials for LeetCode Weekly Contest 256

Minimum Difference Between Highest and Lowest of K Scores (3 points)

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.

class Solution {
public:
    int minimumDifference(vector<int>& 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)

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.

class Solution {
public:
    string kthLargestNumber(vector<string>& 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)

Same question as Elevator Rides. 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.

class Solution {
public:
    int dp[1 << 14][20];
    vector<int> 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<int>& 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.

class Solution {
public:
    int minSessions(vector<int>& 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)

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.

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

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<int> 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<int> 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

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

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<int> a(n);
    vector<vector<int>> cnt(mxN, vector<int>(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

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.

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