K-tačne sekvence zagrada

Autor: Nikola Pešić Tekst i test primeri: Nikola Pešić Analiza rešenja: Nikola Pešić Tester: Ivan Stošić

Analiza

Ideja za dinamičko programiranje

Za rešavanje problema koristićemo dinamičko programiranje. Neka ~dp[i][v][k]~ prstavlja ~dp~ stanje gde ~i~ označava broj zagrada koje još moramo da postavimo, ~v~ označava trenutnu prefiksnu sumu postavljenih zagrada (ako uzmemo da je ( jednako 1 a ) jednako -1) i ~k~ predstavlja broj zagrada koje možemo još da obrišemo. Za prelaze imamo 2 opcije: Postavi ( kao sledeću zagradu ili postavi ) kao sledeću zagradu. Ako postavljamo (, iz stanja ~dp[i][v][k]~ ćemo preći u stanje ~dp[i-1][v+1][k]~. Ako postavljamo ) imamo 2 opcije:

• ~v=0~, iz stanja ~dp[i][0][k]~ ćemo preći u stanje ~dp[i-1][0][k-1]~.
• ~v>0~, iz stanja ~dp[i][v][k]~ ćemo preći u stanje ~dp[i-1][v-1][k]~.

Na početku treba da inicijalizujemo ~dp[0][v][k]~ na ~1~ ako je ~v<=k~, a na ~0~ u ostalim slučajevima. Takođe treba paziti na ~overflow~, vrednosti u ~dp~-u veoma brzo mogu da premaše ~long~long\(, tako da je potrebno ograničiti ih da ne mogu da budu veće od \)2^{61}\( ili neke slične vrednosti. \)2^{61}~ je dobra vrednost jer ~2\cdot 2^{61}~ idalje staje u ~long~long~, dok je ~2^{61}~ veće od najveće moguće vrednosti za ~t~. Uz pomoć ovog ~dp~-a, možemo da odgovorimo na upite. Za upit ~n,k,t~ ćemo krenuti od stanja ~dp[n][0][k]~ i nakon toga ćemo raditi sledeće dok ~n~ ne postane ~0~ :

• Ako je ~dp[n-1][v+1][k]\geq t~, preći ćemo u to stanje i na odgovor dodati (.
• U suprotnom ćemo od ~t~ oduzeti ~dp[n-1][v+1][k]~, na odgovor dodati ) i preći u stanje ~dp[i-1][0][k-1]~ ako je ~v=0~ ili ~dp[i-1][v-1][k]~ ako je ~v>0~.

Sa ovim rešenjem se moglo dobiti ~40~ bodova, dok se sa malo modifikovanim rešenjem (za slučaj kada je ~k=0~), moglo dobiti još ~10~ bodova. Glavni problem ovog rešenja je memorija, tako da ćemo se u sledećem delu fokusirati na smanjenje memorije. Biće opisana 3 rešenja, u redosledu od najlakšeg do najtežeg za implementaciju. Prvo rešenje je alternativno rešenje za problem, drugo koristi ideju koju je Tadija Šebez koristio da reši problem, i treće je zamišljeno rešenje.

U sva 3 rešenja se koristi klasična memorijska optimizacija gde se čuvaju samo poslednja 2 reda. Ovo je poprilično lako uraditi kada se računa u redosledu rastućih dužina, međutim, za odgovaranje na upite nama trebaju vrednosti u redosledu opadajućih dužina.

Rešenje 1

Ovo rešenje koristi činjenicu da u našem ~dp~-u ima malo vrednosti koje nisu ~0~, a manje su od ~2^{61}~. Štaviše, ima tačno ~2,358,736~ takvih vrednosti. Postoje 2 slučaja kada je ~dp[i][v][k]=0~:

• ~i+k-v<0~
• ~k=0~ i ~i\not\equiv v\ (\textrm{mod}\ 2)~

