Розбір

Спочатку необхідно окремо розглянути випадок, коли $k=0$. У такому випадку ми не можемо зменшити жодне число, а тому якщо є хоча б одне число $a_i>0$, то відповідь дорівнює $-1$. Інакше усі числа вже спочатку є недодатними, тому можно зробити $0$ операцій.

Тепер розглянемо послідовно рішення на кожну групу тестів для $k>0$:

Блок 1

У першій групі значення $t=0$, а тому за одну операцію можна просто зменшити будь-яке число $k$. Для того, щоб зробити значення $a_i$ недодатним, необхідно виконати з ним хоча б $\lceil \frac{max(0,a_i)}{k}\rceil$ операцій. А тому мінімальна кількість операцій, за яку можна зробити усі числа недодатними, дорівнує $\sum _{i=1}^n\lceil \frac{max(0,a_i)}{k}\rceil$.

Розв'язок: https://pastebin.com/9H9Z2txE

Блок 2

Для розв'язання цієї групи потрібно було визначити критерій того, що можливо зробити усі числа недодатніми рівно за $x$ операцій. Для цього спробуємо звести задачу до випадку $t=0$. А саме, скажемо, що за одну операцію ми збільшуємо усі $n$ чисел на $t$, та зменшуємо одне число $a_i$ на $(k+t)$. Неважко побачити, що така операція еквівалентна операції з умови. З таким визначенням можна сказать, що після виконання $x$ операцій усі $a_i$ збільшаться на $xt$. Після цього для того, щоб робити число $(a_i+xt)$ недодатним, потрібно виконати з ним хоча б $\lceil \frac{max(0,a_i+xt)}{k+t}\rceil$ операцій. А тому отримуємо доволі простий критерій: усі числа можна зробити недодатними рівно за $x$ операцій тоді і тільки тоді, коли $\sum _{i=1}^n\lceil \frac{max(0,a_i+xt)}{k+t}\rceil \le x$.

Маючи цей критерій може здатися, що можна зробити звичайний бінарний пошук по відповіді. Але таке рішення є неправильним, оскільки не завжди існує відповідь, що використовує рівно $(x+1)$ операцій навіть тоді коли, існує відповідь, що використовує рівно $x$ операцій. Наприклад на тесті $n=2,k=100,t=99,a_1=1,a_2=1$, можна зробити усі числа недодатними за $2$ операції, але не можна за $3$.

Можна довести, що коли відповідь існує, вона не перевищує $nm$, де $m=\max (0,\underset{i=1}{\overset{n}{\max }}{a}_i)$. А тому можна перевірити усі можливі варіанти відповіді від 0 до $nm$, використовуючи описаний вище критерій. Для перевірки критерію необхідно зробити $n$ операцій, а тому загальна складність такого рішення — $O(n^{2}m)$.

Розв'язок: https://pastebin.com/E2Q58fqX

Блок 3

Будемо підтримувати поточну відповідь $x$, яка спочатку дорівнює нулю, а також масив $cnt$, де $cn{t}_i$ позначає кількість операцій, зроблених з позицією $i$. На черговій ітерації алгоритму переберемо усі позиції $i=1\dots n$. Якщо для чергової позиції виконується нерівність $\lceil \frac{max(0,a_i+xt)}{k+t}\rceil >cn{t}_i$, необхідно збільшити $cn{t}_i$ та $x$ на $(\lceil \frac{max(0,a_i+xt)}{k+t}\rceil -cn{t}_i)$. Якщо на черговій ітерації алгоритму значення $x$ не збільшилося, відповідь була знайдена. Якщо ж $x$ стало більше ніж $nm$, необхідно вивести $-1$. Можна довести, що таке рішення працює за $O(nm)$. Також можна помітити, що таке рішення зробить рівно одну ітерацію на тестах першої групи і спрацює за $O(n)$.

Розв'язок: https://pastebin.com/f0risSD7

Блок 4

Для початку зрозуміємо, як допомогає обмеження $1\le a_i$. По-перше, трохи спрощується критерій перевірки, описаний у другому пункті: $\sum _{i=1}^n\lceil \frac{a_i+xt}{k+t}\rceil \le x$. По-друге, можна помітити, що коли усі $a_i\ge 1$, з кожною позицією $i$ необхідно буде зробити хоча б одну операцію. Це означає, що у випадку, коли $k\le (n-1)t$, відповідь буде $-1$. Дійсно, припустимо що існує якась оптимальна відповідь. Оскільки с кожною позицією була виконана хоч одна операція, можемо зменшити кількість операцій з кожною позицією на $1$. Відповідь залишиться валідною, оскільки кожне $a_i$ не збільшиться. Тому ми отримали рішення з меншою кількістю операцій, що протиречить припущенню оптимальності відповіді.

