Attention is all you need.

The current problems are the original A A B C D E, respectively.

The idea for problem D came up after eating at Sushiro, and the idea for problem E came up after eating at McDonald's. However, Sushiro is not a buffet restaurant. :(

The intended solutions are short.

Some (very) strong testers couldn't solve E when testing, and that's why we gave E so much score.

When $$$s$$$ is lexicographically equal to or greater than the reversal of $$$s$$$, is it possible to make $$$s$$$ universal by performing the operations?

If possible, what is the minimum number of the operations required to make $$$s$$$ universal?

Case 1. If $$$s$$$ contains only one kind of letter, the answer will be NO.

Case 2. If $$$s$$$ is universal already, no operation is needed, and the answer will be YES.

Otherwise, $$$s$$$ falls into the following Case 3.

Case 3.1. When $$$s$$$ is not a palindrome, one can make $$$s$$$ universal in one operation by swapping the first pair of different letters of $$$s$$$ and its reversal.

Case 3.2. When $$$s$$$ is a palindrome, swapping any two distinct letters will make $$$s$$$ no longer a palindrome. Note that the reversal of $$$s$$$ after the swap can be obtained by swapping the letters in the symmetric positions of the original $$$s$$$. Since either $$$s$$$ or its reversal is universal, the original $$$s$$$ can be made universal in one operation.

Thus, for Case 3, the answer will be NO if no operation can be performed; otherwise, the answer will be YES.

getint = lambda: int(input())
getints = lambda: map(int, input().split())

def solve():
	n, k = getints()
	s = input().strip()
	if s < s[::-1] or (k >= 1 and min(s) != max(s)):
		print('YES')
	else:
		print('NO')

t = getint()
for _ in range(t):
	solve()

Before the last operation, what should the array be to obtain $$$0$$$?

How to make all the elements in the array non-zero?

Note that before the last operation, all the integers in the array should be positive. Thus, we aim to turn the zeroes in $$$a$$$ into non-zeroes. To achieve this, we split the given array $$$a$$$ into two halves and perform the operations on the halves that contain zeroes. After that, there will be no zeroes in either of the two halves. The final $$$0$$$ can be obtained by performing the last operation on the entire array.

In fact, the final element can be $$$0$$$ after the operations for any array of length $$$4$$$. Can you solve the problem under the constraint of $$$n=4$$$?

When $$$n \gt 4$$$, you can perform the operation on any subarray of length $$$(n-3)$$$. After the operation, the array $$$a$$$ will contain only $$$4$$$ integers, which can be solved by brute force.

getint = lambda: int(input())
getints = lambda: map(int, input().split())

def solve():
	n = getint()
	a = list(getints())
	op = []
	mid, r = n // 2, n
	if 0 in a[mid:]:
		op.append([mid + 1, n])
		r -= n - mid - 1
	if 0 in a[:mid]:
		op.append([1, mid])
		r -= mid - 1
	op.append([1, r])
	print(len(op))
	for o in op:
		print(*o)

t = getint()
for _ in range(t):
	solve()

The formula $$$(x+k) + (y+k) = (x+k) \oplus (y+k)$$$ is equivalent to $$$(x+k) \mathbin{\&} (y+k) = 0$$$, where $$$\&$$$ denotes the bitwise AND operation.

Note that a power of $$$2$$$ shares no common bits with any positive integer less than it.

It can be shown that such an non-negative integer $$$k$$$ does not exist when $$$x=y$$$.

When $$$x\neq y$$$, one can show that $$$k = 2^n - \max(x, y)$$$ is a possible answer, where $$$2^n$$$ is a power of $$$2$$$ that is sufficiently large.

getint = lambda: int(input())
getints = lambda: map(int, input().split())

def solve():
	x, y = getints()
	if x == y:
		print(-1)
	else:
		print(2 ** 48 - max(x, y))

t = getint()
for _ in range(t):
	solve()

Do not go for DP.

How many plates of sushi can be taken?

What are the constraints on the time of taking plates of sushi?

Note that the last $$$i$$$-th time taking a plate of sushi should be no later than the $$$(n - i\cdot(k+1) + 1)$$$-th minute. This constraint limits the time that a taking action can be performed. Therefore, we enumerate the $$$n$$$ minutes in chronological order, and greedily take the untaken plates delivered before with the greatest deliciousness when we reach a constraint, i.e., the current minute is the $$$(n - i\cdot(k+1) + 1)$$$-th minute for a certain $$$i$$$. The deliciousnesses of the untaken plates can be maintained by a heap. The total complexity is $$$O(n \log n)$$$.

#include <cstdio>
#include <queue>

using namespace std;

const int N = 2e5 + 5;

