The Language of Westeros#12425
Author of the problem: | Matvii Hrytsyna |
Prepared by: | Matvii Hrytsyna |
Solution: | Matvii Hrytsyna |
Idea
After an arbitrary shuffle, we still want to obtain a palindrome, so the order of elements in the initial array is not important — what matters is only how we split them into pairs. The key observation for this problem is that it is always beneficial to pair adjacent letters on the circle. Based on this, let us consider two cases.
— even
Sort the array in nondecreasing order. From the observation, we can see that there are two ways to split the elements into pairs that can give an optimal result.
({a}[1],{a}[2]),({a}[3],{a}[4]),...({a}[n-1n
({a}[2],{a}[3]),({a}[4],{a}[5]),...({a}[1],{a}[n
Let dist(x,y) denote the minimum number of operations needed to make letters and equal. Since the alphabet is cyclic, dist(x,y) = min(m,m-|x-y|). Using this formula, compute each of the two variants and choose the minimum.
— odd
First, compute two arrays and . \text{pref}[i] = \text{pref}[i-2]+dist({a}[i],{a}[i-1]), for 2\le i \le n. In other words, is the cost of splitting the prefix of array of length into pairs, while leaving one first element if is odd. Similarly, \text{suff}[i] = \text{suff}[i+2]+dist({a}[i],{a}[i+1]). Now iterate over the element that will be in the middle of the final array and compute the answer for it. If is odd, then the cost of splitting into pairs by the first method is \text{pref}[i-1]+\text{suff}[i+1], and by the second method it is \text{pref}[i-2]+ \text{suff}[i+2]+dist(a[1],a[n])+dist(a[i-1],a[i+1]). If is even, then the cost of splitting into pairs by the first method is \text{pref}[i-2]+\text{suff}[i+2]+dist({a}[i-1],{a}[i+1]), and by the second method it is \text{pref}[i-1]+\text{suff}[i+1]+dist({a}[1],{a}[n]). In addition, the cases i=1 and i=n should be handled separately.
The overall complexity is O(nlogn) due to sorting.
#include <bits/stdc++.h>
using namespace std;
const long long INF = 1e17;
void solve() {
int n, m;
cin >> n >> m;
vector<int> a(n);
for (auto &ai : a) cin >> ai;
if (n == 1) {
cout << 0 << '\n';
return;
}
sort(begin(a), end(a));
auto dist = [m](int x, int y) -> int {
return (int)min(abs(x - y), m - abs(x - y));
};
auto calc = [&](int l, int r) -> long long {
long long res1 = 0, res2 = 0;
for (int i = l; i <= r; i += 2) res1 += dist(a[i], a[i + 1]);
for (int i = l + 1; i < r; i += 2) res2 += dist(a[i], a[i + 1]);
res2 += dist(a[l], a[r]);
return min(res1, res2);
};
if (n % 2 == 0) {
long long res1 = 0, res2 = 0;
for (int i = 0; i < n; i++) {
if (i % 2 == 0 && i + 1 < n)
res1 += dist(a[i], a[i + 1]);
else if (i % 2 == 1 && i + 1 < n)
res2 += dist(a[i], a[i + 1]);
}
res2 += dist(a[n - 1], a[0]);
cout << min(res1, res2) << '\n';
} else {
long long ans = min(calc(0, n - 2), calc(1, n - 1));
vector<long long> pref(n + 1, 0), suff(n + 1, 0);
for (int i = 1; i < n; i++) {
if (i - 2 >= 0) pref[i] = pref[i - 2];
pref[i] += dist(a[i], a[i - 1]);
}
for (int i = n - 2; i >= 0; i--) {
suff[i] = suff[i + 2];
suff[i] += dist(a[i], a[i + 1]);
}
for (int i = 1; i < n - 1; i++) {
long long option_1 = 0, option_2 = 0;
if (i % 2 == 0) {
if (i > 0) option_1 = pref[i - 1];
option_1 += suff[i + 1];
if (i - 2 >= 0) option_2 += pref[i - 2];
option_2 += suff[i + 2];
option_2 += dist(a[i - 1], a[i + 1]);
option_2 += dist(a[0], a[n - 1]);
} else {
if (i > 2) option_1 += pref[i - 2];
option_1 += suff[i + 2];
option_1 += dist(a[i - 1], a[i + 1]);
option_2 = pref[i - 1];
option_2 += suff[i + 1];
option_2 += dist(a[0], a[n - 1]);
}
ans = min(ans, min(option_1, option_2));
}
cout << ans << '\n';
}
}
int main() {
int tt = 1;
cin >> tt;
while (tt--) solve();
}