Suppose the total number of lines of code is a multiple of 3, i.e., of the form $$$3n$$$. Then the work can be evenly distributed among the three members — each writing exactly $$$n$$$ lines of code
If the number of lines is of the form $$$3n + 1$$$, then the optimal distribution would be: $$${n,\ n,\ n + 1}$$$
If the number of lines is of the form $$$3n + 2$$$, then the optimal distribution would be: $$${n,\ n + 1,\ n + 1}$$$
In both uneven cases above, the maximum number of lines any one member has to write is still $$${n + 1}$$$. Thus, for all three forms $$${3n,\ 3n + 1,\ 3n + 2}$$$, the answer is always: $$$\lceil \frac{x}{3} \rceil$$$ where $$$\lceil . \rceil$$$ is the ceiling value, and $$$x$$$ is the total number of lines of code.

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

void solve() {
    int x; cin >> x;
    cout << (x + 3 - 1) / 3 << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int tc = 1;
    // cin >> tc;
    while(tc-- > 0) solve();
    return 0;
}

Just stimulate the process: Iterate from index 0 to n-1, maintain a pointer j to the string "baton" initially at index 0. For each character in the input string, if it matches the current character pointed to in "baton", move the pointer forward. If the pointer reaches the end of "baton" j == 5, that means all characters 'b', 'a', 't', 'o', 'n' have been found in the same order one after another.

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

void solve() {
    string s, ans = "baton"; 
    cin >> s;
    int n = s.length();
    int j = 0;
    for(int i = 0; i < n; ++i){
        if(s[i] == ans[j]) j++;
        if(j == 5) break;
    }
    cout << (j == 5 ? "Yes" : "No") << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int tc = 1;
    cin >> tc;
    while(tc-- > 0) solve();
    return 0;
}

Since it is guaranteed that some combination of up to one row swap and one column swap will convert A into B, you just need to find two rows (if such row exists) which are "Not Equivalent" in both A and B. This means that these rows were swapped in B to get A.

"Not Equivalent" means that the set of elements in the i-th row of A is not the same as the set of elements in the i-th row of B.

1, 2, 3, 4, 5 is "Equivalent" to 1, 4, 3, 2, 5 (both have the same elements)
1, 2, 3, 4, 5 is "Not Equivalent" to 5, 6, 7, 8, 9 (both sets are disjoint)

So we can sort A[i] and B[i] and compare them!
If they are not equal, then obviously the i-th row of A has been swapped with some j-th row in A such that A[j] = B[i]. Find that index j and output i and j (The two rows that were swapped)

Similarly, do the same stuff for columns!

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

void solve(){
    int n, m; cin >> n >> m;
    vector<vector<int>> a(n, vector<int>(m)), b(n, vector<int>(m));
    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++) 
            cin >> a[i][j];
    }

    for (int i = 0; i < n; i++){
        for (int j = 0; j < m; j++) 
            cin >> b[i][j];
    }

    vector<int> r, c;
    for (int i = 0; i < n; i++){
        vector<int> temp1 = a[i], temp2 = b[i];
        sort(temp1.begin(), temp1.end());
        sort(temp2.begin(), temp2.end());

        if (temp1 != temp2){
            r.push_back(i + 1);
        }
    }

    for (int j = 0; j < m; j++){
        vector<int> temp1, temp2;
        for (int i = 0; i < n; i++){
            temp1.push_back(a[i][j]);
            temp2.push_back(b[i][j]);
        }
        sort(temp1.begin(), temp1.end());
        sort(temp2.begin(), temp2.end());

        if (temp1 != temp2){
            c.push_back(j + 1);
        }
    }

    if (r.size() > 0)
        cout << r[0] << " " << r[1] << " ";
    else
        cout << -1 << " " << -1 << " ";

    if (c.size() > 0)
        cout << c[0] << " " << c[1];
    else
        cout << -1 << " " << -1;

    cout << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int tc = 1;
    cin >> tc;
    while(tc-- > 0) solve();
    return 0;
}

Let's break the possible values of m (the uniqueness value) into ranges within [n, 3n - 3]:

Case 1: m == n

