[Rešenja zadataka] SIO 2017

[dd]

Klikeri

Možemo zanemariti odbijanje klikera: ako se dva klikera odbiju, pozicija koja se dobija je identična kao da su se mimoišli. Koristeći ovo, za fiksno T je lako odrediti dve moguće pozicije u koje svaki kliker može stići.

Postoji 2N kandidata za rešenje: za prvi kliker na N načina možemo fiksirati prekidač na kom će se naći. Do njega može stići na dva načina – ili direktno ili odbijanjem od zida (dovoljno je odabrati zid za koji brže stiže do prekidača, jer ako može da se reši za jedan zid, može i za drugi tako što obrnemo sve smerove). Ostaje samo da proverimo da li se mogu odabrati smerovi za fiksno T tako da svi klikeri završe na prekidačima.

Konstruišimo bipartitni graf u kom čvorovi sa jedne strane predstavljaju klikere, a sa druge strane prekidače. Grana od klikera do prekidača postoji ukoliko taj kliker može da bude na tom prekidaču za T sekundi (dakle, svaki kliker ima najviše dve izlazne grane). Očito je da rešenje postoji ukoliko možemo upariti svaki kliker sa po jednim prekidačem, odnosno ukoliko postoji perfect matching na ovom grafu, što možemo proveriti u O(N) (jer postoji O(N) čvorova i grana).

Ovaj graf ima jednu specijalnu osobinu: stepen svakog čvora je najviše dva. Samim tim, sačinjen je od izolovanih čvorova, puteva i ciklusa. Ako postoji izolovan čvor, matching ne postoji. U suprotnom, potreban i dovoljan uslov je da su dužine svih puteva parne (ciklusi sigurno imaju matching), tako da je dovoljno proveriti ovo umesto “redovnog” matching algoritma.

[Ramsey]

Zaduženja

Označimo optimalnu stazu (ciklus u grafu) sa C a njenu ukupnu dužinu sa w©. Jasno je da će tada traženo vreme biti

a * w© + b * minimalno_rastojanje(neki član komisije, ciklus C)

pa ovaj izraz treba minimizovati po C. Izraz se može uprostiti ako za svaki čvor unapred izračunamo A(u) - rastojanje od čvora u do njemu najbližeg člana komisije pomnoženo brojem b (nazovimo ovo “težina čvora”). Za ovo nam je dovoljan Floyd-Warshall ili puštanje Dijkstre iz svakog člana komisije (složenost je O(n^3) ili O(kmlog(n))). Dakle, potrebno je pronaći ciklus C za koji važi da je a*w© + min{A(u) | u iz C} minimalno.

Problem možemo posmatrati i iz drugog ugla: za čvor u, označimo sa MinCyc(u) dužinu najkraćeg ciklusa kome je čvor u čvor minimalne težine (dakle, NE najkraći od SVIH ciklusa koji sadrže u). Tada je
minimum po ciklusima C (a*w© + min{A(u) | u iz C}) = min po čvorovima u (MinCyc(u) + A(u))
pa je za svaki čvor dovoljno izračunati vrednost MinCyc.

Najtrivijalniji način je: za svaki čvor u, izbaciti iz grafa sve čvorove težine ne veće od u (uključujući i sam čvor u), naći sva najkraća rastojanja d[x][y] između čvorova novog grafa i staviti MinCyc(u) = minimum (w(u,x) + w(u,y) + d[x][y]) gde su x i y susedi čvora u koji su ostali u novom grafu. Složenost ovog pristupa je O(n^4) ili O(n^2 * m * log(n)).

Ukoliko sortiramo čvorove opadajuće po vrednosti A(u), tada važi MinCyc(u) = najkraći od SVIH ciklusa na skupu čvorova {1, 2, …, u} koji sadrži čvor u. Sada možemo vrednosti MinCyc računati modifikovanim Floyd-Warshall algoritmom: ovaj algoritam ima osobinu da neposredno pre k-tog koraka (spoljašnja od 3 ugnježdene for petlje) ima izračunate vrednosti d[u][v] - najkraće rastojanje od u do v preko prvih k-1 čvorova. Prema tome, za trenutni čvor k važi MinCyc(k) = minimum (w(k,u) + w(k,v) + d[u][v]) po svim susedima u,v čvora k za koje je u < k, v < k i d[u][v] != INF. Ako ovaj minimum računamo na početku svake spoljašnje for petlje, složenost Floyd-Warshalla ostaje O(n^3) i imamo vrednosti svih MinCyc(u) što je dovoljno za rešenje zadatka.

