Think about the indices that have the same remainder after division by $$$x$$$.

Consider the subsequence formed from the indices that have the same remainder after division by $$$x$$$. There are $$$x$$$ such subsequences. Each subsequence contains distinct characters, so the maximum length of such subsequences is $$$k$$$. As such, the minimum string length that cannot be constructed is $$$n = kx+1$$$.

Time complexity: $$$\mathcal{O}(1)$$$

t = int(input())
for _ in range(t):
    k, x = [int(i) for i in input().split()]
    print(k*x+1)

First observe that it is always helpful to remove a floor. Now the question becomes which floor to remove.

You can simply simulate the process of removing any possible floor. To do this efficiently, compute the current time taken and consider the change to the time taken if a floor is removed. If we remove floor $$$i$$$ where $$$i \neq 1$$$ and $$$i \neq n$$$, then the differences $$$|a[i] - a[i-1]|$$$ and $$$|a[i+1] - a[i]|$$$ are removed and the difference $$$|a[i-1] - a[i+1]|$$$ is added. If $$$i = 1$$$ or $$$i = n$$$, only the adjacent difference is removed.

Time complexity: $$$\mathcal{O}(n)$$$

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
void test_case_run() {
    int n;
    cin >> n;
    
    ll a[n+1];
    for (int i = 1; i <= n; i++) cin >> a[i];
    
    ll sum = 0;
    for (int i = 2; i <= n; i++) sum += abs(a[i]-a[i-1]);
    
    ll ans = min(sum - abs(a[2]-a[1]), sum - abs(a[n]-a[n-1]));
    for (int i = 2; i < n; i++) {
        ans = min(ans, sum - abs(a[i+1]-a[i]) - abs(a[i]-a[i-1]) + abs(a[i+1]-a[i-1]));
    }
    
    cout << ans << "\n";
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    while (t--) test_case_run();
    
    return 0;
}

Making everying zeros works often.

Sometimes, it's better to make all numbers something else that's not zero.

Following Hint 2, if we don't make everything zero, then what's our target number?

Sort the array from small to large.

We can mod every number in the array by itself, and this would require $$$k = a_1$$$.

For a larger value of $$$k$$$, we cannot modify the value of $$$a_1$$$, so every number must be made into $$$a_1$$$. We can mod $$$a_i$$$ with $$$a_i - a_1$$$, using $$$k = a_2 - a_1$$$.

The answer is thus $$$\max(a_1, a_2 - a_1)$$$.

Time complexity: $$$\mathcal{O}(n)$$$ or $$$\mathcal{O}(n \log n)$$$ depending on implementation.

for test_case in range(int(input())):
    n = int(input())
    a = sorted([int(_) for _ in input().split()])
    print(max(a[0], a[1]-a[0]))

Ignore the lexicographically minimum condition first. Can you find any permutation that maximizes $$$S(p)$$$? Can you explain why the permutation maximizes $$$S(p)$$$?

There's an easy permutation that maximizes $$$S(p)$$$.

There are at most $$$2^{n-i}$$$ prefixes of the permutation that has the popcount of the bitwise AND be at least $$$i$$$.

Read all hints. Now, look at this sentence in Hint 3.

"For a popcount of a prefix to exceed $$$i$$$, you'll need to fix $$$i$$$ bits to be all ones."

We will fix the $$$i$$$ lowest-value bits, and iterate the other bits lexicographically minimally.

Here's an example for $$$n=3$$$:

1 1 1 = 7

0 1 1 = 3

0 0 1 = 1

1 0 1 = 5

0 0 0 = 0

0 1 0 = 2

1 0 0 = 4

1 1 0 = 6

For a clean implementation, note that iterating the unfixed bits is basically iterating even numbers.

Time complexity: $$$\mathcal{O}(2^n)$$$.

t = int(input())
for _ in range(t):
    n = int(input())
    print(2**n - 1, end = ' ')
    for i in range(1, n+1):
        for j in range(0, 2**i, 2):
            print(j*2**(n-i) + 2**(n-i) - 1, end = ' ')
    print()

