EVO проти STI#493

EVO проти STI (Розбір)

Автор, розробник, автор розбору: Тимур Дегтеарі

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

Визначимо два допоміжні масиви:

  • c_i = e_i - s_i (позитивний, коли STI Guy швидший на трасі )

  • d_i = s_i - e_i (позитивний, коли EVO Guy швидший на трасі )

Нехай c' буде масивом , відсортованим у невисхідному порядку, а d' буде масивом , відсортованим у невисхідному порядку.

Оптимальний вибір трас для EVO Guy, щоб виграти, складається з префікса c'. Аналогічно, оптимальний вибір для STI Guy, щоб виграти, складається з префікса d'.

Для того, щоб EVO Guy виграв, нам потрібно: [_трасу i обрано c_i < 0]

Припустимо, що — найбільша підмножина трас, така що \sum_{c_i \in S} c_i < 0, і не відповідає префіксу c'. Оскільки c' відсортований у невисхідному порядку, заміна на префікс c' такої ж величини дасть суму, яка не перевищує початкову суму. Отже, префікс принаймні такий же хороший, як (і часто кращий за) будь-яку іншу підмножину такої ж величини.

За симетричним аргументом, те ж саме стосується перемоги STI Guy, використовуючи масив d'.

  1. Обчисліть масиви і з вхідних даних.

  2. Відсортуйте обидва масиви у невисхідному порядку.

  3. Для кожного масиву знайдіть довжину найдовшого префікса, сума якого строго менша за .

  4. Ці довжини дають R_E (для EVO Guy, використовуючи масив c') і R_S (для STI Guy, використовуючи масив d').

Примітка: Якщо жоден префікс не має негативної суми, відповідь дорівнює , що означає, що гонщик не може виграти незалежно від вибору трас.

Часова складність: O(n \log n) через сортування. Обчислення префіксної суми — .