Tema dana: riješi offline

U zadatcima u kojima trebamo odgovarati na nekakve upite (queries) ponekad je moguće na svaki upit efikasno odgovoriti čim se on pojavi, pa kažemo da ga rješavamo online. Ponekad to nije moguće, nego zadatak rješavamo tako da najprije učitamo sve upite, sortiramo ih na odgovarajući način i odgovore na njih računamo u redoslijedu koji nama odgovara (offline), da bismo tek na kraju ispisali te odgovore redom kojim smo dobili upite.

Na primjer, pokušajte riješiti zadatak K-query (prije nego što pročitate rješenje odmah ispod).

Upit se ovdje sastoji od triju brojeva: granice intervala i veličina broja. Već imamo “hint” da treba rješavati offline, tj. da treba naći redoslijed u kojemu možemo efikasno odgovarati na upite. Kako ih sortirati: po lijevoj granici intervala, po desnoj, ili možda po veličini broja? Ako još ne znate rješenje, razmislite o svakoj od ovih mogućnosti.

U ovom slučaju valja odgovarati na upite redom od najmanjeg do najvećeg k. Jer kad je k = 0, upit je trivijalan (cijeli interval zadovoljava uvjet), a ako je sljedeći npr. k = 5, znamo da brojeve manje od 5 treba zanemariti i to zauvijek (jer će u idućim upitima k biti samo još veći). Trebamo dakle efikasno podržati operaciju “ubijanja” elementa iz niza te upit oblika “koliko je živih elemenata u intervalu”. Ako živi element gledamo kao jedinicu, a ubijeni kao nulu, upit se svodi na običnu sumu intervala, uz ažuriranje pojedinih elementa (1 → 0) i to možemo riješiti najjednostavnijim tournamentom ili logaritamskom strukturom. Naravno, na početku i elemente niza valja sortirati da bismo znali kada kojega (i na kojem indeksu) “ubijamo”.

Još nekoliko zadataka, redom po težini:

(Ako se dobro sjećam, službeno rješenje za Nou nije offline, ali Pavić i Lendvaj su ga tako riješili i ispalo je jednostavnije, oni će bolje znati. O zadatcima Menza i Ghost Leg neke natuknice pisao sam ovdje.)

Na ovu temu ima hrpetina zadataka, ali moje je pamćenje (a i forma) na godišnjem pa ih slobodno dopišite u komentare.

Komentiraj

Popunite niže tražene podatke ili kliknite na neku od ikona za prijavu:

WordPress.com Logo

Ovaj komentar pišete koristeći vaš WordPress.com račun. Odjava /  Izmijeni )

Google photo

Ovaj komentar pišete koristeći vaš Google račun. Odjava /  Izmijeni )

Twitter picture

Ovaj komentar pišete koristeći vaš Twitter račun. Odjava /  Izmijeni )

Facebook slika

Ovaj komentar pišete koristeći vaš Facebook račun. Odjava /  Izmijeni )

Spajanje na %s