Сднеирф
Аутор: Павле Мартиновић
Текст и тест примери: Павле Мартиновић
Анализа решења: Јован Бенгин
Тестирање: Алекса Милисављевић
Анализа
Приметимо прво да никада не морамо направити потез са неким X које није степен двојке. Наиме, уместо једног потеза са X = 2^{i_1} + 2^{i_2} + 2^{i_3} + .... + 2^{i_k}, i_1 < i_2 < ... < i_k, можемо да направимо k потеза над истим путем са вредностима 2^{i_1}, 2^{i_2}, ... , 2^{i_k}. Дакле, можемо претпоставити да ће X које бирамо увек бити облика 2^j.
Пошто сада ниједан потез над неким битом не утиче на друге, можемо за сваки бит независно наћи оптимално решење и на крају их сва сумирати.
Формалније, дефинишимо матрице B_0, B_1, ... , B_K, где је B_{x, i, j} = 1 ако A_{i, j} садржи x-ти бит, у супротном је B_{x, i, j} = 0. Ако је C_i оптимално решење за матрицу B_i, онда је оптимално решење за матрицу A једнако \sum\limits_{i=0}^{K} 2^i*C_i. Пошто важи A_{i,j} \leq 10^9 < 2^{30}, довољно је узети K = 29 (јер би матрице B_i за веће вредности i садржале само нуле, па би и C_i било 0).
Даље ћемо разматрати само матрице чији су сви чланови 0 или 1, а потезе вршимо искључиво са X = 1. Циљ нам је да добијемо матрицу са минималним бројем јединица.
Решење када је N, M \leq 2
Ако је N = 1 или M = 1, постоји тачно један пут од (1, 1) до (N, M). Ако је N = M = 2, постоје два пута.
Пошто постоје највише два различита пута, тиме и највише четири различите комбинације потеза (пошто се два иста потеза скраћују), можемо за сваку комбинацију проверити како ће матрица изгледати, и узети ону са најмањом резултујућом сумом.
Решење када је N = 1
Пошто постоји само један могућ пут, постоје само два могућа низа потеза: један где не радимо ништа (тада ће матрица садржати a јединица), и други где пут пролази кроз целу матрицу (тада ће матрица садржати M - a јединица), па ће решење бити min(a, M - a).
Решење када је N = 2
Груписаћемо поља тако да сва поља са истом i + j вредности буду у истој групи. Свака група ће онда заправо бити дијагонала која иде од доле-лево ка горе-десно, и садржаће највише два поља.
Приметимо да сваки пут од (1, 1) до (N, M) садржи по тачно један елемент из сваке групе. То значи да ако је укупан xor свих елемената неке групе једнак 0, после једног потеза биће 1, и обрнуто. Нека на почетку a дијагонала има xor једнак нули, а b дијагонала xor једнак јединици. Онда ће након једног потеза бити b дијагонала са xor 0, и a са 1, након другог потеза ће поново бити a са 0 и b са 1 итд. Пошто свака дијагонала која има xor једнак јединици мора да садржи барем једну јединицу, видимо да је решење барем min(a, b).
Испоставља се да је овај минимум увек могуће постићи. Без умањења општости, нека је a \geq b (b < a се ради на исти начин, само што се на почетку уради било који потез). Показаћемо да је дијагонале са xor-ом 1 (којих има b) могуће трансформисати тако да имају тачно једну јединицу, а оне са xor-ом 0 тако да немају ниједну.
За дијагонале које садрже једно поље је очигледно: ако им је xor 0, онда је њихов једини елемент 0, уосталом је 1.
Дијагонале које садрже два поља и имају xor 1 такоће садрже тачно једну јединицу.
Остало нам је да покажемо да, ако имамо дијагоналу која садржи две јединице, можемо обе претворити у нуле а да не мењамо остале елементе. Нека су елементи те дијагонале (2, i) и (1, i + 1). Направићемо два потеза: у првом бирамо пут (1, 1), (1, 2), ... , (1, i), (1, i+1), (2, i+1), (2, i+2), ..., (2, M), а у другом пут (1, 1), (1, 2), ... , (1, i), (2, i), (2, i+1), (2, i+2), ... , (2, M). Приметимо да су једина поља која се налазе у тачно једном путу баш (2, i) и (1, i + 1). То значи да су то једина два поља чија ће се вредност обрнути, па тако од две јединице добијамо две нуле.
Решење када су све почетне вредности 0 или 1
Пошто смо почетну матрицу A поделили на матрице са вредностима 0 и 1, овај подзадатак се решава на исти начин као главно решење. Ипак, могуће га је урадити и без знања да можемо независно налазити решење за сваки бит.
Главно решење
Слично као у решењу за N = 2, груписаћемо поља по дијагонали. Овде се такође испоставља да, ако имамо a дијагонала са xor 0 и b са xor 1, решење је min(a, b). Ово можемо показати на сличан начин као за N = 2, само што сада морамо за сваку дијагоналу са непарним бројем јединица доказати да је можемо трансформисати да има једну јединицу, а за оне са парним бројем јединица да немају ниједну.
На сличан начин као у случају N = 2, можемо у два потеза обрнути вредности нека два поља (i, j) и (i -1, j + 1). Ако дијагоналу представимо као низ, ова операција нам заправо значи да обрћемо вредности нека два суседна поља. Употребом ове операције треба да добијемо минималан број јединица.
Ово се може урадити на следећи начин: итерирамо кроз низ слева надесно, и ако наиђемо на неки елемент који је 1 (а није последњи), једном операцијом обрћемо њега и следећи елемент.
На крају ће сви елементи низа бити 0, сем евентуално последњег. Пошто наша операција не мења парност броја јединица, ако је на почетку био непаран број јединица, последњи елемент ће бити 1, уосталом ће бити 0, па смо доказали да је могуће достићи жељени минимум.
Укупна сложеност ће бити O(NMlog(max(A_{i,j})), јер за сваки бит решење налазимо у O(NM).