9.10. Ответы на задачи

Контрольный вопрос 9.1: Очевидно: до этих клеток есть только один способ добраться, и потому а) \(ans[1,j]=ans[i,1]=1\); б) \(ans[1,j]\) и \(ans[i,1]\) равен сумме всех чисел по пути от начальной до этой клетки.

Задача 9.2: А до \(O(NS)\) ускоряется довольно легко. В решение подзадачи \((i,j)\) либо \(i\)-ая монета вообще не входит, и тогда \(ans[i,j]=ans[i-1,j]\), либо входит как минимум один раз, но тогда — внимание! — не будем перебирать, сколько именно, а просто выкинем одну \(i\)-ую монету из решения и получим решение для \((i,j-a_i)\) (а не \(i-1\), как было раньше). Т.е. теперь

\[\begin{split}ans[i,j]=\left\{ \begin{array}{ll} ans[i-1,j] {\ \mathrm{or} \ } ans[i,j-a_i],&\quad j\geq a_i,\\ ans[i-1,j],&\quad j<a_i, \end{array}\right.\end{split}\]

отличие в том, что в первой строке теперь \(ans[i,j-a_i]\), а не \(ans[i-1,j-a_i]\).

И ещё подумайте, как тут инициализировать массив перед запуском динамики. Если, как и раньше, отдельно решать задачу с \(i=1\), то понадобится отдельный цикл. Не очень сложно, но неприятно. Можно поступить и проще, введя нулевую строку, о чем я рассказываю ниже в основном тексте.

Задача 9.3: Не буду писать решение с двумя массивами, сразу напишу с одним. Самое простое — хранить в массиве \(ans\) следующее. Если задача \((i,j)\) разрешима, то в \(ans[i,j]\) храним минимальное количество монет для подзадачи \((i,j)\), иначе в \(ans[i,j]\) храним \(\infty\) (т.е. число, которое больше любых ответов на задачу — например, \(N+1\)). Тогда несложно видеть, что верно следующее рекуррентное соотношение:

\[\begin{split}ans[i,j]=\left\{ \begin{array}{ll} \min\big(ans[i-1,j],\quad ans[i-1,j-a_i]+1\big),&\qquad j\geq a_i,\\ ans[i-1,j],&\qquad j<a_i. \end{array}\right.\end{split}\]

(\(+1\) в соответствующем варианте, т.к. на одну монету больше берём. Очевидно, что и \(\infty\) обрабатывается корректно.) Если бы не додумались до \(\infty\), то можно было в \(ans[i,j]\) хранить \(-1\), когда решения нет, но тогда потребовались бы дополнительные if’ы.

Задача 9.4: Ну я думаю, задача очевидна. Пусть оптимальный путь \(P\) из \((1,1)\) до \((i,j)\) проходит через клетку \((i',j')\). Но из этого вовсе не следует, что соответствующее начало этого пути — оптимальный путь до \((i',j')\). Действительно, вполне может быть ещё более хороший путь до \((i',j')\). Раньше, без дополнительного ограничения, мы бы просто заменили начало нашего пути \(P\) на этот путь и получили бы ещё более хороший путь до \((i,j)\), а сейчас может не получиться — может оказаться, что на стыке более двух раз мы сходили в одну и ту же сторону. Говоря по-другому: пусть, например, оптимальный путь до \((i',j')\) заканчивается двумя ходами вправо — тогда после него мы обязаны будем пойти вверх, а может быть, выгоднее было бы дойти до \((i',j')\) другим, не столь дорогим путём, зато потом иметь право сразу пойти вправо.

Задача 9.5: Небольшая нетривиальность сведения: в каждой подзадаче \((i,j,a,b)\) мы теперь точно знаем последний ход, и потому точно знаем, откуда мы пришли в клетку \((i,j)\) — пусть это клетка \((i',j')\) (её координаты легко вычисляются по \((i,j)\) и \(b\)). Тогда наша подзадача сводится к одной или двум подзадачам — \(ans[i',j',c,b]\) с одним или двумя вариантами \(c\). Додумайте и обратите внимание, как тут учитывается требование не ходить более двух раз подряд в одну сторону.

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

Задача 9.6: Для каждого \((i,j)\) определим максимальную сумму, которую можно собрать по пути до \((i,j)\). Переберём, какой вектор будет последним ходом, и сравним ответы на соответствующие клетки.

Задача 9.7: На самом деле эти условия нужны для того, чтобы граф подзадач был ациклическим. Если эти условия не выполняются, то в общем случае черепашка сможет ходить по циклам, и оптимальный путь так просто динамикой искаться не будет (хотя алгоритмы решения существуют и для такого случая, и даже основанные на идеях ДП, но это уже скорее тематика теории графов, а не ДП). Конечно, может быть так, что граф подзадач будет ациклическим, даже если эти условия не выполняются (попробуйте придумать пример? :) ), и тогда ДП будет работать, только придётся писать рекурсию с запоминанием результата, см. ниже в основном тексте. Но для простоты можно поставить эти условия, чтобы гарантировать ацикличность.

Задача 9.8: Ну, я думаю, понятно. Как и в прошлом примере, когда черепашке нельзя ходить несколько раз в одну и ту же сторону, тут тоже возникнут проблемы при замене начала пути на соответствующий оптимальный путь: может оказаться, что какой-то вектор мы используем дважды. Потому не работает принцип оптимальности и потому не работает динамика.

Конечно, можно в подзадачу включить множество векторов, которые мы уже использовали, т.е. «для каждого \(i\), \(j\) и набора векторов \(M\) найдём оптимальный путь до \((i,j)\), использующий только вектора из множества \(M\)». Это и будет динамика по подмножествам. Поскольку всех вариантов для \(M\) у нас будет \(2^K\), то и сложность будет экспоненциальная.

Задача 9.9: Отличие между задачами состоит в следующем. В задаче про монеты порядок монет в решении был не важен: если поменять порядок монет в решении, то решение останется решением. А в задаче про черепашку порядок, очевидно, важен: если поменять порядок ходов, то мы посетим совсем другие клетки и потому набранная сумма будет другой. Поэтому в задаче про монеты мы сумели построить динамическое решение, неявно зафиксировав, в каком порядке берём монеты, а в задаче про черепашку такой фокус не пройдёт.

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

Задача 9.11:

fillchar(old,sizeof(old),false);
old[0]:=true;
for i:=1 to n do begin
    for j:=0 to s do
        if j<a[i] then
           ans[j]:=old[j]
        else ans[j]:=old[j] or old[j-a[i]];
    old:=ans;
end;

Задача 9.12: Если подумать, то очевидно, что задачу про монеты с неограниченным количеством монет каждого достоинства.

Задача 9.13:

procedure out(i,j);
begin
if (i=0)or(j=0) then exit;
if ans[i-1,j]>ans[i,j-1] then begin
   out(i-1,j);
   write('R');
end else begin
   out(i,j-1);
   write('U');
end;
end;

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

procedure out(i,j)
begin
while i<>0 do begin
      if (j>=a[i])and(ans[i-1,j-a[i]]) then begin
         write(i,' ');
         j:=j-a[i];
         dec(i);
      end else
          dec(i);
end;

Или даже можно while на for заменить. Мне кажется, что такой while более аналогичен процедуре, которую я приводил в тексте, и лишь поэтому я не пишу его короче.

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

Задача 9.15: Ну, во-первых, модернизируем динамику так, чтобы можно было выводить решение с начала, а не с конца. Для этого для каждого \(i\) и \(j\) в \(ans[i,j]\) будем хранить лучшую сумму от \((i,j)\) до \((N,M)\). Рекуррентное соотношение и основной цикл динамики напишите сами, я приведу процедуру \(out\). Предполагаю, что мы уже ввели нулевую строку и столбец аналогично ответу на задачу про вывод решения с нулевыми элементами (правда, тут это будет \(N+1\)-ая строка и \((M+1)\)-ый столбец).

procedure out(i,j);
begin
if (i=N+1)or(j=M+1) then exit;
if ans[i+1,j]>ans[i,j+1] then begin
   write('R');
   out(i+1,j);
end;
if ans[i+1,j]=ans[i,j+1] then begin
   write('R');
   out(i+1,j);
end;
if ans[i+1,j]<ans[i,j+1] then begin
   write('U');
   out(i,j+1);
end;
end;
procedure out(i,j);
begin
if (i=N+1)or(j=M+1) then exit;
if ans[i+1,j]>=ans[i,j+1] then begin
   write('R');
   out(i+1,j);
end else begin
   write('U');
   out(i,j+1);
end;
end;

Слева приведено простое решение, которое чётко показывает, что мы делаем: если один из двух имеющихся у нас вариантов явно лучше другого (т.е. \(ans[i+1,j]\neq ans[i,j+1]\)), то мы идём туда. Иначе, если оба равноценны, то надо идти туда, где первый ход будет лексикографически наименьшим, т.е. идти ’R’. Справа — вариант, который показывает, что это же можно написать и проще, объединив варианты хода вправо «потому что туда выгоднее» и «потому что все равно, куда идти».

Задача 9.16: Я думаю, общий цикл насчета количества результатов вы напишите. Я приведу только процедуру \(out\). Сравните с ответом к выводу первого в лексикографическом порядке решения.

procedure out(i,j,k); // k - номер решения, которое надо вывести
begin
if (i=N+1)or(j=M+1) then exit;
if ans[i+1,j]<=k then begin
   write('R');
   out(i+1,j,k);
end else begin
    write('U');
    out(i,j+1,k-ans[i+1,j]);
end;
end;

Задача 9.17: Итак, нам дана хорошая последовательность \(a\) длины \(n\), требуется найти её номер среди всех хороших последовательностей длины \(n\).

Я никогда такого рода программ не писал, но попробую. Вероятность багов выше, чем в других кодах :). Сначала, как всегда в задачах на динамику, посчитаем основной динамикой \(ans[i]\) — количество хороших последовательностей длины \(i\), а потом по данной последовательности \(a\) найдём её номер. Я напишу только вторую часть; похоже, её даже проще тут реализовать нерекурсивно, но я попробую написать рекурсивно, чтобы была видна связь с нахождением объекта по номеру и более понятно обобщение на произвольный случай. Подумайте над нерекурсивной реализацией; это, по-моему, просто.

