Решение задачи Одинаковая палиндромная сумма с Codeforces
С пояснением   Просмотров: 69
Ваша задача — заменить минимальное количество элементов (под заменой понимается следующая операция: выбрать некоторый индекс i от 1 до n и заменить ai на некоторое целое число в отрезке [1;k]) так, чтобы удовлетворялись следующие условия:
после всех замен все ai — положительные целые числа, не превосходящие k;
для всех i от 1 до n2 верно следующее равенство: ai+an−i+1=x, где x должен быть одинаковым для всех n2 пар элементов.
Вам нужно ответить на t независимых наборов тестовых данных.
Пояснение к задаче
Очевидно, что если мы зафиксируем значение то для каждой пары элементов есть всего три случая:
Нам нет необходимости что-то менять в этой паре;
нам необходимо заменить один элемент, чтобы исправить эту пару;
нам необходимо заменить оба элемента, чтобы исправить эту пару.
Первая часть может быть легко посчитана за , нам просто необходимо создать массив частот , где равно количеству таких пар , что .
Вторая часть менее очевидная, но все еще делается за . Давайте поймем для каждой пары минимальную и максимальную суммы, которые мы можем получить, использовав не более одной замены. Для -й пары все такие суммы будут принадлежать отрезку . Давайте сделаем на этом отрезке при помощи префикс-сумм (сделаем в левой границе, в правой границе плюс один, а затем просто посчитаем префиксные суммы на этом массиве). Пусть этот массив равен . Тогда значение будет означать количество таких пар, что нам необходимо заменить не более одного элемента в этой паре, чтобы сделать ее сумму равной .
И последняя часть может быть посчитана как . Таким образом, для суммы ответ равен . Нам просто надо взять минимальное такое значение среди всех возможных сумм от до .
Также есть другое решение, которое использует сканирующую прямую, не зависит от и работает за , но в нем нет никаких крутых идей, чтобы объяснять его здесь (главная идея все равно примерно такая же).