23.01.2013

 Разбор задач второго дня регионального этапа олимпиады по информатике.


Задача 6.

 

Допустим, что в каждой строке встречается символ 'z' (максимальный из всех возможных во входных данных). Тогда искомая строка точно начинается с 'z'. Действительно, если какая-то строка s1 начинается с этого символа, а строка s2 — нет, то s1 всегда больше s2, а ответ требуется лексикографически наибольший, значит, строки вида s2 не подходят. Аналогично, если символ 'z' встречается в каждой строке k раз (минимум из встречаемостей символа в каждой строке), то искомая строка должна начинаться ровно с k символов 'z'.

Пусть мы взяли максимальное количество 'z'. Тогда мы можем провести те же рассуждения для 'y', как второго по "величине" символа. Разница лишь в том, что мы можем брать только те 'y', которые находятся после уже взятых 'z'. Именно поэтому оптимальнее всего брать символы слева направо, пока это возможно.

Отсюда выводится алгоритм нахождения наилучшего ответа: сначала взять все возможные 'z', затем 'y' и так далее до 'a'. Реализовать это можно и за O(N^2) (например, каждый раз просматривать всю строку), здесь будет приведено решение за O(N * ALPH), где ALPH — размер алфавита (здесь — количество всех латинских букв).

Для начала посчитаем двумерный массив next, в котором элемент next[i][c] будет равен позиции ближайшего символа с кодом ('a' + c) после i-го символа в строке, или -1, если такой символ после i-той позиции не встречается. Заполнить массив можно за линейное время, идя с конца строки. Теперь поставим два указателя в начало обеих строк и будем пытаться добавлять максимально возможные символы, передвигая указатели. Как только общие символы в строках закончатся — нужно вывести получившийся ответ, так как в него уже ничего не добавить.

 

Задача 7.

 

Как несложно заметить, это геометрическая задача.

Начать можно с разбора небольших случаев при n от 2 до 4, для которых может существовать бесконечно много окружностей. Рассмотреть их несложно: для n = 2 всегда можно вывести "1" и "2", для n = 3 — "1" и "2 3", для n = 4 — "1 2" и "3 4".

Приведём решение для первой подзадачи (n <= 50) [50 баллов]. Поскольку окружность однозначно строится (если строится) по трём точкам, то можно сделать следующее: перебрать все возможные тройки точек на плоскости и построить по ним окружность O1.

Затем проверить остальные N-3 точек на принадлежность O1. Те, которые лежат на ней, однозначно идут в первое множество. По всем остальным, согласно условию, должна быть построена вторая окружность O2. Если их не более двух, то она точно строится, иначе построим по трём из них O2 и проверим, что каждая из точек принадлежит либо O1, либо O2. Если это условие выполнилось, то ответ найден; по условию это рано или поздно произойдёт.

На самом же деле n <= 2000 [100 баллов], а сложность приведённого решения O(n^4): n^3 на перебор точек и n на "распихивание" по окружностям. Но есть решение, работающее существенно быстрее: перебирать можно только первые (да и вообще любые) 5 точек, так как по принципу Дирихле какие-то три из них точно лежат на одной окружности. Всего способов выбрать эти точки — 10, и каждый из них будет проверяться за O(n), в итоге получаем сложность O(n).

Основная сложность — реализовать построение окружности по трём точкам ABC. В теории эта задача сразу сводится к пересечению серединных перпендикуляров в треугольнике из этих точек (школьный материал по геометрии). Чтобы систематизировать цели: потребуется взять середины векторов AB и AC, провести через них эти же вектора, но повернутые на 90 градусов, получить две прямые, затем повыводить нужные формулы, отсечь "плохие" случаи, найти центр. Также могут возникать проблемы с точностью, но вроде как на баллы это влиять не должно.

 

Задача 8.

 

Для начала — решение за O(N^3) [40 баллов], как наиболее простое: вначале запустим на данном графе алгоритм Флойда (четыре строчки на любом языке), который найдёт кратчайшее расстояние между каждой парой вершин, а затем переберём все тройки, как раз N^3 и получится.

Для написания более быстрого решения требуется нечто более интеллектуальное.

Можно доказать, что если d нечётно, то таких троек не найдётся вообще. В противном случае для любой тройки, удовлетворяющей условию, существует "центр" на расстоянии d/2 от каждой вершины из неё.

Давайте сначала будем перебирать все возможные центры: подвесим всё дерево за каждую вершину-кандидата v. Если выкинуть v, то дерево распадётся на связные поддеревья v1, v2, ..., vk. В каждом поддереве будет ai вершин, находящихся от корня на расстоянии d/2, то есть теоретически подходящих нам.

Заметим, что если мы будем выбирать тройки относительно центра, то мы не сможем брать больше одной вершины из одного поддерева (иначе расстояние между какой-то из пар будет меньше d/2). Тогда количество способов взять три вершины при данном центре будет равно сумме произведений вида ai*aj*ak, где i, j и k попарно различны. Количество баллов за эту задачу будет зависеть от того, как искать ai для каждой вершины и считать произведения.

 

O(N^2) [60 баллов]. Ещё раз: зафиксируем v, подвесим за неё дерево. Все ai подсчитаем одним dfs-ом с параметрами (вершина, расстояние от неё до корня). Теперь, если просто перебрать все тройки, то получится даже N^4 операций.

Поступим по-другому. Присвоим переменной sum сумму всех ai. Затем скажем, что мы можем брать вершины как угодно. В этом случае ответ будет равен sum*(sum-1)*(sum-2)/6, то есть число сочетаний из sum по 3. Вернёмся к поставленному ограничению и получаем, что в нашем ответе есть "лишние" тройки.

Какого они вида? Это либо две вершины из одного поддерева и ещё одна "левая" вершина, либо три вершины из одного поддерева.

Вычесть из найденного ответа все эти тройки несложно: сначала пройдемся по всем i от 1 до k и вычтем число (ai*(ai-1)/2)*(sum-ai), а затем ai*(ai-1)*(ai-2)/6.

Всё, мы получили искомый ответ за линейное время для каждой вершины, следовательно, асимптотика — O(N^2).

 

O(NlogN) [100 баллов]. Здесь решение не приводится, так как автор этого текста сам его не понял :) Единственное, что могу сказать — надо использовать один dfs и считать ответы для всех вершин v на ходу. Здесь придётся учитывать и то, что помимо путей "вниз" появляются ещё пути "наверх", а линейный пересчёт вернёт решению квадратичную сложность. И ещё здесь как-то используется следующая идея: слияние большого списка (массива) с маленьким занимает NlogN времени.

 

 

Вот как-то так.

Материалы от Питера: http://neerc.ifmo.ru/school/archive/2012-2013/ru-olymp-spb-2013-archive.rar
Видеоразбор от Д. П. Кириенко: http://www.100ege.ru/tasks/video?l=3277 

Адрес: 614039, г. Пермь, ул. Комсомольский проспект, 45
Телефон: +7 (342) 212-80-71
E-Mail: school9-perm@ya.ru
Вопрос администратору сайта