Meet-in-the-middle

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

Упражнения

A: Теорема Лагранжа

Теорема Лагранжа заключается в том что каждое целое неотрицательное число может быть представлено в виде суммы четырёх квадратов целых чисел. Научитесь строить такое представление.

Первая строка входных данных содержит целое положительное число $t$ — количество чисел, для которых вам необходимо найти ответ. Следующие $t$ строк содержат $t$ различных целых неотрицательных чисел, не превосходящих ${10}^7$ каждое. Сумма всех данных чисел не превосходит ${10}^8$.

Для каждого из данных $t$ чисел выведите четыре целых неотрицательных числа, дающих в сумме данное число.

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

10
1
2
3
4
5
6
7
8
9
179

0 0 0 1
0 0 1 1
0 1 1 1
0 0 0 2
0 0 1 2
0 1 1 2
1 1 1 2
0 0 2 2
0 0 0 3
0 1 3 13

B: Балансировка

У вас есть несколько камней известного веса $w_1$, ..., $w_n$. Напишите программу, которая распределит камни в две кучи так, что разность весов этих двух куч будет минимальной.

Программа получает на вход количество камней $n$ $(1\le n\le 40)$ и веса камней $w_1$, ..., $w_n$ $(1\le w_i\le {10}^9)$ — целые, разделённые пробельными символами.

Выведите одно целое неотрицательное число — минимальную разность весов двух куч.

5
46 25 62 11 45

7

С: Ещё один вариант задачи о рюкзаке

У вас есть несколько камней известного веса $w_1$, ..., $w_n$ и значение $S$. Определите количество подмножеств данного множества, суммарный вес камней в котором равен $S$.

Программа получает на вход количество камней $n$ $(1\le n\le 40)$, значение $S$ ($0\le S\le 4\cdot {10}^{10}$) и веса камней $w_1$, ..., $w_n$ $(1\le w_i\le {10}^9)$ — целые, разделённые пробельными символами.

Выведите одно целое неотрицательное число — количество искомых подмножеств.

10 20
1 2 3 4 5 6 7 8 9 10

31

D: Робот

Робот начинает движение в точке ($0$, $0$) координатной плоскости и должен оказаться в точке ($x_f$,$y_f$). Изначально есть список из $N$ инструкций для робота, $i$-я из которых перемещает робота на $x_i$ единиц вправо и на $y_i$ единиц вверх (или влево и вниз, если $x_i$ или $y_i$ отрицательные, соответственно).

Для каждого $K$ от $1$ до $N$ вычислите количество способов выбрать $K$ инструкций из исходного списка так, что после применения этих $K$ инструкций робот окажется в точке ($x_f$, $y_f$).

Первая строка входных данных содержит число $N$, $1\le N\le 40$. Следующая строка содержит целые $x_f$ и $y_f$, не превосходящие по модулю ${10}^9$. Следующие $N$ строк описывают инструкции. Каждая строка содержит два целых числа $x_i$ и $y_i$, также не превосходящие по модулю ${10}^9$. Гарантируется, что $(x_f,y_f)\ne (0,0)$ и $(x_i,y_i)\ne (0,0)$ для всех $i$.

Выведите $N$ строк: количество способов, которыми можно выбрать $K$ инструкций из списка оригинальных $N$ для каждого $K$ от $1$ до $N$, чтобы выбранный набор инструкцию приводил робота в нужную точку.

7
5 10
-2 0
3 0
4 0
5 0
0 10
0 -10
0 10

0
2
0
3
0
1
0

E: Дискретное логарифмирование

Пусть дано простое число $p$, основание степени $a$, $2\le a<p$ и другое число $b$, $2\le b<p$. Задача дискретного логарифмирования заключается в нахождении такого числа $x$, что $a^x\equiv b(\mathrm{mod}p)$.

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

Наивный алгоритм решения заключается в последовательном вычислении $a^1$, $a^2$, $a^3$ и т.д. Такой алгоритм имеет сложность $O(p)$.

Используя идею Meet-in-the-middle можно реализовать алгоритм сложности $O(\sqrt{p})$, этот алгоритм называется «Baby–step giant–step».

Возьмём $m=\lceil \sqrt{p}\rceil$. Пусть $x=im+j$, где $0\le i<m$, $0\le j<m$ (здесь мы также используем идею корневой оптимизации).

Тогда $a^x\equiv a^{im+j}\equiv (a^m{)}^i{a}^j(\mathrm{mod}p)$. Теперь искомое сравнение можно переписать в виде $$a^j\equiv b(a^{-m}{)}^i$$

Здесь $a^{-m}$ — это $(a^{-1}{)}^m$, то есть обратный элемент к $a$, возведённый в степень $m$. Напомним, что обратный элемент по простому модулю проще всего искать при помощи малой теоремы Ферма.

