Сложная задача и интересная история

Привет, Хабр!


Примерно год назад я придумал задачу, к которой так и не смог придумать алгоритма для решения. Вот её условие.


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


Вот пример разбиения восьми точек на три направо возрастающих ломанных (BDF, CEGH, A). На меньшее количество ломаных точки разбить нельзя.



Вот собственно и вся задача, можете попробовать ее решить.


Теперь интересная история.


У нас проходил MatCat. Это что-то вроде развлекательной олимпиады, на которой можно порешать задачи. Первая задача была достаточно легкой, я не помню точного условия, но могу примерно его пересказать:


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


Например, Петя записал цифры 123425 а Вася 224123 Минимальным ответом будет 123241253.


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


Красивого алгоритма я не придумал, зато неожиданно для себя обнаружил, что уже сталкивался с очень похожей задачей, но в совершенно другой формулировке! Да-да, это та самая задача, которую я описал в начале. Сейчас я покажу, что у них есть общего. Начнем решать задачу про Петю и Васю.


Для решения задачи Заметим, что одинаковые цифры в строках Васи и Пети могут быть одной и той-же цифрой в ответе, а вот разные, очевидно, не могут. Для наглядности выпишем строку Пети выше и Васи ниже и соединим одинаковые цифры ребрами:



Серые числа – индексы. Например, мы может одновременно объединить числа с индексами 1-0 3-2 4-4 так как ребра 1-0, 3-2, 4-4 не пересекаются. Получим ответ для такого объединения:


Первая цифра 1.


Затем идет 2, причем это одновременно и двойка Васина, и Петина.


Дальше идет еще одна двойка.


Четвертой циврой идет 3. Мы не можем поставить на это место 4, так как обе четверки объеденены, то есть являются одной и той-же цифрой, а в верхнем ряду тройка стоит раньше четверки.


Дальше идет 4, которая встречается и у Пети и у Васи.


Шестой идет 1.


Седьмой идет 2, которая встречается у обоих студентов.


Восьмое и девятое место занимают 3 и 5 в любом порядке.


Мы не можем одновременно объеденить пары цифр с индексами 0-3 и 1-0, так как вверху единица стоит раньше двойки, а в низу наоборот. Таким образом, мы должны найти максимальное количество непересекающихся друг с другом ребер, ведь чем больше мы их найдем, тем больше одинаковых цифр сможем объеденить в одну, тем меньше будет цифр в конечном номере. Давайте представим ребра как точки на плоскости, где их координаты это индекс начала и индекс конца:



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


Вот так две с виду очень непохожих задачи свелись практически к одному и тому же. Причем человеку гораздо легче анализировать рисунок. В данном случае сразу видно две направо-возрастающие ломаные CBE и DBE. Это значит что задача имеет два решения и что конечное количество цифр в номере равно 12 — 3 = 9, где 12 — общее количество цифр (6 Петиных и 6 Васиных), а 3 — количество точек в направо-возрастающей ломаной.

Tags:
задачи для программистов

You can't comment this post because its author is not yet a full member of the community. You will be able to contact the author only after he or she has been invited by someone in the community. Until then, author's username will be hidden by an alias.