Грустные числа

Условие задачи

В задаче Project Euler 1003 рассматривается процесс с камнями на целочисленных позициях прямой. В позиции \(0\) изначально лежит положительное число камней \(n\). Дальше позиции обрабатываются слева направо.

Если в позиции \(i\) находится \(m\) камней, то:

• \(\lfloor m / 2 \rfloor\) камней уходит в позицию \(i + 1\);
• ещё \(\lfloor m / 2 \rfloor\) камней уходит в позицию \(i + 3\);
• если \(m\) нечётно, один камень остаётся в позиции \(i\).

Оставшиеся одиночные камни будем называть singletons. Singleton считается lonely, если от него до любого другого singleton расстояние хотя бы \(3\). Число \(n\) называется sad, если все оставшиеся singletons lonely.

Нужно просуммировать все sad-числа, у которых singletons появляются только на позициях \(0 \le i < k\), для заданного значения \(k\).

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

Почему не перебор по \(n\)

Самая естественная первая идея — взять \(n\), запустить процесс и посмотреть, где остались singletons. Для маленьких \(n\) это работает, но как основная стратегия плохо масштабируется.

Проблем несколько.

Во-первых, в задаче не дано явной верхней границы для \(n\). Мы хотим найти все sad-числа, у которых singletons лежат ниже \(k\), но из этого напрямую не следует удобная граница на само \(n\).

Во-вторых, процесс может не завершаться. Значит, симулятор должен уметь отличать «ещё не дошли до стабилизации» от «процесс будет продолжаться бесконечно». Это уже не просто цикл по позициям.

В-третьих, условие sad относится не к промежуточным кучам, а к позициям одиночных остатков. То есть естественный объект задачи — не траектория всех камней, а бинарная последовательность чётностей: была ли позиция нечётной в момент обработки.

Поэтому удобнее развернуть задачу наоборот: зафиксировать возможное множество позиций одиночных камней и восстановить из него \(n\).

Обозначения

Пусть \(a_i\) — число камней в позиции \(i\) в момент её обработки. Обозначим через \(b_i\) чётность этого числа: \(b_i = a_i \bmod 2\), где \(b_i\) равно \(0\) или \(1\).

Если \(b_i = 1\), значит в позиции \(i\) остаётся singleton. Если \(b_i = 0\), одиночного остатка в этой позиции нет.

Также введём \(q_i = \lfloor a_i / 2 \rfloor\). Это число камней, которое уходит из позиции \(i\) в позицию \(i + 1\), и такое же число уходит в позицию \(i + 3\).

Тогда для каждой позиции верно:

\[ a_i = b_i + 2q_i. \]

С другой стороны, камни в позицию \(i\) могут прийти только из позиций \(i - 1\) и \(i - 3\), кроме стартовой позиции \(0\), где изначально лежит \(n\) камней. Поэтому

\[ a_i = n[i=0] + q_{i-1} + q_{i-3}, \]

где \(q_j = 0\) для отрицательных индексов, а \([i=0]\) — индикаторная функция.

Совмещая две формулы, получаем основную рекурсию:

\[ b_i + 2q_i = n[i=0] + q_{i-1} + q_{i-3}. \]

Это уже почти вся задача. Осталось понять, как извлечь из этой рекурсии удобное условие на множество позиций, где \(b_i = 1\).

Производящие функции

Для работы с такой рекурсией удобно использовать производящие функции. Введём два формальных степенных ряда:

\[ B(x)=\sum_i b_i x^i,\qquad Q(x)=\sum_i q_i x^i. \]

Смысл здесь простой: последовательность чисел упаковывается в многочлен или степенной ряд. Сдвиг индекса превращается в умножение на \(x\). Поэтому рекурсия с задержками на \(1\) и \(3\) шага превращается в алгебраическое равенство.

Из основной рекурсии получается:

\[ B(x)+2Q(x)=n+(x+x^3)Q(x). \]

Переносим члены с \(Q(x)\) в одну сторону:

\[ (2-x-x^3)Q(x)=n-B(x). \]

Дальше появляется ключевое разложение:

\[ 2-x-x^3=(1-x)(x^2+x+2). \]

Именно оно превращает задачу из динамики камней в задачу о сравнении многочленов по модулю квадратного многочлена.

Почему возникает модуль \(x^2 + x + 2\)

Если singletons конечны, то после последней позиции, где \(b_i = 1\), последовательность \(q_i\) удовлетворяет однородной рекурсии:

\[ 2q_i=q_{i-1}+q_{i-3}. \]

Для этой задачи важно, что хвост последовательности стабилизируется. Поэтому \((1-x)Q(x)\) становится обычным многочленом. Обозначим его через \(C(x)\):

\[ C(x)=(1-x)Q(x). \]

Тогда из предыдущего равенства следует:

\[ (x^2+x+2)C(x)=n-B(x). \]

А значит,

\[ B(x)\equiv n \pmod{x^2+x+2}. \]

Это центральный переход. Мы больше не обязаны симулировать процесс для каждого \(n\). Вместо этого можно смотреть на возможные множества позиций singletons и проверять, какой остаток даёт соответствующий многочлен.

Такой подход близок к стандартной идее работы в фактор-кольце многочленов: мы считаем многочлены не буквально, а с точностью до кратности выбранного многочлена \(x^2+x+2\).

Переход к множествам singleton-позиций

Пусть \(T\) — множество позиций, где остаются singletons:

\[ T=\{i:b_i=1\}. \]

Тогда соответствующий многочлен имеет вид:

\[ B_T(x)=\sum_{i\in T}x^i. \]

Условие lonely означает, что любые две позиции из \(T\) отличаются хотя бы на \(3\). То есть в множестве \(T\) нельзя одновременно держать позиции на расстоянии \(1\) или \(2\).

Теперь каждому такому множеству \(T\) можно сопоставить остаток \(B_T(x)\) по модулю \(P(x)=x^2+x+2\).

Так как модуль имеет степень \(2\), любой остаток имеет вид \(ux+v\). Поэтому удобно заранее посчитать пары \((u_i, v_i)\), такие что

\[ x^i \equiv u_i x+v_i \pmod{x^2+x+2}. \]

Из сравнения \(x^2 \equiv -x - 2\) получаем начальные значения \((u_0,v_0)=(0,1)\) и \((u_1,v_1)=(1,0)\), а дальше для \(i \ge 2\):

\[ u_i=-u_{i-1}-2u_{i-2},\qquad v_i=-v_{i-1}-2v_{i-2}. \]

Это обычная линейная рекурсия второго порядка; похожие объекты часто возникают при вычислениях с многочленами по модулю. В терминах алгоритмов это просто динамическое вычисление остатков степеней \(x\).

Для множества \(T\) имеем:

\[ B_T(x)\equiv \left(\sum_{i\in T}u_i\right)x+ \sum_{i\in T}v_i \pmod{x^2+x+2}. \]

Чтобы остаток был обычным числом \(n\), коэффициент при \(x\) должен исчезнуть:

\[ \sum_{i\in T}u_i=0. \]

После этого кандидат на \(n\) равен сумме соответствующих \(v_i\):

\[ n=\sum_{i\in T}v_i. \]

Это и есть главный критерий для генерации кандидатов.

Почему одной проверки остатка недостаточно

На этом месте легко ошибиться и решить, что любое множество \(T\) с нулевым коэффициентом при \(x\) уже даёт sad-число. Это не так.

Сравнение по модулю \(x^2+x+2\) гарантирует только алгебраическую совместимость множества singleton-позиций с некоторым числом \(n\). Но исходный процесс требует больше: все величины \(q_i\) должны быть неотрицательными целыми числами, потому что это реальные количества камней.

Поэтому после получения кандидата нужно восстановить \(C(x)\) из равенства

\[ C(x)=\frac{n-B_T(x)}{x^2+x+2}. \]

Затем используется связь \(C(x)=(1-x)Q(x)\). Если коэффициенты \(C(x)\) обозначить через \(c_i\), то коэффициенты \(Q(x)\) получаются как частичные суммы:

\[ q_i=c_0+c_1+\dots+c_i. \]

Все эти \(q_i\) должны быть неотрицательны. Это точная проверка, а не эвристика.

Такой двухэтапный фильтр удобен практически: сначала дешёвое модульное условие, потом строгая проверка только для сравнительно малого числа кандидатов.

Проверка на примерах из условия

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

Для второго sad-числа в условии множество singleton-позиций равно \(\{2,5,8,13\}\). В терминах многочленов это

\[ B_T(x)=x^2+x^5+x^8+x^{13}. \]

После редукции по модулю \(x^2+x+2\) получается константа, соответствующая примеру из условия.

Для третьего sad-числа множество имеет вид \(\{1,13\}\), то есть

