Editorial

Підзадача 1:

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

Складність: $O(4^{nm}nm)$.

Підзадача 2:

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

Складність: $O(nm)$.

Підзадача 3:

Оскільки кількість кутів не перевищує 8, то ми можемо перебрати всі можливі повороти саме для кутових деталей. Тоді для кожного стану кутових труб, ми зможемо або відновити фігуру, або сказати, що таке неможливо. Для цього потрібно кожну пряму трубу повернути так, щоб один з її кінців був приєднаним до кутової труби або до труби, для якої поворот уже відомий. Зауважимо, що якщо це робити за допомогою проходу по всьому полю, то ваш розв'язок не вкладеться в обмеження за часом. Щоб це виправити, потрібно робити пробіг тільки по тих фрагментах, де у вас знаходяться саме прямі труби, якщо відповідь існує, то їх буде $O(n+m)$ штук.

Складність: $O(4^c(n+m))$, де $c$ "— кількість кутових труб.

Підзадача 4:

Якщо в цьому блоці відповідь існує, то є рівно три варіанти того, що може знаходитись у рядку:

• обидва фрагменти не містять труб;

• обидва фрагменти містять прямі труби;

• обидва фрагменти містять кутові труби.

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

Складність: $O(nm)$.

Підзадача 5:

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

Складність: $O(nm)$.

Підзадача 6:

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

Складність: $O(4^{m}n)$.

Підзадача 7:

Цей блок призначений для розв'язків, які правильні, але написані неоптимально, це може бути розв'язок зі складністю $O(n{m}^2)$, $O(n^{2}m)$ чи якісь оригінальні розв'язки, не передбачені автором.

Підзадача 8:

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

Складність: $O(nm)$.