Let's subtract $$$n$$$ from the minimum number, subtract $$$n - 1$$$ from the second minimum, $$$n - 2$$$ from the third $$$\ldots$$$, and subtract $$$1$$$ from the maximum. Then the number of distinct elements will be $$$n$$$. Obviously, it is impossible to achieve a better result.

Let's prove that the number of distinct elements will be equal to $$$n$$$. Suppose $$$c_i = c_j$$$, then without loss of generality, let's say that $$$b_i > b_j$$$, then $$$a_i \leq a_j$$$, which means $$$c_i = a_i - b_i$$$ < $$$a_j - b_j = c_j$$$. Contradiction.

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

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

void solve() {
	ll n;
	cin >> n;
	vector<pair<ll, ll>> arr(n);
	for (ll i = 0; i < n; i++) {
		ll x;
		cin >> x;
		arr[i].first = x;
		arr[i].second = i;
	}
	vector<ll> ans(n);
	sort(arr.begin(), arr.end());
	reverse(arr.begin(),arr.end());
	for (ll i = 0; i < n; i++) {
		ans[arr[i].second] = i + 1;
	}
	for (auto i : ans) {
		cout << i << ' ';
	}
	cout << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
	ll t = 1;
	cin >> t;
	for (ll i = 0; i < t; i++) {
		solve();
	}
}

Firstly, a string is a palindrome if and only if for any $$$i$$$ ($$$1 \leq i \leq n$$$) $$$s_i = s_{n-i+1}$$$ (because when reversed, $$$s_i$$$ becomes $$$s_{n-i+1}$$$).

We can divide the characters into pairs, where each pair consists of $$$s_i$$$ and $$$s_{n-i+1}$$$. If $$$s_i = s_{n-i+1}$$$, then we need to have $$$l_i = l_{n-i+1}$$$ in order to obtain equal elements after XOR. Therefore, either $$$l_i = l_{n-i+1} = 0$$$ (with $$$0$$$ ones) or $$$l_i = l_{n-i+1} = 1$$$ (with $$$2$$$ ones). If $$$s_i \neq s_{n-i+1}$$$, then $$$l_i \neq l_{n-i+1}$$$ must hold ($$$1$$$ one in any case). Additionally, if $$$n$$$ is odd, then $$$l_{n/2+1}$$$ can be either $$$0$$$ or $$$1$$$ (with $$$0$$$ or $$$1$$$ ones).

We can iterate over the number of pairs where $$$l_i = l_{n-i+1}$$$ will have two ones, as well as whether there will be a one in the center or not. This way, we can obtain all possible numbers of ones in $$$l$$$, i.e., all good $$$i$$$.

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

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        string s;
        cin >> s;
        string t(n+1,'0');
        int ans = 0;
        int max_1 = 0;
        int max_2 = 0;
        for(int i = 0;i <= n/2-1;++i)
        {
            if(s[i] == s[n-i-1])
                max_2++;
            else
                ans++;
        }
        if(n%2 == 1)
            max_1++;
        for(int j = 0;j <= max_2;++j)
        {
            for(int k = 0;k <= max_1;++k)
            {
                t[ans + j*2 + k] = '1';
            }
        }
        cout << t << "\n";
    }
}

The correct strategy for Alice is to add the number $$$\operatorname{MEX}(S)$$$ to the set $$$S$$$ on the first move, and add the last removed number on the remaining moves.

Let m = $$$\operatorname{MEX}(S \cup {\operatorname{MEX}(S)})$$$, at the start of the game. In other words, m is equal to the second $$$\operatorname{MEX}$$$ of the set $$$S$$$. $$$m \geq 1$$$.

Notice that after the first move, $$$\operatorname{MEX}(S) = m$$$, and no matter what Bob removes, we will return that number to the set, so the result of the game will always be equal to $$$m$$$.

Let's prove that with Bob's optimal play, we cannot achieve a result greater than m.

Notice that the $$$\operatorname{MEX}$$$ of a set is the largest number k such that all numbers from $$$0$$$ to $$$k-1$$$ inclusive are present in the set.

Let $$$p_i$$$ be the number of numbers from $$$0$$$ to $$$i-1$$$ inclusive that appear in the set $$$S$$$. Then $$$\operatorname{MEX}(S)$$$ is equal to the maximum $$$i$$$ such that $$$p_i = i$$$.

If Bob removes the number $$$y$$$ during his turn, he decreases all values $$$p_i$$$ where $$$i > y$$$ by $$$1$$$. So, if $$$y = \operatorname{min}(S)$$$, Bob decreases all non-zero values $$$p_i$$$ by $$$1$$$.

Alice can increase some values $$$p_i$$$ by $$$1$$$ during her turn. Therefore, after Alice's first move, $$$\operatorname{MEX}(S)$$$ will no longer increase if Bob keeps removing the minimum, because no non-zero values of $$$p_i$$$ will increase (Bob decreases them by $$$1$$$, and Alice increases them by at most $$$1$$$).

