Олимпиадное программирование, день 1-ый

Правка ru1, от Twenty_Winter, 2020-09-13 19:23:50

Я начинаю серию записей, посвящённых моему старту подготовки к олимпиадам.

В качестве плана подготовки я выбрал темы (список может расширяться):

Рекурсия Комбинаторика Математика Математическое моделирование Структуры данных

Первой задачей стала задача на комбинаторику 1400D "Зигзаг". Её суть сводится к поиску в массиве данных двух пар одинаковых элементов. Эти пары расположены так, что первый элемент второй пары в массиве находится между элементами первой пары, а второй элемент первой пары — между элементами второй.

Первым пришедшим на ум решением стало классическое "в лоб": выбрать элемент А, после него выбрать элемент В, после него выбрать элемент равный А, а после него посчитать количество элементов равных В. Однако, это решение оказалось неспособно выдержать временной критерий, так как его асимптотическая оценка составляет n^4 (4 цикла, опирающихся на размер).

Таким образом, я встал перед выбором, модифицировать существующее или же искать абсолютно новый путь. Главные надежды возложены на проставление меток для одинаковых элементов.

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
ru1 Русский Twenty_Winter 2020-09-13 19:23:50 1120 Первая редакция (опубликовано)