Процедура \(getnum(i)\) находит, какой по счету среди всех последовательностей длины \(i\) является последовательность, образованная последними \(i\) символами данной нам (т.е. находит номер последовательности \(a[(n-i+1)\dots n]\)).

function getnum(i)
begin
if i=n then begin
   getnum:=1;
   exit;
end;
if (i=n+1) then begin //аналог нулевого элемента
   getnum:=1;
end;
if a[n-i+1]=0 then
   getnum:=getnum(i-1)
else getnum:=ans[i-1]+getnum(i-2)
end;

Надеюсь, что правильно :)

Кстати, тут тоже, аналогично задачам про вывод первого пути, вывод k-го пути, можно переписать динамику, и в \(ans[i]\) хранить количество последовательностей длины \(n-i+1\) (т.е. количество возможных окончаний нашей последовательности, начиная с позиции \(i\)), и тогда в процедуре не будет такого странного аргумента \(a[n-i+1]\). Может быть, так будет проще. Во всяком случае, это объясняет, почему в аналогичных задачах про черепашку мы переделаем динамику, а здесь не переделывали: на самом деле обе задачи можно решить, не переделывая динамику, обе можно решить, переделав, я просто решил показать оба способа и, кроме того, в задаче про черепашку мне кажется, что результат будет проще понять с переписанной динамикой.

Задача 9.18: Как и в задачах вывод первого пути и вывод k-го пути, переписываем динамику, чтобы удобнее работать с лексикографическим порядком, хотя, как я отметил в ответе про последовательность, можно её и не переписывать. Додумайте вариант без переписывания.

Если же мы переписали динамику и уже насчитали массив \(ans\), то дальше все просто: \(getnum(i,j,k)\) возвращает номер решения, образованного символами с \(k\)-ого по последний данного нам массива \(a\), среди всех решений, формирующих \(ans[i,j]\) (т.е. идущих из \((i,j)\) и \((N,M)\)). (Обратите внимание, что в ответе про последовательность был один параметр \(i\), а не два параметра \(i\) и аналог \(k\), т.к. там оба параметра имели бы одно и то же значение.)