int n, k;
int d[N];
long long ans;

void solve() {
	scanf("%d%d", &n, &k);
	ans = 0;
	priority_queue <int> q;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &d[i]);
		q.push(d[i]);
		if ((n - i + 1) % (k + 1) == 0) {
			ans += q.top();
			q.pop();
		}
	}
	printf("%lld\n", ans);
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--)
		solve();
	return 0;
}

What happens when an integer $$$a_i$$$ mods $$$k$$$?

Note that the difference between $$$a_i$$$ and $$$b_i$$$ is a multiple of $$$k$$$.

The same holds for the difference between the sum of $$$a_i$$$ and the sum of $$$b_i$$$.

Notice that $$$d(n) \leq 2304$$$ holds for all $$$n \leq 10^{10}$$$, where $$$d(n)$$$ denotes the number of divisors of $$$n$$$.

Note that if such a magic number $$$k$$$ exists, it will be a divisor of $$$\Delta = \sum a_i - \sum b_i$$$ when $$$\Delta \neq 0$$$, or it can be any integer greater than all the $$$a_i$$$. Thus, we can check all the divisors of $$$\Delta$$$, resulting in a solution of $$$O\left(\sum (n \cdot d(\sum a_i) + \sqrt{\sum a_i})\right)$$$ time, where $$$d(n)$$$ denotes the number of divisors of $$$n$$$.

#include <cstdio>

using namespace std;

const int N = 1e4 + 5;
const int C = 1e6 + 5;

int n;
int a[N], b[N];
int cnt[C];
long long s;

bool check(int k) {
	for (int i = 1; i <= n; i++)
		cnt[a[i] % k]++;
	for (int i = 1; i <= n; i++)
		if (--cnt[b[i]] < 0) {
			cnt[b[i]] = 0;
			for (int i = 1; i <= n; i++)
				cnt[a[i] % k] = 0;
			return 0;
		}
	return 1;
}

void solve() {
	scanf("%d", &n);
	s = 0;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		s += a[i];
	}
	for (int i = 1; i <= n; i++) {
		scanf("%d", &b[i]);
		s -= b[i];
	}
	if (s == 0) {
		printf("%d\n", check(0xc0ffee) ? 0xc0ffee : -1);
		return;
	}
	for (int i = 1; 1ll * i * i <= s; i++)
		if (s % i == 0) {
			if (check(i)) {
				printf("%d\n", i);
				return;
			}
			if (i < C && check(s / i)) {
				printf("%d\n", (int)(s / i));
				return;
			}
		}
	printf("-1\n");
}

int main() {
	int t;
	scanf("%d", &t);
	while (t--)
		solve();
	return 0;
}

Consider the integers in the colorful subarray after swapping.

How to gather these integers together, forming a colorful subarray, with the minimum number of swaps?

Consider the middle one among all the the elements in the colorful subarray.

Consider the elements in the colorful subarray after swapping. The first observation is as follows.

Observation. Mark the elements in the colorful subarray. Before swapping, to make these marked elements continuous, gathering them toward the middle one among them minimizes the number of swaps.

Proof. It is not optimal to swap two marked elements. Thus, the leftmost $$$x$$$ elements will move to their right, and the rightmost $$$(k-x)$$$ elements will move to their left. They will meet at some point between the $$$x$$$-th element and the $$$(x+1)$$$-th element. If $$$x \lt {k\over 2}$$$, adjusting the meeting point to its right reduces $$$(k-x)-x \gt 0$$$ swaps. If $$$x \gt {k\over 2}$$$, we can adjust it to its left and reduce the number of swaps similarly. Therefore, one can show that setting the meeting point to the middle of them is optimal through adjustments. $$$\square$$$

From the observation we can also conclude that, the minimum number of swaps required to make the marked elements continuous is the difference between the sum of the distances from each marked element to the middle position before swapping and that sum after swapping, if the marked elements are swapped toward the middle position. Notice that the latter sum is a fixed constant only related to $$$k$$$.

Focusing on the middle position of the colorful subarray, we enumerate all the positions in the array as possible middle positions. For each possible middle position $$$p$$$, to form the colorful subarray whose middle position is $$$p$$$, we should choose $$${k\over 2}$$$ distinct integers from its left and the other $$$k\over 2$$$ from its right. The rounding of $$$k\over 2$$$ will not affect the correctness as long as the sum of the rounded numbers is $$$k$$$.

