- PVSM.RU - https://www.pvsm.ru -
После того, как вроде бы неплохой результат, полученный в предыдущей части [1], оказался лишь «локальным максимумом», я на некоторое время забросил задачку. Напомню условие:
«The decimal number 585 is 1001001001 in binary. It is palindromic in both bases. Find n-th palindromic number». Или, по-русски: «Десятичное число 585 в двоичной системе счисления выглядит как 1001001001. Оно является палиндромом в обеих системах счисления. Найдите n-й подобный палиндром».
Но само существование значительно более быстрого, с принципиально другой вычислительной сложностью, алгоритма не давало мне покоя, и в конце концов я вернулся к его разбору [2].
В конце концов, алгоритм оказался не таким уж и сложным, зато, на мой взгляд, очень красивым.
Оригинальное объяснение и реализация используют префиксное дерево, но на мой взгляд, чуть более глубокое понимание математики алгоритма позволяет обойтись более простыми и быстрыми структурами. Думаю, что лучше всего разобрать алгоритм на примере.
Мы будем искать двоичные палиндромы среди десятичных палиндромов шириной 8. Исходных палиндромов ровно 9000: от 10000001 до 99999999.
Теперь возьмём 2 множества чисел:
Если описывать эти множества формально, то множество А является подмножеством десятичных палиндромов шириной 8, у которых средние 4 разряда — нули, а множество B состоит из 0, множества десятичных палиндромов шириной 2, умноженных на 103 и множества десятичных палиндромов шириной 4, умноженных на 102.
А если неформально, то множество А — это все возможные «края», а множество B — все возможные «серединки» десятичных палиндромов шириной 8. Очевидно, что множество всех десятичных палиндромов шириной 8 — это множество всех попарных сумм элементов множеств A и B.
for each (a in A) {
for each (b in B) {
palindrome = a + b;
}
}
Далее, для краткости я буду использовать «a» вместо «элемент множества A», и «b» вместо «элемент множества B».
Теперь переведём элементы обоих множеств в двоичную систему счисления:
A
10000001 100110001001011010000001
11000011 101001111101100011001011
12000021 101101110001101100010101
…
98000089 101110101110101110011011001
99000099 101111001101001111100100011
B
00000000 000000
00011000 10101011111000
00022000 101010111110000
…
00988900 11110001011011100100
00999900 11110100000111011100
Я выделил по 6 верхних и нижних разрядов у всех a, и 6 нижних разрядов у всех b. Ширина 6 выбрана не случайно — это максимальная степень 2, не превышающая ширину «краёв» A = 102.
Теперь возьмём каждый a, и посмотрим, что общего у всех палиндромов, образованных от него прибавлением b. А общее у них, то, что все они находятся в интервале между самим a и следующим за ним элементом A.
Например, для a = 10000001, все образованные от него десятичные палиндромы { 10000001, 10011001, 10022001, ..., 10988901, 10999901 } находятся в интервале [10000001, 11000011).
Это значит, что все десятичные палиндромы, образованные от a = 10000001 могут начинаться только со следующих 6 двоичных цифр:
100110 — первые двоичные цифры a = 10000001
100111
101000
101001 — первые двоичные цифры a = 11000011
Следовательно, чтобы быть двоичными палиндромами, все эти десятичные палиндромы могут заканчиваться только на обратную перестановку начальных двоичных цифр:
100110 -> 011001
100111 -> 111001
101000 -> 000101
101001 -> 100101
А учитывая, что сам а = 10000001 заканчивается на двоичные цифры 000001, то из всех возможных b нас интересуют только те, которые заканчиваются на двоичные цифры:
011001 — 000001 = 011000
111001 — 000001 = 111000
000101 — 000001 = 000100
100101 — 000001 = 100100
Только для таких b нужно проверять, является ли 10000001 + b двоичным палиндромом.
Используя данный подход, алгоритм для нахождения палиндромов в основаниях BASE0, BASE1 в интервале [1, N] может быть описан следующим образом:
Для каждой ширины W из [1, количество разрядов N в BASE0]
Сгенерировать множества A и B, используя BASE0. Ширина «краёв» A WA = O(W/4), WA ≥ WB
Перевести элементы A и B в BASE1
Рассортировать элементы B по корзинам по последним цифрам в BASE1
Для каждого a из множества A
Для каждого X из множества возможных начальных цифр a + b
Для каждого b, заканчивающегося на (X — конечные цифры a)
Проверить, является ли a + b палиндромом в BASE1
К сожалению, я уже разучился строго доказывать вычислительную сложность алгоритмов, приведу лишь несколько соображений:
В общем, я предполагаю, что вычислительная сложность алгоритма O(N1/4 * log(N) * BASE0 * BASE1).
Первая же реализация этого алгоритма вполне предсказуемо была на пару порядков быстрее, а потратив еще немного времени на оптимизацию я довел время вычисления до чуть более 0.01 секунды, более чем в 1000 раз быстрее предыдыщего алгоритма. Этот результат наконец-то меня удовлетворил, но вполне естественно возникло желание проверить его на числах, бо́льших, чем 260. К этому времени я уже обнаружил интересующую меня последовательность [3] в «Энциклопедии целочисленных последовательностей». В списке двойных палиндромов [4] было 122 члена, самый большой из которых состоял из 131 бита. Это было впечатляюще, но и косвенно указывало на то, что никто пока не придумал алгоритм логарифмической сложности.
Вызов был серьёзный — можно было не сомневаться, что люди, получившие такой результат, вложили немало сил в разработку алгоритма и к тому же наверняка были готовы потратить дни и недели машинного времени на последующий поиск. Поэтому, я решил хотя бы приблизительно оценить, время, которое необходимо моему алгоритму на повторение:
2131 / 260 = 271
271 * 1/4 < 218 = 262144
Учитывая 0.01 секунды, необходимых для предела в 260, выходило, что мой алгоритм должен был справиться с этой задачей примерно за 1 час! Я чувствовал какой-то подвох, но вызов был уже принят.
Продолжение следует.
Автор: ilyanik
Источник [5]
Сайт-источник PVSM.RU: https://www.pvsm.ru
Путь до страницы источника: https://www.pvsm.ru/programmirovanie/106494
Ссылки в тексте:
[1] предыдущей части: http://habrahabr.ru/post/272555/
[2] разбору: https://discuss.codechef.com/questions/74483/dualpal-editorial
[3] последовательность: https://oeis.org/A007632
[4] списке двойных палиндромов: https://oeis.org/A007632/b007632.txt
[5] Источник: http://habrahabr.ru/post/272659/
Нажмите здесь для печати.