function getnum(i,j,k);
begin
if (i=N+1)or(j=M+1) then begin // можно написать и if k=N+M-1
   getnum:=1;
   exit;
end;
if ans[k]='R' then
   getnum:=getnum(i+1,j,k+1)
   write('R');
   out(i+1,j,k);
end else
    getnum:=ans[i+1,j]+getnum(i,j+1,k+1);
end;

Ещё обратите внимание на следующий момент: когда вы только услышали такую задачу, может показаться, что тут есть какие-нибудь идеи, методы решения, специфические только для этой задачи (например, какая-нибудь игра с \(C_n^k\), а в задании про последовательности — с числами Фиббоначчи). Нет! Все идеи тут совершенно стандартны, и ничего специфичного для задачи нет.

Задача 9.20: Видимо, код будет примерно такой (я не тестировал):

procedure out(i, j, pos);
{ pos указывает, на какую позицию в выходном массиве мы сейчас ставим монету }
begin
if i=n then begin
    check;
    exit;
end;
if (j>=a[i])and(ans[i+1,j-a[i]]) then begin
    { попробуем поставить i-ю монету. Мы проверили ans и знаем, что это можно}
    ans[pos] := a[i];
    out(i+1, j-a[i], pos + 1);
end;
if ans[i+1, j] then
    { попробуем не ставить i-ю монету. Мы проверили ans и знаем, что это можно}
    out(i+1, j, pos);
end;

Задача 9.21: Итак, заметим, что найти, от каких задач зависит задача \(t\), очень нетривиально: либо перебрать все предыдущие моменты \(t'\) и посмотреть, подходит ли момент \(t'\) нам (т.е. верно ли, что \(t'+time[t']=t\), где \(time[t']\) — сколько секунд папа Карло будет забивать гвоздик, начав в момент \(t'\)), либо построить полный граф подзадач, пробежавшись заранее по всем моментам \(t'\) и для каждого посчитав \(t'+time[t']\) и добавив момент времени \(t'\) в связный список, хранящий подзадачи для момента времени \(t'+time[t']\)

Но, с другой стороны, очень просто понять, какие задачи зависят от задачи \(t\). Поэтому пишем ДП с просмотром вперёд. Ещё раз: от задачи \(t\) зависят две задачи: \(t+1\) (если делать маленький перерывчик) и \(t+time[t]\) (если начать забивать гвоздик). Получаем код:

fillchar(ans,sizeof(ans),0);
ans[0]:=0;
for i:=1 to n do begin
    ans[i+1]:=max(ans[i+1],ans[i]);
    ans[i+time[i]]:=max(ans[i+time[i]],ans[i]+1);
end;

Все!

И напоследок замечу, что эту задачу, видимо, можно легко решить без всякого просмотра вперёд, «обратив» динамику и для каждого момента времени \(t\) вычисляя, сколько максимум гвоздей сможет папа Карло забить от момента \(t\) до конца рабочего дня. Додумайте. Может быть, такой вариант даже возможен во всех задачах на ДП с просмотром вперёд; не знаю. Тем не менее это не повод пренебрегать просмотром вперёд :)

Задача 9.22: Пожалуй, приведу целых два с половиной варианта решения.

Во-первых, можно поступить совершенно стандартно. Пусть \(ans[i]\) будет ответ для строки, состоящей из первых \(i\) символов (цифр) входной строки. Как связать \(ans[i]\) с ответами для меньших \(i\)? Ну очевидно: посмотрим, на что мог заканчиваться вывод программы, соответствующий первым \(i\) цифрам? Ясно, что на одно-, двух-, или т.д., значное число. Каждый из этих вариантов имеет место только если 1) соответствующее число не начинается на ноль и 2) соответствующее число не превосходит максимального возможного числа, \(C\). Второе условие заодно, очевидно, даёт ещё и ограничение на значность последнего числа. Итого сложность \(O(nl)\), где \(l\) — число цифр в \(C\). Реализация не очень сложна, надо только проверять ведущий ноль и т.д. Или можно написать ДП с просмотром вперёд, тогда не надо будет проверять ведущий ноль у каждого числа, а только один раз для каждого \(i\).

Но второй вариант — «обратить» динамику. Пусть \(ans[i]\) обозначает ответ для строки, образованной последними \(n-i+1\) символами (цифрами) входной строки (т.е. с \(i\)-ой цифры до последней). Тогда переберём, с чего может начинаться этот вывод. Если \(s[i]=0\) (\(s\) — входная строка), то только с нуля (однозначное число ’0’ допустимо в выводе, судя по условию), и тогда \(ans[i]=ans[i+1]\), иначе может начинаться с одно-, двух- и т.д. значных чисел, до тех пор, пока это число не превзойдёт \(C\). Соответственно будет \(ans[i]=ans[i+1]+ans[i+2]+\dots\).

В обоих решениях надо отдельно подумать про инициализацию динамики; как всегда, вам помогут нулевые элементы. И, конечно, все вычисления делаете по модулю \(10^k\).

И «второй с половиной» вариант — это фактически как дойти до второго решения, не зная динамики вообще. Если бы вы писали тут перебор, то наверняка у вас была бы функция типа \(find(i)\), которая перебирает все способы вывести цифры с \(i\)-ой по последнюю. Она бы запускала \(find(i+1)\), \(find(i+2)\) и т.д. и суммировала бы результаты. (Точнее, можно считать решения путём команды inc(ans) в процедуре check, а можно написать так, чтобы \(find\) возвращала количество решений. Мы будем считать, что \(find\) именно возвращает количество решений). Тогда, заметив перекрытие подзадач, можно легко додуматься до запоминания, и получить рекурсию с запоминанием результата.

Вот результат:

function ch(m:word):int64;
var r:int64;
    i:word;
    chis:longint;
    o:word;
