Задача "Магический массив" (A в div1, B в div2).
Несложно заметить, что массив, в котором минимум и максимум совпадают, есть массив из одинаковых чисел. В противном случае, найдется хотя бы пара различных чисел, а значит минимум и максимум никак не смогут совпасть.
Поэтому решение у задачи следующее: выделим отрезки подряд идущих одинаковых чисел. Пусть длина очередного отрезка равна len. Тогда к ответу нужно добавить треугольное число len * (len + 1) / 2. Асимптотическая сложность решения O(N).
Распространённой ошибкой многих участников было использование 32-ух битного типа данных. Очевидно, что ответ на задачу пропорционален квадрату. Подсказкой служила фраза из условия, но многие оказались невнимательны.
Задача "Биатлон" (C в div2).
Отсортируем все круги относительно их центра (координаты x). Поскольку окружности не вкладывались и не пересекались (только касались), то после сортировки окружности будут идти одна за другой слева направо.
Теперь будет по очереди отвечать на запросы. Пусть координаты очередного точки (x, y). Теперь давайте поймем, в какие окружности этот выстрел мог попасть. Если посмотреть только на координату x этой точки, то становится понятно, что либо это точка попадет в один какой-то круг, либо на границу каких то двух или же не попадет никуда.
Подберем бинпоиском именно это "примерное" место попадания выстрела в исходные мишени. Для удобства в реализации, просто посмотрим пару окружностей слева и справа от найденной и запишем в ответ для них номер этой точки (если эти круги еще не были закрыты).
Итого получаем решение со сложностью O(M * log N). Также можно отметить, что эту задачу можно решать за линейной время с помощью двух указателей, однако из-за сортировки это решение имеет такую же сложность.
Комментарии (4)
0
