SRM 404

Только ленивый не пошутил по поводу «матч не найден»

→ Main → “Topcoder in Russian” → Guestbook → About me

Подняться в рейтинге в этот раз мне удалось не сильно (1423 → 1444): я решил только лёгкую задачу, среднюю не успел додумать, а тяжёлую только пролистал по диагонали (как оказалось, зря). Впрочем, у меня есть уважительные причины, о которых будет сказано ниже.

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

Приятным сюрпризом стало появление в арене старого знакомого [info]er_v. Для новичка Алексей выступил весьма достойно. Пожелаем ему дальнейших успехов!

На этом вводная заканчивается и мы переходим к самому вкусному — к задачам.

ReadingBooks

Division 2 Easy

Под покровом ночи Иммануил прокрался в библиотеку имени Ленина, выбрал несколько книг и принялся их читать. Каждая книга состоит из трёх частей: введения, повествования и морали. Иммануил берёт одну книгу, прочитывает ноль или более частей из неё в произвольном порядке, выбрасывает книгу и принимается за следующую. Одну и ту же книгу Иммануил два раза не берёт. После прочтения очередной части Иммануил записывает её тип (введение, повествование или мораль) на листочек.

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

Вход

Массив parts (длиной не более 50), представляющий злополучный листочек.

Выход

Целое число — максимальное количество книг, которое Иммануил мог прочитать.

Примеры листочков

  • {"введение", "повествование", "введение", "мораль"} — здесь Иммануил мог прочитать максимум одну книгу (последние три записи в листочке).
  • {"повествование", "введение", "мораль", "повествование", "мораль", "введение"} — две книги одну за другой.
  • {"мораль", "мораль", "мораль", "введение", "введение", "введение", "повествование", "повествование", "повествование"}
    • — частей много, но ни одной книги Иммануил полностью прочитать не мог (он не возвращается к книгам, у которых прочитал хоть что-то).

Div2 Easy всегда составляется в расчёте на то, что её должны решить почти все, даже новички. Так получилось и в этот раз: не требуется никаких особых навыков, чтобы интуитивно понять (или даже доказать), что можно просто:

Решение в коде занимает примерно столько же, сколько словесное описание.

RevealTriangle

Division 2 Medium / Division 1 Easy

Физик Эдуард в обеденный перерыв нарисовал на доске треугольник из цифр следующего вида:

74932
1325
457
92
1

Составляется он так: каждая цифра равна последней цифре суммы своих верхнего и верхнего правого соседей (а в самом верхнем ряду стоят произвольные цифры).

К сожалению, в этот момент сзади незаметно подкрался математик Михаил, стёр в каждом ряду все цифры, кроме одной, и стремительно убежал. Когда Эдуард опомнился, то понял, что, несмотря на подлянку Михаила, исходный треугольник можно восстановить однозначно. Это вам и предстоит сделать.

Вход

Массив строк questionMarkTriangle (длиной не более 50), представляющий собой покоцанный треугольник. На месте безвозвратно утерянных цифр стоят знаки вопроса.

Выход

Восстановленный треугольник: тот же массив, но уже с цифрами вместо знаков вопроса.

Примеры треугольников

  • 1 — треугольник из одного ряда. Восстанавливать нечего, поэтому ответ 1.
  • 4??
?2
1
    В результате восстановления получается 
    457
92
1

Хотя эта задача чуть посложнее предыдущей, особых трудностей с ней не возникает: если удалось пройти примеры из условия, то ошибиться было практически негде. Статистика подтверждает мои слова: успешных челленджа по этой задаче было всего 2 (в первом дивизионе). Тут, на мой взгляд, Бобан не доглядел: в хорошей 250 обязательно должны быть пусть и небольшие, но хитрости.

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

abcde   ← позиции
=====
??5??   ← ряд i + 1
4093    ← ряд i

Одна цифра из ряда i + 1 нам точно известна по условию (в данном случае она стоит на позиции c). Сначала восстановим цифры слева от c, потом справа. На позиции b стоит вопросик, к которому справа присоседилась 5, а снизу — 0. Если вы сообразили (как я вас просил :)), почему такие вопросики можно заменить на цифру однозначно, то поймёте, что на позиции b должна стоять 5. Теперь от вопросика на позиции a справа находится 5, а снизу — 4. Заменяем этот вопросик на 9. Понятно, что если бы слева ещё были вопросики, то мы бы их по цепочке все заменили на цифры. Справа от позиции c цифры расставляются абсолютно аналогично (на позиции d будет стоять 4, а на e — 9). Вуаля: мы нашли все цифры (95549) из ряда i + 1, а значит, можем заполнить ряд i + 2, да и все остальные ряды до самого верха.

