Разбор задач VK Cup 2016 — Квалификация 1

Revision ru1, by GlebsHP, 2016-03-14 18:01:01

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

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.

Для ускорения работы программы можно было складывать в 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, значит спортсмен не сможет добраться до финиша. В противном случае нужно выполнить такой прыжок и продолжить работу программы. После преодоления всех препятствий нужно проверить нужно ли спортсмену бежать до финишной точки, или он уже находится в ней.

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

Пример решения
Tags разбор задач, vkcup2016

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
ru5 Russian GlebsHP 2016-03-14 18:49:48 39 Мелкая правка: 'dash; $O(n)$, где $' -> 'dash; $O(n \log n)$, где $'
ru4 Russian MikeMirzayanov 2016-03-14 18:31:54 145
ru3 Russian MikeMirzayanov 2016-03-14 18:29:07 45 Мелкая правка: 'ибо [user:mikemirzayanov,2016-03-1' -> 'ибо [user:kuviman,2016-03-1'
ru2 Russian GlebsHP 2016-03-14 18:10:00 144 (опубликовано)
ru1 Russian GlebsHP 2016-03-14 18:01:01 7149 Первая редакция (сохранено в черновиках)