The problem asks us to find two integers, $$$a$$$ and $$$b$$$, such that their product equals a given area $$$n$$$. Mathematically, we are looking for any two factors of $$$n$$$.

The constraints are small ($$$1 \le n \le 200$$$). Every integer $$$n \ge 1$$$ has at least one pair of factors: $$$1$$$ and $$$n$$$. Since the problem allows us to print any valid pair of dimensions, the absolute simplest approach is to always output $$$1$$$ and $$$n$$$.

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

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    if (cin>>n) {
        cout << 1 << " " << n <<"\n";
    }
    return 0;
}

Since any left shoe can form a pair with any right shoe, it is always optimal to greedily pair the cheapest available left shoe with the cheapest available right shoe. Sort the cost arrays of both the left and right shoes in non-decreasing order. Iterate through both arrays simultaneously, taking the $$$i$$$-th pair as long as their combined cost does not exceed the remaining budget $$$k$$$.

Time Complexity: $$$\mathcal{O}(N \log N)$$$

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

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    long long k;
    if (cin >> n >> k) {
        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];
        sort(a.begin(), a.end());
        sort(b.begin(), b.end());
        int ans = 0;
        for (int i=0; i<n; i++) {
            if (k >= a[i]+b[i]) {
                k -= (a[i]+b[i]);
                ans++;
            } else {
                break;
            }
        }
        cout << ans << "\n";
    }
    return 0;
}

To guarantee that the three target constituencies secure strictly more votes than all others, their final vote counts must be strictly greater than the maximum vote count among the remaining $$$N-3$$$ non-target constituencies. Let $$$M$$$ be this maximum vote count. For each target constituency with a current vote count $$$V$$$, we must add $$$(M + 1 - V)$$$ votes if $$$V \le M$$$. If it already has strictly more than $$$M$$$ votes, no additions are needed. Summing these required additions for all three targets yields the minimum total votes required, which can be easily computed in $$$\mathcal{O}(N)$$$ time.

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

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    if (cin >> n) {
        vector<int> a(n);
        for (int i = 0; i < n; i++) cin >> a[i];
        int x, y, z;
        cin >> x >> y >> z;
        x--; y--; z--;
        int m = -1;
        for (int i = 0; i < n; i++) {
            if (i != x && i != y && i != z) {
                m = max(m, a[i]);
            }
        }
        long long ans = 0;
        if (a[x] <= m) ans += (m + 1 - a[x]);
        if (a[y] <= m) ans += (m + 1 - a[y]);
        if (a[z] <= m) ans += (m + 1 - a[z]);
        cout << ans << "\n";
    }
    return 0;
}

The problem asks us to determine the parity of the difference between the final scores, $$$|S_1 - S_2|$$$. Notice that mathematically, $$$(S_1 - S_2) = (S_1 + S_2) - 2 \cdot S_2$$$. Since $$$2 \cdot S_2$$$ is inherently an even number, subtracting it does not change the parity. Therefore, the parity of the difference $$$|S_1 - S_2|$$$ is always exactly the same as the parity of the total sum of all elements, $$$S_1 + S_2$$$. Because the total sum is just the sum of the entire array and remains constant regardless of the players' choices, the "optimal play" aspect is a trap; the game's outcome is entirely predetermined by the input.

We simply need to check if the total sum of the array is odd or even, which can be done safely without overflow by counting the number of odd elements. If the count of odd elements is odd, Ravi ("Alice") wins; otherwise, Priyanshu ("Bob") wins. This is evaluated on the fly in $$$\mathcal{O}(n)$$$ time and $$$\mathcal{O}(1)$$$ space.

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

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    if (cin >> n) {
        int c = 0;
        for (int i = 0; i < n; i++) {
            int x;
            cin >> x;
            if (x % 2 != 0) c++;
        }
        if (c % 2 != 0) cout << "Alice\n";
        else cout << "Bob\n";
    }
    return 0;
}

To find the total number of integers less than or equal to $$$n$$$ with an odd number of digits, we can group the valid numbers by their lengths. An integer has $$$L$$$ digits if it falls in the range $$$[10^{L-1}, 10^L - 1]$$$. Within this specific range, there are exactly $$$9 \cdot 10^{L-1}$$$ such numbers.

