Долго я не писал – сначала был занят подготовкой к сабжу, затем доделываением того, что не получилось сделать из-за подготовки и вот выдалась свободная минутка.

NEERC 2008 – событие года для сотен студентов по всему СНГ. Именно к нему в течение года готовятся сильнейшие команды ВУЗов России, Беларусии, Грузии, Казахстана, Кыргызстана, Прибалтики, Армении, Азербайджана, Узбекистана и, как выяснилось в этом году, Украины. Именно здесь рождаются легенды и умирают мечты. И именно здесь меня больше не будет в качестве участника.

Этот год по правилам соревнований последний, когда я могу участвовать в ACM ICPC, и я, соответсвенно старался использовать этот шанс по полной, собрал довольно сильную команду, но, увы, не получилось. Как всегда оказалась одна задача, решение которой было понятно, но по неизвестным причинам проходить все тесты оно не хотело. Итог – 7 задач и 20 место.

Вообще, складывается такое ощущение, что насколько 2008 год удачен для России (ACM ICPC, футбол, хоккей, Евровидение), настолько же он неудачен для Казахстана и в частности для меня. Сначала совершенно глупое непрохождение отборочных раундов TCO, затем бредовый случай с визой для GCJ, теперь вот NEERC… Ну что, не будем отчаиваться, как говорится, не везет мне в картах, повезет в любви.

Далее – краткий обзор некоторых задач.

Во-первых следует сказать, что впервые на полуфинале был представлен новый вид задач – интерактивные задачи. По словам организаторов (да к тому же это очевидно), это открывает для жюри и участников совершенно новый обширный класс интересных проблем. В частности, смухлевать с решением онлайн задач в оффлайне уже не получится. Так как это был «пробный заезд», задача B, которая была интерактивной, была сделана достаточно легкой, но, думаю, уже в следующем году сложность будет доведена до предела и командам придется туго.

Задача A. Aerodynamics

В задаче предлагается посчитать площади сечения выпуклой оболочки заданных точек плоскостями перпендикулярными оси OZ.

Во-первых понятно, что площади сечения будут выпуклыми многоугольниками (кроме вырожденных случаев). Во-вторых, вершинами этих многоугольников будут точки пересечения ребер нашей 3-мерной фигуры с плоскостями сечения. В-третьих, эти ребра представляют собой подмножество отрезков, построенных между каждой парой точек.

Используя эти факты и то, что ограничения довольно небольшие (всего 100 точек), можно предложить следующий алгоритм (считаем, что конкретная плоскость сечения у нас задана): построим всевозможные отрезки между точками и найдем точки их пересечения с нашей плоскостью. Затем построим выпуклую оболочку точек пересечения (уже 2-мерную (!)) и найдем ее площадь.

Задача B. Blind Walk

В задаче надо обойти все достижимые клетки лабиринта. При этом можно пытаться двигаться в разные стороны и программа жюри будет отвечать, можем ли мы туда пойти.

Решение просто – будем делать обычный обход в глубину, но вместо проверки возможности прохождения по карте будем спрашивать это у жюри.

Задача D. Drive through MegaCity

Эту задачу мы не решили, но судя по заверениям других участников один из возможных вариантов решения использует тот факт, что при оптимальном пути одна из координат изменяется монотонно.

Задача E. Exclusive Access

По слухам здесь надо было прочитать условие и, немного подумав, написать то, что просят.

Задача F. Fibonacci System

Выпишем в одну строку все натуральные числа от 1 до бесконечности в фиббоначиевой системе счисления. Нужно посчитать количество единиц среди первых N символов строки.

Во-первых, научимся считать количество единиц в строке из чисел от 1 до X, где X – число фиббоначи. Очевидно, что здесь можно вывести простую рекуррентную формулу, которую я приводить не буду ибо лень.

Во-вторых, найдем Y и Z – максимальное число фиббоначи и максимальное целое число, которое целиком поместилось в первые N символов строки.

Теперь, если мы сумеем посчитать количество единиц до Z, то задача решена (остаток строки можно просчитать переведя Z + 1 в фиббоначиеву систему счисления). Для этого посчитаем количество единиц до Y (это мы уже умеем), затем прибавим к ответу Z – Y + 1 и запустив рекурсивно функцию для Z – Y. Конец рекурсии – это 0 или 1.

Задача G. Giant Screen

Нужно просто сделать то, что просят в задаче.

Задача H. Hell on the Markets

Немного перефразированное условие задачи выглядит так: разделить массив чисел на два массива так, чтобы суммы чисел в обоих массивах были равны. При этом дается условие: a[i] <= i (a – исходный массив чисел).

Насколько помню, задача решается жадно. Отсортируем числа по убыванию и будем добавлять их по порядку в тот массив, в котором текущая сумма меньше (если суммы одинаковы, то в любой). Если в конце получатся одинаковые суммы, то выводим ответ, если нет, то ответа не существует. Если кто знает доказательство правильности алгоритма, расскажите, пожалуйста, в комментариях.

UPD. Доказательство правильности получено, спасибо ttim. Идея основана на том, что в условии задачи сказано, что i-й элемент исходного массива не больше i.

Задача I. iSharp

Just do it!

Задача J. Javanese Cryptoanalysis

В задаче нужно поставить каждой букве текста в соответствие букву так, чтобы в итоге в каждом слове чередовались гласные и согласные буквы.

Составим граф. Вершинами будут буквы исходного текста. Между двумя вершинами будет ребро, если буквы соответствующие этим вершинам в каком-то слове стоят рядом. Тогда если граф не двудольный, решения не существует. В противном случае нам надо сделать так, чтобы в одной доле было не больше 5 букв (по количеству гласных), а в другой – не больше 21 (по количеству согласных). Сделать это можно, например, перебором.

Задача K. KINA Is Not Abbreviation

В задаче требуется заменить какое-нибудь словосочетание в тексте аббревиатурой с выполнением некоторых условий так, чтобы результирующий текст был минимально возможной длины.

На этой задаче многие команды и встали :( Идея решения – заменим слова числами, преобразовав текст в последовательность чисел. Теперь переберем количество слов в последовательности и за один проход по строке посчитаем, сколько раз встречается каждое словосочетание. Для этого можно хешировать каждое словосочетание и использовать хеш таблицу для подсчета. Теперь осталось все аккуратно реализовать, что является здесь, как оказалось, главной проблемой.

Постовой:

фотограф