Podzadaci uključuju slučajeve za čije je rešavanje dovoljan pristup složenosti O(n^4) poput gore pomenutog, slučajeve gde je a = 0 (tada je rešenje min A(u) među svim čvorovima u koji pripadaju bar jednom ciklusu) i slučajeve gde je b = 0 (klasično traženje najkraćeg ciklusa u grafu). Zadatak se može uraditi i puštanjem Dijkstre iz svih čvorova sa komisijama (istovremeno) i fiksiranjem čvora koji će biti “ulaz” u kružnu stazu a zatim za njega računati najkraći ciklus koji ga sadrži i sastavljen je od čvorova “ispod njega” u Dijkstra-stablu (ovo je suštinski ista ideja kao i u gore pomenutom rešenju jer je redosled obilaska Dijsktrom rastući po vrednostima A).

[Ramsey]

Tetke

Označimo sa dist(i,j) menhetn rastojanje izmedju i-tog i j-tog polja a sa h[i] visinu i-tog polja.

Lema: Skup od n polja sa visinama u matrici je konzistentan (u smislu da postoji opisana matrica koja sadrži ova polja) ako i samo ako važe sledeća dva uslova
(1) Svi parni h[i]-ovi su na poljima čiji je zbir koordinata paran, a svi neparni h[i]-ovi na poljima čiji je zbir koordinata neparan ili obrnuto
(2) Za svaka dva polja i i j vazi |h[i] - h[j]| <= dist(i,j)

Ovo su očigledno potrebni uslovi, dok je za obrnut smer dovoljno pokazati da ako ovi uslovi važe, tada za bilo koje polje (x,y) postoji vrednost h koju možemo upisati u njega tako da ova dva uslova važe i za novi skup polja sa ovim poljem (to bi značilo da mozemo da popunimo celu matricu i da važe ova dva uslova, ali onda je ta matrica ok na osnovu primene tih uslova na susedna polja). Ideja dokaza je: u novo poolje (označimo ga sa n+1) možemo upisati konzistentnu vrednost (u smislu (2)) akko je pesek svih segmenata (na realnoj pravoj) [h[i] - dist(i,n+1), h[i] + dist(i,n+1)] neparazn (tada upisujemo odgovarajuću vrednost iz preseka vodeći računa i o (1)) a ovo se pokazuje koristeći već pretpostavljene uslove za prvih n polja i nejednakost trougla.

Uslov (1) se može trivijalno proveravati nezavisno od uslova (2) pa se koncentrišemo isključivo na uslov (2). Nazovimo par polja (i, j) “loš” ukoliko ne zadovoljava uslov (2) tj. ukoliko važi
() |h[i] - h[j]| > |x[i] - x[j]| + |y[i] - y[j]|
Koristeći oznake
Vpp(i) = L[i] + x[i] + y[i], Vpm(i) = h[i] + x[i] - y[i], Vmp(i) = h[i] - x[i] + y[i], Vmm(i) = h[i] - x[i] - y[i]
možemo se osloboditi apsolutnih vrednosti iz () razlikovanjem slučajeva. Tačnije, važi:

Za polje i postoji polje j za koje je (i,j) loš par ako i samo ako je tačno bar jedno od sledećih tvrđenja

1. j je “gore-levo” od i i važi Vmm(i) > Vmm(j)
2. j je “gore-levo” od i i važi Vpp(i) < Vpp(j)
   … (ukupno 8 slučaja koja zavise od položaja gore/dole-levo/desno i odnosa h[i] i h[j])

Ovo možemo rešavati 2D segmentnim stablom - za svako novo polje postavljamo 8 upita “vrati min/max iz date 2D oblasti” i ubacujemo ga u strukturu posle upita. Međutim, ovde je problem memorijsko ograničenje - čak i implicitno (dinamičko) stablo uz kompresiju koordinata zauzima n * log^2(n) memorije što je praktično nemoguće uklopiti u zadata ograničenja.