Denote the party that is supposed to win a district as the 'designated winner.' A minimum population $$$p_i$$$ for each district and a strict majority condition creates a lower bound on the number of votes from the designated winner. What is this lower bound?

The lower bound is $$$\lfloor \frac{p_i}{2} \rfloor + 1$$$.

What happens if at least one pair of districts has a different designated winner?

What happens if that is not true; i.e all districts have the same designated winner?

Consider the process of constructing a solution, even though we will not explicitly construct it in the code. First note that if $$$x+y \lt \sum p_i$$$, then it is impossible.

Then if $$$x+y \geq \sum p_i$$$, we start off by filling each district with the lower bound number $$$\lfloor \frac{p_i}{2} \rfloor + 1$$$ of votes from the designated winner. If we run out of votes from either party then the answer is no. After that we have two cases:

Case 1: if there is at least one pair of districts with different designated winners, we can arbitrarily fill (with any color) each district up to its minimum capacity $$$p_i$$$, and then allocate the rest of the votes to a district where that vote's party is supposed to win in. Therefore we only need to check if the lower bound on designated winner votes can be achieved.

Case 2: if all districts have the same designated winner, sometimes there are too many votes from the 'losing' party for a solution to exist. The minimum votes the winning party must have over the losing party is $$$n$$$, because we need a strict majority in every district, which corresponds to a vote difference of at least 1 in each district. WLOG let $$$x$$$ be the votes from the winning party and $$$y$$$ be the votes from the losing party, and we simply check if $$$x \geq y + n$$$.

Time complexity: $$$\mathcal{O}(n)$$$

#include <bits/stdc++.h>
 
using namespace std;
typedef long long ll;
 
void test_case_run() {
    int n;
    ll x, y;
    cin >> n >> x >> y;
    
    string s;
    cin >> s;
    s = '.'+s;
    
    ll p[n+1];
    for (int i = 1; i <= n; i++) cin >> p[i];
    
    if (accumulate(p+1, p+n+1, 0LL) > x+y) {
        cout << "NO\n";
        return;
    }
    
    if (s == "." + string(n, '0') || s == "." + string(n, '1')) {
        if (s == "." + string(n, '1')) {
            swap(x, y);
        }
        
        ll x_need = 0;
        for (int i = 1; i <= n; i++) {
            x_need += p[i]/2 + 1;
        }
        
        if (x < x_need || x < y+n) {
            cout << "NO\n";
        } else {
            cout << "YES\n";
        }
        
        return;
    }
    
    ll x_need = 0, y_need = 0;
    for (int i = 1; i <= n; i++) {
        if (s[i] == '0') {
            x_need += p[i]/2 + 1;
        } else {
            y_need += p[i]/2 + 1;
        }
    }
    if (x >= x_need && y >= y_need) cout << "YES\n";
    else cout << "NO\n";
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    while (t--) test_case_run();
    
    return 0;
}

Solve for a line graph.

Solve for a tree.

Does the exact same thing work? Why?

In the first run, use breadth-first search to find the distance of each vertex from vertex $$$1$$$. Color a vertex red if the distance is dividsible by $$$3$$$, green if the remainder of the division by $$$3$$$ is $$$1$$$, and blue if the remainder of the division by $$$3$$$ is $$$2$$$.

Note that if two vertices are connected by an edge, then their distances differ by no more than $$$1$$$. In fact, the distances differ by exactly $$$1$$$ for a bipartite graph.

In the second run, move anywhere if every neighbor have the same color. Otherwise, note that

• If the neighbors are red and green, then B is at a blue vertex, and should move to any green vertex.

• If the neighbors are green and blue, then B is at a red vertex, and should move to any blue vertex.

• If the neighbors are blue and red, then B is at a green vertex, and should move to any red vertex.

Time complexity: $$$\mathcal{O}(n+m)$$$

#include <bits/stdc++.h>
 