• We only need the n single-element subarrays, each trivially distinct.
• Output any array with all equal elements like [1, 1, 1, ..., 1].
• This ensures no subarray of length > 1 has all distinct elements.
• Total uniqueness value: n.

Case 2: n < m < 2n

• We already get $$$n$$$ uniqueness from 1-element subarrays.
• We now need $$${m - n}$$$ more distinct subarrays of length 2.
• Example: $$$[1, 2, 1, 2]$$$
  Subarrays with indices: $$$[0,1]$$$, $$$[1,2]$$$, $$$[2,3]$$$ contribute 1 to the uniqueness → 3 subarrays of length 2 with distinct elements.
• In general, we can form n - 1 such subarrays in an array of size n.
• Hence, we can reach up to m = 2n - 1 using only 1 and 2.

Case 3: m ≥ 2n

• We introduce the third element 3 to push f(a) further.
• Similar construction: start with [1, 2, 3], then alternate like [1,2,3,1,2,...] to get more distinct subarrays.
• Try analyzing how many new unique subarrays we get of lengths 2 and 3.
• (Try to prove this part yourself): The maximum uniqueness we can achieve is 3n - 3.

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

void solve() {
    int n,m;
    cin >> n >> m;

    if (n==m) {
        for (int i = 0; i < n; i++)
            cout << 1 << " ";
        cout << "\n";
    }
    else if (m<=2*n-1) {
        vector<int> res(n);
        res[0] = 1;
        res[1] = 2;

        int i = 2, ext = m-n;
        for (int iter = 0; iter < ext-1; iter++) {
            res[i] = 1+i%2;
            i++;
        }

        while (i<n) {
            res[i] = res[i-1];
            i++;
        }

        for (auto &x: res) cout << x << " ";
        cout << "\n";
    }
    else {
        vector<int> res(n);
        int ext = m-(2*n-1);
        res[0] = 1;
        res[1] = 2;
        res[2] = 3;

        int i = 3;
        for (int iter = 0; iter < ext-1; iter++) {
            res[i] = 1+i%3;
            i++;
        }

        while (i<n) {
            res[i] = res[i-2];
            i++;
        }

        for (auto &x: res) 
            cout << x << " ";
        cout << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int tc = 1;
    cin >> tc;
    while(tc-- > 0) solve();
    return 0;
}

Mukesh wants to maximize the number of sweets he can get, which is determined by the minimum marks he can achieve across 3 subjects (Physics, Chemistry, and Mathematics) within a given time interval T. We need to maximize the minimum marks and that's where Binary Search comes in!

We will precompute the maximum achievable marks for each subject, considering different total times. We use DP to calculate the maximum marks obtainable within a given time limit for each subject. This is similar to the knapsack problem where we are trying to maximize the total marks subject to a time constraint. For each subject, we construct a DP array:
dp[i] = minimum time required to get exactly i marks
We then use this DP array to track the minimum time needed for any given number of marks (from 0 to the maximum possible marks).

Now for each query, we need to find the maximum number of marks x such that the total time to achieve x marks in each subject does not exceed the given time limit T and maximize it if its possible.

#include <bits/stdc++.h>
using namespace std ;
using ll = long long;
typedef vector<ll> vii;
typedef pair<ll, ll> pii;
typedef vector<pii> vpii;
typedef vector<vii> vvii;
const int MAXN = 5000;

void input(vpii &v, ll n)
{
    for (int i = 0; i < n; i++)
    {
        ll a, t;
        cin >> a >> t;
        v[i] = {a, t};
    }
}

void precompute(vpii &v, vii &dp, ll n)
{
    dp[0] = 0;
    for (int i = 0; i < n; i++)
    {
        for (int j = MAXN - v[i].first; j >= 0; j--)
        {
            dp[j + v[i].first] = min(dp[j + v[i].first], dp[j] + v[i].second);
        }
    }

    for (int i = MAXN - 1; i >= 0; i--)
    {
        dp[i] = min(dp[i], dp[i + 1]);
    }
}

void solve(){
    ll n, m, k;
    cin >> n >> m >> k;

    vpii physics(n), chemistry(m), maths(k);

    input(physics, n);
    input(chemistry, m);
    input(maths, k);

    vii dp_phy(MAXN + 1, 1e17), dp_che(MAXN + 1, 1e17), dp_math(MAXN + 1, 1e17);

    precompute(physics, dp_phy, n);
    precompute(chemistry, dp_che, m);
    precompute(maths, dp_math, k);

    ll q;
    cin >> q;
    while (q-- > 0)
    {
        ll T;
        cin >> T;

        ll l = 0, r = MAXN;
        while (r - l > 1)
        {
            ll mid = (l + r) / 2;
            if (dp_phy[mid] + dp_che[mid] + dp_math[mid] <= T)
                l = mid;
            else
                r = mid;
        }
        ll ans = l;
        if (dp_phy[r] + dp_che[r] + dp_math[r] <= T)
            ans = r;

        cout << ans << " ";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int tc = 1;
    // cin >> tc;
    while(tc-- > 0) solve();
    return 0;
}

To approach the problem effectively, let us analyze each bit position independently. For every bit index i from 0 to 29 (assuming the maximum element fits within 30 bits), define cnt[i] as the number of elements in the array a that have the i-th bit set. The bits are considered from the least significant bit (0-th) upwards. Computing this array of counts requires O(30 * n) time, or more generally O(n * log(max(ai))) operations.

Now, consider how the score is calculated:
While there exists at least one non-zero element in the array, we perform the following operations: - Count how many elements are odd, i.e., have the 0-th bit set. - Add that count to the score. - Right shift each element in the array by one position (equivalent to dividing by 2 and taking the floor).

This process continues until all elements reduce to zero. If we track how many times a 1 appears at each bit position throughout the execution, the total score is simply the sum of all cnt[i] for i in [0, 29].

Our objective is to minimize this total score, and we are allowed to do so by selecting a single integer x to XOR with every element in the array before the process starts.

Here’s the key idea:

• There are n elements in total, so for each bit i, the maximum possible value of cnt[i] is n.
• If cnt[i] > n / 2, it means the majority of elements have a 1 at that bit.
• To reduce the number of 1s at that bit, we can flip them by setting bit i in x to 1.
• This effectively inverts all bits at that position, changing the count of 1s to n - cnt[i].
• If cnt[i] <= n / 2, the 0s are already in the majority.
• Flipping would increase the number of 1s, so we leave bit i in x as 0 and keep cnt[i] unchanged.

By applying this logic across all bit positions, we construct the integer x that minimizes the total contribution of set bits across all elements and all positions.

Finally, after applying XOR with x, we recalculate the modified cnt[i] values and sum them up.
This sum gives us the minimum achievable score, and the corresponding x is the optimal number to apply the XOR transformation with.

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

void solve() {
    int n; cin >> n;
    int cnt[30] = {0};
    for(int i = 0; i < n; ++i) {
        int a; cin >> a;
        for(int j = 0; j < 30; ++j) if(a & (1 << j)) cnt[j]++;
    }
    int score = 0, x = 0;
    for(int i = 0; i < 30; ++i){
        if(cnt[i] > n / 2){
            x += (1 << i);
            cnt[i] = n - cnt[i];
        }
        score += cnt[i];
    }
    cout << score << " " << x << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int tc = 1;
    cin >> tc;
    while(tc-- > 0) solve();
    return 0;
}

Suppose we are given a list of nodes: u₁, u₂, ..., uₘ.
We want to check whether all these nodes lie on a single path from the root (vertex 1) to some vertex v, where depth[v] ≥ max{depth[u₁, u₂, ..., uₘ]}.

Observation:
If the given nodes lie on such a path, then their parents must also lie on the same path from root to v.

First, find the node with the maximum depth among the list, call it mx_v. This mx_v will serve as our candidate v (the bottom of the path). Now, traverse from mx_v upward to the root (vertex 1) and mark all nodes on this path. Then, for every node uᵢ in the list:

• If uᵢ == 1 (the root), you can skip checking — it's always part of the path.
• Otherwise, check whether the parent of uᵢ lies on the upward path from mx_v to root.
• If any such parent is not found in this path, then the list of nodes does not lie on a valid single path from root to v.

This logic can be used efficiently using depth arrays and parent arrays after a DFS traversal of the tree.

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

vector<vector<int>> g;
vector<int> depth, parent;

void dfs(int v, int par){
    for(auto c : g[v]){
        if(c != par){
            parent[c] = v;
            depth[c] = depth[v] + 1;
            dfs(c, v);
        }
    }
}

void solve() {
    int n, q; cin >> n >> q;
    g.resize(n);
    depth.resize(n);
    parent.resize(n);
    for(int i = 1; i < n; ++i){
        int u, v; cin >> u >> v; --u, --v;
        g[u].pb(v);
        g[v].pb(u);
    }
    parent[0] = -1;
    dfs(0, -1);
    while(q--){
        int m; cin >> m;
        int ok = 0; 
        int mx_d = 0, mx_v = 0;
        set<int> nodes;
        for(int i = 0; i < m; ++i){
            int a; cin >> a; --a;
            if(a != 0) nodes.insert(parent[a]);
            if(mx_d < depth[a]) {
                mx_d = depth[a];
                mx_v = a;
            }
        }
        while(mx_v != -1){
            if(nodes.find(mx_v) != nodes.end()) nodes.erase(mx_v);
            mx_v = parent[mx_v];
        }
        cout << (nodes.empty() ? "YES" : "NO") << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int tc = 1;
    // cin >> tc;
    while(tc-- > 0) solve();
    return 0;
}

Controlling the ship involves two types of operation. One movement operation and one laser operation (to kill the alien). Both these operations are independent.
By Linearity of Expectation,

Let's assume the range of the $$$ith$$$ alien is $$$[l_i,r_i]$$$.

Let $$$dp_{i,j}$$$ be the sum of count of movement operations performed to kill the $$$ith$$$ alien spawning at $$$x=j$$$, over all possible combination of occurrences of the previous $$$i-1$$$ aliens.

A naive recurrence relation can be achieved from here, $$$dp_{i,j} = \sum_{y = l_{i-1}}^{r_{i-1}} dp_{i-1,y} + |j-y|$$$

Case 1: $$$l_{i-1} \leq l_i \leq r_i \leq r_{i-1}$$$

The previous recurrence relation can be re-arranged to the form,

$$$dp_{i,j} = \sum_{y=l_{i-1}}^{j} dp_{i-1,y} + (j-y) + \sum_{y=j}^{r_i-1}dp_{i-1,y} + (y-j)$$$

$$$ \Rightarrow dp_{i,j} = \sum_{y = l_{i-1}}^{r_{i-1}} dp_{i-1,y} + f(j-l_{i-1}) + f(r_{i-1}-j)$$$,

where $$$f(x) = \sum_{i=1}^{x} i$$$.

Let $$$dpsum_i = \sum_{j=l_i}^{j=r_i} dp_{i,j}$$$

$$$dpsum_i = \sum_{j=l_i}^{j=r_i} \sum_{y = l_{i-1}}^{r_{i-1}} dp_{i-1,y} + f(j-l_{i-1}) + f(r_{i-1}-j)$$$

$$$ \Rightarrow dpsum_i = \sum_{j=l_i}^{j=r_i} dpsum_{i-1} + f(j-l_{i-1}) + f(r_{i-1}-j)$$$

$$$ \Rightarrow dpsum_i = (r_i-l_i+1) \cdot dpsum_{i-1} + g(r_i-l_{i-1}) - g(l_i-l_{i-1}) + g(r_{i-1}-l_{i}) - g(r_{i-1}-r_{i})$$$

where $$$g(x) = \sum_{i=1}^{x} f(x)$$$.

Case 2: $$$l_i \gt r_{i-1}$$$ or $$$r_i \lt l_{i-1}$$$. A similar process can be used to get a recurrence relation for $$$dpsum$$$.

$$$dpsum_i = (f(r_i-r_{i-1})-f(l_i-r_{i-1}-1))\cdot(r_{i-1}-l_{i-1}+1) + f(r_{i-1}-l_{i-1})\cdot(r_i-l_i+1)$$$

$$$dpsum_i = (f(l_{i-1}-l_i)-f(l_{i-1}-r_i-1))\cdot(r_{i-1}-l_{i-1}+1) + f(r_{i-1}-l_{i-1})\cdot(r_i-l_i+1)$$$

Thus by breaking the $$$ith$$$ range into three parts with respect to $$$i-1th$$$ range, we can calculate $$$dpsum_i$$$ in $$$O(1)$$$.

It can be trivially shown that,

Hence we can calculate the expected value in $$$O(n)$$$.

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

#ifdef LOCAL
#include  "../debug.cpp"
#else
#define debug(...)
#define debugArr(...)
#endif

#define all(x) begin(x), end(x)
#define sz(x) (int)(x).size()
#define ff first
#define ss second
#define pb push_back
#define BIG 998244353
#define MOD 1000000007
#define fast_io ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL)
typedef long long ll;
typedef pair<ll, ll> pii;
typedef vector<ll> vi;
typedef vector<pii> vpii;
typedef vector<vi> vvi;

const int MAXN = 2e6;
ll sums[MAXN+1], prefsum[MAXN+1];

ll mult(ll p, ll q, ll m = MOD) {
    return (((p%m)*(q%m))%m);
}

ll binpow(ll p, ll q) {
    if (q == 0) return 1ll;
    ll temp = binpow(p, q/2);
    temp = mult(temp, temp);
    
    if (q%2) return mult(temp, p);
    return temp;
}

ll mod_inv(ll a, ll m = MOD) {
    return binpow(a, m - 2);
}

void precompute() {
    sums[0] = 0, prefsum[0] = 0;
    for (int i = 1; i <= MAXN; i++) {
        sums[i] = (sums[i-1]+i)%MOD;
    }
    for (int i = 1; i <= MAXN; i++) {
        prefsum[i] = (prefsum[i-1]+sums[i])%MOD;
    }
}

void solve() {
    int n;
    cin >> n;

    vector<array<ll,2>> alien;
    ll l,r;
    for (int i = 0; i < n; i++) {
        cin >> l >> r;
        alien.pb({l,r});
    }

    vi dp(n);
    ll ways = 1;
    ll prevl = 0, prevr = 0;
    dp[0] = (sums[prevr]-sums[max(prevl-1,0ll)]+MOD)%MOD;

    for (int i = 0; i < n; i++) {
        ll l = alien[i][0], r = alien[i][1];
        if (i>0) dp[i] = mult((r-l+1),dp[i-1]);

        ll il = max(l,prevl), ir = min(r,prevr);
        if (il<=ir) {
            ll temp = (prefsum[ir-prevl]-prefsum[max(il-prevl-1,0ll)]+MOD)%MOD;
            dp[i] = (dp[i]+temp)%MOD;
            
            temp = (prefsum[prevr-il]-prefsum[max(prevr-ir-1,0ll)]+MOD)%MOD;
            dp[i] = (dp[i]+temp)%MOD;
        }

        il = max(prevr+1,l), ir = r;
        if (il<=ir) {
            ll a = (sums[ir-prevr]-sums[il-prevr-1]+MOD)%MOD;
            ll cnt = (ir-il+1)%MOD;
            dp[i] = (dp[i]+mult(cnt,sums[prevr-prevl]))%MOD;
            dp[i] = (dp[i]+mult(a,prevr-prevl+1))%MOD;
        }

        il = l, ir = min(r,prevl-1);
        if (il<=ir) {
            ll a = (sums[prevl-il]-sums[prevl-ir-1]+MOD)%MOD;
            ll cnt = (ir-il+1)%MOD;
            dp[i] = (dp[i]+mult(cnt,sums[prevr-prevl]))%MOD;
            dp[i] = (dp[i]+mult(a,prevr-prevl+1))%MOD;
        }

        prevl = l, prevr = r;
        ways = mult(ways,(r-l+1));
    }

    debug(dp[n-1],ways);
    ll exp = mult(dp[n-1],mod_inv(ways))%MOD;
    exp = (exp+n)%MOD;
    cout << exp << "\n";
}

int main() {
    auto start = chrono::high_resolution_clock::now();
    precompute();
    fast_io;
    int t;
    cin >> t;

    while (t--) {
        solve();
    }

    #ifdef LOCAL
        auto end = chrono::high_resolution_clock::now();
        chrono::duration<double> duration = end - start;
        cerr << "Execution time: " << duration.count() << " seconds" << endl;
    #endif
}