We can iterate through the possible lengths $$$L$$$ starting from $$$1$$$. As long as the entire range of $$$L$$$-digit numbers is strictly less than or equal to $$$n$$$, we check if $$$L$$$ is odd. If it is, we add all $$$9 \cdot 10^{L-1}$$$ numbers to our total. When we reach the length $$$L$$$ where $$$n$$$ itself resides, we stop the loop. If this final length $$$L$$$ is odd, we simply add the remaining valid numbers from $$$10^{L-1}$$$ up to $$$n$$$. Processing the lengths this way allows us to answer each testcase very efficiently in $$$\mathcal{O}(\log_{10} n)$$$ time.

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

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t;
    if (cin >> t) {
        while (t--) {
            long long n;
            cin >> n;
            long long ans = 0;
            long long p = 1;
            int l = 1;
            // Using n / 10 >= p instead of p * 10 <= n to prevent long long overflow when n = 10^18
            while (n / 10 >= p) {
                if (l % 2 != 0) {
                    ans += (p * 9);
                }
                p *= 10;
                l++;
            } 
            if (l % 2 != 0) {
                ans += (n - p + 1);
            }
            cout << ans << "\n";
        }
    }
    return 0;
}

To prevent the running XOR checksum from ever becoming $$$0$$$, the final prefix XOR $$$S_N$$$ must also not be $$$0$$$. Since $$$S_N$$$ is simply the XOR sum of all integers from $$$1$$$ to $$$N$$$, we can use the well-known property that the XOR sum of $$$1 \dots N$$$ equals $$$0$$$ strictly when $$$N \equiv 3 \pmod 4$$$. In these cases, it is mathematically impossible to form a valid permutation, so we must output $$$-1$$$. For all other values of $$$N$$$, a valid permutation always exists.

To find the lexicographically smallest sequence, we should greedily attempt to place the numbers in strictly increasing order ($$$1, 2, 3, \dots, N$$$). A collision happens if placing the current number $$$i$$$ makes the new prefix XOR $$$0$$$, which only occurs if the running prefix XOR is exactly equal to $$$i$$$. Because we are largely placing numbers in order, the running prefix XOR before placing $$$i$$$ is equivalent to the XOR sum of $$$1 \dots i-1$$$. Based on XOR properties, $$$\bigoplus_{j=1}^{i-1} j = i$$$ happens exactly when $$$i \equiv 3 \pmod 4$$$. To avoid the $$$0$$$ in this scenario, we just deviate from our greedy choice minimally by swapping $$$i$$$ with $$$i+1$$$. Since we already ruled out $$$N \equiv 3 \pmod 4$$$, we are guaranteed that $$$i \lt N$$$, meaning $$$i+1$$$ is always available to be safely swapped. We can construct the answer by iterating from $$$1$$$ to $$$N$$$, printing $$$i+1$$$ then $$$i$$$ whenever $$$i \equiv 3 \pmod 4$$$, and printing normally otherwise.

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

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    if (cin >> n) {
        if (n % 4 == 3) {
            cout << -1 << "\n";
        } else {
            for (int i = 1; i <= n; i++) {
                if (i % 4 == 3) {
                    cout << i + 1 << " " << i << " ";
                    i++; 
                } else {
                    cout << i << " ";
                }
            }
            cout << "\n";
        }
    }
    return 0;
}

The condition $$$(p_i + p_{i+1}) \pmod 2 \neq (p_{i+1} + p_{i+2}) \pmod 2$$$ mathematically simplifies to $$$p_i \pmod 2 \neq p_{i+2} \pmod 2$$$. This means that any two elements separated by exactly one position must have different parities. In other words, the parities of the array must follow a repeating block of four: Odd, Odd, Even, Even (or a shifted version of this pattern, such as Odd, Even, Even, Odd).

