Focus on the fact that Monocarp can freely choose his training days, but Stereocarp is forced to train the day after Monocarp. Monocarp should carefully pick days where the problems he solves outweigh those Stereocarp would solve the following day.

To maximize $$$m - s$$$, Monocarp should always train on the last day, as it contributes $$$a[n]$$$ without affecting Stereocarp. For earlier days, Monocarp should train on day $$$i$$$ only if $$$a[i] > b[i+1]$$$, adding the difference $$$a[i] - b[i+1]$$$ to the total. This greedy approach ensures that Monocarp maximizes his problems solved while minimizing Stereocarp's. Iterate through the array once for each test case, adding valid differences and always including $$$a[n]$$$ from the last day.

Time Complexity: $$$O(n)$$$ per test case
Space Complexity: $$$O(n)$$$

#include <bits/stdc++.h>
using namespace std;

void solve () {
    int n;
    cin >> n;
    vector<int> a(n), b(n);
    for (int &i : a) cin >> i;
    for (int &i : b) cin >> i;
    int res = 0;
    for (int i = 0; i < n - 1; i++) {
        res += max(0, a[i] - b[i + 1]);
    }
    cout << res + a.back() << endl;
}

int32_t main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t; 
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

Monocarp's walking pattern repeats every three days, with distances $$$a$$$, $$$b$$$, and $$$c$$$. To find the day he completes his journey, calculate how many complete $$$3$$$-day cycles he can finish before walking at least $$$n$$$ kilometers.

The total distance Monocarp walks in one $$$3$$$-day cycle is $$$a + b + c$$$. First, calculate how many complete cycles he can walk, which is

Subtract the distance covered by these cycles from $$$n$$$ to find the remaining distance $$$n_{\text{rem}}$$$. If $$$n_{\text{rem}} = 0$$$, he finishes at the end of a complete cycle, i.e., on day $$$3 \times \text{cycles}$$$. Otherwise, determine the day within the next cycle by checking if $$$n_{\text{rem}}$$$ is covered by $$$a$$$, $$$a + b$$$, or $$$a + b + c$$$, corresponding to days $$$1$$$, $$$2$$$, or $$$3$$$ of the partial cycle. Finally, the result is

Time Complexity: $$$O(1)$$$ per test case
Space Complexity: $$$O(1)$$$

#include <bits/stdc++.h>
using namespace std;

#define int long long

void solve () {
    int n, a, b, c;
    cin >> n >> a >> b >> c;
    int res = n / (a + b + c);
    n %= (a + b + c);
    if (n == 0) cout << res * 3 << endl;
    else if (a >= n) cout << res * 3 + 1 << endl;
    else if (a + b >= n) cout << res * 3 + 2 << endl;
    else cout << res * 3 + 3 << endl;
}

int32_t main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t; 
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}

The problem revolves around checking if Monocarp knows all the questions in each list. Observe that each list has to miss less than two questions.

If $$$k + 1 < n$$$, it is impossible for Monocarp to pass any list, because he cannot know $$$n-1$$$ questions simultaneously. Output $$$m$$$ zeros.

If $$$k = n$$$, Monocarp knows all questions, so he passes every list. Output $$$m$$$ ones.

Otherwise, sort the known questions $$$q_1, q_2, \dots, q_k$$$. For each $$$a_i$$$, check if $$$a_i$$$ is in the sorted list of known questions. If $$$a_i$$$ is known, Monocarp cannot pass this list, so append '0' to the result. Otherwise, append '1'.

Time Complexity: $$$O(k \log k + m \log k)$$$ per test case
Space Complexity: $$$O(m + k)$$$

#include <bits/stdc++.h>
using namespace std;

void solve () {
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(m), q(k);
    for (int i = 0; i < m; i++) {
        cin >> a[i];
    }
    for (int i = 0; i < k; i++) {
        cin >> q[i];
    }
    if (k + 1 < n) {
        cout << string(m, '0') << endl;
    } else if (k == n) {
        cout << string(m, '1') << endl;
    } else {
        sort(q.begin(), q.end());
        string res;;
        for (int i = 0; i < m; i++) {
            if (binary_search(q.begin(), q.end(), a[i])) {
                res += '0';
            } else {
                res += '1';
            }
        }
        cout << res << endl;
    }
}

int32_t main () {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t; 
    cin >> t;
    while (t--) {
        solve();
    }
    return 0;
}