A3 - Sdneirf
| Vremensko ograničenje | Memorijsko ograničenje |
|---|---|
| 2000ms | 256MB |
Prethodnih godina, filmovi duologije o velikom šefu mafije ekskluzivne disjunkcije Okram Ćivas postali su neki od najpopularnijih i najvoljenijih na tržištu. Duologija se sastojojala od, kao što ime kaže, dva filma, koji se zovu Okram i Ćivas. Međutim, usled lude popularnosti prethodna dva filma, pokrenula se proizvodnja za treći i poslednji deo ovog serijala - "Sdneirf". U ovom filmu Okram Ćivas je odavno napustio mafiju i sad živi srećno sa svojom porodicom. Međutim, onda stiže poziv za jedan poslednji zadatak...
U poslednjoj avanturi našeg heroja, slično kao u prvoj (mora da se gađa na nostalgiju u ovakvim filmovima), on se zatekao u misterioznoj matrici, dimenzija \(N\times M\). U svakom polju matrice je napisan po jedan ceo nenegativan broj, konkretno u polju u preseku reda \(i\) i kolone \(j\) se inicijalno nalazi vrednost \(a_{i,j}\). Posle zabune oko toga šta se dešava, Okram Ćivas je shvatio da ima samo jedan način na koji može da menja vrednosti u ovoj matrici. U svakom potezu, on može da izabere nenegativan ceo broj \(X\) i neki niz od \(N+M-1\) polja koji počinje od gornjeg levog polja i završava se na donjem desnom, tako da svaka dva susedna polja u tom nizu dele stranicu, i onda za svako polje na tom putu promeni vrednost u njemu na sledeći način: ako se pre ovog poteza u ovom polju nalazio broj \(Y\), nova vrednost u ovom polju će biti \(Y\text{ xor }X\).
Kako je Okram Ćivas poznat po svojoj majstoriji sa ekskluzivnom disjunkcijom, on je sebi zadao sledeći zadatak: posle proizvoljnog broja poteza, koja je najmanja moguća suma svih vrednosti u matrici? Ako uspe da minimizuje sumu, deluje da će uspeti da pobegne iz ove matrice i zauvek napusti svet kriminala.
Opis ulaza
Prva linija standardnog ulaza sadrži dva cela broja, broj redova \(N\) i broj kolona \(M\), redom. Narednih \(N\) linija sadrže po \(M\) celih brojeva: \(j\)-ti broj u \((i+1)\)-voj liniji predstavlja broj \(a_{ij}\), koji označava početnu vrednost polja u \(i\)-tom redu i \(j\)-toj koloni.
Opis izlaza
U jedinoj liniji standardnog izlaza potrebno je ispisati jedan ceo broj: najmanju moguću sumu brojeva u matrici posle nekog broja poteza.
Primer 1
Ulaz
Izlaz
Primer 2
Ulaz
Izlaz
Objašnjenje primera
U prvom primeru, početna suma je jedan. Ovo je minimalna vrednost jer je suma pozitivna posle proizvoljno mnogo poteza.
U drugom primeru, u prvom potezu Okram Ćivas može uzezi \(X=7\) i niz polja \((1,1),\) \((1,2),\) \((2,2),\) \((2,3)\), a onda napravi \(3\) poteza sa \(X=5\) i prvo nizom polja \((1,1),\) \((2,1),\) \((2,2),\) \((2,3)\), zatim nizom polja \((1,1),\) \((1,2),\) \((1,3),\) \((2,3)\) i na kraju nizom \((1,1),\) \((1,2),\) \((2,2),\) \((2,3)\).
Ograničenja
- \(1 \leq N,M \leq 1.500\).
- \(0\leq A_{ij}\leq 1.000.000.000\).
Test primeri su podeljeni u pet disjunktnih grupa:
- U test primerima vrednim \(10\) poena: \(N,M\leq2\).
- U test primerima vrednim \(10\) poena: \(N=1\).
- U test primerima vrednim \(20\) poena: \(N=2\).
- U test primerima vrednim \(30\) poena: \(0\leq A_{ij}\leq 1\).
- U test primerima vrednim \(30\) poena: Bez dodatnih ograničenja.
Napomena
Operator ekskluzivne disjunkcije u Pascal-u je označen sa xor, dok u C++ ga zapisujemo pomoću simbola ^. Ova operacija \(x\ \text{xor} \ y\) se za nenegativne cele brojeve \(x,y\) definiše na sledeći način. Prvo se brojevi zapišu u binarnom zapisu. Ukoliko jedan broj ima manje cifara od drugog, dopisuju mu se vodeće nule sve dok ne budu imali isti broj binarnih cifara. Tako se dobijaju dva niza binarnih cifara, označimo ih sa \(a_1, \ldots, a_k\) i \(b_1, \ldots b_k\). Zatim se za svaku poziciju \(i \in {1, \ldots, k }\) računa \(c_i\) pomoću sledećih pravila:
- Za \(a_{i} = 0, b_{i} = 0\) važi \(c_{i} = 0\)
- Za \(a_{i} = 0, b_{i} = 1\) važi \(c_{i} = 1\)
- Za \(a_{i} = 1, b_{i} = 0\) važi \(c_{i} = 1\)
- Za \(a_{i} = 1, b_{i} = 1\) važi \(c_{i} = 0\)
Niz binarnih cifara \(c_1, \ldots, c_k\) (koji možda ima vodeće nule) je binarni zapis rezultata, odnosno broja \(x \ \text{xor} \ y\).
Ako želite da upoznate sa prethodnim avanturama Okrama Ćivasa, posle takmičenja možete da pogledate prošlogodišnji treći zadatak za B kategoriju na okružnom: Okram, kao i prošlogodišnji drugi zadatak za A kategoriju na okružnom: Ćivas
| Autor | Tekst i test primeri | Analiza rеšenja | Testiranje |
|---|---|---|---|
| Pavle Martinović | Pavle Martinović | Jovan Bengin | Aleksa Milisavljević |
Analiza
Primetimo prvo da nikada ne moramo napraviti potez sa nekim \(X\) koje nije stepen dvojke. Naime, umesto jednog poteza sa \(X = 2^{i_1} + 2^{i_2} + 2^{i_3} + .... + 2^{i_k}\), \(i_1 < i_2 < ... < i_k\), možemo da napravimo \(k\) poteza nad istim putem sa vrednostima \(2^{i_1}, 2^{i_2}, ... , 2^{i_k}\). Dakle, možemo pretpostaviti da će \(X\) koje biramo uvek biti oblika \(2^j\).
Pošto sada nijedan potez nad nekim bitom ne utiče na druge, možemo za svaki bit nezavisno naći optimalno rešenje i na kraju ih sva sumirati. Formalnije, definišimo matrice \(B_0, B_1, ... , B_K\), gde je \(B_{x, i, j} = 1\) ako \(A_{i, j}\) sadrži \(x\)-ti bit, u suprotnom je \(B_{x, i, j} = 0\). Ako je \(C_i\) optimalno rešenje za matricu \(B_i\), onda je optimalno rešenje za matricu \(A\) jednako \(\sum\limits_{i=0}^{K} 2^i*C_i\). Pošto važi \(A_{i,j} \leq 10^9 < 2^{30}\), dovoljno je uzeti \(K = 29\) (jer bi matrice B_i za veće vrednosti \(i\) sadržale samo nule, pa bi i \(C_i\) bilo \(0\)).
Dalje ćemo razmatrati samo matrice čiji su svi članovi \(0\) ili \(1\), a poteze vršimo isključivo sa \(X = 1\). Cilj nam je da dobijemo matricu sa minimalnim brojem jedinica.
Rešenje kada je \(N, M \leq 2\)
Ako je \(N = 1\) ili \(M = 1\), postoji tačno jedan put od \((1, 1)\) do \((N, M)\). Ako je \(N = M = 2\), postoje dva puta. Pošto postoje najviše dva različita puta, time i najviše četiri različite kombinacije poteza (pošto se dva ista poteza skraćuju), možemo za svaku kombinaciju proveriti kako će matrica izgledati, i uzeti onu sa najmanjom rezultujućom sumom.
Rešenje kada je \(N = 1\)
Pošto postoji samo jedan moguć put, postoje samo dva moguća niza poteza: jedan gde ne radimo ništa (tada će matrica sadržati \(a\) jedinica), i drugi gde put prolazi kroz celu matricu (tada će matrica sadržati \(M - a\) jedinica), pa će rešenje biti \(min(a, M - a)\).
Rešenje kada je \(N = 2\)
Grupisaćemo polja tako da sva polja sa istom \(i + j\) vrednosti budu u istoj grupi. Svaka grupa će onda zapravo biti dijagonala koja ide od dole-levo ka gore-desno, i sadržaće najviše dva polja.
Primetimo da svaki put od \((1, 1)\) do \((N, M)\) sadrži po tačno jedan element iz svake grupe. To znači da ako je ukupan xor svih elemenata neke grupe jednak \(0\), posle jednog poteza biće \(1\), i obrnuto. Neka na početku \(a\) dijagonala ima xor jednak nuli, a \(b\) dijagonala xor jednak jedinici. Onda će nakon jednog poteza biti \(b\) dijagonala sa xor \(0\), i \(a\) sa \(1\), nakon drugog poteza će ponovo biti \(a\) sa \(0\) i \(b\) sa \(1\) itd. Pošto svaka dijagonala koja ima xor jednak jedinici mora da sadrži barem jednu jedinicu, vidimo da je rešenje barem \(min(a, b)\).
Ispostavlja se da je ovaj minimum uvek moguće postići. Bez umanjenja opštosti, neka je \(a \geq b\) (\(b < a\) se radi na isti način, samo što se na početku uradi bilo koji potez). Pokazaćemo da je dijagonale sa xor-om \(1\) (kojih ima \(b\)) moguće transformisati tako da imaju tačno jednu jedinicu, a one sa xor-om \(0\) tako da nemaju nijednu.
Za dijagonale koje sadrže jedno polje je očigledno: ako im je xor \(0\), onda je njihov jedini element \(0\), uostalom je \(1\). Dijagonale koje sadrže dva polja i imaju xor \(1\) takoće sadrže tačno jednu jedinicu. Ostalo nam je da pokažemo da, ako imamo dijagonalu koja sadrži dve jedinice, možemo obe pretvoriti u nule a da ne menjamo ostale elemente. Neka su elementi te dijagonale \((2, i)\) i \((1, i + 1)\). Napravićemo dva poteza: u prvom biramo put \((1, 1), (1, 2), ... , (1, i), (1, i+1), (2, i+1), (2, i+2), ..., (2, M)\), a u drugom put \((1, 1), (1, 2), ... , (1, i), (2, i), (2, i+1), (2, i+2), ... , (2, M)\). Primetimo da su jedina polja koja se nalaze u tačno jednom putu baš \((2, i)\) i \((1, i + 1)\). To znači da su to jedina dva polja čija će se vrednost obrnuti, pa tako od dve jedinice dobijamo dve nule.
Rešenje kada su sve početne vrednosti \(0\) ili \(1\)
Pošto smo početnu matricu \(A\) podelili na matrice sa vrednostima \(0\) i \(1\), ovaj podzadatak se rešava na isti način kao glavno rešenje. Ipak, moguće ga je uraditi i bez znanja da možemo nezavisno nalaziti rešenje za svaki bit.
Glavno rešenje
Slično kao u rešenju za \(N = 2\), grupisaćemo polja po dijagonali. Ovde se takođe ispostavlja da, ako imamo \(a\) dijagonala sa xor \(0\) i \(b\) sa xor \(1\), rešenje je \(min(a, b)\). Ovo možemo pokazati na sličan način kao za \(N = 2\), samo što sada moramo za svaku dijagonalu sa neparnim brojem jedinica dokazati da je možemo transformisati da ima jednu jedinicu, a za one sa parnim brojem jedinica da nemaju nijednu.
Na sličan način kao u slučaju \(N = 2\), možemo u dva poteza obrnuti vrednosti neka dva polja \((i, j)\) i \((i -1, j + 1)\). Ako dijagonalu predstavimo kao niz, ova operacija nam zapravo znači da obrćemo vrednosti neka dva susedna polja. Upotrebom ove operacije treba da dobijemo minimalan broj jedinica.
Ovo se može uraditi na sledeći način: iteriramo kroz niz sleva nadesno, i ako naiđemo na neki element koji je \(1\) (a nije poslednji), jednom operacijom obrćemo njega i sledeći element. Na kraju će svi elementi niza biti \(0\), sem eventualno poslednjeg. Pošto naša operacija ne menja parnost broja jedinica, ako je na početku bio neparan broj jedinica, poslednji element će biti \(1\), uostalom će biti \(0\), pa smo dokazali da je moguće dostići željeni minimum.
Ukupna složenost će biti \(O(NMlog(max(A_{i,j}))\), jer za svaki bit rešenje nalazimo u \(O(NM)\).