Решение получается коротким и изящным.

GetToTheTop

Division 2 Hard

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

На каждой платформе лежит целое число монеток (≥ 0). Марио незаметно подкрался к платформам и хочет собрать наибольшее количество монеток. У него есть максимальная длина прыжка K, и он может перепрыгнуть с платформы a на другую платформу b, только если расстояние между этим платформами ≤ K и высота b ≥ высота a.

Изначально Марио стоит на оси абсцисс и выбирает платформу на свой вкус, до которой может допрыгнуть из произвольной точки (X, 0). Дальше он может прыгать как угодно, руководствуясь изложенными выше правилами. По прибытии на платформу, он немедленно собирает все лежащие там монеты. Необходимо помочь Марио выбрать платформы, по которым он будет прыгать, так, чтобы собрать как можно больше монет.

Вход

K — максимальная длина прыжка; x, y, length, coins — массивы, описывающие параметры каждой платформы: координаты левой точки, длина и количество монет. Всего платформ не более 50.

Выход

Целое число — максимально количество монет, которое может собрать Марио.

Пример расположения платформ

22 платформы

Зелёным отмечены платформы, которые надо посетить, чтобы заработать максимальное количество монет — 129.

Эту задачку не так сложно решить идейно, но реализация её за 75 минут матча — не самое простое дело. Статистика по задаче показывает это наглядно: в Division 2 её сдали всего два человека.

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

Группы для K = 3

Пусть мы построили набор групп платформ $A = \{\,A_1, A_2, \ldots, A_k\,\}$. Построим граф $G = (V, E)$, где $V = A, (A_i, A_j) \in E \Leftrightarrow \exists a \in A_i, b \in A_j : $ из a можно прыгнуть в b. Назначим ребру $(A_i, A_j)$ вес $w = \sum\limits_{a \in A_j} Coins(a)$ (Coins(a) — количество монет на платформе a). Граф получился ориентированный ациклический, а значит, найти путь максимального веса из данной стартовой вершины в нём можно за $O(|V| + |E|)$. Чтобы найти ответ, необходимо перебрать все возможные стартовые вершины, до которых мы можем дотянуться с оси абсцисс.

Осталось всего одна маленькая (но ключевая) деталь при построении графа: как определить, можем ли мы запрыгнуть с платформы a на платформу b (напомню, расстояние между ними должно быть ≤ K)? Здесь есть два случая (расстояние между платформами обозначено как d):
Простой случай — проекции платформ на ось абсцисс пересекаются.

Более сложная формула. Квадратный корень считать, конечно, не надо: достаточно возвести обе части в квадрат.

Платформа b может находиться и полностью слева от a — принципиально это ничего не меняет.

Решение писалось медленно, но аккуратно.

KSubstring

Division 1 Medium

Дан массив натуральных чисел B. Пусть

$ A_{i, k} = \{ B[i], B[i + 1], \ldots, B[i + k - 1] \}; $
$ S_{i, k} = \sum_{a \in A_{i, k}} a. $

Рассмотрим все пары непересекающихся последовательностей одинаковой длины $\{ (A_{i, k}, A_{j, k}) \mid i + k \leqslant j \}$. Среди этих пар надо выбрать такую, что значение модуля разности их сумм $|S_{i, k} - S_{j, k}|$ минимально.

Вход

Массив B (длиной не более 3000 и не менее 2).

Выход

Пара чисел (k, d), где d — минимальное значение указанного в условии модуля разности, а k — наибольшая длина последовательности, при которой достигается d.

Примеры

  • {5, 19, 11, 12, 15} — ответ (2, 1). Разности 1 можно достичь, выбрав последовательности ({11}, {12}) или ({5, 19}, {11, 12}). Мы выбираем последний вариант, потому что длина последовательности в нём больше.
  • {8, 169, 1135, 652, 1940, 1296, 1618, 1457, 491, 974, 1779, 330} — ответ (5, 161). Разность 161 даёт пара ({169, 1135, 652, 1940, 1296}, {1457, 491, 974, 1779, 330}).

Теоретически это была самая интересная и сложная задача на этом матче, даром что Medium, а не Hard. К сожалению, произошёл ляпсус, который значительно понизил её интересность.

Поскольку размер массива может быть до 3000, а алгоритм полного перебора всех последовательностей будет работать за $O(n^3)$, то он не уложится в две секунды на максимальных тестах. Следовательно, надо искать что-то более быстрое.

