Идея: нужно разбить массив на три непересекающихся отрезка подряд так, чтобы суммы этих частей удовлетворяли условию задачи. Возможны два подхода.
Брутфорс. Перебираем все пары (l,r), где 1 ≤ l < r ≤ n-1. Для каждого варианта считаем: — sum(x) = prefix[l], — sum(y) = prefix[r] — prefix[l], — sum(z) = prefix[n] — prefix[r]. Проверяем условие. Если вычислять суммы напрямую, будет O(n³). С префиксными суммами — O(n²). Работает при маленьких ограничениях.
Конструктив. Рассмотрим свойства суммы всего массива: — Если total % 3 ≠ 0 и total % 2 ≠ 0, то равные разбиения невозможны. — Если total % 3 == 0, можно попытаться сделать все три суммы равными (каждая = total/3). Тогда нужно найти такие l,r, где prefix[l] = total/3 и prefix[r] = 2*total/3. Это делается линейным проходом. — Если total % 2 == 0, можно попробовать разбиение на две равные части и третью отличную. Тогда проверяем, есть ли r, где prefix[r] = total/2.
Часто достаточно зафиксировать l=1, r=n-1. Тогда x = a₁, z = aₙ, y = всё между ними. Если условия на суммы выполняются — решение готово. Если нет, можно линейным перебором сдвинуть l и искать r.
Сложность: — Конструктив: O(n). — Брутфорс: O(n²) с префиксами. — Память: O(n) на префиксы.
--- Хочешь, я ещё добавлю схему «если sum делится на 3 → ищем равные трети, если на 2 → ищем половину», прям как дерево решений?
Сложность: O(n) — O(n²) в зависимости от проверки; брутфорс — O(n²) с префиксами.
Идея (интуиция): Нужно сделать как можно больше элементов «не на своём месте» по сравнению с отсортированным вариантом. Нули можно заменить на отсутствующие элементы так, чтобы они оказались максимально вне своих целевых индексов.
Подход:
- Построить отсортированную версию массива (целевая позиция для каждого значения).
- Собрать все отсутствующие в исходном элементы — кандидаты для подстановки в нули. Лучше брать наибольшие отсутствующие.
- Заполнить нули этими значениями.
- После замены задача сводится к поиску максимальной длины отрезка, в котором a[i] != target_pos_of(a[i]). Это решается двумя указателями: расширяем правый, пока условие выполняется, при нарушении сдвигаем левый.
Сложность: сортировка + двухуказатель → O(n log n).
Замечания: аккуратно работать с множественными одинаковыми значениями и индексированием в отсортированном массиве (использовать multimap/вектор позиций).
Идея (динамика по позиции и состоянию swap): На каждом индексе можно либо сделать swap между a[i] и b[i], либо не делать. Включение индекса в хорошее множество зависит от соседних сравнений. Поэтому держим два состояния для позиции i:
dp[i][0] — количество способов (или достижимость), если на i не сделали swap. dp[i][1] — если на i сделали swap.
Переходы (условия): Чтобы перейти в dp[i][1], нужно, сравнив с i-1, чтобы условия после и перед swap'ов выполнялись: — если и на i-1 была swap: b[i-1] <= a[i] и a[i-1] <= b[i] — если на i-1 не было swap: a[i-1] <= a[i] и b[i-1] <= b[i] Аналогичные проверки для dp[i][0].
Таким образом на каждом i обновляем dp[i][0] и dp[i][1] суммируя допустимые переходы из i-1. Не забываем про модуль, если нужно считать числа способов.
Сложность: O(n) по времени и O(1) по памяти (храним только предыдущий слой).
Идея (группировка + префикс частот): Если фиксировать d, итоговые значения группируются по диапазонам длины d: [1..d], [d+1..2d], ... Для каждого диапазона все числа переходят в одно значение (value_level).
Алгоритм:
- Посчитать частоты каждого числа до mx = max(a).
- Построить префикс частот pref, чтобы быстро получить количество элементов в любом числовом диапазоне [L..R] как pref[R] — pref[L-1].
- Для каждого d от 1 до mx: — Итерируем по диапазонам длины d: [1..d], [d+1..2d], ... — Через pref получаем количество элементов cnt в каждом диапазоне. — Вычисляем вклад диапазона в итоговую сумму: cnt * value_level (value_level = (R)/d округлённо вверх или по нужной формуле). — Если есть лишние элементы, которые нельзя покрыть (d — cnt), учитываем штраф/уменьшение.
- Для каждого d суммируем вклад по всем диапазонам и обновляем максимум.
Почему это быстро: суммарно для всех d работа примерно mx * (1 + 1/2 + 1/3 + ...) = mx * log(mx).
Сложность: ~ O(mx * log mx), где mx = max(a), с O(mx) памяти на частоты и префиксы.
Замечания: аккуратно работать с границами диапазонов, округлением вверх и пустыми диапазонами.
