Editorial

Примітка: На усіх ілюстрація до розв'язку вважатимемо, що $n=2,m=3$.

Нехай базовим полем є таке поле, що у ньому є чорний прямокутник, такий, що його лівий нижній кінець має координати $(1,1)$. Тобто, таке поле виглядатиме так:

Тоді будь-яке інше поле можна отримати за допомогою деякого зсуву базового поля. Наприклад, якщо зсунути його на 2 клітинки вліво і на 1 вгору, отримаємо такий малюнок:

Твердження. Всього різних полів $2nm$. Усі види полів можна отримати зсунувши поле на деяке число $a$ вліво та деяке число $b$ вниз, де $0\le a\le 2m-1,0\le b\le n-1$.

Якщо вас не цікавить доведення, перегорніть на $2$ сторінку, де буде описуватись сам розв'язок.

Доведення. Нехай у нас є деяке поле, і деяка точка на ньому. У цієї точки є координати $(x,y)$. Тоді нехай трійка чисел $(c,x^{\prime },y^{\prime })$ — це її шахові координати, які формуются таким чином:

• $c$ — дорівнює $1$, якщо ця клітинка знаходиться в білому квадраті, і $0$, якщо у чорному.

• $x$ — відстань по осі $OX$ від лівого нижнього кута прямокутника, в якому ця клітинка знаходиться.

• $y$ — відстань по осі $OY$ від лівого нижнього кута прямокутника, в якому ця клітинка знаходиться.

Якщо ми зафіксуємо деяку точку та знатимемо її шахові координати, то ми зможемо однозначно побудувати поле, дізнавшись координати лівого нижнього кута прямокутника, в якому ця клітинка знаходиться та колір цього прямокутника. Очевидно, що для деякої фіксованої точки для кожної трійки будуть різні поля.

Можливих значень $c$ — 2, $x^{\prime }$ — m, $y^{\prime }$ — n. Отже, всього різних полів $2nm$.

Отже, ми знаємо, що всього полів $2nm$. Для того, щоб довести друге тверждення достатньо довести, що при будь-якому зсуві поля на деяке число $a$ вліво та деяке число $b$ вниз, де $0\le a\le 2m-1,0\le b\le n-1$, ми будемо отримувати різні поля.

Перше, що варто помітити, що при зсуванні поля на $a$ клітинок вліво і на $b$ вниз, шахові координати клітинок змінюються так само, як якби $x$-координату збільшили на $a$, а $y$-координату на $b$.

Зафіксуємо точку з шаховими координатами $(c,x^{\prime },y^{\prime })$. Без обмеження загальності скажемо, що $c=0$ (клітинка у чорному прямокутнику). Також скажемо, що $x^{\prime }\ne 0,y^{\prime }\ne 0$ (ці випадки доводяться ще легше).

Тоді можливі такі випадки:

• $0\le a\le m-x^{\prime }-1,0\le b\le n-y^{\prime }-1$. Тоді ми будемо залишатись всередині одного прямокутника, отже шахові координаті будуть дорівювати $(0,x^{\prime }+a,y^{\prime }+b)$.

• $0\le a\le m-x^{\prime }-1,n-y^{\prime }\le b\le n$. Тоді ми перейдемо в новий білий квадратик при зсуві вниз, і наші координати будуть $(1,x^{\prime }+a,b-n+y^{\prime })$

• І т.д.... Продовжити цей список читачу на домашнє завдання =). В кінці маємо отримати всі можливі види шахових координат.

Для інтуїтивного розуміння ось ілюстрація (червоним виділено ті місця, в які ми можемо потрапити з точки $(2,2)$ при зсуві):

Можна бачити, як зі шматочків білих та чорних квадратиків, на які можна потрапити можна зібрати білий прямокутник та чорний прямокутник.

А тепер власне розв'язок:

Це була центральна лема цієї задачі. Ось, що треба зробити, щоб отримати бали за блоки:

Нагадаємо, що при зсуві поля на $a$ клітинок вліво та $b$ клітинок вниз, кольори клітинок змінюються также само, як і при додаванні до відповідних координат клітинок чисел $a$ і $b$.

Блок 1

У першому блоці можна скласти велике поле, наприклад, $5000\times 5000$, (двовимірний масив символів або чисел). І перевіряючи на цьому полі чи можна зсунути точку на кожен з можливих $a$ і $b$, будемо рахувати кількість зсувів, які підходять для всіх точок.

Асимптотика $O(S^2+2nm\cdot k)$, де $S\times S$ — розмір вашого поля.

Розв'язок: https://pastebin.com/NWqwwG3B

Блок 2

Тепер ми будемо робити те саме, що у першому прикладі, але тепер замість того, щоб явно будувати поле, навчимося за $O(1)$ шукати колір клітинки за її координатами.

Підсказка. Для того, що знайти колір клітинки за її координатами, варто вважати, що спочатку у нас базове поле. Також дуже зручно вважати, що координати клітинок починаються не з $1$, а з $0$. Спробуйте вивести формулу. Якщо не зможете, то погляньте на функцію $getColor$ у розв'язку.

Асимптотика $O(2nm\cdot k)$.

Розв'язок: https://pastebin.com/2q72v6TL

Блок 3

У розв'язку третього блоку я буду вважати, що $n\le m$. Якщо це не так, то робимо аналогічно, але тепер знаходимо відрізки не для зсувів по вертикалі, а для зсувів по горизонталі.

Давайте для кожного зсуву точок вгору від 0 до $n-1$ знайдемо для кожної точки відрізки, які їй підходять. Ось наприклад, для точки з координатами $(2,2)$, потрібним їй білим кольором та вертикальним зсувом 1, їй підходять такі зсуви вправо (світло-сірим виділено саму клітинку, червоним обведено можливі зсуви):

Потім окремо для кожного з $n$ вертикальних зсувів знаходимо множину таких зсувів по горизонталі, що підходять нам. Для цього можна використати scanline, щоб знайти множину таких точок, які покриваються $k$ відрізками. Зауважте, що це не перетин відрізків, бо для одного вертикального зсуву для точки може бути не один, а два відрізка.

Для тих, хто ніколи не використовував метод scanline, почитайте про нього більше тут: https://informatics.mccme.ru/mod/resource/view.php?id=39111

Сума кількістей таких точок для кожного з $n$ зсувів точок вгору і є нашою відповіддю.

Асимптотика $O(k\cdot min(n,m))$.

Розв'язок: https://pastebin.com/w4TRJwu5

Блок 4

Якщо ми ще сильніше подивимось на ілюстрації, то зрозуміємо, що допустимі зсуви являють собою не випадковий набір відрізків, а прямокутнички, ось наприклад прямокутнички, для попередньої ілюстрації і для більшої зрозумілості, ілюстрація для випадку $n=m=3$ (координати і потрібний колір точки ті самі):

Тепер ми знову можемо використати scanline, але тепер замість того, щоб додавати в scanline точки, будемо додавати відрізки. Наша задача тепер знайти площу, яка покрита $k$ квадратиками.

Для того, щоб знаходити перетин відрізків у сканлайні вам знадобиться будь-яке збалансоване дерево пошуку. У мові програмування C++ для цього можна використати set.

Асимптотика $O(klog(k))$.

Розв'язок: https://pastebin.com/cpmL7TXX