Tip of the day: disjunktne maske

Pretpostavimo da radimo dinamiku gdje je stanje bitmaska – koje smo elemente već iskoristili, a u prijelazu biramo neki podskup neiskorištenih elemenata.

Na prvi pogled složenost je 2N * 2N = 4N, ali ne i ako prijelaz pišemo ovako:

for (int nova = ~mask; nova > 0; nova = (nova - 1) & ~mask) { ... }

To će iterirati po svim podskupovima koji su disjunktni s mask. Može se iterirati i u rastućem poretku:

for (int nova = 0; nova < (1 << N); nova = (nova + mask + 1) & ~mask) { ... }

Ako ovdje ne želimo nulu, treba početi od nova = (mask + 1) & ~mask. Probajte na papiru razumjeti ove petlje i zašto funkcioniraju, inače ih vjerojatno nećete zapamtiti.

Ukupna je složenost O(3N). Ako ne vjerujete, zavrtite ovo:

int cnt = 0;
for (int mask = 0; mask < (1 << N); mask++)
  for (int nova = 0; nova < (1 << N); nova = (nova + mask + 1) & ~mask)
    ++cnt;

…i možete se uvjeriti da će cnt biti točno 3N. Dokaz slobodno ostavite u komentarima.

Primjer zadatka: Z-most.

Tu, međutim, nije kraj optimizaciji — još efikasniji pristup, složenosti O(N * 2N), i mnogo zadataka (uključujući jedan s HONI/COCI) možete pronaći ovdje. Hvala Patriku Paviću na ovim linkovima.

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