using namespace std;
const int INF = 1e9;
 
void test_first() {
    int n, m;
    cin >> n >> m;
    
    vector<vector<int>> edge(n+1);
    for (int i = 1; i <= m; i++) {
        int a, b;
        cin >> a >> b;
        edge[a].push_back(b);
        edge[b].push_back(a);
    }
    
    vector<int> dist(n+1, INF);
    dist[1] = 0;
        
    queue<int> bfs;
    bfs.push(1);
    while (!bfs.empty()) {
        int a = bfs.front();
        bfs.pop();
            
        for (int b : edge[a]) {
            if (dist[b] > dist[a] + 1) {
                dist[b] = dist[a] + 1;
                bfs.push(b);
            }
        }
    }
    
    for (int i = 1; i <= n; i++) cout << "rgb"[dist[i]%3];
    cout << "\n";
}
 
void test_second() {
    int dv;
    string color;
    cin >> dv >> color;
    
    bool fr = false, fg = false, fb = false;
    for (char c : color) {
        if (c == 'r') fr = true;
        if (c == 'g') fg = true;
        if (c == 'b') fb = true;
    }
    
    if ((int)fr + (int)fg + (int)fb == 1) {
        cout << 1 << "\n";
        return;
    }
    
    char target;
    if (fr && fg) target = 'g';
    if (fg && fb) target = 'b';
    if (fb && fr) target = 'r';
    
    for (int i = 0; i < dv; i++) {
        if (color[i] == target) {
            cout << i+1 << "\n";
            return;
        }
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    string player;
    int t;
    cin >> player >> t;
    
    if (player == "first") while (t--) test_first();
    else while (t--) {
        int q;
        cin >> q;
        while (q--) test_second();
    }
    
    return 0;
}

Think about corners.

Think about non-opposite corners.

Think about cells furthest from another cell.

The idea is that distance from two non-opposite corners uniquely determine the position.

Start from an arbitrary cell, and query the distance from that cell to every other cell, using $$$n^2$$$ queries. Any cell furthest is a corner.

Next, from that corner, query to every other cell, using $$$n^2$$$ queries. We now get the distances from one corner.

Now, notice that the non-opposite corners would have a distance of $$$n-1$$$ from the corner we have right now. There will be $$$n$$$ candidate corners. Choose one arbitrary candidate and query the distance from this candidate to all other candidates, using $$$n$$$ queries. Any furthest cell is a desired non-opposite corner.

Lastly, query from the new-found corner, using $$$n^2$$$ queries. We now have sufficient information to answer.

Query count: $$$3n^2 + n - \mathcal{O}(1)$$$. This analysis did not account for small constant optimizations like not querying the same pair twice and not querying the distance to self.

Time complexity: $$$\mathcal{O}(n^2)$$$

#include <bits/stdc++.h>
 
using namespace std;
 
int query(int i, int j) {
    cout << "? " << i << " " << j << endl;
    int ret;
    cin >> ret;
    return ret;
}
 
void test_case_run() {
    int n;
    cin >> n;
    
    // Find the first corner
    int dist1[n*n+1];
    for (int i = 1; i <= n*n; i++) dist1[i] = query(1, i);
    
    int corner1 = 1;
    for (int i = 1; i <= n*n; i++) if (dist1[i] > dist1[corner1]) corner1 = i;
    
    // Query distance from first corner
    int dist_corner1[n*n+1];
    for (int i = 1; i <= n*n; i++) {
        dist_corner1[i] = query(corner1, i);
    }
 
    // Find second corner    
    vector<int> corner2_candidates;
    for (int i = 1; i <= n*n; i++) {
        if (dist_corner1[i] == n-1) corner2_candidates.push_back(i);
    }
    
    int dist_findcorner2[corner2_candidates.size()];
    for (int i = 0; i < corner2_candidates.size(); i++) {
        dist_findcorner2[i] = query(corner2_candidates[0], corner2_candidates[i]); 
    }
    
    int corner2_index = 0;
    for (int i = 0; i < corner2_candidates.size(); i++) {
        if (dist_findcorner2[i] > dist_findcorner2[corner2_index]) corner2_index = i;
    }
    
    int corner2 = corner2_candidates[corner2_index];
    
    // Query distance from second corner
    int dist_corner2[n*n+1];
    for (int i = 1; i <= n*n; i++) {
        dist_corner2[i] = query(corner2, i);
    }
    
    // Find position
    /*
    d1 = |x-1|+|y-1| = x+y-2
    d2 = |x-1|+|y-n| = x-y+n-1
    
    d1 + d2 = 2x+n-3 => x = (d1+d2-n+3)/2
    d1 - d2 = 2y-n-1 => y = (d1-d2+n+1)/2
    */
    int ans[n+1][n+1];
    for (int i = 1; i <= n*n; i++) {
        int d1 = dist_corner1[i], d2 = dist_corner2[i];
        int x = (d1+d2-n+3)/2;
        int y = (d1-d2+n+1)/2;
        ans[x][y] = i;
    }
    
    cout << "!" << endl;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) cout << ans[i][j] << " ";
        cout << endl;
    }
};
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    while (t--) test_case_run();
    
    return 0;
}