Перед поиском решения отметим следующий факт: после нехитрой предварительной обработки за $O(n)$ произвольную сумму $S_{i, k}$ можно найти за $O(1)$ (фактически, два обращения к массиву; подумайте как). Поэтому затратами на нахождение всевозможных сумм можно пренебречь.

Бинарное дерево поиска

Если не запрещать пересекающиеся последовательности, то алгоритм решения за $O(n^2 \log n)$ достаточно прост:

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

Поступим так: зафиксируем длину k и будем перебирать последовательности, слева от которых что-то есть. Первая такая последовательность будет $A_{k, k}$; слева от неё находится только $A_{0, k}$. Сдвинемся чуть вправо: для $A_{k + 1, k}$ слева появится ещё и $A_{1, k}$. Сдвигаясь так до конца массива, получим, что на каждом шаге слева добавляется всего одна последовательность.

Это означает, что мы можем завести некую структуру данных, в которой хранить суммы, которые у нас есть слева от текущей последовательности $A_{x, k}$ и добавлять в эту структуру новые суммы по одной. Ключевой же момент — возможность находить в этой структуре сумму, ближайшую к $S_{x, k}$.

Сбалансированное бинарное дерево поиска позволяет выполнить и вставку, и нахождение ближайшего элемента за $O(\log m)$, где m — количество элементов в дереве. Вставка реализуется стандартным алгоритмом, а нахождение ближайшего примерно похоже на обычный поиск. Эффективность этих операций достигается за счёт того, что дерево поддерживает внутри себя элементы в «отсортированном» виде.

Казалось бы, отлично. Но тут, к сожалению, автор Бобан допустил досадный промах. В C++ уже есть структура данных std::map (в которой скрывается красно-ч0рное дерево), а в ней — метод lower_bound(), с помощью которого тривиально осуществляется поиск ближайшего элемента. Поэтому программисты на C++ эту задачу дружно и быстро зарешали в количестве 101 человек. Само по себе это не страшно, но оказалось, что реализовать дерево поиска на языках C# и Java так, чтобы оно укладывалось в две секунды, во время контеста невозможно. На Java было сдано 2 (два!) успешных решения, на C# — 1 (одно!!!). Такой радикальной разницы я даже и не припомню.

Элитное решение

После матча разозлённый Petr, которому пришлось переключиться на C++, чтобы сдать эту задачу, весьма справедливо наехал на Бобана в арене. К чести последнего, он твёрдо выстоял под натиском вице-чемпиона TCO-2008 и рассказал, что существует решение за $O(n^2 \log n)$, которое не использует никаких структур данных, отличных от массивов. За счёт этого константа в O-обозначении мала, и это загадочное решение работает на всех языках очень быстро. В доказательство Бобан отсабмитил исходник, использующий хитрую идею, в Practice Room.

Заинтересованный, я попытался в нём разобраться. Увы, вникнуть в логику работы я не смог и обратился за помощью на форумы топкодера. Со стороны топкодеровских знатоков с ответом выступил Александр Друзь Yarin, который помогал Бобану тестировать эту задачу при подготовке контеста.

Секрет (до которого во время контеста было додуматься очень сложно) заключается в том, что Claim неверен. Точнее, не совсем верен. Мы можем (с некоторой оговоркой) рассматривать только соседние элементы в массиве сумм, и всё равно будем правы. Но это не очевидно.

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

Начнём перебирать k сверху вниз. Для каждой позиции i в отсортированном массиве будем находить самую левую последовательность, соответствующую сумме на позиции i, и самую правую (это легко сделать за $O(n)$). Обозначим сумму на позиции i за S, а на позиции i + 1 за T. Утверждается, что достаточно проверить, нет ли в исходном массиве B двух непересекающихся последовательностей либо с суммами S и S, либо S и T (это легко сделать за $O(1)$, поскольку мы знаем самые левые и самые правые последовательности с этими суммами).

Почему?

Если оптимальная разница — 0, то мы её найдём (потому что мы рассматриваем все пары последовательностей с одинаковыми суммами).

Пусть оптимальная сумма не 0. Вообще говоря, теоретически может получиться так:

Здесь всё правдоподобно, кроме одного пункта — первого. 2 не может быть оптимальной разницей, потому что из пересекающейся пары последовательностей с суммами, например, {3, 4} можно выкинуть общую часть (как было указано выше) и получить разницу 1. (И наш алгоритм найдёт эту разницу для меньшего значения k.)