Вычислим все значения $a^j$ для $0\le j<m$ и сохраним их в map. Теперь будем вычислять последовательно $b(a^{-m}{)}^0$, $b(a^{-m}{)}^1$, $b(a^{-m}{)}^2$, .... Для каждого такого значения будем проверять, есть ли в map посчитанное подходящее значение $a^j$, которое сделает равенство верным. Если есть — мы нашли решение.

Программа получает на вход числа $p$, $a$, $b$, где $p$ — простое число, $3\le p<2\times {10}^9$, $2\le a<p$, $2\le b<p$.

Программа должна вывести такое минимальное целое положительное $x$, что $a^x\equiv b(\mathrm{mod}p)$, или число $-1$, если такого $x$ не существует.

17
12
3

5

3
2
2

1

7
2
3

-1

F: Размер наибольшей подклики

Эта задача не на meet-in-the-middle, а на динамическое программирование. Она пригодится для решения задачи о клике.

Вам дан граф из $n\le 12$ вершин. Рассмотрим $2^n$ подмножеств его вершин. Для каждого подмножества $A$ найдите размер максимальной клики, которую можно выделить в $A$ (то есть размер максимальной клики, которая была бы подмножеством $A$).

Первая строка входных данных содержит количество вершин в графе $n$ ($1\le n\le 12$). В следующих $n$ строках задана матрица смежности графа: $n$ строк по $n$ чисел в каждой. Число, стоящее в $i$-й строке $j$-м столбце равно 1, если есть ребро между вершинами $i$ и $j$.

Программа должна вывести $2^n$ строк, каждая строка соответствует одному подмножеству. Сначала выводится код подмножества: последовательность из $n$ символов $0$ или $1$, означающих, входит ли данная вершина в множество. Кодировать вершины будем от большего номера к меньшему. Например, строка $100110$ при $n=6$ означает, что в множество входят вершины $6$, $3$, $2$.

После кода подмножества через пробел выведите размер максимальной подклики в данном подмножестве. Строки должны идти в лексикографическом порядке кодов подмножества.

Указание. Будем использовать динамическое программирование. Пусть $f(A)$ — размер максимальной подклики для множества $A$. В частности, $f(\varnothing )=0$.

Научимся пересчитывать $f(A$). Пусть $i$ — номер наибольшей вершины в множестве $A$, то есть индекс старшей единицы в $A$. Пусть $B=A\setminus \{i\}$, то есть множество, полученное удалением $i$ из $A$.

У нас есть два варианта построить максимальную подклику в $А$.

Если $i$ не войдёт в подклику, тогда ответ для $A$ будет совпадать с ответом для $B$: $f(A)=f(B)$.

Если $i$ войдёт в подклику, тогда рассмотрим множество вершин из $B$, которые соединены с вершиной $i$. Это $\text{mask}(i)\cap B$, где $\text{mask}(i)$ — множество вершин, смежных с $i$. Размер максимальной подклики в этом множестве мы уже вычислили, это $f(\text{mask}(i)\mathrm{\&}B)$. Тогда $f(A)=1+f(\text{mask}(i)\mathrm{\&}B)$.

Теперь выберем наибольшее: $f(A)=max(f(B),1+f(\text{mask}(i)\mathrm{\&}B))$, где $B=A\setminus \{i\}$.

4
0 1 0 0
1 0 1 1
0 1 0 1
0 1 1 0

0000 0
0001 1
0010 1
0011 2
0100 1
0101 1
0110 2
0111 2
1000 1
1001 1
1010 2
1011 2
1100 2
1101 2
1110 3
1111 3

G: Количество подклик

Решите задачу, аналогичную предыдущей, только для каждого подмножества вершин $A$ посчитайте количетсво подграфов этого множества, являющихся кликами. Пустой подграф и граф из одно вершины также является кликой.

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

Формат ввода и вывода аналогичен предыдущей задаче.

4
0 1 0 0
1 0 1 1
0 1 0 1
0 1 1 0

0000 1
0001 2
0010 2
0011 4
0100 2
0101 3
0110 4
0111 6
1000 2
1001 3
1010 4
1011 6
1100 4
1101 5
1110 8
1111 10

H: Количество клик

В данном графе из $n\le 40$ вершин найдите количество подграфов, являющихся кликами.

Воспользуемся методом Meet-in-the-middle. Разобьём множество вершин графа на две части $A$ и $B$ размером $n/2$ каждая. В каждой части для каждого подмножества вершин посчитаем количество подграфов данного множества, являющихся кликами, пусть $f(m)$ — количество подклик в множестве $m$, как в предыдущей задаче.

Будем перебирать подмножества $a$ первой части $A$. Чтобы $a$ являлось частью какой-то клики, необходимо, чтобы $a$ само было кликой. Это можно проверить, используя насчитанные значения динамики (как?).

Давайте посчитаем количество способов добавить к множеству $a$ вершины из $B$ так, чтобы получилась клика. То есть вершины из $a$ должны быть соединены со всеми вершинами из добавляемых вершин $b$.

