Матриця#400

Матриця (Розбір)

  1. Ця підзадача має обмеження n,m \le 20. Її можна розв'язати багатьма способами, наприклад, ми можемо перебирати "центр" трикутника, перебирати всі клітинки та перевіряти, чи належить ця клітинка трикутнику. Це дає нам часову складність \mathcal{O}((nm)^2).

  2. Ця підзадача має обмеження n,m \le 100. Тепер ми могли б робити майже те саме, але замість того, щоб перебирати всі клітинки та перевіряти їх потім, ми могли б одразу перебирати клітинки трикутника. Це дає нам часову складність \mathcal{O}((n-k)(m-k) k^2).

  3. Ця підзадача має лише одне додаткове обмеження a_{i,j} \le 1. Вона відрізняється від інших тим, що ми фактично можемо замінити операції знаходження максимуму на операції суми — нам потрібно порахувати кількість одиниць у трикутнику. Ми можемо порахувати цю суму всередині трикутника, використовуючи префіксну суму. Спочатку ми рахуємо префіксні суми по рядках, а потім по діагоналях. Якщо у нас є сума попереднього трикутника, ми можемо додати до неї рядок і відняти суму по діагоналі. Це дає часову складність .

  4. Ця підзадача має обмеження n,m \le 1000. Її можна розв'язати за \mathcal{O}(nm \log^2 k), \mathcal{O}(nm \log k) або за . Тут ми обговоримо розв'язок за \mathcal{O}(nm \log k). Важливе спостереження: ми можемо розбити трикутник на три частини — квадрат розміру \lceil \frac{k}{2} \rceil та два трикутники розміру \lfloor \frac{k}{2} \rfloor. Використовуючи це, нам потрібно порахувати максимум на квадратах і трикутниках \mathcal{O}(\log k) різних розмірів.

  5. Для цієї підзадачі немає додаткових обмежень. Її можна розв'язати за . Розмістимо "спостерігачів" у кожній точці (\lfloor \frac{k}{2} \rfloor a;\lfloor \frac{k}{2} \rfloor b) для кожних a,b \in \mathbb{N}. Ці спостерігачі будуть обчислювати блоки розміру у кожному з напрямків. Ці блоки потрібно обчислювати таким чином, щоб, якщо спостерігач знаходиться всередині трикутника, ми могли розбити трикутник щонайбільше на непересічні попередньо обчислені частини та об'єднати їх. Щоб оптимізувати споживання пам'яті цим розв'язком, ми спочатку призначимо спостерігача для кожного трикутника, потім переберемо спостерігачів, попередньо обчислимо блоки, а потім переберемо трикутники. Це призведе до часової складності .