It is obvious that in order to maximize $$$\operatorname{MEX}(S)$$$ after the first move, Alice needs to add the number $$$\operatorname{MEX}(S)$$$ to the set $$$S$$$.

We have proven that $$$R \leq m$$$ and provided a strategy that achieves a result of $$$m$$$.

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

#include <iostream>
#include <vector>

using namespace std;

void solve() {
	int n;
	cin >> n;
	vector<int> s(n);
	for (int i = 0; i < n; ++i)
		cin >> s[i];
	int mex = -1;
	for (int i = 0; i < n; ++i) {
		if (i == 0 && s[i] != 0) {
			mex = 0;
			break;
		}
		if (i > 0 && s[i] != s[i - 1] + 1) {
			mex = s[i - 1] + 1;
			break;
		}
	}
	if (mex == -1)
		mex = s[n - 1] + 1;
	cout << mex << endl;
	int y;
	cin >> y;
	while (y != -1) {
		cout << y << endl;
		cin >> y;
	}
}

int main() {
	int t;
	cin >> t;
	while (t--)
		solve();

	return 0;
}

If $$$k = 1$$$, then we can change $$$b_i$$$ to $$$i$$$, so the answer is YES only if $$$b_i = i$$$, otherwise the answer is NO.

Otherwise, let's build an undirected graph with $$$n$$$ vertices and edges ($$$i, b_i$$$). Any component of this graph will look like a cycle (possibly of size $$$1$$$) to each vertex of which a tree is attached (possibly empty).

Now it is claimed that if the cycle in each component has a size exactly $$$k$$$, then the answer is YES, otherwise NO.

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

#include <bits/stdc++.h>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        int n,k;
        cin >> n >> k;
        int b[n];
        int vis[n];
        for(int j = 0;j < n;++j)
        {
            cin >> b[j];
            vis[j] = 0;
        }
        if(k == 1)
        {
            int no = 0;
            for(int j = 0;j < n;++j)
            {
                if(b[j] != j+1)
                {
                    no = 1;
                }
            }
            cout << (no ? "NO\n" : "YES\n");
            continue;
        }
        int num[n];
        int no = 0;
        int tgr = 1;
        for(int j = 0;j < n;++j)
        {
            if(!vis[j])
            {
                int ind = j;
                int cnum = 0;
                while(!vis[ind])
                {
                    vis[ind] = tgr;
                    num[ind] = cnum++;
                    ind = b[ind]-1;
                }
                if(vis[ind] != tgr)
                {
                    tgr++;
                    continue;
                }
                if(cnum-num[ind] != k)
                {
                    no = 1;
                    break;
                }
                tgr++;
            }
        }
        cout << (no ? "NO\n" : "YES\n");
    }
}

Let's make queries to subarrays starting at positions $$$1$$$, $$$k + 1$$$, $$$2k + 1$$$, $$$\ldots$$$ $$$m \cdot k + 1$$$, as long as these queries are valid, meaning their right boundary does not exceed $$$n$$$. Let's save the $$$\operatorname{XOR}$$$ of all the answers to these queries. We will call these queries primary.

Now, we will shift the last subarray of the query one unit to the right and make a new query, as long as the right boundary does not exceed $$$n$$$. We will call these queries secondary. It is claimed that the $$$\operatorname{XOR}$$$ of the entire array will be equal to the $$$\operatorname{XOR}$$$ of all the queries. Let's prove this.

Let $$$i$$$ be the position at which the first secondary query starts. Notice that after this query, the subarray [$i$; $$$i + k - 2$$$] will turn into the subarray [$$$i + 1$$$; $$$i + k - 1$$$] and reverse. After the next query, the same thing will happen, the subarray will shift one unit to the right and reverse. Therefore, the prefixes of length $$$k-1$$$ of each secondary query will be the same, up to the reversal, which does not affect the $$$\operatorname{XOR}$$$. Since the number of secondary queries is equal to $$$n \operatorname{mod} k$$$, which is an even number, the $$$\operatorname{XOR}$$$ of these prefixes will not affect the $$$\operatorname{XOR}$$$ of all the secondary queries, which will therefore be equal to the $$$\operatorname{XOR}$$$ of the elements [$a_{i + k — 1}$; $a_n$], that is, all the elements that we did not consider in the primary queries.

The number of primary queries is equal to $$$\lfloor \frac{n}{k} \rfloor \leq k \leq 50$$$, since $$$n \leq k^2 \leq 2500$$$.

The number of secondary queries is equal to $$$n \operatorname{mod} k < k <= 50$$$, since $$$k^2 \leq 2500$$$.

The total number of queries does not exceed $$$100$$$.