Since any permutation of length $$$n$$$ has exactly $$$\lceil n/2 \rceil$$$ odd numbers and $$$\lfloor n/2 \rfloor$$$ even numbers, we can simply test the four possible starting shifts of this repeating pattern. We count how many odd slots a shift requires for a given length $$$n$$$, and once we find the one that perfectly matches our available number of odd integers, we greedily populate the array by placing the odd and even numbers into their respective slots. This constructs the answer cleanly in $$$\mathcal{O}(n)$$$ time and $$$\mathcal{O}(1)$$$ space.

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

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t;
    if (cin >> t) {
        while (t--) {
            int n;
            cin >> n;
            int req_o = (n + 1) / 2;
            int shift = 0;
            
            for (int s = 0; s < 4; s++) {
                int odds = 0;
                for (int i = 0; i < n; i++) {
                    if (((i + s) / 2) % 2 == 0) odds++;
                }
                if (odds == req_o) {
                    shift = s;
                    break;
                }
            }
       
            int o = 1, e = 2;
            for (int i = 0; i < n; i++) {
                if (((i + shift) / 2) % 2 == 0) {
                    cout << o << " ";
                    o += 2;
                } else {
                    cout << e << " ";
                    e += 2;
                }
            }
            cout << "\n";
        }
    }
    return 0;
}

This is a classic interval scheduling problem. To maximize the number of non-overlapping meetings the President can attend, we should greedily always choose the available meeting that ends as early as possible. By doing this, we leave the maximum amount of remaining time available for any subsequent meetings.

To implement this, we first convert the HH:MM time strings into a single integer representing the total minutes since midnight (i.e., $$$H \cdot 60 + M$$$). We store each meeting's end time, start time, and its original 1-based index, and then sort all meetings primarily by their end times in ascending order. We then iterate through this sorted list, maintaining a variable to track the end time of the last meeting we chose to attend. If the current meeting's start time is greater than or equal to our tracked end time, we can safely attend it, so we record its original index and update our tracked end time. Because the selected meetings are strictly non-overlapping and are processed in order of their end times, they are naturally ordered by their start times as well, directly satisfying the problem's output requirement. This greedy approach finds the optimal schedule in $$$\mathcal{O}(N \log N)$$$ time.

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

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    if (cin >> n) {
        vector<array<int, 3>> a(n);
        for (int i = 0; i < n; i++) {
            int h1, m1, h2, m2;
            char c1, c2;
            cin >> h1 >> c1 >> m1 >> h2 >> c2 >> m2;
            int start_time = h1 * 60 + m1;
            int end_time = h2 * 60 + m2;
            a[i] = {end_time, start_time, i + 1};
        }
        
        sort(a.begin(), a.end());
        
        vector<int> ans;
        int last_end = -1;
        
        for (int i = 0; i < n; i++) {
            if (a[i][1] >= last_end) {
                ans.push_back(a[i][2]);
                last_end = a[i][0];
            }
        }
        
        for (int i = 0; i < ans.size(); i++) {
            cout << ans[i] << (i == ans.size() - 1 ? "" : " ");
        }
        cout << "\n";
    }
    return 0;
}

Since the two mangoes move down the tree completely independently of each other, the destination of one mango does not affect the destination of the other. Therefore, the total number of valid pairs of leaves $$$(a, b)$$$ where the mangoes can end up is simply the number of possible destinations for the first mango multiplied by the number of possible destinations for the second mango. Because a mango always moves downwards to a child vertex until it falls off, the reachable leaves from any starting vertex $$$u$$$ are exactly all the leaves contained within the subtree rooted at $$$u$$$.

To solve this efficiently for multiple queries, we can precalculate the number of leaves in the subtree of every vertex. We can accomplish this using a single Depth First Search (DFS) starting from the root (vertex $$$1$$$). If a visited vertex has no children, it is a leaf, and we set its leaf count to $$$1$$$. Otherwise, its leaf count is simply the sum of the precalculated leaf counts of all its direct children. Once this information is stored, every query $$$(x, y)$$$ can be answered instantly by multiplying the precomputed leaf counts for vertex $$$x$$$ and vertex $$$y$$$. This approach seamlessly processes all queries in $$$\mathcal{O}(n + q)$$$ time and requires $$$\mathcal{O}(n)$$$ space to store the tree and leaf counts.

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

