Tema dana: neočekivani graf

Sanjao sam sfingu koja daje proročanstva i mogao sam postaviti jedno pitanje. Pitao sam: kada će Blogaritam ponovno biti o algoritmima? Sfinga je odgovorila: hokus pokus, bogovi su odlučili, to će biti danas!

Pa evo onda neka bude.

Znamo da se grafovi prirodno pojavljuju u mnogim zadacima, npr. kad je riječ o gradovima i cestama, poznanstvima, širenju virusa i slično. No postoji značajan broj zadataka koji se svode na graf a da to nije očito, nego se graf konstruira na netrivijalan i dosjetljiv način. Ti su zadatci često vrlo lijepi i vrijedi im posvetiti temu dana. O jednom takvom zadatku već sam pisao u postu Zadatak dana: kineski poštar.

Krenemo li od očitijeg prema manje očitom, počet ćemo od zadataka gdje treba pronaći najmanji broj nekakvih operacija da bismo nešto učinili. Shvatimo li operaciju kao prijelaz iz jednog stanja u drugo, prirodno se nameće graf čiji su vrhovi stanja, a bridovi operacije. Ovaj graf ne treba eksplicitno konstruirati, tj. pohraniti sve njegove
bridove, što možda ne bi bilo ni lako učiniti (možda ih je previše, a trebalo bi i nekako numerirati stanja). Dovoljno je pustiti npr. BFS i za pamćenje posjećenih vrhova koristiti npr. set:

U idućim zadatcima naivan BFS nije dovoljno efikasan pa je potrebna dodatna dosjetka:

I još jedan ovog tipa (preporuka Marina Kišića):

Drugu kategoriju čine zadatci gdje graf izvire iz neke tablice. O nekima od njih pisao sam u postu Tip of the day: tablica je bipartitan graf, gdje sam opisao dvije različite transformacije tablice u bipartitni graf. A malo drugačiji zadatak dao mi je Marin Kišić: Sorting a Grid.

Treću kategoriju čine zadatci gdje se konstruira graf na kojemu je rješenje neki flow. Lakši takav zadatak je A (Blokada) – Studentsko 2016., a teži je zadatak Orders (CEOI 2008.) – rješenje i testne primjere možete naći ovdje.

Naravno, najbolji su oni zadatci koji se ne mogu lako kategorizirati. Odlični zadatci s neočitim graf rješenjem pojavili su se u zadnjoj sezoni HONI-ja:

… kao i na zadnjem VRSIH-u:

Jedan teški za kraj (preporuka Patrika Pavića): Subset with zero sum. Ima ih još mnogo, slobodno dopišite u komentar.

2 misli o “Tema dana: neočekivani graf

  1. Povratni ping: Neočekivani graf u još dva zadatka sa stringovima | Blogaritam

  2. Povratni ping: Tema dana: skakanje po neboderima (ili: Ne pokušavajte ovo kod kuće) | Blogaritam

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