Treba nam još dobar način da sačuvamo ove vrednosti. Možemo da napravimo matricu gde za sve vrednosti ~i~ i ~v~ čuvamo sve vrednosti ~k~ (listu vrednosti) i vrednosti odgovarajućeg ~dp~ stanja. Međutim, kako vrednosti ~i~ i ~v~ mogu biti do ~1000~, ova matrica će koristiti previše memorije. Da bi smanjili memoriju, možemo da primetimo da za neku vrednosti parametra ~i~, vrednost parametra ~v~ će biti u intervalu ~[i-k,i+k]~ za sva polja čija je vrednost u traženom intervalu. Time možemo da smanjimo matricu na dimenzije ~1000\times 200~. Što se tiče, pronalaženja odgovarajuće vrednosti za ~k~ iz liste, dovoljno je samo da prođemo kroz celu listu ako nam treba neka vrednost iz nje. Ovo je moguće uraditi i u ~O(\log{k})~ ali nema potrebe kako složenost programa ostaje ista. Složenost: Vreme: ~O(n^2\cdot k)~, Memorija: ~O(~Broj polja čija je vrednost u intervalu ~(0,2^{61})~ ~)~.

Rešenje 2

U ovom i sledećem rešenju rešavaćemo upite oflajn, tj. rešićemo ih sve jednim prolazom kroz ~dp~ tabelu u redosledu opadajućih dužina. Za ovo rešenje definisaćemo konstantu ~S~ i u odvojenu tabelu ćemo zapamtiti svaki ~S~-ti red, tj. ~dp[0][v][k]~, ~dp[S][v][k]~, ~dp[2\cdot S][v][k]~,... Nakon toga, prolazimo kroz sve dužine u opadajućem redosledu, i za svaku dužinu ~i~ ćemo da dobijemo red koji koji nam treba, tj. ~dp[i][v][k]~ tako što ćemo krenuti od najbližeg zapamćenog reda, u ovom slučaju to je ~dp[\lfloor\frac{i}{S}\rfloor\cdot S][v][k]~, i pomeriti se ~i-\lfloor\frac{i}{S}\rfloor\cdot S~ koraka do ~i~-tog reda. Odabir konstante ~S=20~ je dovoljno velik da rešenje prođe memorijsko ograničenje, a dovoljno mali da prođe vremensko ograničenje. Složenost: Vreme: ~O(n^2\cdot k\cdot S)~, Memorija: ~O(\frac{n^2}{S}\cdot k)~.

Rešenje 3

Ovo rešenje se svodi na memorijsku optimizaciju prve dimenzije ~dp~ tabele. Ako znamo sve vrednosti za dužinu ~i+1~ i prva 2 reda za trenutnu dužinu tj. ~dp[i][0][k]~ i ~dp[i][1][k]~, možemo da izračunamo sve vrednosti za dužinu ~i~. Ovo je moguće uraditi tako što konstruišemo graf svih prelaza i ako znamo neku vrednost u redu ~i~, oduzećemo tu vrednost od svih stanja (iz reda ~i+1~) sa kojima je to stanje povezano, a ako imamo neko stanje u redu ~i+1~ koje je povezano sa tačno jednim stanjem (iz reda ~i~) za koje ne znamo vrednost, možemo da zaključimo koja je vrednost tog stanja. Kako bi ovo radilo, moramo da računamo vrednosti po modulu, moduo ~2^{61}~ radi iz istih razloga kao u rešenju 1. Sad nam još treba način da kažemo da li je vrednost u nekom polju zapravo veća od modula ili ne. Za ovo ćemo definisati vrednost ~p=i+k-v~, polje ~kada[p][k]~ će nam čuvati najmanje ~i~ za koje je neko stanje ~dp[i][v][k]~ čija je vrednost parametra ~p~ odgovarajuća, postalo veće od modula. Primetimo da kad jednom postane veće od modula za neko ~i~, vrednost za svako veće ~i~ i istom vrednošću parametra ~p~ će takođe biti veća od modula. Ovo je sve što nam treba da rešimo problem, rešavaćemo uptite oflajn, prvo izračunamo vrednosti u predosledu rastućih dužina, popunimo tabelu ~kada~ i sačuvamo ~dp~ vrednosti za ~v=0~ i ~v=1~, i odgovorimo na upite za koje je rešenje "Ne postoji". Nakon toga ćemo da izračunamo vrednosti u redosledu opadajućih dužina i odgovorimo na ostale upite. Složenost: Vreme: ~O(n^2\cdot k)~, Memorija: ~O(n\cdot k)~.