algrid

char *strstr(const char *haystack, const char *needle);

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

Но я это все не к тому, чтобы раскритиковать авторов - передача забавная, посмотреть интересно, если оставить за скобками всякие заумные научности :) Вся эта история с резонансом навела меня на другую мысль - возможно у сложной конструкции в процессе "раскачивания" резонансная частота будет меняться. (А может быть таких пиковых частот будет несколько с различной добротностью колебательной системы на этих частотах? Хотя я не уверен, что на самом деле бывает несколько подобных частот, за исключением кратных основной, резонансной.)

Почему бы тогда не встроить в пресловутое устройство Теслы акселерометр, который будет периодически измерять частоту собственных колебаний системы и соответствующим образом корректировать частоту устройства, воздействующего на систему? Может быть тогда и получится разрушить мост или здание? :)

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

Обозначим:

P[x..y] – паттерн, состоящий из символов с x по y исходного паттерна
SP[x..y] – строка, состоящая из символов с x по y исходной строки super password
A[i, j] – минимальная сложность пароля, соответствующего паттерну P[1..i] в строке SP[1..j] (или -1, если такого не существует)
W[k] – сложность символа SP[k]
Считаем, что символы в P и SP нумеруются, начиная с единицы.

Для начала, положим A[0,j] = 0 для всех j
Далее A[i,j] будет определяться следующим образом

1. Если P[i] = ‘?’, то
Если A[i-1, j-1] = -1 или j =0, то A[i,j] = -1,
иначе A[i,j] = A[i-1, j-1]+W[j]

2. Если P[i] – буква
Если A[i-1, j-1] = -1 или P[i]=SP[j] или j =0, то A[i,j] = -1,
иначе A[i,j] = A[i-1, j-1] +W[j]

3. Если P[i] = ‘*’
A[i,j] = A[i-1,k]+W[k+1]+…+w[j],
где k – наибольшее значение, для которого k<=j, A[i-1,k] != -1
Если таких k не существует, то A[i,j] = -1

Поясню последний пункт, а именно, почему выбирается именно наибольшее значение k. Пусть существует меньшее значение k1<k, для которого

A[i-1,k1]+W[k1+1]+…+W[j] < A[i-1,k]+W[k+1]+…+W[j] (1)

Значение A[i-1,k] соответствует некоторой подстроке SP[x,k], а значение A[i-1,k1] – подстроке SP[x1,k1], причем x1 > x (иначе не будет выполнено (1)). Таким образом, SP[x1,k1] является подпоследовательностью SP[x,k], причем обе эти строки соответствуют одному и тому же паттерну P[1..i-1]. Это строки различной длины, следовательно этот паттерн содержит хотя бы один символ ‘*’.

Обозначим наибольший индекс символа ‘*’ в P[1..i-1] за q и рассмотрим паттерн P[q..i-1]. В строке SP[x,k] ему соответствует некоторая подстрока SP[y,k], а в строке SP[x1,k1] - SP[y1,k1]. Тогда этому же паттерну соответствует и строка SP[y1, k], а, следовательно, исходному паттерну P[1..i-1] соответствует строка SP[x1, k], причем сложность ее меньше, чем сложность SP[x,k] (так как x1 > x). Это противоречит тому, что A[i-1,k] – это минимальная сложность. Следовательно, значения k1<k, удовлетворяющего (1) не существует.

При решении нам достаточно лишь двух строк A[i-1,…] и A[i, …], следовательно, с памятью проблем не возникает. Пройдясь по всем символам паттерна (индекс i), мы получим массив A[n,…], из которого выберем минимальное значение (среди элементов, не равных -1), которое и будет решением. Если же все элементы этого массива равны -1, то таков и ответ.

Остается перебрать все |b| <= 10^5 и найти такое значение b, для которого мы получим целое p – это и будет искомый результат. Так как при изменении знака b корни уравнения меняют знак, мы можем перебирать значения b от 0 до 10^5, а вычислив значения корня, принимать за p его абсолютную величину.

Верхняя граница для b при небольших n и k может быть уменьшена. Если n/2 + n*k/a < 10^5, то принимаем n/2 + n*k/a за эту границу. Здесь a=up(sqrt(n)), где up – округление вверх до ближайшего целого. Это справедливо, так как p <= q, и, следовательно, |q-kp| < q+kp<= n/2 + k*n/a

Большая часть вычислительных ресурсов уходит на определение, является ли дискриминант b^2+4kn квадратом целого числа. Быстрых алгоритмов проверки этого факта, не требующих вычисления квадратного корня, я не знаю (если знаете - подскажите). Таким образом, приходится вычислять квадратный корень, что занимает значительную часть времени работы программы.

Для решения этой задачи выбрана Java, так как там есть готовая библиотека для работы с большими числами. Я использовал класс BigInteger, который, к сожалению, не поддерживает вычисление квадратного корня (что мне показалось несколько странным – вполне можно было бы реализовать вычисление целой части корня целого числа). Пришлось реализовать эту функцию самому. Для этого использовался алгоритм Ньютона, причем начальное приближение вычислялось как минимальная степень двойки, превышающая sqrt(x). Хороший выбор первого приближения очень важен, так как обеспечивает высокую скорость вычисления требуемого значения.

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

При решении задачи был замечен такой интересный момент – если перебирать значения b в обратном направлении (то есть от 10^5 до 0), то время работы программы увеличивается почти на 2 порядка и составляет более 10 секунд - такой вариант уже вряд ли бы прошел.

Насколько я знаю, такого рода задача может решаться двумя способами: либо перебором, либо методами динамического программирования. Размерность M <= 10^9 сразу навела на мысль, что для динамического программирования явно не хватит памяти. Возможно, тут и есть какие-то перспективы, но я от этого подхода отказался. Ограничение N <= 15, напротив, внушало оптимизм в плане применения перебора. Но все оказалось не так просто. Реализованный «в лоб» перебор работал слишком медленно. Пришлось искать отсечения, которые уменьшили бы дерево поиска.

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

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

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

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

3. Если для некоторых двух ящиков i и j (считаем, что i<j, и ящики в процессе поиска рассматриваются в порядке возрастания их номеров) выполнено: w[i] <= w[j] и c[i] >= c[j], то брать алмазы из ящика j имеет смысл только тогда, когда уже взято максимальное количество алмазов из ящика i.

4. Если для некоторых двух ящиков i и j (считаем, что i<j, и ящики в процессе поиска рассматриваются в порядке возрастания их номеров) выполнено: w[i] >= w[j] и c[i] <= c[j], и из ящика i взято ненулевое количество алмазов, то брать алмазы из ящика j имеет смысл только все.

В итоге программа на не очень быстрой машине проходит тесты за время около 1,5 секунд. Думаю, что это более-менее удобоваримый результат.

Согласно данным acm.ro , эту задачу на олимпиаде не решила ни одна команда. Думаю, что это не удивительно, потому что, во-первых, я сам решал ее пару дней, имя под рукой тесты :) (хотя это, конечно, не показатель), а во-вторых, абсолютно не факт, что данный перебор с данными отсечениями будет работать за приемлемое время на произвольных входных данных. Но, тем не менее, программа работает, тесты проходит… :)