Вообще, реализация этой идеи совсем не сложная, но догадаться до неё (мне, по крайней мере) — сложно.

Я реализовал оба решения: и элитное, и деревянное (я использовал декартово дерево, также известное как treap).

SoftwareCompanies

Division 1 Hard

На рынке есть несколько компаний, обрабатывающих данные. Каждая компания принимает на вход N килобайт данных в каком-то формате и выдаёт на выход N килобайт данных в своём уникальном формате. Компания X характеризуется следующими параметрами:

  • именем;
  • списком компаний, которые могут принимать на вход формат, производимый X;
  • максимальным количеством данных, которое X может обработать;
  • стоимостью приобретения X.

Необходимо незаметно подкрасться и совершить следующие безумные действия:

  • купить набор компаний, включающий две компании company1 и company2;
  • подать company1 на вход N килобайт (N не больше, чем company1 может обработать) необработанных данных и получить N килобайт данных в формате company1;
  • путём цепочки обработок данных в купленных компаниях, перевести эти N килобайт в формат company2.

Первоочередная задача — сделать N максимальным. Если несколько наборов компаний даёт одно и то же N, нужно выбрать тот, который стоит меньше. Если и таких несколько — выбрать набор компаний, в котором отсортированная по возрастанию последовательность имён компаний будет лексикографически наименьшей.

Вход

Строки — имена компаний company1 и company2; массивы names, process, amount, cost — параметры компаний, указанные в условии. Компаний на рынке не больше 12.

Выход

Список имён компаний (отсортированный по возрастанию), купив которые, мы максимизируем N. Если ни одного килобайта данных передать не получается, вернуть пустой список.

Пример

7 компаний

Стрелка из компании X в компанию Y указывает на то, что Y может обрабатывать формат X. company1 выделена красным, а сompany2 — синим.

В данном случае нужно купить все компании, кроме D, тогда мы сможем получить 21 килобайт данных в формате company2. Последовательность обработок будет такой:

  • Обработать 21 килобайт данных в A.
  • Послать 11 килобайт в C и 10 — в B.
  • С, обработав 11 килобайт, посылает их в Е, которая, в свою очередь, обрабатывает их и шлёт на обработку в пункт назначения − G.
  • 10 килобайт из B распределяются так: 1 килобайт идёт в Е (которая может обработать ещё максимум 3 килобайта), а 9 — в F, после чего всё это направляется в пункт назначения.

На покупку этих компаний потратится в сумме 22 у. е. Можно было бы купить ещё и D, но она не увеличивает количества обработанных данных (потому что не связана с G), а только повышает цену. Поэтому мы её в ответ не включаем.

Поскольку компаний всего 12, то можно перебрать все 4096 возможных ответов, и для каждого проверить, какое максимальное количество килобайт мы можем обработать. Звучит страшно, но опытный алгоритмист сразу поймёт, что, в сущности, перед нами немного изменённая задача нахождения максимального потока в сети.

На пальцах постановку задачи нахождения потока можно объяснить так:

Умные люди придумали графовую модель для потоков и научились эффективно находить максимальный поток самыми разными алгоритмами. На язык потоков наша задача переводится достаточно просто: ребро-труба между компаниями X и Y означает, что Y может обработать данные X, жидкость — это просто килобайты, текущие по этой трубе, а начальная и конечная точки — это company1 и company2.

Есть, правда, и отличие: в стандартной формулировке пропускные способности указаны у самих труб, а не у точек их соединения. Однако эта проблема решается. Разделим каждую вершину X на две − X1 и X2. В X1 проведём все рёбра, которые входили в X, а из X2 — все рёбра, выходившие из X. Этим рёбрам назначим пропускную способность, равную бесконечности. Между X1 и X2 проведём ребро с пропускной способностью, равной пропускной способности X.
До преобразования (пропускная способность X — 9).

После преобразования.

Можно показать, что максимальный поток в новой сети не изменится.

Поскольку вершин очень-очень мало, для нахождения потока можно использовать совершенно любой алгоритм (а их очень много). Я выбрал простейший поиск дополняющих путей с поиском в ширину, также известный, как алгоритм Эдмондса — Карпа.

Теперь у меня есть готовая реализация потока для будущих контестов. :)

Заключение

При подготовку этой статьи были использованы Markdown Extra, Latex, Syntax Colorizer, Metapost и Graphviz. SRM 405 состоится в субботу, 14 июня в 20:00 по московскому времени. Подключайтесь!

You are the 771st visitor