This problem is solvable in $$$3n^2$$$ queries. Try it.

Solve the easier version of this problem first:

• Let $$$f(x)$$$ be the value of the least significant bit of $$$x$$$.

Read Hint 1 first.

You can extend the idea from the easier version to solve the actual task.

Since the value of the least significant bit can be represented using the sum of $$$2^0, 2^1, 2^2, \ldots$$$, the only thing left to consider is the coefficient of those values in each position.

For watering operations that cover the range $$$[l, r]$$$, you can perform the following update to the coefficient array:

• For all $$$l \leq i \leq r$$$, add $$$i$$$ to the $$$i$$$-th position.
• For all $$$l \leq i \leq r$$$, subtract $$$l-1$$$ from the $$$i$$$-th position.

Which is basically the same as increasing the coefficients value in each $$$l \leq i \leq r$$$ by $$$i - l + 1$$$.

These operations can be implemented using prefix sum arrays separately in each $$$a$$$, too.

Time complexity: $$$\mathcal{O}((n+q)\log n)$$$.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 200200;
int qs1[20][N];
ll qs2[20][N];
ll ans[N];
void solve() {
    int n, q;
    cin >> n >> q;
    int sz = 31 - __builtin_clz(n);
    for (int i = 1;i <= n;i++) ans[i] = 0;
    for (int j = 0;j <= sz;j++) {
        for (int i = 0;i <= n;i++) qs1[j][i] = 0, qs2[j][i] = 0;
    }
    while (q--) {
        int l, r;
        cin >> l >> r;
        int sz = 31 - __builtin_clz(r - l + 1);
        for (int j = 0;j <= sz;j++) {
            int k = (r - l + 1) >> j;
            qs1[j][l + (1 << j) - 1]++;
            qs2[j][l + (1 << j) - 1] += l - 1;
            qs1[j][min(n + 1, l + ((k + 1) << j) - 1)]--;
            qs2[j][min(n + 1, l + ((k + 1) << j) - 1)] -= l - 1;
        }
    }
    for (int i = 0;i <= sz;i++) {
        for (int j = 1;j <= n;j++) {
            if (j >= (1 << i)) {
                qs1[i][j] += qs1[i][j - (1 << i)];
                qs2[i][j] += qs2[i][j - (1 << i)];
            }
            ans[j] += 1ll * qs1[i][j] * j * (1 << max(0, i - 1));
            ans[j] -= 1ll * qs2[i][j] * (1 << max(0, i - 1));
        }
    }
    for (int i = 1;i <= n;i++) {
        cout << ans[i] << ' ';
    }
    cout << '\n';
}
 
int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
    int q;
    cin >> q;
    while (q--) {
        solve();
    }
    return 0;
}