Випадкові паліндроми#399

Випадкові паліндроми (Розбір)

  1. Цю підзадачу з n \le 10 можна розв'язати повним перебором усіх можливих допустимих шляхів з подальшою перевіркою, чи є отриманий рядок паліндромом. Це дає часову складність \mathcal{O}(n 2^{2n-1}).

  2. Ця підзадача має обмеження n \le 100. Її можна розв'язати за допомогою ідеї динамічного програмування. Ми можемо ітерувати по паліндрому, починаючи з лівого та правого кінців. Нехай стан dp (x_1;y_1;x_2;y_2) — це стан, що позначає, що ми зіставили x_1 + y_1 позицій паліндрома, а останні позиції — (x_1;y_1) та (x_2;y_2). Ми можемо перейти зі стану (x_1;y_1;x_2;y_2) у стан (x'_1;y'_1;x'_2;y'_2) тоді й лише тоді, коли (x'_1;y'_1) можна досягти з (x_1;y_1) за один допустимий крок (у напрямку вправо або вниз), а (x'_2;y'_2) можна досягти з (x_2;y_2) за один допустимий крок (у напрямку вліво або вгору), і при цьому клітинки (x'_1;y'_1) та (x'_2;y'_2) рівні. Це дає часову та просторову складність \mathcal{O}(n^4).

  3. Ця підзадача має обмеження n \le 500. Її можна розв'язати за допомогою схожого dp. Однак можна помітити, що існує багато недосяжних станів. Ми можемо оптимізувати це, використовуючи той факт, що x_1 + y_1 + x_2 + y_2 = 2n-2, звідки y_2 = 2n-2 - x_1 - y_1 - x_2. Таким чином, ми можемо реалізувати dp з часовою складністю \mathcal{O}(n^3).

  4. Ця підзадача має обмеження n \le 1500. Оскільки тести генеруються випадковим чином, ми можемо перевірити велику кількість шляхів і з великою ймовірністю стверджувати, що ми отримали правильну відповідь. Розглянемо всі шляхи, для яких |x_1-y_1| \le C та |x_2 - y_2| \le C, де — константа. Тепер ми можемо представити кожен стан dp як (x_1;x_1-y_1+C;x_2;x_2-y_2+C) і виконати те саме dp, що й у підзадачі , що дає часову складність \mathcal{O}(n^2C^2).

  5. Остання підзадача не має жодних додаткових обмежень. Її можна розв'язати, оптимізувавши dp з підзадачі 4, використовуючи ту саму ідею, яку ми застосували для оптимізації dp з 2-ї до 3-ї підзадачі. Нас цікавить видалення найбільшого виміру, тож у нас залишиться часова складність \mathcal{O}(n C^2).

    Встановлення C=50 дасть достатньо високу ймовірність, щоб пройти всі тестові приклади.

    Це один із розв'язків цього завдання. Може існувати багато інших розв'язків, відмінних від цього, які також пройдуть випадкові тести.