Analiza problema

Jasno da svaki listić možemo posmatrati kao ~K~-točlani podskup skupa ~\{1, 2, 3, ...., M\}~, te tako imamo ukupno ~N~ podskupova sa po ~K~ elemenata (~K~-točlanih). Označimo te podskupove sa ~S_1, S_2, ..., S_N~. Za svako pojedinačno izvlačenje i svaki broj ~j~ između 1 i ~K~ potrebno je odrediti koliko ima skupova u nizu ~S_1, S_2, ..., S_N~ koji sadrže kao poskup skup sastavljen od prvih ~j~ brojeva izvučenih u tom izvlačenju.

Naivna varijanta se sastoji baš od brojanja koliko ima listića (tj. skupova) kojima je skup sastavljen od prvih ~j~ izvučenih brojeva podskup (tj. koliko ima skupova-listića koji sadrže svih ~j~ prvih izvučenih brojeva). Zavisno od implementacije, složenost ovog rešenja može biti ~O(QNK)~ ili ~O(QNK^2)~.

Svaka od naprednijih varijanti podrazumeva preprocesiranje listića tako da se za svako ~j\in \{1, 2, ..., K\}~ formiraju svi podskupovi sa tačno ~j~ od ~K~ izvučenih brojeva. Zatim se podskupovi iste kardinalnosti (sa istim brojem elemenata) smeštaju u kolekciju koja će omogućiti efikasno određivanje koliko se puta neki podskup (sa istim brojem elemenata) pojavljuje u datoj kolekciji. Primetimo da je broj podskupova sa ~j~ elemenata skupa koji ima ~K~ elemenata jednak ~\binom{K}{j}~. Tako će ukupan broj poskupova sa ~j~ elemenata skupova ~S_1, S_2, ..., S_N~ biti ~N\times\binom{K}{j}~. Ukupan broj svih podskupova (za sve vrednosti ~j~) će biti ~N\times (2^K-1)~.

U podzadatku dva su elementi skupova (tj. izvučeni brojevi) brojevi manji od 100. Podskupovi koje izdvajamo imaju najviše 3 elementa i elementi svakog podskupa se mogu sortirati, a zatim posmatrati kao cifre nekog broja u sistemu sa osnovom 100 (budući da su elementi manji od 100). Tako će svaki podskup biti predstavljen kao najviše trocifren broj u sistemu sa osnovom 100, odnosno svaki skup može biti predstavljen pomoću broja koji je manji od milion. Zahvaljujući tome mogu se izbrojati pojavljivanja svakog podskupa i zapamititi u nizu dužine 1000000 (tj. sa milion elemenata).

U podzadatku tri se skupovi opet mogu predstaviti pomoću brojeva u sistemu sa osnovom 100 ali kako u podzadatku 3 broj ~K~ može imati vrednost 5, to će biti najviše potocifreni brojevi i njihova vrednost je ograničena sa 10 milijardi. Ovaj put ne možemo primeniti obično brojanje, već formiramo nizove sa brojevima koji predstavljaju skupove. Nizove možemo sortirati i na kraju jednim prolazom izbrojati broj pojavljivanja svake vrednosti (tj. svakog podskupa). Pri odgovaranju na upite podskup koji se sastoji od ~j~ prvih izvučenih brojeva predstavimo kao broj (na isti način kao i podskupove oformljene od listića) i binarnom pretragom pronalazimo u nizu brojeva koji predstavljaju podskupove listića.

U podzadatku četiri maksimalni broj izvučenih brojeva, kao i maksimalna vrednost izvučenih brojeva su takvi da se podskupovi sa više elemenata ne mogu reprezentovati pomoću celobrojnih tipova podržanih u jezicima koji se koriste za takmičenje. Zbog toga je potrebno podskupove predstaviti na neki drugi način. Jedan od načina je struktura koja sadrži broj elemenata u podskupu i elemente podskupa smeštene u niz koji je sortiran. Nad tako reprezentovanim podskupovima možemo definisati poređenje (uobičajeno leksikografsko poređenje). Koristeći to poređenje možemo sorirati nizove koji sadrže sve podskupove sa istim brojem elemenata. Nakon toga brojanje koliko puta se neki podskup ~P~ pojavljuje u nizu obavljamo varijacijom binarne pretrage u kojoj prvo određujemo deo niza sa podskupovima u kome se prvi element poklapa sa prvim elementom podskupa ~P~, zatim u tako izdvojenom podnizu (određen je početnim i krajnjim elementom podniza) deo u kome se drugi element poklapa sa drugim elementom podskupa ~P~, itd. Postupak prekidamo kada iscrpimo sve elemente podskupa ~P~, nakon čega je broj podskupova jednak dužini izdvojenog podniza, ili kada podniz u kome se elementi mogu poklapati sa podskupom ~P~ postane prazan (tada je odgovor nula).

Poslednji podzadatak može biti rešen i tako što se podskupovi smeštaju u heš tabelu, pri čemu u toku dodavanja istovremeno brojimo koliko se puta pojavljuju podskupovi. Nakon toga odgovaranje na upite se svodi na pronalaženje odgovarajućih skupova u heš tabeli i izdvajanju informacije koliko puta se taj podskup nalazi u heš tabeli.

Pokazalo se da maksimum poena može biti osvojen i tako što se svakim izvučenim brojem u jednom konkretnom izvlačenju izdvoje samo listići koji sadrže sve do tog trenutka izvučene brojeve. Broj izdvojenih listića je odgovor za konkretno izvlačenje i konkretan broj izvučenih brojeva. Kada se nakon toga obrađuje sledeći izvučeni broj, analiziraju se samo listići koji su izdvojeni i od njih izdvajaju samo oni koji sadrže izvučeni broj. Uz pažljivu implementaciju dobija se rešenje koje se izvršava u predviđenom vremenu.

Algoritamske smernice

Written with StackEdit.

Written with StackEdit.