Тепер розглянемо випадок коли $k>(n-1)t$. Припустимо, що рівно за $x$ операцій можна зробити усі числа недодатними. Тоді неважко побачити, що за $(x+n)$ операцій усі числа також можна зробити недодатними. Дійсно, можна просто зробити ще по одній операції з кожною позицією $i$, після чого значення на усіх позиціях зменшаться на $(k-(n-1)t)$. Саме тому можна перебрати остачу від відповіді при діленні на $n$, і зробити бінарний пошук на числах $x$ з такою остачею. Складність такого рішення $O(n^2\log ans)$.

Розв'язок: https://pastebin.com/kgUTa61U

Блок 5

На відміну від попереднього рішення, будемо перебирати остачі $rem$ ($0\le rem<n$) від відповіді при діленні на $n$ у випадковому порядку. Також будемо підтримувати мінімальну знайдену відповідь $x$ серед усіх остач, що були розглянути попередньо. Тоді перед запуском бінарного пошуку на черговій остачі перевірими, чи покращуються взагалі відповідь. Для цьго необхідно перевірити описаний раніше критерій на максимальному числі меншим за $x$ з остачею $rem$. Тільки у випадку, коли критерій виконується, треба запускати бінарний пошук. Можна довести, у такому рішенні бінарний пошук буде запускатися $O(\log n)$ разів, а тому загальна складність — $O(n^2+n\log n\log ans)$.

Розв'язок: https://pastebin.com/D8KpR3ZX

Блок 6

Для прискорення попереднього рішення навчимося рахувати суму $\sum _{i=1}^n\lceil \frac{a_i+xt}{k+t}\rceil$ швидше ніж за $O(n)$.

Для цього помітимо, що $\sum _{i=1}^n\lceil \frac{a_i+xt}{k+t}\rceil =\sum _{i=1}^n\lfloor \frac{a_i}{k+t}\rfloor +\sum _{i=1}^n\lfloor \frac{xt}{k+t}\rfloor +\sum _{i=1}^n\lceil \frac{xt\mathrm{mod}(k+t)+a_i\mathrm{mod}(k+t)}{k+t}\rceil =A+B+C$. Значення $A$ не залежить від $x$, а тому його можна підрахувати один раз до виконання всіх перевірок. Значення $B$ можна підрахувати як $B=n\cdot \lfloor \frac{xt}{k+t}\rfloor$. Нехай $xt\mathrm{mod}(k+t)=r$, та $a_i\mathrm{mod}(k+t)=b_i$. Тоді неважко побачити, що значення $\lceil \frac{r+b_i}{k+t}\rceil$ буде дорівнювати $0$ у випадку, коли $r=b_i=0$, дорівнювати $1$, коли $1\le r+b_i\le (k+t)$, та $2$ інакше. Тому значення $C$ можна підрахувати як кількість чисел у масиві $b$, що більше або дорівнюють $(1-r)$ плюс кількість чисел у масиві $b$, що більше $(k+t-r)$. Ці кількості можна знайти за допомогою бінарного пошуку, якщо попередньо відсортувати масив $b$.

Таким чином, ми навчилися перевіряти критерій за $O(\log n)$, що набагато швидше $O(n)$. Загальна складність рішення — $O(n\log n\log ans)$.

Розв'язок: https://pastebin.com/9wHi9fdg

Блок 7

Для прискорення попереднього рішення достатньо використати ідею, що була описана у п'ятому пункті. А саме необхідно запускати бінарний пошук тільки у випадку, коли відповідь для чергової остачі покращується. Складність такого рішення — $O(n\log n+{\log }^{2}n\log ans)$.

Розв'язок: https://pastebin.com/N7yFLqYE

Блок 8

Для зручності будемо вважати, що усі числа $a_i$ відсортовані за спаданням. В останніх чотирьох блоках числа $a_i$ могли бути від'ємними, але насправді це не дуже сильно ускладнює задачу. Дійсно, позначимо через $n^{\prime }$ — максимальне число не більше за $n$ таке, що $k>(n^{\prime }-1)t$. Тоді неважко довести, що хоча б одна операція могла бути виконана максимум з $n^{\prime }$ позиціями (можна провести доведення, аналогічне доведенню з пункту $4$). Це означає, що з останніми $(n-n^{\prime })$ позиціями не було проведено жодної операції.