void dfs(int u, int p, vector<vector<int>>& adj, vector<long long>& leaves) {
    bool is_leaf = true;
    for (int v : adj[u]) {
        if (v != p) {
            is_leaf = false;
            dfs(v, u, adj, leaves);
            leaves[u] += leaves[v];
        }
    }
    if (is_leaf) {
        leaves[u] = 1;
    }
}

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t;
    if (cin >> t) {
        while (t--) {
            int n;
            cin >> n;
            vector<vector<int>> adj(n + 1);
            for (int i = 0; i < n - 1; i++) {
                int u, v;
                cin >> u >> v;
                adj[u].push_back(v);
                adj[v].push_back(u);
            }
            
            vector<long long> leaves(n + 1, 0);
            dfs(1, 0, adj, leaves);
            
            int q;
            cin >> q;
            while (q--) {
                int x, y;
                cin >> x >> y;
                cout << leaves[x] * leaves[y] << "\n";
            }
        }
    }
    return 0;
}

The maximum number of times we can extract the subsequence "ICPC" is monotonic, making it an ideal candidate for binary searching the answer $$$X$$$. To verify if a specific $$$X$$$ is possible, we can employ a strict greedy matching strategy. First, we iterate through the string from left to right, picking the first $$$X$$$ available 'I' characters and the first $$$X$$$ available 'C' characters that appear after them to form $$$X$$$ disjoint "IC" pairs. We immediately mark the indices of these selected characters as visited. Next, we iterate from right to left using only the remaining unvisited characters. We greedily pick the first $$$X$$$ available 'C' characters and the first $$$X$$$ available 'P' characters that appear before them to form $$$X$$$ disjoint "PC" pairs.

Finally, we match these groups sequentially: if the $$$i$$$-th "IC" pair finishes strictly before the $$$i$$$-th "PC" pair begins for all valid pairs, then the combination is successful. By locking the visited characters in the forward pass, we prevent the backward pass from accidentally reusing the same 'C', successfully guaranteeing the result in $$$\mathcal{O}(N \log N)$$$ time and $$$\mathcal{O}(N)$$$ space.

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

int main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    int t;
    if (cin >> t) {
        while (t--) {
            string s;
            cin >> s;
            int n = s.length();
            int low = 1, high = n / 4, ans = 0;
            vector<array<int, 4>> res;
            
            while (low <= high) {
                int mid = low + (high - low) / 2;
                vector<int> i_idx(mid), c1_idx(mid), p_idx(mid), c2_idx(mid);
                vector<bool> vis(n, false);
                
                int i_cnt = 0, c1_cnt = 0;
                for (int i = 0; i < n && c1_cnt < mid; i++) {
                    if (s[i] == 'I' && i_cnt < mid) {
                        i_idx[i_cnt++] = i;
                        vis[i] = true;
                    } else if (s[i] == 'C' && c1_cnt < i_cnt) {
                        c1_idx[c1_cnt++] = i;
                        vis[i] = true;
                    }
                }
                
                if (c1_cnt < mid) {
                    high = mid - 1;
                    continue;
                }
                
                int p_cnt = 0, c2_cnt = 0;
                for (int i = n - 1; i >= 0 && p_cnt < mid; i--) {
                    if (!vis[i]) {
                        if (s[i] == 'C' && c2_cnt < mid) {
                            c2_idx[mid - 1 - c2_cnt] = i;
                            c2_cnt++;
                        } else if (s[i] == 'P' && p_cnt < c2_cnt) {
                            p_idx[mid - 1 - p_cnt] = i;
                            p_cnt++;
                        }
                    }
                }
                
                if (p_cnt < mid) {
                    high = mid - 1;
                    continue;
                }
                
                bool ok = true;
                for (int i = 0; i < mid; i++) {
                    if (c1_idx[i] > p_idx[i]) {
                        ok = false;
                        break;
                    }
                }
                
                if (ok) {
                    ans = mid;
                    res.clear();
                    for (int i = 0; i < mid; i++) {
                        res.push_back({i_idx[i] + 1, c1_idx[i] + 1, p_idx[i] + 1, c2_idx[i] + 1});
                    }
                    low = mid + 1;
                } else {
                    high = mid - 1;
                }
            }
            
            cout << ans << "\n";
            for (int i = 0; i < ans; i++) {
                cout << res[i][0] << " " << res[i][1] << " " << res[i][2] << " " << res[i][3] << "\n";
            }
        }
    }
    return 0;
}