For each $$$1\leq i\leq k$$$, we should determine whether $$$i$$$ should be chosen from the left side of $$$p$$$ or the right side of $$$p$$$. Let the distance from $$$p$$$ to the rightmost integer $$$i$$$ on its left be $$$l_i$$$, and the distance for the right side be $$$r_i$$$. We should choose either $$$l_i$$$ or $$$r_i$$$ for each $$$i$$$ under the constraint that both the number of chosen $$$l_i$$$ and that of $$$r_i$$$ are $$$k\over 2$$$, minimizing the sum of the distances we choose. This can be done by first forcing to choose all the $$$l_i$$$, and then choosing the smallest $$$k\over 2$$$ elements of $$$(r_i-l_i)$$$ greedily.

In implementation, when enumerating the middle position $$$p$$$, both $$$l_i$$$ and $$$r_i$$$ can be simply calculated in $$$O(n)$$$ time, and then sort $$$(r_i - l_i)$$$ in $$$O(n\log n)$$$ time. The total complexity is $$$O(n^2\log n)$$$.

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 3005;
const long long oo = 1e18;

int n, k;
int a[N], l[N], r[N], d[N];
long long ans;

void solve() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++)
		scanf("%d", &a[i]);
	ans = oo;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= k; j++)
			l[j] = r[j] = n + 1;
		for (int j = i; j; j--)
			l[a[j]] = min(l[a[j]], i - j);
		for (int j = i; j <= n; j++)
			r[a[j]] = min(r[a[j]], j - i);
		long long s = 0;
		for (int j = 1; j <= k; j++) {
			s += l[j];
			d[j] = r[j] - l[j];
		}
		sort(d + 1, d + k + 1);
		for (int j = 1; j <= (k + 1) / 2; j++)
			s += d[j];
		ans = min(ans, s);
	}
	for (int i = 1; i <= k; i++)
		ans -= abs(i - (k + 1) / 2);
	printf("%lld\n", ans);
}

int main() {
	int T;
	scanf("%d", &T);
	while (T--)
		solve();
	return 0;
}

Is it possible to simplify the constraints?

Is it possible to remove the constraint that exactly $$$k\over 2$$$ elements should be chosen from both sides of the enumerated position?

Optimizing the solution of F1 using (possibly, heavy) data structures results in a $$$O(n\log n)$$$ solution.

Here we introduce a linear approach for F2 came up by Error_Yuan. In fact, the following proposition holds.

Proposition. The answer obtained is still correct without the constraint that exactly $$$k\over 2$$$ elements should be chosen from both sides of the enumerated position.

Without the constraint, when enumerating the position $$$p$$$, we can directly choose the smaller one between $$$l_i$$$ and $$$r_i$$$ for each $$$1\leq i\leq k$$$.

Proof. On the one hand, notice that the distance sum will not be smaller when $$$p$$$ is not the middle position among the chosen elements. On the other hand, consider the colorful subarray that produces the optimal answer, and mark the elements in it first. When $$$p$$$ enumerates to the middle position of the marked elements before swapping, the minimal distance sum without the constraint is no greater than that under the constraint. Therefore, all the considered candidates are no less than the real answer, and the real answer can be reached, completing the proof. $$$\square$$$

In implementation, we consider the contribution to each position $$$p$$$ for each integer $$$1\leq i\leq k$$$. For a certain $$$i$$$, it can be shown that the delta of the contribution will be one of $$$-1$$$, $$$0$$$, or $$$+1$$$ when $$$p$$$ moves to an adjacent position. The delta of the contribution remains unchanged for most positions, and only changes either at the position where $$$i$$$ placed, or at the midpoint between two adjacent $$$i$$$. By pre-calculating the changes of contribution deltas over all the $$$i$$$ and performing the prefix sum on the array twice, we can obtain the distance sums, resulting in an $$$O(n)$$$ solution.

#include <cstdio>
#include <algorithm>

using namespace std;

const int N = 4e5 + 5;
const long long oo = 1e18;

int n, k;
int a[N];
int last[N], dd[N];
long long s, d, ans;

void solve() {
	scanf("%d%d", &n, &k);
	for (int i = 1; i <= n; i++)
		last[i] = dd[i] = 0;
	s = 0;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
		if (!last[a[i]])
			s += i - 1;
		else {
			int pre = last[a[i]];
			int mid = (pre + i) / 2;
			if ((pre + i) & 1) {
				dd[mid]--;
				dd[mid + 1]--;
			} else
				dd[mid] -= 2;
		}
		dd[i] += 2;
		last[a[i]] = i;
	}
	ans = oo;
	d = -k;
	for (int i = 1; i <= n; i++) {
		ans = min(ans, s);
		d += dd[i];
		s += d;
	}
	for (int i = 1; i <= k; i++)
		ans -= abs(i - (k + 1) / 2);
	printf("%lld\n", ans);
}

int main() {
	int T;
	scanf("%d", &T);
	while (T--)
		solve();
	return 0;
}