begin
o:=m;
if b[m]<>-1 then begin
ch:=b[m];
exit;
end;
if m=n then begin
ch:=1;
exit;
end;
if a[m+1]=0 then begin
ch:=ch(m+1);
exit;
end;
r:=0;
chis:=0;
while (m<n) do begin
    inc(m);
    chis:=chis*10+a[m];
    if (chis>c) then break;
    r:=(r+ch(m)) mod kvc;
end;
ch:=r;
b[o]:=r;
end;

Реализация немного нешаблонная и нагруженная, но вроде все просто и легко понимается.

Параметр функции тут — сколько цифр с начала входной строки мы отбрасываем (т.е. сколько мы уже вывели), т.е. в отличие от приведённого выше варианта, \(m=i-1\). Соответственно, «нулевой элемент» — \(m=n\), тогда ответ — один. «Количество цифр» \(kvc=10^k\).

Задача 9.23: Итак, возможны два варианта. Пусть \(s_1[i]=s_2[j]\). Рассмотрим оптимальное решение для подзадачи \((i,j)\). Если оно подразумевает вычёркивание как \(s_1[i]\), так и \(s_2[j]\), то очевидно, что оно не оптимальное: не будем их вычёркивать — получим тоже общую подпоследовательность, но длиннее. Значит, хотя бы она из двух букв не вычёркивается. Пусть это \(s_1[i]\). Но тогда последняя невычеркнутая буква в \(s_2\) — пусть это буква \(s_2[j']\) — должна совпадать с \(s_1[i]\) (а иначе после вычёркивания получаются разные строки). Но тогда вычеркнем \(s_2[j']\), но не будем вычёркивать \(s_2[j]\) — получим оптимальное решение, в котором как \(s_1[i]\), так и \(s_2[j]\) сохранены. Значит, существует оптимальное решение, где обе буквы сохранены. Но тогда несложно показать, что наибольшая общая подпоследовательность будет ответом для \((i-1,j-1)\), к которому приписан символ \(s_1[i]\), т.е. \(ans[i,j]=ans[i-1,j-1]+1\).

Если же \(s_1[i]\neq s_2[j]\), то ясно, что хотя бы одну из них надо вычеркнуть. Если вычёркиваем \(s_1[i]\), то ответ будет \(ans[i-1,j]\) (независимо от того, вычёркиваем ещё и \(s_2[j]\) или нет — вопрос о необходимости вычёркивания \(s_2[j]\) решится уже в задаче \((i-1,j)\), а в \((i,j)\) мы воспользуемся готовым решением). Если же вычёркиваем \(s_2[j]\), то ответ будет \(ans[i,j-1]\) (независимо от того, вычёркиваем ещё и \(s_1[i]\) или нет!). Т.е. в общем случае \(ans[i,j]=\max(ans[i-1,j],ans[i,j-1])\). Ещё раз обратите внимание, как мы избавились от варианта «вычеркнуть обе и взять \(ans[i-1,j-1]\)»: это та же идея, что и в задаче про неограниченное количество монет, и в конце раздела ДП на подотрезках.

Задача 9.24: Вроде ничего сложного, все совсем по стандартному шаблону.

procedure out(i,j)
begin
if (i=0)or(j=0) then exit;
if s1[i]=s2[j] then begin
   out(i-1,j-1);
   write(s1[i]);
end else begin
    if ans[i-1,j]>ans[i,j-1] then
       out(i-1,j)
    else out(i,j-1);
end;
end;

Задача 9.25: Итак, главная идея — раз не получается простыми методами, то подойдём к задаче серьёзно. А именно, давайте для каждого \((i,j)\) найдём не просто длину решения, но и само первое в лексикографическом порядке решение! Т.е. \(ans[i,j]\) будет хранить нужное нам решение. Тогда рекуррентное соотношение будет следующее:

