Решение задачи "Одинаковая палиндромная сумма" с Codeforces

С пояснением Просмотров: 9

Вам задан массив a, состоящий из n целых чисел (гарантируется, что n четное, то есть делится на 2). Все ai не превосходят некоторое число k.

Ваша задача — заменить минимальное количество элементов (под заменой понимается следующая операция: выбрать некоторый индекс i от 1 до n и заменить ai на некоторое целое число в отрезке [1;k]) так, чтобы удовлетворялись следующие условия:

после всех замен все ai — положительные целые числа, не превосходящие k;
для всех i от 1 до n2 верно следующее равенство: ai+an−i+1=x, где x должен быть одинаковым для всех n2 пар элементов.
Вам нужно ответить на t независимых наборов тестовых данных.

#include <bits/stdc++.h>

using namespace std;

int main() {
	int t;
	cin >> t;
	while (t--) {
		int n, k;
		cin >> n >> k;
		vector<int> a(n);
		for (auto &it : a) cin >> it;
		vector<int> cnt(2 * k + 1);
		for (int i = 0; i < n / 2; ++i) {
			++cnt[a[i] + a[n - i - 1]];
		}
		vector<int> pref(2 * k + 2);
		for (int i = 0; i < n / 2; ++i) {
			int l1 = 1 + a[i], r1 = k + a[i];
			int l2 = 1 + a[n - i - 1], r2 = k + a[n - i - 1];
			assert(max(l1, l2) <= min(r1, r2));
			++pref[min(l1, l2)];
			--pref[max(r1, r2) + 1];
		}
		for (int i = 1; i <= 2 * k + 1; ++i) {
			pref[i] += pref[i - 1];
		}
		int ans = 1e9;
		for (int sum = 2; sum <= 2 * k; ++sum) {
			ans = min(ans, (pref[sum] - cnt[sum]) + (n / 2 - pref[sum]) * 2);
		}
		cout << ans << endl;
	}
	
	return 0;
}

Очевидно, что если мы зафиксируем значение то для каждой пары элементов есть всего три случая:

Нам нет необходимости что-то менять в этой паре;
нам необходимо заменить один элемент, чтобы исправить эту пару;
нам необходимо заменить оба элемента, чтобы исправить эту пару.
Первая часть может быть легко посчитана за , нам просто необходимо создать массив частот , где равно количеству таких пар , что .

Вторая часть менее очевидная, но все еще делается за . Давайте поймем для каждой пары минимальную и максимальную суммы, которые мы можем получить, использовав не более одной замены. Для -й пары все такие суммы будут принадлежать отрезку . Давайте сделаем на этом отрезке при помощи префикс-сумм (сделаем в левой границе, в правой границе плюс один, а затем просто посчитаем префиксные суммы на этом массиве). Пусть этот массив равен . Тогда значение будет означать количество таких пар, что нам необходимо заменить не более одного элемента в этой паре, чтобы сделать ее сумму равной .

И последняя часть может быть посчитана как . Таким образом, для суммы ответ равен . Нам просто надо взять минимальное такое значение среди всех возможных сумм от до .

Также есть другое решение, которое использует сканирующую прямую, не зависит от и работает за , но в нем нет никаких крутых идей, чтобы объяснять его здесь (главная идея все равно примерно такая же).