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 \gt 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 \lt 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;
}

To determine the number of interesting pairs, observe that removing elements at positions $$$i$$$ and $$$j$$$ leaves a sum of $$$S - a_i - a_j$$$, where $$$S$$$ is the total sum of the array.

First, compute the total sum $$$S = \text{sum}(a)$$$. The condition for an interesting pair translates to $$$l \leq a_i + a_j \leq r$$$, where $$$l = S - y$$$ and $$$r = S - x$$$. Sort the array to facilitate efficient pair counting. For each $$$a_i$$$, use binary search to find the range of indices $$$j \gt i$$$ where $$$a_i + a_j$$$ satisfies the bounds $$$[l, r]$$$. Specifically, use $$$\text{lower_bound}$$$ to find the first $$$a_j \geq l - a_i$$$ and $$$\text{upper_bound}$$$ to find the first $$$a_j \gt r - a_i$$$. The difference between these indices gives the number of valid pairs for the current $$$i$$$. Iterate through all $$$i$$$ to compute the total count efficiently. This approach, combining sorting and binary search, ensures the solution is fast enough for the input constraints.

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

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

#define int long long

void solve () {
    int n, x, y;
    cin >> n >> x >> y;
    vector<int> v(n);
    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }
    int sum = accumulate(v.begin(), v.end(), 0LL);
    sort(v.begin(), v.end());
    int l = sum - y, r = sum - x, cnt = 0;
    for (int i = 0; i < n; i++) {
        int a = upper_bound(v.begin() + i + 1, v.end(), r - v[i]) - v.begin();
        int b = lower_bound(v.begin() + i + 1, v.end(), l - v[i]) - v.begin();
        cnt += a - b;
    }
    cout << cnt << endl;
}

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

The key is to consider all possible tree prices. For each price, determine how many customers will buy trees and how many negative reviews will be received. Notice that the possible tree prices are limited to the values in arrays $$$a$$$ and $$$b$$$.

To solve the problem efficiently, treat each customer as contributing two potential price points: $$$a_i$$$ (positive review) and $$$b_i$$$ (negative review). Create a list of events where each $$$a_i$$$ adds a potential negative review, and each $$$b_i$$$ removes a potential buyer. Sort these events by price to process them in ascending order. Maintain a running count of total buyers and negative reviews, and for each price, calculate the store's total earnings. Only consider prices where the number of negative reviews does not exceed $$$k$$$. The maximum earnings across all valid prices give the result.

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

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

#define int long long

void solve () {
    int n, k;
    cin >> n >> k;
    vector<int> a(n), b(n);
    for (int &i : a) cin >> i;
    for (int &i : b) cin >> i;
    vector<pair<int, int>> res;
    for (int i = 0; i < n; i++) {
        res.emplace_back(a[i], 1);
        res.emplace_back(b[i], 2);
    }
    sort(res.begin(), res.end());
    int cnt = n, tmp = 0, ans = 0;
    for (int i = 0; i < 2 * n; i++) {
        int j = res[i].first;
        if (tmp <= k) ans = max(ans, j * cnt);
        while (n * 2 > i && res[i].first == j) {
            tmp += (res[i].second == 1) - (res[i].second == 2);
            cnt -= (res[i].second == 2);
            i++;
        }
        i--;
    }
    cout << ans << endl;
}

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

Since $$$n$$$ is a two-digit number, you can access each digit by simple arithmetic operations.

To find the sum of digits of a two-digit number $$$n$$$, divide $$$n$$$ by 10 to get the first digit and take $$$n$$$ modulo 10 to get the second digit. Adding these gives the desired result.

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

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

int main() {
    int n;
    cin >> n;
    cout << (n / 10) + (n % 10) << endl;
    return 0;
}

For each pair of cards, consider all possible matchups and count how many games Suneet can win by winning more rounds.

Each player has two cards, and the game consists of two rounds. For each matchup of cards, there are four possible ways for the players to reveal their cards. We simulate each of these cases and count how many result in Suneet winning more rounds than Slavic.

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

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

int main() {
    int t;
    cin >> t;
    while (t--) {
        int a1, a2, b1, b2;
        cin >> a1 >> a2 >> b1 >> b2;
        int count = 0;
        int a[2] = {a1, a2}, b[2] = {b1, b2};
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                int suneet = 0, slavic = 0;
                if (a[i] > b[j]) suneet++;
                else if (a[i] < b[j]) slavic++;
                if (a[1 - i] > b[1 - j]) suneet++;
                else if (a[1 - i] < b[1 - j]) slavic++;
                if (suneet > slavic) count++;
            }
        }
        cout << count << endl;
    }
    return 0;
}

Check each gap between tasks, as well as the beginning and end of the day, to see if there’s enough free time for Alex to shower.