Bolji pristup je korišćenje binarne pretrage po rešenju - tada problem postaje “da li postoji loš par među prvih m polja” i više nije bitno da vratimo najmanji indeks tj. da na prethodne upite odgovaramo redom. Koristimo “offline” pristup - sortiramo sva polja npr. po y-koordinati a zatim ih redom ubacujemo u obično segmentno stablo (indeksirano po x-koordinatama) uz upite “min/max na segmentu” (potrebno je 2 puta proći kroz stablo, po jednom u svakom smeru). Vremenska složenost ovog pristupa je O(n * log^2(n)) a memorijska je O(n) i nosi maksimalan broj poena.

Podzadaci uključuju slučajeve kada prolazi rešenje složenosti O(n^2) (što je jedan od načina za “proveru” leme za vreme takmičenja), 1D slučaj (novo polje je dovoljno uporediti sa njegovim susedima), slučajeve u kojima su visine polja mali brojevi (na osnovu (*) za svako polje je dovoljno proveriti samo ona koja su na rastojanju ne većem od MaxH a njih ima O(MaxH^2)) kao i slučaj gde prolazi 2D segmentno.

[Ramsey]

Pogled

Neka je L[i] = optimalna zarada za prvih i zgrada ukoliko postavljamo samo uređaje okrenute ulevo i poslednji postavljeni uređaj je na i-toj zgradi. Analgo se definiše R[i] za desne uređaje i nije teško zaključiti da je rešenje zadatka max {L[i] + R[i]} i da se ova dva niza računaju simetrično pa nadalje gledamo samo za L[i]. Neka su h[], v[] i c[] visine, zarade i cene rušenja, redom. Zadatak rešavamo dinamičkim programiranjem. Važi

(1) L[i] = v[i] + maximum { L[j] - suma {c[k] | j < k < i, h[k] > h[i]} | j < i, h[j] < h[i] }

(sa desne strane je maximum po svim zgradama j < i koje su niže od i; to je kandidat za pretposlednju zgradu, a moramo srušiti sve zgrade između j i i koje su više od h[i] dok će cena preostaih rušenja zgrada viših od h[i] a levo od j biti uračunata u L[j] jer je h[j] < h[i]). U cilju nalaženja boljeg rešenja od O(n^2), jedan od načina je da se dinamika radi po visinama a ne redom s leva udesno; to ujedno omogućava da ne moramo da proveravamo uslov h[j] < h[i] u (1). Za dato i treba nam indeks j < i za koji je vrednost

L[j] - suma {c[k] | j < k < i, h[k] > h[i]} (*)

maksimalna. Međutim, primetimo da (*) dostiže maksimum u indeksu j ako i smo ako izraz

L[j] - suma {c[k] | j < k, h[k] > h[i]} (**)

dostiže maksimum maksimum u indeksu j (ostatak sume ne zavisi od j). Ovim smo izbacili parametar i iz granica pa sada možemo prebaciti priču na segmentno stablo i računanje nekih upita.

Neka su na početku svi L[i] = -INF. Posmatrajmo niz A dužine n koji je u i-tom koraku dinamike (idemo od najmanje do najveće zgrade) definisan sa (uzimamo da je h[0] = 0)

(2) A[j] = L[j] - suma {c[k] | j < k, h[k] > h[i]}

(dakle, na početku za sve j važi A[j] = -INF - suma {c[k] | j < k}). Kako računamo vrednosti L[i] redom po visinama zgrada, treba odraditi n koraka i u i-tom koraku:

a) Odrediti L[i] kao L[i] = v[i] + max(A[1],A[2],…,A[i]) + suma { c[k] | i < k, h[k] > h[i]};
b) Update-ovati niz A, tj. povećati A[i] za (L[i] + INF) i za sve j < i povećati A[j] za c[i].

Formula iz a) je tačna jer zamenom A[i] iz (2) dobijamo (1) (do tada su izračunati svi A[j] za h[j] < h[i]). Deo “+ suma…” je tu da bismo nadoknadili razliku između (*) i (**). Kod dela b), menja se više еlemenata niza A na osnovu definicije (2). Obe ove operacije možemo raditi u složenosti O(log n) - dovoljno nam je segmetno stablo nad nizom A koje podržava “vrati maximum na segmentu” i “povećaj sve elemente iz datog segmenta za dati broj” a to je max-segmento sa lazy propagation-om.
Za upit U(i) = suma { c[k] | i < k, h[k] > h[i]} možemo koristiti (drugo) suma-segmentno stablo nad nizom c[] pri čemu u i-tom koraku vraćamo sumu na segmentu [i, n] a zatim izbacujemo element c[i] (tj. postavljamo c[i] = 0) jer dinamiku radimo po visinama i za svaki naredni upit j važi h[j] > h[i] pa vrednsot c[i] ne učestvuje u sumi. Ukupna složenost je O(n log n).