Тоді для перших $n^{\prime }$ чисел можна розв'язати задачу так само, як і у групі $4$, а далі необхідно буде перевірити, що останні $(n-n^{\prime })$ чисел залишаться недодатними після виконання знайденної кількості операцій.

Розв'язок: https://pastebin.com/WXaDSk8n

Блок 9

Для прискорення попереднього рішення достатньо використати ідею, що була описана у п'ятому пункті. Складність такого рішення — $O(n^2+n\log n\log ans)$.

Розв'язок: https://pastebin.com/Eh5cfipg

Блок 10

Для прискорення квадратичного розв'язку необхідно навчитися швидко перевіряти критерій, описаній в пункті $2$. Відмінність від розв'язку шостої групи полягає в тому, що $a_i$ можуть бути менше нуля, а тому деякі $a_i$ не повинні додавати від'ємні значення $\lceil \frac{a_i+xt}{k+t}\rceil$ до суми.

Оскільки усі значення $a_i$ відсортовані за спаданням, то в першу чергу можна знайти максимальну позицію $i$ таку, що $a_i+xt\ge 0$. Для усіх наступних позицій внесок в шукану суму буде дорівнюавти нулю, а тому про ці позиції можна просто забути. Для знайденого префіксу позицій $1\dots i$ можна використовувати ідею з пункту $6$, але для цього потрібно навчитися швидко рахувати кількість чисел більших даного на префіксі. Це можна зробити за допомогою техніки «часткове каскадування». Ця техніка дозволяє відповідати не необхідні запити за той самий час $O(\log n)$ та потребує $O(n\log n)$ часу та пам'яті на побудову. З її допомогою можна розв'язати задачу за час $O(n\log n+n\log n\log ans)$.

Розв'язок: https://pastebin.com/U4CQse1c

Блок 11

Для прискорення попереднього рішення достатньо використати ідею, що була описана у п'ятому пункті. Складність такого рішення — $O(n\log n+{\log }^{2}n\log ans)$.

Розв'язок: https://pastebin.com/kjFkP61L

У цієї задачі також існує інше, більш просте, рішення, що було знайдено під час тестування задачі Соболєвим Євгеном. Основна ідея полягає в тому, що можна робити звичайний бінарний пошук по відповіді, але перевіряти, що відповідь уснує не у точці $mid$, а у вікні розміром $n$ на інтервалі $[mid;mid+n)$. Для того, щоб швидко перевіряти критерій, описаний раніше у пункті $2$, можна спочатку за час $O(n)$ знайти значення суми при $x=mid$. Для того, щоб перараховути значення суми при збільшенні $x$ на 1, можна було помітити, що кожен доданок суми може збільшитися максимум один раз на $1$. Дійсно, при збільшенні $x$ на 1, чисельник дробу збільшується на $t$, а знаменник рівен $(k+t)$. Оскільки виконується рівність $k>(n-1)t$, то $k+t>(n-1)t+t=nt$. Саме тому при збільшенні на $t$ лише $n$ разів, значення дробу може збільшитися максимум на $1$. Момент часу, у який це значення збільшиться, можна знайти за формулою, і у відповідний момент часу збільшити поточне значення суми на $1$. Складність такого рішення — $O(n\log ans)$.

Розв'язок: https://pastebin.com/DTmqmKBM

Зауваження та цікаві факти:

• При реалізації рішення потрібно дуже уважно слідкувати за операціями множення, щоб випадково не вийти за межі 64-бітного типу даних. Найбільш небезпечне місце, де може переповнитися 64-бітний тип — це множення $x$ на $t$ у функції перевірки (наприклад, якщо виставляти межі бінарного пошуку рівними $10^{15}$). Але можно помітити, що оскільки $k>(n-1)t$, то $nt\le 2k=2\cdot 10^9$. Оскільки відповідь не перевищує $nm$ ($x\le nm$), то $xt\le ntm\le 2\cdot 10^9\cdot 10^9=2\cdot 10^{18}$. Це означає, що у якості правої межі бінарного пошуку можна виставити значення $\frac{2\cdot 10^{18}}{t}$ та більше не думати про переповнення.

• Спочатку ця задача була запропонована на позицію «A» з неправильним авторським рішенням, описаним у пункті $2$ (звичайним бінарним пошуком по відповіді). Після знаходження правильного розв'язку складність задачі різко зросла, і задача пересунулася на останню позицію.