Здравствуйте! Я нашел две задачи, в которых надо вычислять значение функции для достаточно больших графов. Проблема в том, даже битовое сжатие не позволяет хранить их в явном виде.

Первая: http://acm.petrsu.ru/site/problems/problemset/0289/ . Дана некоторая клавиатура (размера 3 на 10) и текст, который робот должен на ней набрать. Нажатие каждого символа занимает одну минуту. Перемещение пальца – одну минуту. Пробел всегда можно набрать одним нажатием (без перемещений).

Палец представляет собой точку (x;y) Никакие 2 пальца не могут находиться в одном столбце клавиатуры. Пальцы также не могут менять порядок (Указательный не становится правее среднего и т.д.). Руки не могут менять порядок, и на одной руке – 4 пальца.

Операция перемещения – изменение координаты x или y пальца, но не обеих сразу.

Так как палец может иметь y от 1 до 3, и быть сдвинутым не более чем на 2 позиции (иначе какие-то из них будут меняться местами), для кодирования достаточно 9 значений. Всего 9^8=43046721.

Всего символов 20, и даже если мы научимся вычислять расстояние между позициями за без дополнительной памяти, граф [позиция][номер символа] будет иметь 344373768 вершин при ML 256Мб. (TL=5 с)

Жадность не проходит, например если к клавиатуре из условия набрать текст pon (указательный палец переместится на p, и далее не будет разницы, каким из двух ближайших пальцев набирать o, хотя указательным правой — выгоднее)

Брутфорс по пальцам, которыми мы набираем текущий символ, не проходит по времени, если символы на клавиатуре повторяются.

Вторая лежит в архиве комбинаторных алгоритмов того же сайта под номером 24. Это единственная задача, которую я видел, с ограничением по времени в 180 секунд. (ML – 256Mb).

В ней надо найти количество кратчайших путей коня по доске n x n из левого верхнего угла в правый нижний. n до 10^5

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

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

Буду благодарен за помощь.

Upd: Архив комбинаторных алгоритмов:http://acm.petrsu.ru/site/contest/combalgs_archive Ссылка на pdf второй задачи: acm.petrsu.ru/site/problems/combalgs_archive/024/