Розбиття на три#11811

Розбиття на три (Розбір)

Автор задачі:	Антон Тригуб
Задачу підготував:	Ігнат Жаріхін
Розбір написав:	Ігнат Жаріхін

10pt

Блок 1( $n = 3$ n = 3)

Очевидно, існує єдине можливе розбиття на три підмасиви, кожен розміром один елемент.

Блок 2( $a_{i} \leq 1$ a_i \leq 1)

Спочатку вирішимо, які будуть суми в підмасивах. Нехай змінна $c n t$ означає кількість одиничок в масиві. Логічно, кожен підвідрізок зробити за сумою якомога ближче до $⌊ \frac{c n t}{3} ⌋$ \left\lfloor \frac{cnt}{3} \right\rfloor. Якщо $c n t ∣ 3$ cnt \mid 3, то все добре і ми знайшли суми. Інакше, у нас може бути ще $1$ чи $2$ залишкові одинички, які ми не розподілили нікуди. Якщо вона одна, додаємо її в будь-який підмасив, а якщо їх дві — розподіляємо їх в будь-які два різні підмасиви.

Коли ми знаємо суми, просто проходимось по масиву і додаємо наступний елемент в поточний підмасив. Якщо досягли його суми(а пропустити її ми не можемо, бо $a_{i} \leq 1$ a_i \leq 1), зачиняємо його і відкриваємо наступний. Таким чином знаходимо межі підмасивів.

$a + b = c$ a+b=c

Блок 3(гарантується, відповідь $0$ )

Порахуємо повну суму масиву, нехай це $s u m$ . Додаткові обмеження цієї групи означають, що є таке розбиття, де всі три підмасиви мають суму $\frac{s u m}{3}$ \frac{sum}{3}. Будь-які підмасиви з іншою сумою нас взагалі не цікавлять.

Для кожного індексу $i$ порахуємо такий мінімальний індекс $n e x t_{i} \leq n$ next_i \leq n(якщо він існує), що сума на відрізку $[a, b)$ дорівнює $\frac{s u m}{3}$ \frac{sum}{3}. Якщо не існує, запам'ятаємо це.

Проходимось по масиву, перебираючи початок першого підмасиву — $i$ . Якщо не існує $n e x t_{i}$ next_i, то цей початок точно не підходить, пропускаємо. Тоді, нехай $j = n e x t_{i}$ j = next_i. Аналогічно, обов'язково треба, аби $n e x t_{j}$ next_j існував, бо інакше таке розбиття не підходить. Якщо ж він існує, ми знайшли всі три межі між підвірізками. Перші два з них мають суму $\frac{s u m}{3}$ \frac{sum}{3}, отже і третій має таку саму, тобто ми знайшли відповідь. Складність — $O (n)$

Блок 4( $n \leq 100$ n \leq 100)

Повністю переберемо три початки підмасивів, як це запропоновано в «форматі вихідних даних». Коли маємо межі $x, y, z$ x, y, z, рахуємо суми просто проходом по масиву чи префіксними сумами. Складність — $O (n^{4})$ \mathcal{O}(n^4) чи $O (n^{3})$ \mathcal{O}(n^3), в залежності від того, який метод обрати.

Надалі, всі суми будемо рахувати за допомогою префіксних сум.

Блок 5( $n \leq 2000$ n \leq 2000) та 6( $n \leq 5000$ n \leq 5000)

Переберемо лише перші два індекси. Наразі за допомогою них ми розбили масив на два підвідрізки. Один з них залишаємо, і його суму рахуємо, нехай це буде $s$ . Тепер нам залишилось розбити другий підвідрізок ще на два: префікс і суфікс. Помітимо, що багато з цих розбиттів точно не оптимальні. Інтуїтивно, нам цікаво розбити масив на два максимально рівні за сумою. Теоретично, нехай ми розбили таким чином, що суми префікса і суфікса дорівнюють $p r e f$ і $s u f f$ відповідно. Без втрати загальності, нехай $p r e f \leq s u f f$ pref \leq suff. Припустимо, що один елемент масиву(той, що зараз на межі) можна перевести з суфікса в префікс(те саме, що змістити межу на один), і при цьому нерівність залишиться вірною. Формально, $p r e f + x \leq s u f f - x$ pref+x\leq suff-x. Нам завжди буде вигідно зробити цей перехід, тому що $min (s, p r e f) \leq min (s, p r e f + x)$ \min(s,pref)\leq min(s,pref+x) і $max (s, s u f f) \geq ma x (s, s u f f - x)$ \max(s,suff)\geq max(s,suff-x), а отже відповідь буде не гіршою. Єдиний момент, коли нам може бути не вигідно робити перехід, це коли знак в нерівності змінюється. Отже, треба фактично перевірити лише два випадки: найбільший префікс, сума якого менша за суму суфікса та навпаки, найбільший суфікс, сума якого менша за суму префіксу. Зі всіх інших можна перейти в ці, не погіршуючи відповідь.

Перший варіант реалізації: після перебору перших двох індексів бінарним пошуком шукаємо переломний момент в сумах, і перевіряємо ці два випадки. Складність — $O (n^{2} \cdot lo g n)$ \mathcal{O}(n^2 \cdot\log n), проходить п'яту групу.

Другий варіант реалізації: Переломний момент шукаємо другим вказівником, який завжди рухається праворуч по циклічному масиву. Складність — $O (n^{2})$ \mathcal{O}(n^2), проходить шосту групу.

Блок 7( $n \leq 1 0^{5}$ n \leq 10^5) та 8(без додаткових обмежень)

Нехай сума всіх елементів масиву це $s u m$ . Помітимо, що в будь-якому розбитті рівно одне з наступних двох тверджень правдиве:

або рівно два масиви мають суму $\leq ⌊ \frac{s u m}{3} ⌋$ \leq \left\lfloor \frac{sum}{3} \right\rfloor і третій має суму $\geq ⌊ \frac{s u m}{3} ⌋$ \geq \left\lfloor \frac{sum}{3} \right\rfloor,
або рівно два масиви мають суму $\geq ⌊ \frac{s u m}{3} ⌋$ \geq \left\lfloor \frac{sum}{3} \right\rfloor і третій має суму $\leq ⌊ \frac{s u m}{3} ⌋$ \leq \left\lfloor \frac{sum}{3} \right\rfloor.

Переберемо розріз масиву між двома підмасивами, що обидва мають суму, не більшу за третину $s u m$ . Аналогічно до доведення з попередньої групи, з усіх таких масивів вигідно взяти найбільші за сумою з обох сторін. Це можна зробити за допомогою бінарного пошуку або двома вказівниками. Суму третього відрізка рахуємо як залишок.

Аналогічно, перебираємо розріз між двома підмасивами, що обидва мають суму, більшу за третину $s u m$ , проте тепер мінімізуємо ці два підмасиви. Кінцева складність — $O (n \cdot lo g n)$ \mathcal{O}(n\cdot\log n) з бінпошуком(7 група) та $O (n)$ зі вказівниками(повне рішення).

З точки зору реалізації, може допомогти подвоїти масив, вставивши в кінець копію початкового. Тоді замість того, щоб переходити з останнього елементу до початкового, можна просто продовжувати обхід масиву, єдине що треба буде перевірити, це те, чи не накладається кінець третього підмасиву на перший.