Horse-racing Duals

Horses2

Задача

Рассмотрим последнюю задачу уровня Easy с сайта codingame.com. Некоторое количество лошадей участвует в скачках и у каждой есть некая характеристика, выраженная целым числом. Формат скачек — парные заезды — и организаторы хотят, чтобы в заезде участвовали две лошади, различие между которыми (т.е. разность их характеристик) минимальна.

Входные данные

Первая строка: число  n  — количество лошадей.

Следующие  n  строк — в каждой указано одно целое число — характеристика соответствующей лошади.

 Выходные данные

Наименьшая положительная разность характеристик.

Решение

Пусть задана конечная последовательность целых чисел  a. В исходной формулировке задачи, без каких-либо оптимизаций, от нас требуют найти  [latex] D = \min_{1 \leq i < j \leq n} \left| a_{i} — a_{j} \right|[/latex]. Если решать задачу  в лоб, нам понадобятся два цикла: один пробегает все значения по   i, а другой — все значения по  [latex] j > i [/latex]. На каждом шаге внешнего цикла будет проделано  [latex] n — i [/latex] шагов внутреннего. Итого получаем приблизительную оценку сложности такого алгоритма:  [latex] n\left( n — i \right)[/latex], что асимптотически эквивалентно  [latex] n^2 [/latex].

Оказывается, можно решить задачу «проще». Как утверждают авторитетные источники, сложность встроенного в стандартную библиотеку алгоритма сортировки составляет  [latex] O(n \cdot \log \left( n \right) [/latex], что при больших значениях  n  лучше, чем  [latex] n^2 [/latex]. Пусть  b  —  конечная последовательность, в которой элементы последовательности  a  расположены по возрастанию. Поскольку множество значений у этих последовательностей одинаково, имеем: [latex] D = \min_{1 \leq i < j \leq n} \left| a_{i} — a_{j} \right| [/latex]. Однако нам уже не нужен двойной цикл. Благодаря монотонному возрастанию последовательности  b,  при любом   [latex] i [/latex]   имеем  [latex] b_{i+1} — b_{i} > 0 [/latex] и при любых  [latex] i,j [/latex]  если  [latex]i < j[/latex], то  [latex] b_{j} — b_{i} \geq b_{i+1} — b_{i}[/latex].

Значит, [latex] D = min_{1 \leq i \leq n} \left( b_{i+1} — b_{i} \right) [/latex], а эту проверку можно провести за  n  действий. Таким образом, новая сложность составит примерно  [latex] n \cdot log(n) + n [/latex], что асимптотически эквивалентно  [latex] n \cdot log(n) [/latex]  и, значит, для больших значений лучше «безоптимизационного» подхода.

Код на С++

Код на Java

Подтверждение

Horses3

Horses

 

Вустянюк Ігор Дмитрович
Вустянюк Ігор Дмитрович

Latest posts by Вустянюк Ігор Дмитрович (see all)

3 thoughts on “Horse-racing Duals

Добавить комментарий