GlebsHP's blog

By GlebsHP, history, 4 years ago, In Russian,

Это был бы самый обычный разбор, если бы не новая фича — спойлеры. Заценить как это круто и удобно можно уже прямо в этом посте, к каждой задаче под спойлером прикладывается код решения. Скажем спасибо kuviman :)

Текст разбора: MikeMirzayanov, fcspartakm и GlebsHP.

637A - Voting for Photos

Автор идеи: MikeMirzayanov. Разработка: fcspartakm.

Для решения данной задачи достаточно было проитерироваться по поставленным лайкам в хронологическом порядке и в отдельном массиве поддерживать количество лайков, которые уже были поставлены фотографиям (например, в cnt[i] будет храниться количество лайков, поставленных i-й фотографии). Для нахождения ответа достаточно на каждой итерации обновлять имеющийся максимум лайков текущим значением cnt[i], и если cnt[i] > maxCnt обновлять ответ, где maxCnt — это текущее максимальное количество лайков.

Асимптотика такого решения — O(n), где n — количество поставленных лайков.

Пример решения

637B - Chat Order

Автор идеи: GlebsHP. Разработка: fcspartakm.

Для решения данной задачи нужно проитерироваться в обратном порядке по адресатам сообщений, начиная с последнего, так как верно то, что чем позднее Поликарп отправит сообщение какому-то собеседнику, тем выше этот собеседник будет в списке чатов. На каждой итерации нужно проверять, что текущий собеседник еще не был добавлен в список чатов (то есть Поликарп еще не писал ему сообщение). Это можно сделать с помощью структуры данных set. Таким образом, если текущего собеседника еще нет в списке чатов, нужно добавить имя этого собеседника в конец ответного списка чатов и добавить имя этого собеседника в set.

Асимптотика такого решения — O(n·log(n)), где n — количество сообщений, отправленных Поликарпом.

Пример решения

637C - Promocodes with Mistakes

Автор идеи: GlebsHP. Разработка: GlebsHP.

Для начала научимся решать задачу проверки фиксированного значения k. Правда ли, что если мы в каждом промокоде совершим не более чем k ошибок, ты мы сможем однозначно идентифицировать исходных промокод? Иначе говоря, верно ли, что для любой последовательности из шести цифр, существует не более одного промокода отличающегося от данной последовательности в k или менее позициях.

Для каждого промокода можно построить множество последовательностей отличающихся от него не более чем в k позициях, то есть шар радиуса k в данной метрике. Так, для промокода 123456 подойдут последовательности ?23456, 1?3456, 12?456, 123?56, 1234?6 и 12345? (вопросик заменяется на любую цифру). Очевидно, что некоторое k подходит, если никакие два шара радиуса k не пересекаются. Этого уже достаточно для решения задачи, просто честно перебрать значения k и проверить наличие пересечения шаров. Единственная тонкость — процесс необходимо остановить как только найдётся любая последовательность принадлежащая двум шарам.

Благодаря условию n ≤ 1000 задачу можно было решить и гораздо проще. Заметим, что два шара радиуса k пересекаются если расстояние между их центрами не превосходит k. Таким образом достаточно найти пару прокодов с минимальным расстоянием между ними и выбрать максимальное подходящее k. Не забываем про случай n = 1.

Пример решения

637D - Running with Obstacles

Автор идеи: MikeMirzayanov. Разработка: fcspartakm.

В самом начале отсортируем все координаты препятствий по возрастанию. Затем воспользуемся следующим фактом: если спортсмен может преодолеть препятствие номер x и успевает разбежаться перед прыжком до препятствия номер x + 1 (то есть s ≤ a[x + 1] - a[x] - 2, где s — длина разбега перед прыжком), ему выгодно разбежаться и начать новый прыжок в точке a[x + 1] - 1.

Таким образом, для решения задачи достаточно проитерироваться по препятствиям слева направо. Пусть спортсмен преодолеть препятствие с номером i. Тогда нужно найти первое такое препятствие с номером j (правее i), что спортсмен успеет разбежаться для прыжка после препятствия j - 1 и до препятствия j. В таком случае спортсмену необходимо выполнить прыжок из точки a[i + 1] - 1 в точку a[j - 1] + 1. Если расстояние между этими точками больше чем d, значит спортсмен не сможет добраться до финиша. В противном случае нужно выполнить такой прыжок и продолжить работу программы. После преодоления всех препятствий нужно проверить нужно ли спортсмену бежать до финишной точки, или он уже находится в ней.

Асимптотика такого решения — , где n — количество препятствий.

Пример решения
 
 
 
 
  • Vote: I like it
  • +71
  • Vote: I do not like it

»
4 years ago, # |
  Vote: I like it +51 Vote: I do not like it
Spoiler