Здравствуйте! Я нашел две задачи, в которых надо вычислять значение функции для достаточно больших графов. Проблема в том, даже битовое сжатие не позволяет хранить их в явном виде.
Первая: 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/
В первой задаче вы слишком грубо оценили количество состояний. Вот точная оценка: у нас каждый палец может независимо находиться в любом y. Значит, уже есть 38. А вот с x интереснее: так как в каждом столбце находится не более одного пальца и порядок фиксирован, то по набору из 8 столбцов однозначно определяется кто где находится. Сочетаний из 10 по 8 всего
штук. Итого 38·45 = 295 245 состояний. Домножаем на 20 символов в строке, получаем 6 миллионов состояний, что довольно немного.
Ясно, спасибо!
Вторая задача совсем простая, решается обычным поиском в ширину. Достаточно заметить, что нам нужно хранить не все состояния, а только несколько диагоналей. Проэмулируйте визуально алгоритм у себя в голове, все станет понятно.
Какие именно диагонали надо хранить? Диагональ можно удалить из памяти, если конь обошел все ее элементы. Уже для n=175 встречаются диагонали, которые содержат клетки, с расстояниями от начальной в диапазоне [59;87], т.е. они хранятся достаточно долго. Их можно выкидывать их по какому-то другому критерию?
Мне вот интересно, я сам должен искать на сайте вторую задачу? Я минут пять искал, спасибо, свой минус ты заслужил. Так сложно ссылку дать?
Вообще, я не знал, что на архив комбинаторных алгоритмов можно дать ссылку. (Там много контестов, которые доступны только через систему) http://acm.petrsu.ru/site/contest/combalgs_archive 24-я Ссылка на pdf acm.petrsu.ru/site/problems/combalgs_archive/024/
Для решения задачи нужно применить формулу, получив при этом достаточно большое значение в длинной арифметике. Формулу можно найти на oeis по нескольким первым ответам. Возможно можно её как-то вывести самому, но лень думать.
TL в 180 секунд говорит о существовании более понятного решения.
Не думаю. Просто ответ порядка 100 000 двоичных знаков. Если бы требовалось найти решение по модулю, то можно реализовать "тупой" алгоритм за N^2 / 6, просто матрицу следует заполнять с одной стороны от главной диагонали, и следить за тем чтобы мы не выходили за область клеток находящихся на кратчайших путях. Не удивлюсь если можно улучшить до N^2 / 12, заполняя матрицу не далее чем до побочной диагонали. В любом случае 180 секунд не хватит чтобы найти ответ из 100 000 двоичных знаков.