#include <iostream>

using namespace std;

int ask(int i) {
	cout << "? " << i << endl;
	int x;
	cin >> x;
	return x;
}

void solve() {
	int n, k;
	cin >> n >> k;
	int res = 0;
	int i;
	for (i = 1; i + k - 1 <= n; i += k)
	    res ^= ask(i);
	for (; i <= n; ++i)
	    res ^= ask(i - k + 1);
	cout << "! " << res << endl;
}

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

Let's make queries to subarrays starting at positions $$$1$$$, $$$k + 1$$$, $$$2k + 1$$$, $$$\ldots$$$ $$$m \cdot k + 1$$$, such that the size of the uncovered part is greater than $$$2 \cdot k$$$ and not greater than $$$3 \cdot k$$$. In other words, $$$2 \cdot k < n - (m + 1) \cdot k \le 3 \cdot k$$$. Let's keep the $$$\operatorname{XOR}$$$ of all the answers to these queries. We will call these queries primary.

Let the size of the remaining (uncovered) part be $$$x$$$ ($$$2 \cdot k < x \le 3 \cdot k$$$). Let's learn how to solve the problem for an array of size $$$x$$$ in three queries.

If $$$x = 3 \cdot k$$$, simply make queries to positions $$$1$$$, $$$k + 1$$$, $$$2 \cdot k + 1$$$.

Otherwise, let $$$y = x - k$$$. Note that $$$y$$$ is even, since $$$x$$$ and $$$k$$$ are even.

Make queries at positions $$$1$$$, $$$1 + \frac{y}{2}$$$, $$$1 + y$$$.

Note that after this query, the subarray [$1$; $$$k - \frac{y}{2}$$$] will turn into the subarray [$$$y/2 + 1$$$; $$$k$$$] and reverse. After the next query, the same thing will happen, the subarray will shift one unit to the right and reverse. Therefore, the prefixes of length $$$k - \frac{y}{2}$$$ for each query are the same, up to the reversal, which does not affect the $$$\operatorname{XOR}$$$. Since the number of queries in the second group is $$$3$$$, which is an odd number, the $$$\operatorname{XOR}$$$ of these prefixes will be taken into account exactly once in the $$$\operatorname{XOR}$$$ of all the queries, which will therefore be equal to the $$$\operatorname{XOR}$$$ of the elements.

The number of primary queries does not exceed $$$\lfloor \frac{n}{k} \rfloor \leq k \leq 50$$$, since $$$n \leq k^2 \leq 2500$$$.

The total number of queries does not exceed $$$53$$$.

#include <iostream>

using namespace std;

int ask(int i) {
	cout << "? " << i << endl;
	int x;
	cin >> x;
	return x;
}

void solve() {
	int n, k;
	cin >> n >> k;
	int res = 0;
	int i;
	for (i = 1; n - i + 1 >= 2 * k; i += k)
		res ^= ask(i);
	if (n - i + 1 == k) {
		res ^= ask(i);
		cout << "! " << res << endl;
		return;
	}
	int y = (n - i + 1 - k) / 2;
	res ^= ask(i);
	res ^= ask(i + y);
	res ^= ask(i + 2 * y);
	cout << "! " << res << endl;
}

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

Here we say that the answer for tree $$$G'$$$ is the number of subtrees in $$$P(G')$$$ that have an isomorphic subtree in $$$P(G)$$$.