\[ B_T(x)=x+x^{13}. \]

Оно снова даёт константный остаток, совпадающий с публичным примером.

Также алгоритм должен воспроизводить два контрольных значения из условия: \(S(14)\) и \(S(30)\). Эти проверки полезны тем, что ловят разные классы ошибок:

• ошибку в рекурсии для остатков \(x^i\);
• ошибку в lonely-условии;
• ошибку в проверке неотрицательности \(q_i\);
• ошибку на границе диапазона \(0 \le i < k\).

Почему нужен meet-in-the-middle

После математического сведения остаётся перебрать множества \(T\) с расстоянием между элементами хотя бы \(3\). Количество таких множеств растёт экспоненциально. Это похоже на подсчёт независимых множеств в графе-пути с дополнительными рёбрами между вершинами на расстоянии \(2\).

Для \(k=80\) полный перебор всех допустимых \(T\) уже неприятен. Но структура условия хорошо подходит для meet-in-the-middle. Идея стандартная: вместо одного большого перебора по \(80\) позициям делим задачу на две половины по \(40\) позиций.

Левая половина: позиции \(0\ldots39\). Правая половина: позиции \(40\ldots79\).

Для каждой половины перебираются все подмножества с внутренним расстоянием хотя бы \(3\). Для каждого такого подмножества сохраняются:

• сумма \(u_i\);
• сумма \(v_i\);
• небольшая граничная маска.

Граничная маска нужна потому, что lonely-условие может нарушиться через разрез. Если делить между \(39\) и \(40\), то потенциальные конфликты только такие:

\[ (38,40),\qquad (39,40),\qquad (39,41). \]

Других конфликтов через границу нет, потому что расстояние уже будет хотя бы \(3\).

Дальше левая и правая половины склеиваются так, чтобы:

1. граничные маски были совместимы;
2. сумма коэффициентов \(u_i\) по двум половинам была равна нулю;
3. полученный кандидат \(n\) был положительным;
4. восстановленные значения \(q_i\) были неотрицательны.

Это резко уменьшает объём работы по сравнению с прямым перебором.

Почему я выбрал именно такой алгоритм

Были как минимум три возможных направления.

Первое — симулировать процесс по \(n\). Я его отбросил, потому что нет хорошей естественной верхней границы для \(n\), а часть процессов не завершается. Такой подход удобен для проверки маленьких примеров, но плохо подходит как основное решение.

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

Третье — перейти к множеству singleton-позиций и использовать производящие функции. Этот путь оказался самым чистым: условие lonely становится простым ограничением на расстояния в множестве \(T\), а восстановление \(n\) сводится к остатку многочлена по модулю \(x^2+x+2\).

После этого meet-in-the-middle — естественная инженерная оптимизация. Она не меняет математику решения, а только делает перебор достаточно быстрым.

Эскиз алгоритма без готового кода

Публично я не привожу готовую реализацию, но алгоритм можно описать так:

1. Для всех \(i < k\) вычислить пары \((u_i, v_i)\) из сравнения \(x^i \equiv u_i x + v_i \pmod{x^2+x+2}\).
2. Разделить диапазон позиций на две половины.
3. В каждой половине перебрать все подмножества, где расстояние между любыми двумя выбранными позициями хотя бы \(3\).
4. Для каждого подмножества сохранить сумму \(u_i\), сумму \(v_i\) и граничную маску.
5. Склеить левые и правые подмножества с совместимыми масками и противоположными суммами \(u_i\).
6. Для каждого кандидата восстановить \(n\) как сумму \(v_i\).
7. Проверить \(n > 0\).
8. Восстановить \(C(x)\) и через частичные суммы проверить, что все \(q_i\) неотрицательны.
9. Просуммировать все прошедшие кандидаты.

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

Итог

Главная идея решения — не моделировать камни напрямую, а смотреть на позиции одиночных остатков. Производящие функции переводят процесс в сравнение

\[ B_T(x)\equiv n \pmod{x^2+x+2}. \]

После этого sad-условие превращается в ограничение на расстояния внутри множества \(T\), а поиск всех подходящих \(n\) становится конечным перебором lonely-множеств с алгебраическим фильтром.

Meet-in-the-middle делает этот перебор практичным для нужного значения \(k\), а восстановление \(q_i\) через \(C(x)=(1-x)Q(x)\) даёт строгую финальную проверку, что найденный кандидат действительно соответствует исходному процессу с неотрицательным числом камней на каждом шаге.