Podzadaci uključuju slučajeve kada prolazi dinamičko programiranje u složenosti O(n^2) tj. direktno dinamičko iz formule (1), slučajeve gde se ne isplati rušiti zgrade (tada je rešenje jedinstveno - postaviti levi urđaj na prvu zgradu, zatim na prvu narednu koja nije zaklonjena prvom, zatim na prvu narednu koja nije zaklonjena drugom izabranom itd. do najviše zgrade i sl. za desne uređaje) kao i slučajeve gde su cena zgrada 0 što značajno pojednostavljuje formulu (1) na L[i] = v[i] + maximum { L[j] | j < i, h[j] < h[i] } pa ovo možemo rešavati slično kao LIS konstrukcijom max-segmentnog nad nizom L[i] (koje je indeksirano visinama ako računamo vrednosti L[i] od 1 do n ili je indeksirano pozicijama ako računamo vrednosti L[i] po visinama).

[PetarV]

Neonke

Prvi zadatak sa drugog dana Srpske Informatičke Olimpijade predstavlja challenge tip problema, tj. problema u kome najoptimalnije rešenje nije neophodno poznato. Stoga, cilj je bio maksimizovati pogodnost rešenja, sa parcijalnim nagrađivanjem za rešenja koja su između određenih graničnih vrednosti. Zadatak je uključivao pravilno raspoređivanje resursa, tako da se maksimizira prekrivanje prostorije neonskim sijalicama. Određene uštede su bile moguće ukoliko se sijalice “nadovezuju” jedne na drugu (tj. ukoliko jedna sijalica upada u svetlost druge), što može značajno umanjiti ukupnu cenu, ali i broj pokrivenih polja. Dodatne probleme izaziva relativno neoptimalan efekat blizine zidovima.

Generalno najbolji način da se “napadne” ovakav problem i njemu slični je da se napravi neka “osnovna” strategija za postavljanje neonki, sa svom neophodnom infrastrukturom (pomoćnim metodama itd.), pa da se nakon toga isprobavaju razne varijacije osnovnog algoritma, koje više uzimaju u obzir različite aspekte problema—uzimajući za svaki test primer onaj algoritam koji daje najbolje rezultate.

Verovatno najvažniji deo izgradnje rešenja je metoda koja određuje efekte postavljanja nove neonke na neko polje (na potencijalno već parcijalno osvetljenom podrumu). Ovo je izuzetno korisno iako je takmičarima bio dat na korišćenje detaljan vizualizator, i predstavlja glavni algoritamski izazov ovog zadatka, jer čini inkrementalno pravljenje rešenja izuzetno praktičnim. Ova metoda zahteva preračunavanje broja osvojenih polja, kao i spajanje nove neonke sa nekim drugim povezanim komponentama neonki, ukoliko je ovo primenljivo. Pošto su jačine neonki u test primerima bile relativno male, bilo je prikladno direktno ispitati sva polja u kvadratu oko potencijalne nove neonke. Za jednostavno održavanje povezanih komponenti moguće je bilo koristiti bilo koju strukturu za održavanje disjunktnih skupova.

Nakon što je ova metoda u mestu, moguće je bilo definisati neke osnovne strategije (Komisijske konstante za ocenjivanje su određivane na osnovu najboljeg i najgoreg učinka ovih strategija na test primerima):