Given Alex's tasks, represented as non-overlapping time intervals, we need to find a continuous free interval of at least $$$s$$$ minutes.

i. Sort and scan the intervals:

• Check the time from the start of the day to the beginning of the first task.
• Check the gaps between tasks.
• Check from the end of the last task to the end of the day.

ii. If any of these free intervals is at least $$$s$$$ minutes, Alex can shower.

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

#include <bits/stdc++.h>
using namespace std;
 
int main () {
    int t;
    cin >> t;
    while (t--) {
        int n, time, total, temp;
        cin >> n >> time >> total;
        temp = n;
        vector<pair<int, int>> v;
        while (temp--) {
            int x, y;
            cin >> x >> y;
            v.push_back({x, y});
        }
        int mx = 0;
        for (int i = 0; i < n; i++) {
            if (i == 0) {
                mx = max(mx, v[i].first);
            } else {
                mx = max(mx, v[i].first - v[i - 1].second);
            }
        }
        if (total - v[n - 1].second >= time) {
            mx = time;
        }
        cout << ((mx >= time) ? "YES" : "NO") << endl;
    }
    
    return 0;
}

Check if the string $$$t$$$ can appear as a subsequence in string $$$s$$$, replacing '?' with appropriate letters from $$$t$$$ wherever possible. Fill remaining '?' characters with any letter.

The goal is to replace each '?' in string $$$s$$$ with lowercase letters so that $$$t$$$ becomes a subsequence of $$$s$$$.

1. Attempt to match each character of $$$t$$$ with a character in $$$s$$$ by iterating through $$$s$$$.

2. For each character in $$$t$$$, try to find a match in $$$s$$$. If you encounter '?', replace it with the matching character in $$$t$$$.

3. If $$$t$$$ becomes a subsequence of $$$s$$$, fill remaining '?' with any valid letter (e.g., 'a') and print the modified $$$s$$$.

4. If it is not possible to make $$$t$$$ a subsequence of $$$s$$$, print "NO".

Time Complexity: $$$O(|s|)$$$ per test case
Space Complexity: $$$O(|s|)$$$ per test case

#include <bits/stdc++.h>
using namespace std;
 
int main () {
    int t;
    cin >> test;
    while (t--) {
        string a, b;
        cin >> a >> b;
        int count = 0;
        int j = -1;
        for (int i = 0; i < b.length(); i++) {
            for (j = j + 1; j < a.length(); j++) {
                if (b[i] == a[j]) {
                    count++;
                    break;
                } else if (a[j] == '?') {
                    count++;
                    a[j] = b[i];
                    break;
                }
            }
        }
        if (count >= b.length()) {
            cout << "YES" << endl;
        } else {
            cout << "NO" << endl;
            continue;
        }
        for (int i = 0; i < a.length(); i++) {
            if (a[i] != '?') {
                cout << a[i];
            } else {
                cout << 'a';
            }
        }
        cout << endl;
    }
    
    return 0;
}

Observe that each operation reduces numbers effectively by dividing and multiplying, so precompute the minimum number of operations needed to reduce each possible integer to zero.

The goal is to minimize the number of operations needed to reduce every number between $$$l$$$ and $$$r$$$ to zero.

i. Precompute Operations for Each Number:

• Use dynamic programming to calculate the minimum operations required to make any number from 1 up to $$$2 \times 10^5$$$ equal zero.
• For each integer $$$x$$$, recursively compute the minimum operations to reduce it by dividing by 3 until reaching zero.

ii. Result Calculation for Each Range $$$[l, r]$$$:

• With the precomputed values, sum the operations needed for each integer from $$$l$$$ to $$$r$$$.

Time Complexity: $$$O(\text{precompute}) + O(r - l)$$$ per query.
Space Complexity: $$$O(\text{range})$$$

#include <bits/stdc++.h>
using namespace std;
 
const int N = 2 * 1e5 + 1;
vector<int> dp(N, -1);
 
int search (int value) {
    if (value == 0) {
        return 0;
    }
    if (dp[value] != -1) {
        return dp[value];
    }
    return dp[value] = search(value / 3) + 1;
}
 
int main () {
    int t;
    cin >> t; 
    for (int i = N; i >= 0; i--) {
        search(i);
    }
    while (test--) {
        int l, r;
        cin >> l >> r;
        int as = dp[l] * 2;
        for (int i = l + 1; i <= r; i++) {
            as += dp[i];
        }
        cout << as << endl;
    }
    
    return 0;
}

To get the sum of medians, consider each element's contribution to all subsequences of length $$$k$$$ it could be part of.

i. Median in Subsequences:

• For a subsequence of odd length $$$k$$$, the median is the $$$(\frac{k + 1}{2})^{th}$$$ element when sorted.

ii. Counting Combinations Efficiently:

