Comments 2
Это вводная задача? Какая-то простая, на таких размерах подойдёт даже решение за O(n³) с двумя динамиками + перебор (причём само условие задачи так и говорит «используйте динамику»).
Если бы было 2000x2000, тогда бы прокатило только O(n²log n), например, с помощью 2-х динамик + предподсчёт нахождения первой преграды для всех ячеек за O(n²) + предподсчёт деревьев отрезков за O(n²log n) + перебор за O(n²) + выборка в дереве отрезков за O(log n) от текущего элемента до преграды, которая уже посчитана и берётся за O(1) — суммарно O(2n² + n² + n²log n + n²log n) = O(n²log n).
Далее можно пооптимайзить и выдать за O(n²) решение, причём намного более простое. Мы можем идти только вниз и вправо, значит если мы можем дойти, то величина пути не может меняться, она вычисляется строго по формуле S=(n — x + m — y). Дальше мы перебираем ячейки за O(n²). Находим верхнюю ячейку перед преградой, с которой можно дойти до финиша. И чем ниже мы изначально были, тем лучше. Дальше нужно продолжать поиск после преграды. Суммарная асимптотика — O(n²). И никаких сложных извращений.
Если бы было 2000x2000, тогда бы прокатило только O(n²log n), например, с помощью 2-х динамик + предподсчёт нахождения первой преграды для всех ячеек за O(n²) + предподсчёт деревьев отрезков за O(n²log n) + перебор за O(n²) + выборка в дереве отрезков за O(log n) от текущего элемента до преграды, которая уже посчитана и берётся за O(1) — суммарно O(2n² + n² + n²log n + n²log n) = O(n²log n).
Далее можно пооптимайзить и выдать за O(n²) решение, причём намного более простое. Мы можем идти только вниз и вправо, значит если мы можем дойти, то величина пути не может меняться, она вычисляется строго по формуле S=(n — x + m — y). Дальше мы перебираем ячейки за O(n²). Находим верхнюю ячейку перед преградой, с которой можно дойти до финиша. И чем ниже мы изначально были, тем лучше. Дальше нужно продолжать поиск после преграды. Суммарная асимптотика — O(n²). И никаких сложных извращений.
Учитывая простое решение, стоило сделать размеры до 10000x10000. Причём кодить его очень быстро.
Если что, две динамики никуда не уходят, но их можно заменить даже не на динамики, а просто на покраску таблицы. В результате мы должны просто сохранить, можно ли дойти в эту ячейку и с этой ячейки. И дальше простой перебор середины пути за O(2n²) — суммарно всё за O(n²).
А без машин ответ всегда будет (max(n,m)*3 + min(n,m) – 3) не считая маленьких n/m. Для 5x5 без машин ответ 17, для 6x6 — 21, для 7x7 — 25 и т. д.
Если что, две динамики никуда не уходят, но их можно заменить даже не на динамики, а просто на покраску таблицы. В результате мы должны просто сохранить, можно ли дойти в эту ячейку и с этой ячейки. И дальше простой перебор середины пути за O(2n²) — суммарно всё за O(n²).
А без машин ответ всегда будет (max(n,m)*3 + min(n,m) – 3) не считая маленьких n/m. Для 5x5 без машин ответ 17, для 6x6 — 21, для 7x7 — 25 и т. д.
Sign up to leave a comment.
Решение задачи «AAAAAA» с Facebook Hacker Cup методом динамического программирования на B-Prolog