Автор задачі: | Костянтин Денисов |
Задачу підготував: | Павло Цікалишин |
Розбір написав: | Костянтин Денисов |
Нехай ми розставили одинички в перших стовпчиках. Яку інформацію нам варто зберегти, щоб ефективно працювати з таблицею і надалі розставляти наступні стовпці? Всю матрицю зберігати це досить багато інформації. Можна помітити, що єдине, що нам потрібно знати про перші стовпчиків — це скільки поточно є рядків з непарною кількістю . Тоді якщо маємо рядків з непарною кількістю одиниць, то матимемо n-cnt з парною кількістю. Далі коли будемо ставити новий стовпчик, то будемо намагатися перераховувати цю кількість "непарних" рядків (це ті рядки в яких непарна кількість одиничок).
Тому виникає ідея писати динаміку dp[i][cnt]=true/false. Стан dp[i][cnt]=true тоді та тільки тоді, коли можна поставити одинички у перших стовпчиках, так що кількість непарних рядків у них дорівнює . База динаміки dp[0][0]=true.
Як робити переходи? Нехай ми маємо стан dp[i][cnt]=true та у i+1 стовпчику в нас одиничок. Розглянемо два випадки:
x+cnt \le n.
В цьому випадку максимальна кількість одиничок після того, як ми встановимо i+1 стовпчик буде x+cnt, оскільки ми можемо поставити всі наші в "парні" рядки. Тобто в цьому випадку перетин поточних непарних рядків з новими одиничками буде порожнім.
А який максимальний перетин може бути? Виявляється, \min(x, cnt). Нескладно зрозуміти, що ми можемо зробити всі перетини з відрізка [0, \min(x, cnt)]. Тоді можливі кількості непарних рядків після встановлення стовпчика i+1 мають вигляд x+cnt-2\cdot y, де — ціле число з проміжку [0, \min(x, cnt)].
x+cnt>n.
В цьому випадку ми вже не можемо зробити порожній перетин між поточними "непарними" рядками та одиничками у новому стовпчику. Який тоді можливий мінімальний перетин? Нескладно зрозуміти, що x+cnt-n. Коли ми розставимо n-cnt одиничок у i+1 стовпчику у "парні" рядки, то всі інші прийдеться розставляти у непарні.
Максимальний перетин залишається \min(x, cnt). Тоді можливі кількості непарних рядків після встановлення стовпчика i+1 мають вигляд x+cnt-2\cdot y, де — ціле число з проміжку [x+cnt-n, \min(x, cnt)].
Помітимо, що наші переходи зі стану dp[i][cnt] відбувається у якийсь відрізок станів [l, r] у dp[i+1], але по парності (тобто переходимо у l, l+2, l+4, \ldots).
В лоб робити такі переходи займає O(n^2 \cdot m) операцій, тому є потреба у оптимізаціях. А саме помітимо, що для фіксовано всі стани, де dp[i][cnt]=true утворюють неперервний відрізок [l, r] по парності (тобто dp[i][l]=true, dp[i][l+2]= true, \ldots).
Тоді виникає ідея зберігати масиви та . Коли переходимо до i+1 рядка з -ого, то проходимося по всім станам з відрізка [l[i], r[i]] по парності. Для кожного рахуємо відрізок в яких переходимо і визначаємо l[i+1], r[i+1] як об'єднання всіх таких відрізків по всім .
Тоді буде максимальною кількістю непарних рядків. Це вже працює за O(n \cdot m), що досить швидко.
Як тоді відновлювати? Можемо іти з кінця і за допомогою наших l[i], r[i] відновлювати в кожному стовпчику. Ми знаємо останнього рядка — . Дізнаємося для передостаннього і далі послідовно будемо рахувати через cnt[i+1].
Дізнаватися через cnt[i+1] досить просто. Проходимося по всім станам по парності з відрізка [l[i], r[i]]. Нехай зараз розглядаємо стан cur_cnt. Знаходимо відрізок в який можемо перейти з нього . Якщо cnt[i+1] \in [a, b], то нам підходить cur_cnt в якості .
Так побудувавши масив , вже нескладно відновити вихідну таблицю.
Складність алгоритму: O(n \cdot m).