• Use combinatorics to calculate how many times each element can be the median in a subsequence of length $$$k$$$.
• Use a precomputed factorial array to quickly compute combinations using modular inverses.

iii. Dynamic Sum Calculation:

• For each "1" in the array, calculate its total contribution as a median and sum these contributions modulo $$$10^9 + 7$$$.

Time Complexity: $$$O(n + k)$$$ per query (for factorial precomputation and each test case).
Space Complexity: $$$O(n)$$$ for storing results.

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

#define int long long int
 
const int MOD = 1e9 + 7;
const int N = 2 * 1e5 + 1;
vector<int> factorial(N, 1);
 
int modular (int power, int base, int as) {
    while (power != 0) {
        if (power & 1) {
            as *= base;
            as %= MOD;
        }
        base *= base;
        base %= MOD;
        power >>= 1;
    }
    return as;
}
 
int search (int n, int r) {
    if (n < r) {
        return 0;
    } else if (r < 0) {
        return 0;
    } else if (n < 0) {
        return 0;
    }
    r = (factorial[r] * factorial[n - r]) % MOD;
    return (modular(MOD - 2, r, 1) * factorial[n]) % MOD;
}
 
int32_t main () {
    int t;
    cin >> t;
    for (int i = 1; i <= N; i++) {
        factorial[i] = (factorial[i - 1] * i) % MOD;
    }
 
    while (test--) {
        int n, k;
        cin >> n >> k;
        vector<int> v(n), res(n + 1, 0);
        for (int &as : v) {
            cin >> as;
        }
        for (int i = 0; i < n; i++) {
            res[i + 1] = res[i] + v[i];
        }
        int count = 0, one = res[n], zero = n - res[n];
        for (int i = 0; i < n; i++) {
            if (v[i] != 0) {
                int value = search(zero + res[i], k / 2);
                value *= search(res[n] - res[i + 1], k / 2);
                count = (count + (value % MOD)) % MOD;
            }
        }
        cout << count << endl;
    }
    
    return 0;
}

Think about the number of queries. Here, number of queries = $$$10$$$. $$$\lceil \log_2(1000) \rceil = 10$$$

I used same code in G1 & G2. The implementation is done by ternary search.

But you can use binary search as well for G1. Just take one $$$mid$$$ for this and look at the tutorial of G2 for clear concepts.

Look at G2's implementation.

Again, think about the number of queries. Here, number of queries = $$$7$$$. $$$\lceil \log_3(1000) \rceil = 7$$$

We can apply a ternary search to find the value of $$$x$$$ within the range $$$[1, 999]$$$ using queries in the form $$$? , a , b$$$. Each query effectively narrows down the range by dividing it into three segments based on the area result. Starting with $$$l = 1$$$ and $$$r = 999$$$, each iteration calculates two points, $$$mid_1$$$ and $$$mid_2$$$, which split the range into thirds. The query response ($$$area$$$) helps determine in which third $$$x$$$ lies.

If the area matches $$$(mid_1 + 1) \cdot (mid_2 + 1)$$$, then $$$x$$$ must be less than $$$mid_1$$$, so $$$r$$$ is updated to $$$mid_1$$$. If the area is $$$mid_1 \cdot (mid_2 + 1)$$$, $$$x$$$ lies between $$$mid_1$$$ and $$$mid_2$$$, so $$$l$$$ and $$$r$$$ are adjusted to this range. Otherwise, $$$x$$$ is greater than $$$mid_2$$$, so $$$l$$$ is updated to $$$mid_2$$$.

When the possible values are down to just two ($$$r - l = 2$$$), a final query confirms the exact position of $$$x$$$. The search concludes within a maximum of $$$7$$$ queries due to the three-way division at each step. This method uses ternary search principles to efficiently narrow down $$$x$$$.

Time Complexity: $$$O(1)$$$ per test case because $$$\lceil \log_3(1000) \rceil = 7$$$
Space Complexity: $$$O(1)$$$

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

#define ll long long int

int query (int a, int b) {
    cout << "? " << a << ' ' << b << endl;
    int n;
    cin >> n;
    return n;
}

void solve () {
    int l = 1, r = 999, x, y = 0;
    while (l - r < -2) {
        int mid_1 = l + (r - l) / 3;
        int mid_2 = r - (r - l) / 3;
        int area = query(mid_1, mid_2);
        if (area == (mid_1 + 1) * (mid_2 + 1)) {
            r = mid_1;
        } else if (area == mid_1 * (mid_2 + 1)) {
            l = mid_1;
            r = mid_2;
        } else {
            l = mid_2;
        }
        if (r - l == 2) {
            int area = query(1, l + 1);
            if (area != l + 1) {
                r = l + 1;
            } else {
                l++;
            }
        }
    }
    cout << "! " << r << endl;
}

int32_t main () {
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    
    return 0;
}