Neki moji načini razmišljanja dok sam radio zadatke.
Crazy LCP
Napravio sam Trie koji sadrži sve stringove, svaki čvor Trie-a ima još jednu dodatnu oznaku, koja će uskoro biti objašnjena. Upite radim offline po Mo-ovom algoritmu. Ono što je malo nezgodno je kako odrediti veličinu bloka. Naime, blok nije fiksne veličine, već blokove kreiramo greedy sleva na desno, prvi put kad ukupna dužina stringova unutar nekog bloka pređe neki zadati broj (veličina bloka, npr. 400) tada se zaustavljamo (poslednji string, tj. onaj koji je prekoračio veličinu jeste uključen u taj blok). Kada ubacujemo string u Trie dodamo +1 u čvorove koji odgovaraju prefiksima ubačenog stringa. Nas u svakom trenutku zanima koja je dubina najdubljeg čvora koji ima vrednost bar 2. Ovo radimo tako što za svaku dubinu pamtimo koliko ima čvorova na baš toj dubini u kojima je upisana vrednost barem 2. Ako označimo taj niz sa b, primetimo prvo da je taj niz nerastući pa binarnom pretragom tražimo poziciju poslednjeg broja većeg od nule. String uklanjamo tako što za sve njegove čvorove vrednost u njima smanjujemo za 1 i ažuriramo odgovarajuće nizove.
Vremenska složenost: Približno O(N \sqrt{N}), što je i na moje iznenađenje dovoljno brzo. Postoji i pametnije (a verovatno i jednostavnije) rešenje u O(N \log N)@TadijaSebez
EDIT: Ranije je pisalo da mi je vremenska složenost O(N \sqrt{N \log N}), naknadno sam uvideo da ipak može i bolje da se ograniči.
Izračunamo za svaki prefiks datog stringa skup svih pozicija gde može da se nađe nakon što izvrši taj prefiks. Za prazan string to je jednoelementni skup koji sadrži samo početnu poziciju. Za neki neprazan prefiks P, proverimo da li je neki od kodova za četiri strane sveta njegov sufiks. Npr ako je sufiks kod za N, gde je dužina koda za N jednaka l, u skup svih pozicija u koje možemo otići sa stringom P dodamo sve pozicije do kojih možemo doći pomoću prefiksa dužine |P| - l, pomerene za jedno mesto na sever. Složenost je, ako se ne varam, u najgorem slučaju O(n^3) ali ovo rešenje prolazi glatko, bez ikakvih optimizacija. Valjda je moguće napraviti primer gde sa stringom dužine n možemo otići u O(n^2) različitih pozicija.
Najteža stvar kod ovog zadatka je sama implementacija. Tu je veliki hint ime i tekst zadatka Real phobia koji bi valjda trebalo da ubedi ljude da počnu da rade geometrijske zadatke pomoću celobrojne aritmetike kad god je moguće . Sve relacije između položaja tačaka, dužina i uglova u ovom zadatku mogu da se urade pomoću kombinacija skalarnog i vektorskog proizvoda. Pri implementaciji rotating calipers metoda paziti da relativni poredak četiri tačke ostane validan nakon svakog pomeranja, tj. da se ne desi da jedna tačka “preskoči” drugu.
Moje rešenje za zadatak Crazy LCP je bazirano na modifikaciji Trie strukture podataka. U svakom čvoru pamtim dubinu i najveći index id takav da je reč koju predstavlja čvor prefiks id-te reči iz ulaza i id-ta reč iz ulaza je dodata u strukturu. Takođe pamtim niz b koji kasnije koristim za rešavanje upita. Reči dodajem u Trie po redu kojim se pojavljuju u unosu. Kada dodajem novu reč ako je čvor koji predstavlja prefiks te reči već bio posećen, postavljam vrednost b[dubina_čvora]=index_prošle_reči. Nije teško dokazati da je niz b opadajuće sortiran. Ako u Trie imamo prvih i reči onda možemo rešiti sve upite kod kojih je r jednako i. Binarnom pretragom možemo naći rešenje koristeći niz b. ako je b[x] veće ili jednako levom kraju upita onda je odgovor tog upita x ili više. Sortiranjem upita po desnom kraju mozemo rešiti zadatak offline.
Ako koristimo counting sort za sortiranje upita dobijamo kompleksnost O(S+QlogS), gde je S zbir dužina svih reči.
Moje rešenje za Rocks takođe koristi segmentno stablo, malo je jednostavnije pošto možemo da zamenimo dva elementa tako što na mesto prvog elementa dodamo razliku drugog i prvog, a na mesto drugog razliku prvog i drugog.
Ima još dosta rešenja za LCP koja sam čuo od drugih nakon takmičenja. Moje je da hešujemo svaki prefix, radimo binarnu po rešenju, za svaku dubinu napravimo minsegtree, gde čuvamo prvi desno indeks koji je isti, i onda ima dva ista ako query(L, R) <= R. Čudi me da je NsqrtN prošao, s obzirom da je moj Nlog^2N dao TLE kad sam kucao implicitno, morao sam da kompresujem.
Implementacija odrađena skoro u potpunosti sa celim brojevima, mogao sam da izbacim onaj nepotrebni cerr na jednom mestu a takođe i da bez vađenja korena sračunam konačno rešenje (pošto delim i visinu i širinu sa korenom), mada ovako kako sam ga uradio se vrlo vrlo malo gubi na preciznosti (svakako mnogo manje od 0.01)
. Sve relacije između položaja tačaka, dužina i uglova u ovom zadatku mogu da se urade pomoću kombinacija skalarnog i vektorskog proizvoda. Pri implementaciji rotating calipers metoda paziti da relativni poredak četiri tačke ostane validan nakon svakog pomeranja, tj. da se ne desi da jedna tačka “preskoči” drugu.