\[\begin{split}ans[i,j]=\left\{\begin{array}{ll} ans[i-1,j-1]+s_1[i],\quad&s_1[i]=s_2[j],\\ ans[i-1,j],\qquad&s_1[i]\neq s_2[j]\text{ и }ans[i-1,j]\text{ «лучше» }ans[i,j-1],\\ ans[i,j-1],\qquad&s_1[i]\neq s_2[j]\text{ и }ans[i,j-1]\text{ «лучше» }ans[i-1,j],\\ \end{array}\right.\end{split}\]

здесь под «\(a\) лучше \(b\)» понимается «строка \(a\) длиннее строки \(b\) или у них одинаковые длины, но \(a\) идёт раньше в лексикографическом порядке, чем \(b\)». Короче, выбираем более длинное решение, а при равных длинах — то, что идёт лексикографически раньше.

Символ ’\(+\)’ в первом варианте обозначает, конечно, конкатенацию строк (т.е. к строке \(ans[i-1,j-1]\) приписываем символ \(s_1[i]\)).

Сложность решения стала \(O(N^3)\) не только из-за необходимости копировать строки (от чего, наверное, можно было бы и избавиться), но ещё и из-за необходимости сравнивать строки, от чего, я думаю, избавиться не так просто.

Кстати, обратите внимание, что тут вполне все получилось и без «обращения» динамики. Можно было и обратить, решение осталось бы аналогичным.

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

Да, я не предлагаю всегда в подобных ситуациях хранить сразу решение, нет. Только минимальную информацию, необходимую для выбора нужного решения в процедура \(out\). Например, потребовали бы здесь выводить решение с минимально возможным количеством букв a — мы бы легко это сделали, просто в \(ans\) хранили бы длину решения, а в \(mina\) — минимальное количество букв a в правильном решении. Решение потом восстановили бы стандартным способом с помощью процедуры \(out\). Кстати, работало бы за \(O(N^2)\).

Задача 9.26: Контрпример, например, такой: s_1="abcd", s_2="adbc" и s_3="ad". НОП первых двух строк — abc, и буква d пропала. Что дальше ни делай, но правильного ответа ad не получим.

Задача 9.27: Пусть \(ans[i,j,k]\) — длина наибольшей общей подпоследовательности для первых \(i\) символов первой строки, первых \(j\) второй и первых \(k\) третьей. Тогда если \(s_1[i]=s_2[j]=s_3[k]\), то ответ \(ans[i-1,j-1,k-1]+1\), иначе нужно какую-то букву вычеркнуть. Окончательно

\[\begin{split}ans[i,j,k]=\left\{\begin{array}{ll} ans[i-1,j-1,k-1]+1,\quad&\text{если }s_1[i]=s_2[j]=s_3[k],\\ \max(ans[i-1,j,k],ans[i,j-1,k],ans[i,j,k-1]),\quad&\text{иначе.} \end{array}\right.\end{split}\]

Задача 9.28: Рассмотрим случай \(s[l]=s[r]\). Если в оптимальном для \((l,r)\) решении мы обе эти буквы вычёркиваем, то решение не оптимальное — можно их не вычёркивать и получить решение на 2 символа длиннее. Значит, хотя бы один из этих двух символов мы сохраняем. Пусть мы сохраняем \(s[l]\), и \(s[r]\) вычёркиваем — тогда пусть последний невычеркнутый справа символ \(s[r']\). Тогда \(s[r']=s[l]=s[r]\) и мы можем вычеркнуть \(s[r']\), но оставить \(s[r]\) — решение останется решением и останется оптимальным. Значит, есть оптимальное решение, где мы не вычёркиваем ни \(s[l]\), ни \(s[r]\). Но тогда несложно показать, что \(ans[l,r]=ans[l-1,r+1]+2\).

Если же \(s[l]\neq s[r]\), то надо как минимум одну вычеркнуть. Если вычёркиваем \(s[l]\), то ответ равен \(ans[l+1,r]\), независимо от того, вычёркиваем ли мы \(s[r]\). Аналогично с \(s[r]\). Общий итог — \(ans[l,r]=\max(ans[l+1,r],ans[l,r-1])\).

Задача 9.29:

fillchar(ams,sizeof(ans),0);
for i:=1 to n-1 do
    ans[i+1,i]:=0;
for len:=2 to n do
    for l:=1 to n-len+1 do begin {обратите внимание на аккуратное значение верхнего предела}
      r:=l+len-1;
      if s[l]=s[r] then
         ans[l,r]:=ans[l+1,r-1]
      else ans[l,r]:=max(ans[l+1,r],ans[l,r-1]);
    end;

Задача 9.30:

procedure out(l,r)
begin
if l>r then
   exit;
if l=r then begin
   write(s[l]);
   exit;
end;
if s[l]=s[r] then begin
   write(s[l]);
   out(l+1,r-1);
   write(s[r]);
end else begin
    if ans[l+1,r]>ans[l,r-1] then
       out(l+1,r)
    else out(l,r-1);
end;
end;

Здесь сначала два if’а, соответствующие «базе» динамики, а потом основной код. С вариантом, когда \(s[l]\neq s[r]\), все понятно, а вот если \(s[l]=s[r]\), то тут небольшая необычность. Мы делаем write, потом out, потом ещё раз write, в отличие от обычных процедур out, где мы делаем out и только потом write.

Задача 9.31: Ну, как и в задаче про первую в лексикографическим порядке общую подпоследовательность, будем вместо длины максимального подпалиндрома хранить сам подпалиндром. Далее, я думаю, очевидно, я даже не буду ни рекуррентного соотношения, ни кода приводить.

Задача 9.32: По-моему, эта задача очень напоминает задачу про монеты (а ещё больше — задачу про минимальное число монет), только то, что было раньше достоинством монеты, теперь — вес вещи, а стоимость вещи — новый параметр. Поэтому решается совсем аналогично. Соответственно, \(ans[i,j]\) будет обозначать, какую максимальную стоимость можно набрать из первых \(i\) вещей при условии, что суммарный вес набранного будет ровно \(j\) (если суммарный вес \(j\) невозможно набрать из первых \(i\) вещей, то будем тут хранить \(-\infty\)). Рекуррентное соотношение пишется легко, полностью аналогично задаче про монеты: либо мы берём \(i\)-ую вещь (если \(j\geq w_i\), где \(w_i\) — вес \(i\)-ой вещи), или нет.

\[\begin{split}ans[i,j]=\left\{ \begin{array}{ll} max(ans[i-1,j],ans[i-1,j-w_i]+c_i),&\quad j\geq a_i,\\ ans[i-1,j],&\quad j<a_i, \end{array}\right.\end{split}\]

здесь \(c_i\) — стоимость \(i\)-ой вещи.

«База» динамики аналогична задаче про монеты, индекс \(j\), конечно, идёт до \(w\), независимо от весов вещей. Вроде я нигде не наглючил.

Кстати, если хотите, то это ещё один пример на «тяжёлую артиллерию» для вывода требуемого решения. Переформулирую задачу так: «Можно ли унести вещей общим весом не более \(W\)? Если решений несколько, то выведите то, у которого суммарная стоимость вещей максимальна.» Теперь, я думаю, совершенно очевидно, что эта задача — иллюстрация к замечаниям в конце решения про первую наибольшую общую подпоследовательность.

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

Задача 9.33: Итак, тут все не совсем уж прямолинейно по предыдущим примерам, зато это пример на использование массива \(from\). Итак, заведём массив \(from\), и в \(from[u]\) будем хранить, на какой именно вершине нашёлся максимум при обработке вершины \(u\). Тогда основной код динамики немного изменится, а процедура \(out\) будет писаться элементарно:

function find(u):integer;
var max,t,v...
begin
if ans[u]<>-1 then begin
   find:=ans[u];
   exit;
end;
max:=-1;
from[u]:=0;
for v:=1 to n do
    if gr[v,u]<>0 then begin{если из v в u идет ребро}
       t:=find(v);
       if t>max then begin
          max:=t;
          from[u]:=v;
       end;
    end;
ans[u]:=max+1;
find:=ans[u];
end;
procedure out(u)
begin
if u=0 then
   exit;
out(from[u]);
write(u,' ');
end;

Если в вершину \(u\) не входит ни одного ребра, то \(ans[u]=1\), и в вышеприведённом коде \(from[u]=0\), потому и процедура \(out\) так обрабатывает случай \(u=0\) (допонимайте!).

В общем, вот оно, использование массива \(from\). В принципе, и раньше его можно было использовать, например, в черепашке в \(from[i,j]\) хранить 0 или 1 в зависимости от направления хода и т.п. — тогда не надо будет ещё раз в процедуре \(out\) реализовывать рекуррентное соотношение. В принципе, так, наверное, даже проще.

Задача 9.34: Итак, для каждого поддерева решаем две указанные в подсказке задачи. Пусть ответ на первую — \(a[u]\), на вторую — \(b[u]\). Очевидна формула для \(b[u]\):

\[b[u]=\sum_v c[v],\]

сумма берётся по всем детям вершины \(u\), здесь \(c[v]=max\big(a[v],b[v]\big)\) — максимальное паросочетание в поддереве \(v\) без всяких ограничений.

Как найти \(a[u]\)? Ну легко: если \(u\) входит в паросочетание, то \(u\) связана с неким своим сыном \(v\). Тогда размер паросочетания равен \(1+b[v]\) плюс максимальное вообще паросочетание в поддеревьях остальных детей. По \(v\), конечно, надо взять максимум:

\[a[u]=\max_v \bigg(1+b[v]+\sum_{v'\neq v} c[v']\bigg),\]

максимум берётся по всем детям вершины \(u\), сумма — по всем детям, кроме \(v\), Соответственно, внутренняя сумма — это максимальное паросочетание во всех дочерних поддеревьях, кроме поддерева \(v\).

Но считать сумму для каждых \(u\) и \(v\) не хочется. Поэтому идёт стандартный трюк — добавим и вычтем слагаемое \(c[v]\), тем самым превратив сумму в сумму по всем детям вообще, т.е. в \(b[u]\), и вынесем её из-под максимума, чтобы максимум легко находился с помощью просмотра вперёд:

\[a[u]=\max_v \Big(b[v]-c[v]\Big)+b[u]+1.\]

(Соотношение, по-моему, неочевидно и с ходу не ясно, почему оно верно. Но оно верно, т.к. мы его только что вывели.)

Теперь пишем ДП с просмотром вперёд, вычисляя величину \(b\) элементарно, для величины \(a\) динамикой вычисляем максимум, а второе слагаемое к нему прибавляем уже при обработке соответствующей вершины, там же вычисляем и \(c\):

fillchar(a,sizeof(a),255);
fillchar(b,sizeof(b),0);
fillchar(c,sizeof(c),0);
for i:=n downto 2 do begin
    {заканчиваем обработку вершины i}
    a[i]:=a[i]+b[i]+1;
    c[i]:=max(a[i],b[i]);
    {смотрим на задачи, которые зависят от i}
    b[p[i]]:=b[p[i]]+c[i];
    a[p[i]]:=max(a[p[i]], b[i]-c[i]);
end;

Обратите внимание, что массив \(a\) изначально заполняю минус единицами (ясно, почему? И какого типа должно быть \(a\), чтобы это работало?), чтобы для листьев правильно в основном цикле вычислялся \(a[i]\).

Постарайтесь это дело понять. Тут, имхо, весьма нетривиально получилось (надеюсь, я тут нигде не наглючил), но это неплохой пример на ДП с просмотром вперёд. Помоделируйте, что здесь происходит.

Кстати, может быть, тут можно додуматься до каких-нибудь дополнительных соображений, которые это все упростят. Например, мне кажется, что не включать корень поддерева в паросочетание всегда бессмысленно, и потому, может быть, всегда \(c[i]=a[i]\). Не знаю, поможет ли это.

Задача 9.35: Позицией здесь в игре будет пара чисел \((i,j)\), указывающих, что в куче осталось \(i\) камней, а первым ходом можно взять не более \(j\) камней. Тогда возможные ходы — взять от 1 до \(j\) камней, и ясно, в какие позиции они ведут. Получаем код:

fillchar(ans,sizeof(ans),2); {осторожно тут с типом ans}
for i:=1 to n do
    for j:=1 to m do begin
        {ans[i,j] уже равно 2}
        for k:=1 to j do
            if (k<=i)and(ans[i-k,k]=2) then
              ans[i,j]:=1;
    end;
end;

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

Задача 9.36: Итак, для каждого \(i\) и \(j\) определим, является ли позиция с \(i\) камешками выигрышной для игрока \(j\). Ясно, какие ходы отсюда возможны, и ясно, в какие позиции они ведут. Только, чтобы не возиться с определением порядка, в котором надо решать подзадачи, напишем рекурсию с запоминанием результата. Теперь \(ans[i,j]=2\), если игрок \(j\) проигрывает из этой позиции, и \(1\), если выигрывает.

function find(i,j)
begin
if i<0 then begin
   find:=1;
   exit;
end;
if i mod 30=0 then
   find:=2;
   exit;
end;
if ans[i,j]=-1 then begin
   ans[i,j]:=2;
   if j=1 then begin
      if (find(i-3,2)=2) or (find(i-4,2)=2)
                   or (find(i-5,2)=2) then
         ans[i,j]:=1;
   end else begin {j=2}
      if (find(i+1,1)=2) or (find(i+2,1)=2)then
         ans[i,j]:=1;
   end;
end;
find:=ans[i,j];
end;

Поймите, почему так обрабатывается случаи \(i<0\) и \(i\bmod 30=0\).

Задача 9.37: Итак, мы перепишем немного динамику, чтобы сохранять массивы \(from\) и \(first\). Обратите внимание, что у нас есть два глобальных варианта: либо мы вообще выкидываем вершину \(j\), либо находим ей пару. Но не страшно, можно просто в \(from\) особым значением (например, нулём) отмечать выкидывание этой вершины. Итак, получаем следующий текст, новые строки помечены комментариями:

for i:=0 to (1 shl N)-1 do begin
    ans[i]:=0;
    for j:=0 to N-1 do
        if (i and (1 shl j)<>0) then begin
           first[i]:=j;                            {+}
           from[i]:=0;                             {+}
           t:=ans[i and (not (1 shl j))];
           ans[i]:=t;

           for k:=j+1 to N-1 do if (i and (1 shl k)<>0) and (gr[j,k]<>0) then begin
               t:=ans[i and (not (1 shl j)) and (not (1 shl k))];
               if t+1>ans[i] then begin
                  ans[i]:=t+1;
                  from[i]:=k;                      {+}
               end;
           end;
           break;
        end;
end;

И теперь процедура \(out\) пишется в две строчки:

procedure out(i)
var j;
begin
if i=0 then exit; {i=0 --- пустое множество --- "база" динамики}
j:=first[i];
if from[i]=0 then
   out(i and (not (1 shl j)));
else begin
     writeln(j,' ',from[i]); {выведем, что это ребро входит в паросочетание}
     out(i and (not (1 shl j)) and (not (1 shl k)));
end;
end;

Надеюсь, понятны два момента. Во-первых, то, что в общем случае можно использовать не только один массив \(from\), но и что-нибудь сложнее (два массива, или структуру и т.п.) для хранения всей той информации, которая все равно явно или неявно вычисляется в процессе основного цикла динамики и потом нужна в процедуре \(out\). Во-вторых, в массиве \(from\) мы не обязаны хранить непосредственный номер подзадачи, от которой зависит наша задача, а можно и что-нибудь другое полезное, причём можно вводить особые значения для особых случаев и т.д.

И ещё отмечу, что, конечно, можно было ничего этого не вводить (если, например, памяти не хватает), а заново проводить все циклы по \(j\) и по \(k\), «вспоминая», какие были значения у оптимальных величин.

Задача 9.38: Итак, написал я эту задачу и даже протестил на всех тестах. Действительно, нетривиально. Привожу код.

{$r+,q+,s+,i+,o+}
{$apptype console}
uses sysutils;
var n,gcdmin:integer;
    reqn:int64;
    a:array[0..16] of integer;
    can:array[0..16,0..16] of integer;
    ans:array[0..1 shl 17-1,0..16] of int64;
    f:text;
    ii,i,j,k:integer;
    t:integer;

function gcd(a,b:integer):integer;
begin
if b=0 then
   gcd:=a
else gcd:=gcd(b,a mod b);
end;

procedure out(i,j:integer;reqn:int64);
var k,ii:integer;
begin
ii:=i and (not (1 shl j));
for k:=0 to n do if (i and (1 shl k)<>0)
          and(k<>j)and(can[j,k]=1) then begin
    if ans[ii,k]>=reqn then begin
       write(f,a[k],' ');
       out(ii,k,reqn);
       exit;
    end;
    reqn:=reqn-ans[ii,k];
end;
end;

begin
assign(f,'perm.in');reset(f);
read(f,n,reqn,gcdmin);
a[0]:=0;
for i:=1 to n do
    read(f,a[i]);
close(f);
for i:=n-1 downto 1 do
    for j:=1 to i do
        if a[j]>a[j+1] then begin
           t:=a[j];a[j]:=a[j+1];a[j+1]:=t;
        end;
for i:=1 to n do
    for j:=1 to n do
        if gcd(a[i],a[j])>=gcdmin then
           can[i,j]:=1
        else can[i,j]:=0;
for i:=0 to n do begin
    can[0,i]:=1;
    can[i,0]:=1;
end;
for i:=2 to 1 shl (n+1)-1 do
    for j:=0 to n do if i and (1 shl j)<>0 then begin
        ii:=i and (not (1 shl j));
        if ii=0 then begin
           ans[i,j]:=1;
           continue;
        end;
        ans[i,j]:=0;
        for k:=0 to n do if (i and (1 shl k)<>0)
                and(can[j,k]=1)and(j<>k) then
            inc(ans[i,j],ans[ii,k]);
    end;
assign(f,'perm.out');rewrite(f);
if ans[1 shl (n+1)-1,0]<reqn then
   writeln(f,-1)
else out(1 shl (n+1)-1,0,reqn);
close(f);
end.

Комментарии. Функция \(gcd\) считает НОД двух чисел по алгоритму Евклида; надеюсь, вы это знаете. Если вы пиите длиннее, то обратите внимание, что это можно писать так коротко.

Функцию \(out\) прокомментирую ниже, пока комментарии к основной проге. Завожу число №0 — то самое дополнительное число. Считываю числа и сортирую их (сортирую пузырьком, т.к. все равно их мало). Насчитываю матрицу \(can\): \(can[i,j]=1\), если \(j\) может идти после \(i\). Нулевое число может идти после любого и перед любым, на это нужен отдельный цикл. Дальше основной цикл динамики. Для каждого множества \(i\) и каждого \(j\) нахожу число \(k\)-перестановок множества \(i\), начинающихся на число №\(j\). Ясно, что надо перебрать, какое число будет идти после \(j\) — пусть \(k\), и если оно действительно может идти (т.е. \(can[j,k]=1\)), то добавить к \(ans[i,j]\) ответ на подзадачу с множеством, получающимся из \(i\) выкидыванием числа \(j\) (т.е. ii=i and (not (1 shl j)), и этот номер не зависит от не зависит от \(k\)) и первым числом \(k\) — т.е. к \(ans[i,j]\) добавляем \(ans[ii,k]\). Особо обрабатываем случай, когда в \(i\) содержится только одно число — т.е. \(ii=0\). Это — база динамики, поэтому отдельно присваиваем \(ans[i,j]:=1\).

Далее выводим решение. Обратите внимание, что, за счёт введения нулевого числа ответ у нас сразу хранится в ans[1 shl (n+1)-1, 0] (а (а иначе пришлось бы суммировать по всем возможным начальным числам).

Функция \(out\) стандартным образом выводит \(reqn\)-ое решение (я везде на протяжении программы использую \(mingcd\) вместо того, что в условии называется \(k\), и \(reqn\) вместо \(m\)). Обратите внимание: это как раз тот случай, на который я не давал примера в основном тексте: когда вариантов много и надо перебрать их все в цикле. Казалось бы, что можно \(j\) выводить сразу на входе в процедуру \(out\), но я его вывожу в цикле, что позволяет не выводить нулевое число. Ещё обратите внимание, что база динамики тут обрабатывается основным кодом.

Ещё обратите внимание, что числа, считанные из входного файла, я нумерую с единицы. Обычно в задачах на динамику по подмножествам приходится нумеровать с нуля, чтобы битовая арифметика работала, но тут у меня есть особое нулевое число, и потому остальные элементы нумерую с единицы.

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

Задача 9.39: Я не буду тут писать никакого ответа, но постарайтесь все-таки что-нибудь придумать.

Задача 9.40: Ясно, что профилем тут будет расстановка королей в одной строке. Таким образом, профилей будет \(2^N\), легко определить, какой профиль может идти после какого и т.д. Код приводить не буду.

Задача 9.41: Может быть, тут тоже все проще понять, если подумать, как бы вы писали перебор (а в переборе была такая задача :) ). Например, вариант а: разложения, различающиеся порядком слагаемых, считаются различными. Как бы мы писали перебор: мы бы просто перебирали, какое будет очередное слагаемое, и для каждого варианта запускались бы рекурсивно. Можно это сделать функцией, которая будет возвращать число способов разбиения на слагаемые того, что осталось. Если попытаться теперь это превратить в рекурсию с запоминанием результата, то какие вызовы функций нам надо объединить, т.е. какие вызовы будут возвращать один и тот же результат? Ну ясно, те, которые просто считают число способов разбиения для одного и того же числа (т.е. единственный важный тут параметр — это сколько нам осталось разбить). Т.е. теперь в динамике будем считать \(ans[i]\) — количество способов разбиения на слагаемые числа \(i\) — и, перебирая первое слагаемое, будем сводить к более мелким подзадачам.

А если вариант б: разложения, отличающиеся лишь порядком слагаемых, считаем одинаковыми? В переборе уже была у нас полезная идея: учесть это требование можно, потребовав, чтобы в разложении слагаемые были отсортированы. Как мы тут стали бы писать перебор? Опять, наша функция перебирала бы первое слагаемое и запускалась бы рекурсивно, но теперь это слагаемое нужно перебирать лишь до некоторого \(k\), где \(k\) — это предыдущее слагаемое в разложении (т.е. то, которое мы выбрали на предыдущем уровне рекурсии; если мутно, то отвлекитесь и сначала напишите или в уме продумайте реализацию перебора). (Я считаю, что мы потребовали, чтобы слагаемые убывали; если же хотим, чтобы слагаемые возрастали, то перебирать будем от \(k\) до максимума — до \(N\), видимо). Соответственно, теперь параметрами динамики будут \(i\) и \(k\) и будем считать число способов разбиения числа \(i\) на слагаемые, не превосходящие \(k\).

Остальные варианты разбираются аналогично.

Задача 9.42: Про пункт а). В первом решении считаем \(ans[i,j]\), при этом при \(j>0\) получаем \(ans[i,j]=ans[i-1,j+1]+ans[i-1,j-1]\), а при \(j=0\)\(ans[i,j]=ans[i-1,1]\).

Во втором решении

\[ans[i]=\sum_{k=1}^N ans[k-1]\cdot ans[N-k],\]

здесь база динамики — \(ans[0]=1\).

Про пункт б). Первое решение я не знаю, как обобщить, а вот второе — легко. Первая скобка может быть любого из 3 видов, и для каждого варианта у нас будет \(\sum_{k=1}^N ans[k-1]\cdot ans[N-k]\) последовательностей. Итого

\[ans[i]=3\sum_{k=1}^N ans[k-1]\cdot ans[N-k].\]

Можно считать по этой формуле, но вообще сразу понятно, что ответ на задачу б) — это ответ на задачу а), умноженный на \(3^N\) :).

