Занятие №5. STL

Теория: Лекция                                           [Все занятия]

Практика:                                                [Официальная страница]

Учебные задачи:
   Задача A.
   [Сортировка]
На этой задаче можно тестировать корректность работы “быстрых” сортировок.
   Задача B.
   [Хеширование с удалением]
На момент 26Sep2011 15:59 данная реализация получала RE на 8 тесте. Верное решение 2-х летней давности получала тот же вердикт. Проблема связана с нехваткой памяти, вызванное переходом на 64 битную версию линукса, стоящего на сервере проверяющей системы. 
Эту задачу можно сдать с текущими ограничениями с помощью хеширования(алгоритм Рабина-Карпа) или с помощью построения дерева(алгоритм Ахо-Корасик), но т.к. данная задача предусматривалась в рамках учебных задач на STL, то условимся, что решение с использованием set нас полностью устраивает.
   Задача С. 
   [Двоичный поиск]
А на этой задаче можно тестировать рукописную дихотомию.
Олимпиадные задачи:
   Задача A.
   [Сплоченная команда]
Решение получилось прям очень STL’вским) Сначала сортируем игроком по их ПП. Далее последовательно перебираем пары двух игроков G1 и G2, стоящих рядом. Сумма их ПП определяет значение ПП максимального игрока G3 в команде. G3<=G1+G2. Чтобы найти позицию игрока G3 максимально удовлетворяющему игрокам G1 и G2 можно воспользоваться функцией upper_bound на отсортированном массиве игроков. Чтобы найти сумму игроков в команде за O(1), можно заранее сделать подсчет интервальных подсумм. 
   Задача B.
   [Древние цивилизации] Ответ за O(NlogN): multiset
Написал небольшого монстрика, который сильно перегружен STL. Но зато я впервые попользовался обратными итераторами (reverse_iterator). Восстановление ответа использует multiset. Это связано с компаратором. На самом деле основная идея лучше реализована в исходнике двух летней давности, который находится ниже. Там восстановление ответа написано тоже за O(NlogN), но константа будет меньше. Этот исходник выкладываю исключительно для себя, чтобы в следующий раз такого не делать).
   [Древние цивилизации] Ответ за O(N)
Самая адекватная реализации данной задачи. Очередной пример того, что не надо нагружать программу красивыми фенечками, вместо того, чтобы немного подумать. Можно заметить, что нужный интервал будет образовываться между двумя соседними историческими событиями. Под историческим событием я понимаю либо зарождение, либо гибель одной из цивилизаций. При этом левой границей интервала будет зарождение, а правой – гибель цивилизации. Крайний случай будет если нужный интервал совпадает с периодом одной из цивилизации (назовем ее цивилизации A). В крайнем случае нужно найти вторую цивилизацию, которая существовала до цивилизации A а погибла после. Это можно сделать за O(N).
   [Древние цивилизации] Ответ за O(NlogN): set [25Nov2009]
Данное решение выкладываю тоже исключительно для себя. Логарифм в сложности вылезает из-за крайнего случая, описанного во втором решении. Я пытался сразу обрабатывать крайний случай для поиска второй цивилизации. Это приводило к тому, что все зародившиеся множества клались в множество, а при гибели они из этого множества удалялись. Как известно каждая операция выполняется за O(logN).
   Задача С.
   [Число]
Идентичная задача была на ACM ICPC Subregional Contest 2007 в Саратове. Вот она на сервере acm.sgu.ru. Приятно вспомнить, что тогда мы ее зачли). Спасибо Роману и Рамилю. 
Дополнительные олимпиадные задачи:
   Задача A.
   [Современники]
Задача на сканирующую линию. Создаем массив из дат. Для каждой даты храним метку, является ли она началом периода или концом. В качестве даты нужно добавлять день [18-летия](начало) и день [80-летия – 1 день](конец). Небольшая сложность состоит в подсчете даты [80-летия – 1 день]. Для этого нужно аккуратно выписать количество дней в месяцах и не забыть обработать случай високосного года.
   Задача B.
   [Контрольная по ударениям]
Задача на быстрое нахождение слова в словаре. По ходу решения удобно завести два множества. В первом будем хранить слова с ударением, а во втором – те же слова в нижнем регистре для определения наличия слова без проверки на ударение.
   Задача С.
   [Умный чертежник] Сложное решение =)
По условию задачи робот не может проехать по нарисованной ранее линии. Можно представить перемещения работа в виде графа. Этот граф будет представлен либо Эйлеровым путем, либо Эйлеровым циклом(справка). Следовательно либо все степени вершин графа являются четными(Эйлеров цикл), либо 2 вершины имеют нечетную степень,а все остальные четную(Эйлеров путь). Также отметим, что граф является связным. Суть данного решения заключается в том, что мы двигаемся по исходному графу как захотим. Во время движения не меняем направления только в том случае, если этого сделать нельзя. Т.е. избегаем комбинаций в маршруте типа “EE”, “WWW” и подобных, если это возможно. Такая тактика приведет к тому, что все вершины с нечетными степенями будут содержаться в нашем пути. Но может возникнуть ситуация, когда некоторые вершины будут не использованы в маршруте. Неиспользованные вершины будут образовывать конечное количество циклов. Чтобы все неиспользованные циклы добавить в ответ нужно найти место в ответе, куда нужно их вставить. Эту операцию можно сделать путем пересечения множеств использованных и неиспользованных вершин. Вершина считается использованной, если не осталось неиспользованных ребер, исходящих из нее. Поясним более наглядно вышесказанное.
Исходный путь: NNWSEE
Первоначальный путь: NE
В результате остался неиспользованный цикл WNES. Его нужно вставить после первого шага. В итоге получаем ответ: NWNESE
   [Умный чертежник] Простое решение !
Предыдущее решение было не очень продуманным в плане простоты реализации. Если подумать, можно заметить, что если робот наткнулся на самопересечение в точке P, то нужно двигаться в обратную сторону между двумя попаданиями в точку P в рамках первоначального пути. Важно учесть, что после такого “реверса” пути заново пройти весь путь с первоначального попадания в точку P, чтобы проверить наличие самопересечений последующего пути с “реверснутым” подпутем.