Построим множество $b=\bigcap _{i\in a}\text{mask}(i)\cap B$ — множество всех вершин из $B$, которые соединены с вершинами из $a$. Любое подмножество этих вершин, являющееся кликой, останется кликой, если добавить к нему вершины из $a$. То есть к ответу нужно добавить $f(b)$.

Сложность решения будет $O(n{2}^{n/2})$.

Формат входных данных совпадает с предыдущей задачей, только $n\le 40$.

Программа должна вывести единственное число — количество клик в данном графе.

5
0 1 0 0 0
1 0 1 0 1
0 1 0 1 1
0 0 1 0 1
0 1 1 1 0

14

I: Максимальная клика

В данном графе из $n\le 40$ вершин найдите наибольшую клику.

Воспользуемся методом Meet-in-the-middle. Разобьём множество вершин графа на две части $A$ и $B$ размером $n/2$ каждая. В каждой части для каждого подмножества вершин найдём наибольшую клику.

Теперь будем искать наибольшую клику $c$. Вершины $c$ попадают в $A$ и в $B$. Пусть $a=C\cap A$  множество вершин клики $c$, попавшие в $A$. Тогда $a$ является кликой, возможно, пустой.

Будем перебирать $a$, проверяя, что $a$ является кликой. Для подходящего множества $a$ найдём все вершины из $B$, которые соединены со всеми вершинами из $a$. Это множество $b=\bigcap _{i\in a}\text{mask}(i)\cap B$. Найдём теперь размер максимальной подклики в $b$, что мы уже посчитали заранее. Так мы получили размер максимальной клики, содержащей подмножество $a$ (и не содержащее других вершин из $A$).

Сложность решения будет $O(n{2}^{n/2})$.

Формат входных данных совпадает с предыдущей задачей, $n\le 40$.

Программа должна вывести номера вершин, входящих в максимальную клику.

5
0 1 0 0 0
1 0 1 0 1
0 1 0 1 1
0 0 1 0 1
0 1 1 1 0

3 4 5

J: Четыре разворота

Даны две строки. Определите, можно ли получить одну из другой используя четыре операции вида «взять подстроку в строке и развернуть её в обратном порядке».

Программа получает на вход две строки, состоящие из строчных английских букв. Длины строк равны $n$, $n\le 20$.

Если вторую строку можно получить из первой при помощи четырёх операций разворота подстроки, то выведите эти четыре операции в виде четырёх строк. $i$-я из этих строк должна содержать два числа $a_i$ и $b_i$, $1\le a_i\le b_i\le n$ — номера первого и последнего символа подстроки, которые нужно развернуть. Нумерация начинается с 1, крайние символы также участвуют в развороте. Если решений несколько, можно вывести любое.

Если получить вторую строку из первой при помощи четырёх таких операций нельзя, выведите одно число «$-1$».

abacaba
aaaabbc

2 3
3 7
6 7
4 5

ababababab
bbbbbaaaaa

-1

K: Почти пятнашки

В игре «Пятнашки» необходимо упорядочить 15 фишек, перемещая их внутри квадрата $4\times 4$, используя одно свободное место.

В пятнашках возможно построить кратчайшее решение для любой позиции (для которой это решение существует) используя возможности обычного компьютера, но решение будет довольно долго работать и ему понадобится несколько гигабайт памяти. Поэтому вам нужно научиться решать упрощённую версию головоломки, в которой поле состоит из 3 строк и 4 столбцов и 11 фишек с числами от 1 до 11. Вам необходимо переместить фишки так, чтобы в верхнем ряду были числа 1, 2, 3, 4, во втором ряду — 5, 6, 7, 8, в третьем ряду  9, 10, 11, пустой была бы клетка в правом нижнем углу.

Программа получает на вход 12 чисел — по 4 числа в 3 строках. Числа имеют значения от 0 до 12, значение 0 обозначает пустую клетку. Гарантируется, что все числа от 0 до 11 встречаются ровно 1 раз и что головоломка с таким размещением фишек имеет решение.

Программа должна вывести в первой строке число $n$ — минимальное число перемещений фишек, необходимое для решения головоломки. Во второй строке выведите $n$ символов, обозначающих перемещения. Символы могут быть «L» (влево), «R» (вправо), «U» (вверх), «D» (вниз), обозначающих перемещение какой-то фишки в указанном направлении, на место пустой фишки.

Ограничения по времени (30 секунд) и памяти (2 GiB) установлены экcпериментально, они в два раза превышают ограничения авторского решения. Но если использовать больше 1 GiB памяти есть шанс активного использования своп-памяти, что приведёт к превышению ограничения астрономического времени. Возможно, вам придётся экономить и память программы. Вероятно, вам понадобится множество экспериментов со своим приложением. В системе Linux вы можете определить время работы программы и размер использованной памяти при помощи команды time.

Одну игровую позицию рекомендуется хранить в 64-битной целочисленной переменной.

 1  2  7  3
 5  6 11  4
 9 10  8  0

6
RDDLUU