Задача 9.43: Посмотрим заполнение доски \(N\times i\), причём в \(i\)-ом столбце разрешим некоторым доминошкам вылезать за край доски на одну клетку. То, в каких именно строках они будут вылезать, и будет профилем. Дальше думайте сами, тут немного сложнее обычного определить, какой профиль может следовать за каким.

Задача 9.44: Для каждого \(i\) и \(j\) определим, подходят ли первые \(i\) символов строки под первые \(j\) символов маски. Если \(j\)-ый символ маски — буква, то все легко: либо ответ сразу нет, либо надо посмотреть на \(ans[i-1,j-1]\). Если знак вопроса, то просто надо посмотреть на \(ans[i-1,j-1]\). А вот если звёздочка… С ходу хочется посмотреть на \(ans[i-k,j-1]\) при всех \(k\), но можно быстрее, воспользовавшись приёмом сведения циклов к предыдущим подзадачам. А именно, посмотрим на \(ans[i,j-1]\) (как будто звёздочка соответствует пустой строке) и на \(ans[i-1,j]\) (если звёздочка соответствует непустой строке, то строка на один символ короче тоже подходит под ту же маску). Итого сложность \(O(NM)\).

Для базы динамики нельзя просто так ввести нулевые элементы и сказать, что \(ans[0,0]=true\), а остальные \(false\): если маска начинается со звёздочек, то будут проблемы. Поэтому лучше приписать к маске и к строке в начало одну и ту же букву и только после этого считать \(ans[0,0]=true\), а остальные \(ans[0,i]=ans[i,0]=false\) (а ответы для первой строки и столбца уже насчитывать по основной формуле).

Задача 9.46: Эта задача может иметь (и имеет) большое применение в различных ситуациях, когда вам нужно обрабатывать возможно ошибочный ввод. Например, электронные словари могут быть готовы к тому, что пользователь введёт слово с ошибкой, и в таком случае выдавать ему список похожих слов; «похожесть» будет определяться по алгоритму, аналогичному решению этой задачи. Можно даже реализовать пункт в), например, допуская, что перепутать в английском слове буквы ’i’ и ’y’, ’c’ и ’k’ легко, но вряд ли кто перепутает, например, ’a’ и ’p’. Можно и другие идеи подключить, например допустить замену ’oo’ на ’u’ — решаться задача будет аналогично.

Другое аналогично применение — системы автоматической проверки орфографии. Здесь тоже в качестве возможных вариантов замены надо бы выдавать слова, которые отличаются не сильно; и также можно ввести веса для разных операций и разных букв (например, логично считать, что можно перепутать буквы, которые расположены на клавиатуре рядом, и т.п.).