Matrix#484

Matrix (Editorial)

Автор, розробник, автор розбору: Андрій Столітній

Для фіксованого стану матриці задачу можна розв'язувати за допомогою динамічного програмування. Нехай dp_{i,j} — сторона найбільшої квадратної матриці, яка складається тільки з одиниць та має правий нижній кут в . Тоді можна зробити перерахунок значень наступним чином:

dp_{i,j} = \begin{cases} 0, & \text{якщо } a_{i,j} = 0, \\[6pt] 1 + \min\ { \left( dp_{i-1,j-1},\, dp_{i-1,j},\, dp_{i,j-1}\right) }, & \text{якщо } a_{i,j} = 1. \end{cases}

А відповідь тоді буде максимумом по всіх значеннях , \displaystyle ans = \max_{1 \le i,j \le n} dp_{i,j}.

Можна помітити, що 0 \le dp_{i,j} \le n для всіх позицій . Друга важлива річ, що запити тільки можуть поміняти на , тобто відповідь ніколи не погіршується, тобто кожне зі значень dp_{i,j} ніколи не зменшується. Отже, можемо оновлювати значення частково. Якщо ми оновили значення dp_{i,j}, то воно може вплинути тільки на значення dp_{i,j+1}, dp_{i+1,j}, dp_{i+1, j+1}. Можемо перераховувати значення , і якщо воно змінилось, перерахуймо значення, які залежать від нього. Якщо вони змінились, то перерахуємо значення, які залежать від них і так далі. Це можна реалізувати або чергою, або за допомогою рекурсії. Так як кожне значення може змінюватись не більше ніж разів, а таких значень маємо n^2, то загальний час виконання програми буде \mathcal{O}(n^3).