• Gramzivo (greedy) rešenje fokusirano na pokrivenost: u svakom koraku, odabrati polje koje pokriva najviše nepokrivenih polja. Ovo rešenje je izuzetno neefikasno ukoliko je konstanta P velika, jer će rezultovati velikim brojem komponenti koje moraju da se odvojeno pale!
• 1-“zmija” rešenje, gde se prvo polje bira gramzivo, a sva naredna polja određuju tako da sve neonke konstantno ostaju u jednoj komponenti. Ovo rešenje je jako efektivno ako je cena dodavanja nove neonke značajno manja od cene paljenja jedne neonke, i ukoliko je moguće identifikovati povezanu komponentu u test primeru koja sadrži većinu slobodnih polja.
• nepovezano k-“zmija” rešenje, koje predstavlja korekciju prethodnog algoritma za višestruke odvojene povezane komponente slobodnih polja—krenuti ne od jednog nego od k gramzivo odabranih polja u odvojenim povezanim komponentama, i onda se od njih širiti tako da broj komponenti ne raste.
• nasumično k-“zmija” rešenje, gotovo identično kao prethodno, s tim da se početna polja ne biraju tako da budu u odvojenim komponentama, nego potpuno nasumično. Ovo može biti vrlo efektivno ako ima dosta prostora u podrumu, uz naznaku da će potencijalno u nekom momentu neke komponente da se spoje.

Nakon pravljenja osnovnog rešenja, moguće je dodatno ga poboljšati stohastičnom hill-climber strategijom (ova strategija nije bila korišćenja pri računanju gornjih granica), gde se pozicije neonki nasumično pomeraju za neku malu vrednost, ili se neonke potpuno izbacuju i postavljaju ponovo na neko drugo mesto. Tokom ove procedure, sve vreme pamtimo do sada najbolje dobijeno rešenje.

Test primeri (čije matrice su povučene sa finala Google-ovog Hash Code 2017 takmičenja, koje je i služilo kao glavna inspiracija za ovaj problem) su bili direktno dostupni takmičarima, tako da o njima ne moramo dodatno raspravljati. Prvi test primer je dizajniran da bude jednostavno maksimalno rešiv (dokle god je korišćenja k-“zmijska” strategija ili neka njena varijanta), dok su parametri ostalih test primera birani da pokriju širok spektar scenarija, poput:

• Veliki prostor, izuzetno mali poluprečnik, jeftino pravljenje novih komponenti;
• Veliki prostor, izuzetno veliki poluprečnik;
• Skučeni prostor (sa mnogo odvojenih sitnih komponenti).

Zadovoljstvo nam je da vidimo da je značajan broj takmičara pokušao da se oproba u rešavanju bar jednog test primera. Posebne čestitke Dušanu Živanoviću za osvojenih 98 poena na ovom zadatku! U prilogu možete videti vizuelizaciju njegovih poslatih rešenja za sva četiri test primera. Nadam se da vam se zadatak svideo!

[redemption99]

Ovo je super. Da li cete izbaciti ovako i resenja sa ostalih nivoa takmicenja od ove godine?

[nenad.bauk]

Virus

Zadatak se svodi na: za dato stablo sa N čvorova, izabrati minimalan broj parova čvorova (neka je taj broj P) tako da se svaki čvor stabla nalazi na bar jednom od P puteva čiji su krajevi izbaranih P parova čvorova. Drugim recima, unija tih P puteva treba da ‘prekrije’ ceo graf.

Prvo treba uočiti da je uvek optimalno da se povežu dva lista u grafu. Jedini način da se neki list ‘prekrije’ je da taj list bude jedan od čvorova iz skupa odabranih P parova. Prema tome, donja granica rešenja je P = floor((L+1)/2) gde L broj listova u stablu, a floor je funkcija koja vraća donji ceo deo.

Uzmimo proizvoljan čvor X koj nije list. Kad bismo izabrali P parova čvorova tako da svaki par čine neka dva lista i da put između ta dva lista prolazi kroz X, ceo graf bi bio prekriven. Zaista, ovim smo prekrili put od svakog lista do X, a to je celo stablo. Uslov da putevi između listova svakog para prolaze kroz X je ekvivalentan sa uslovim da listovi svakog para pripadaju različitim podstablima sinova čvora X.

Umesto da proizvoljno biramo čvor X, možemo izabrati čvor za koji važi da podstablo svakog njegovog sina sadrzi najvise L / 2 listova (nije teško pokazati da takav čvor uvek postoji a možemo ga pronaći uz pomoć jednog DFS obilaska grafa i računanjem broja listova u svakom podstablu). Koristeći ovu osobinu čvora X, mozemo da povežemo floor((L+1)/2) parova listova tako da svaki od pomenutih puteva prolazi kroz čvor X, npr. za svako i <= L/2, možemo upariti i-ti i (i + L/2)-ti čvor (redni brojevi na osnovu DFS obilaska).

Slozenost: O(n)