Рассмотрим, например, последовательность

4 5 3 8 2 6 1 7

Если ограничиться тремя первыми элементами, то наиболее длинная возрастающая подпоследовательность — это

4 5

Добавим четвертый элемент, 8. Он может быть присоединен к концу этой подпоследовательности и дает возрастающую подпоследовательность длины 3:

4 5 8

Следующий элемент — 2 — ничего не меняет. Следующий — 6 — не может быть присоединен к концу последовательности длины 3, но он может быть присоединен к концу последовательности длины 2 — последовательности 4 5 — чтобы дать другую подпоследовательность длины 3:

4 5 6

Эта последовательность меньше предыдущей, поскольку ее последний элемент меньше, и поэтому у нее больше шансов иметь возможность продолжаться. На самом деле, 7 может быть присоединено к ее концу, что дает максимальную возрастающую последовательность

4 5 6 7

Мы уже видим, что нужно уточнить понятие максимальной возрастающей подпоследовательности, определяя наилучшую из них: это — такая последовательность, у которой последний элемент — наименьший возможный. В этой строке наилучшая подпоследовательность длины 1 есть элемент 1, наименьший элемент последовательности. Таким образом, мы приходим к следующей идее: предположим, что мы знаем последний элемент наилучшей подпоследовательности длины k в пройденной части для любого значения k от 1 и вплоть до максимального значения m.

Новый рассматриваемый элемент изучается с точки зрения возможности его присоединения к концу подпоследовательности длины k, чтобы превратить ее в подпоследовательность длины k + 1. Покажите, что если это возможно, то эта новая последовательность лучше, чем предыдущая подпоследовательность длины k + 1. Может случиться также, что этот новый член оказывается меньше элемента, образующего подпоследовательность длины 1. Тогда он дает лучшую, чем предыдущая, подпоследовательность длины 1.

Таким образом, вы получаете алгоритм, в котором для любого элемента рассматриваемого вектора нужно искать в таблице последние элементы наилучших подпоследовательностей, и размер этой таблицы равен m. Покажите, что эта таблица упорядочена. Осуществите в ней поиск места рассматриваемого элемента вектора с помощью дихотомического поиска[27] и вы получите алгоритм порядка n In n.

Головоломка 36.

Вы можете вдохновиться решением предыдущей задачи. Нужно пробежать одну из двух цепочек символ ea символом. Предположим, что мы ее пробежали до некоторого i включительно. Нужно осуществить регистрацию лучших из наиболее длинных слов в порядке возрастания длин, содержащихся в пройденном куске рассматриваемой цепочки и во второй цепочке в целом. Как определить наилучшее слово длины k? Скажем, что это — такое слово, которое имеет наибольшие шансы оказаться продолжаемым, следовательно, такое слово, у которого положение последнего символа во второй цепочке минимально. Это приводит к рассмотрению того, насколько важно знать положение символов во второй цепочке и, следовательно, к заданию наилучших слов списком из положений в цепочке (например, с помощью конкатенации совпадающих с ними символов во второй цепочке).

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

Больше я вам ничего не сообщаю. Ищите дальше сами…

Головоломка 37.

Вы можете рассмотреть задачу самым простым способом. Пусть задан прямоугольник — координатами x₁, y₁ и x₂, y₂ верхней левой и нижней правой вершины соответственно. Мы выясняем, является ли этот прямоугольник белым (нет ли внутри черной клетки), и если да, то измеряем его площадь.

Мы проделываем это для x₁, y₁, пробегающих все игровое поле, а x₂, y₂ должны удовлетворять неравенствам x₂ ≥ x₁, y₂ ≥ y₁ и пробегать часть игрового поля, удовлетворяющую этим неравенствам.

Так как для каждого прямоугольника вы должны пробежать его по всей его площади целиком, то порядок роста программы есть n⁴. Но вы можете улучшить программу уже здесь, не рассматривая такие точки x₁, y₁, которые не могут дать площади прямоугольника, превосходящей уже найденный максимум (это — близкие к правому краю или к нижнему краю точки игрового поля).

Вы можете сделать еще лучше, задав лучшую информацию. Предположим, например, что у вас есть вектор размерности n, — скажем вектор l такой, что l[i] есть число последовательных белых полей на строке i, начиная со столбца l. Тогда вы можете легко найти площади белых прямоугольников, одна из вершин которых находится в точке x₁ = j, y₁ = i. Нисколько не более трудно перейти и от вектора l для столбца j к вектору, связанному со столбцом j + 1.

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

Головоломка 38.

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

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

8 12 16 20 и другим числом, скажем 24,

чтобы ответы образовывали арифметическую прогрессию с разностью 4. Сделаем то же самое для других вопросов. Таким образом, вы получите, например:

R1: 8 12 16 20 24

R2: 12 14 16 18

RЗ: 10 12 14

R4: 16 18 20 22 24

Исследуем все полученные из оценок четверки чисел, отводя по строчке для каждой из них. Они образуют 5*4*3*5 = 300 строк. Для каждой из них ваша программа смотрит, сколько учеников получило 0, и запоминает только те четверки чисел, для которых один и только один ученик получил 0 (это дано в условии). Заметьте к тому же, что вам сообщено, что ответом на один из вопросов должна быть площадь поверхности куба с целым ребром, следовательно, число вида 6n², возможные значения которого 6, 24… Ни один из ответов не имеет вида 6n² с целым n. Следовательно, мы должны получить, что в выделенных четверках есть одна или несколько четверок, у которых хотя бы одна компонента имеет значение, не предложенное ни одним из учеников. Ваша программа легко их найдет (такой набор в точности один). На этом основании мы узнаем правильность всех ответов на вопросы, остальное просто.

При всем том, это — головоломка для начинающих…

Головоломка 39.

Эта головоломка сопротивлялась мне много дней и была для меня очень поучительной. В условии сказано, что эта программа должна выполняться за время вычисления, пропорциональное n. Следовательно, и речи нет о том, чтобы исследовать все суммы подпоследовательностей вектора, чтобы выбрать из них наилучшую. Нужно исхитриться. Так же, как мы здесь уже упоминали, ответ может состоять в получении свойств подпоследовательности с максимальной суммой.

Я совершил ошибку, пойдя по этому пути. Я сказал себе: назовем S(i, j) сумму элементов вектора с номерами от i до j:

S(i, j) = a_i + a_i+1 + … + a_j−1 + a_j.