Let's find a tree $$$T$$$ of minimum size that has no isomorphic tree in $$$P(G)$$$. Let the size of tree $$$T$$$ be $$$x$$$. Then take a chain of size $$$n - x$$$, and let the root of $$$T$$$ be the kid of the last vertex on the chain. We say that this is the tree $$$G'$$$ we were looking for (with the root of $$$G'$$$ being the first vertex of the chain). The number of matching subtrees will be at most $$$x - 1$$$, since all subtrees of the vertices on the chain and the subtree $$$T$$$ itself will not have isomorphic trees in $$$P(G)$$$, because $$$T$$$ lies entirely in them, and $$$T$$$ has no isomorphic tree in $$$P(G)$$$. Therefore, the answer is not greater than $$$n - (n - x) - 1 = x - 1$$$.

Let's prove why the answer cannot be less than $$$x - 1$$$: suppose there exists a tree $$$G*$$$ for which the answer is less than $$$x - 1$$$. Let's find a subtree of minimum size whose size is at least $$$x$$$ (it always exists, since we can take the entire tree for example). In this subtree, there are at least $$$x - 1$$$ other subtrees, whose sizes are less than $$$x$$$ (because in the previous step we chose a subtree of minimum size not less than $$$x$$$). And since all trees of size less than $$$x$$$ have isomorphic trees in $$$P(G)$$$ (by definition $$$T$$$ is the tree of minimum size that has no isomorphic tree in $$$P(G)$$$ and its size is $$$x$$$), the number of matching subtrees in tree $$$G*$$$ is at least $$$x - 1$$$, which is a contradiction.

Therefore in our case the answer is $$$x - 1$$$.

Now let's solve the second part of the problem — finding $$$T$$$. To do this, let's first find all trees of size 1, then of size 2, then 3, 4 and so on until we find a tree that has no isomorphic subtree in $$$P(G)$$$. One can see that if we generate all trees of size up to 15 we will definitely find $$$T$$$ there. Within each size, let's number the trees in the order in which we've generated them. To find all trees of size $$$x$$$ if we are given all trees of size $$$x - 1$$$ and smaller, let's say that the sizes of the children of the root of the tree we generate must not decrease, and if the sizes are the same, their positions in the order must not decrease. Then, we can iterate over the first child, then among the smaller and suitable ones, the second child, then the third, and so on until the total size of the tree becomes exactly $$$x$$$. This way, we will enumerate all trees of size $$$x$$$ in complexity of their total number (since we will not consider any tree twice and will not consider any extra trees). Let's do this until we find a tree that is not in $$$P(G)$$$.

Hashes can be used to compare trees for isomorphism. For more details, read the blog post

Time Complexity: $$$O(n \log n)$$$.

#include <bits/stdc++.h>

using namespace std;

const int MAXSZ = 15;

void rec(int ns, int last, vector<int>& now, vector<vector<int>>& aint, vector<int>& col, vector<int>& sz, int& ss, int sns) {
    if (ss < 0) {
        return;
    }
	if (ns == 0) {
		col.back()++;
		aint.push_back(now);
		ss -= sns;
		return;
	}
	for (int i = min(last, col[ns] - 1); i >= 0; i--) {
		now.push_back(i);
		rec(ns - sz[i], i, now, aint, col, sz, ss, sns);
		now.pop_back();
	}
}

void dfs(int v, int p, vector<vector<int>>& arr, vector<int>& num, map<vector<int>, int>& m, vector<int>& sz) {
	vector<int> now;
	sz[v] = 1;
	for (auto i : arr[v]) {
		if (i != p) {
			dfs(i, v, arr, num, m, sz);
			sz[v] += sz[i];
			if (sz[v] <= MAXSZ) {
			    now.push_back(num[i]);
			}
		}
	}
	if (sz[v] > MAXSZ) {
		num[v] = -1;
		return;
	}
	stable_sort(now.begin(), now.end());
	reverse(now.begin(), now.end());
	num[v] = m[now] - 1;
}

void dfs2(int x, int p, vector<vector<int>>& aint, vector<int>& ans) {
	if (p >= 0) {
		ans.push_back(p);
	}
	int now = ans.size();
	for (auto i : aint[x]) {
		dfs2(i, now, aint, ans);
	}
}

void solve() {
	int n;
	cin >> n;
	vector<vector<int>> aint(1);
	vector<vector<int>> arr(n);
	for (int i = 1; i < n; i++) {
		int a, b;
		cin >> a >> b;
		a--;
		b--;
		arr[a].push_back(b);
		arr[b].push_back(a);
	}
	map<vector<int>, int> m;
	vector<int> col(1, 0), sz(1, 1);
	col.push_back(1);
	for (int i = 2; i <= MAXSZ; i++) {
		vector<int> now;
		col.push_back(col.back());
		int ss = n;
		rec(i - 1, aint.size() - 1, now, aint, col, sz, ss, i);
		while (sz.size() < col.back()) {
			sz.push_back(i);
		}
		if (ss < 0) {
		    break;
		}
	}
	for (int i = 0; i < col.back(); i++) {
		m[aint[i]] = i + 1;
	}
	vector<int> num(n), szi(n, 1);
	dfs(0, 0, arr, num, m, szi);
	set<int> s;
	for (int i = 0; i < col.back(); i++) {
		s.insert(i);
	}
	for (auto i : num) {
		s.erase(i);
	}
	int x = *s.begin();
	vector<int> ans;
	if (sz[x] > n) {
		for (int i = 0; i < n; i++) {
			for (auto j : arr[i]) {
				if (i < j) {
					cout << i + 1 << ' ' << j + 1 << '\n';
				}
			}
		}
		return;
	}
	for (int i = 0; i < n - sz[x] - 1; i++) {
		ans.push_back(i);
	}
	dfs2(x, n - sz[x] - 1, aint, ans);
	for (int i = 0; i < ans.size(); i++) {
		cout << ans[i] + 1 << ' ' << i + 2 << '\n';
	}
}

int main() {
    	ios_base::sync_with_stdio(false);
    	cin.tie(0);
    	cout.tie(0);
	int t = 1;
	//cin >> t;
	for (int i = 0; i < t; i++) {
		solve();
	}
}