Бојење
Аутор: Димитрије Ердељан
Текст и тест примери: Филип Ћосовић
Анализа решења: Димитрије Ердељан
Тестер: Марко Савић
Доказаћемо да оптимално решење сигурно има следећи облик: број белих
поља у колони опада до неке тачке, а затим расте до краја, или расте
до неке тачке па опада до краја. Ово значи да, ако сортирамо редове по
позицији где им се мења боја, првих K редова бојимо бело-црно, а
остале црно-бело.
Да би доказ био једноставнији, уместо да бирамо боје за редове,
бираћемо функцију f, где је f(i) број белих поља у колони између
“промена” i-1 и i. За валидна бојења зида важе следеће особине
f, и обрнуто, ако особине важе можемо направити бојење:
-
f(0) + f(n) = n (сви редови промене боју)
- За свако i, |f(i) - f(i-1)| = 1 (сваки пут се мења тачно један
ред)
Доказ овога остављамо читаоцу.
Прво, сигурно постоји тачно један “тренутак” (део зида између две
промене) када имамо по \frac{N}{2} црних и белих поља (за непарно
N, сличним аргументом доказујемо да се тачно једном број мења са
“више белих” на “више црних”), тј. постоји тачно једно x за које
f(x) = \frac{n}{2}. Када ово не би било тачно, могли бисмо да
побољшамо решење:
- Нађемо x такво да је f(x) = \frac{n}{2} и f(x-1) = f(x+1) =
\frac{n}{2} + 1 (или слично за -1) – ако не постоји, можемо
одабрати неки интервал између две тачке где f(i) = \frac{n}{2} и
“обрнути” их (поставити f(i) = n - f(i)) тако да се не промени
вредност решења.
- Поставимо f(x) = \frac{n}{2} - 2.
Без губитка општости претпоставићемо да f(0) < \frac{n}{2} (почињемо
са мање белих него црних поља). На сличан начин можемо доказати да на
интервалу од 0 то тачке где имамо исти број црних и белих поља
функција f опада до неке тачке па расте, а од те тачке расте па
опада.
Дакле, оптимално f мора имати облик “опада, па расте, па
опада”. Сада ћемо доказати да не можемо имати оба опадајућа дела: ако
постоје, можемо смањити f(0) за 2 и повећати f(n) за 2 и
добити боље решење.
Сада смо доказали да је оптимално решење или да број белих поља расте
до неке тачке па опада до краја, или обрнуто. Како за сваки избор
броја белих поља на почетку постоји тачно једна тачка где можемо прећи
са растућег на опадајуће, или са опадајућег на растуће (када су сва
поља исте боје), имамо \mathcal{O}(n) опција које треба проверити.
Сада још остаје да нађемо начин да израчунамо колико бојење вреди, ако
је дат број белих поља K на почетку, и знамо да тај број опада првих
x колона а затим расте до N-K.
Смернице за алгоритам
Израчунаћемо само вредност бојења од почетка до колоне x. Од те
колоне до краја метод је идентичан.
Вредност коју треба израчунати је:
\sum_{i = 0}^{x} (A_i - A_{i-1}) \cdot (K - i) = K \sum_{i=0}^x
(A_i - A_{i-1}) - \sum_{i=0}^x i \cdot (A_i - A_{i-1})
Да бисмо ово рачунали у константном времену, на почетку програма је
довољно да израчунамо низове префиксних сума које нам дају ове две
“мале” суме за свако x.