Put među permutacijama

[Osvrt na ovosezonske zadatke – 1. dio]

Na Školskom natjecanju 2018. postavljena su dva zadatka vrijedna spomena, zadatak Dwight u P1 (1. i 2. razred) i zadatak Trans u P2 (3. i 4. razred). Oba zadatka su na istu temu: jednu zadanu permutaciju brojeva {1, 2, …, N} treba pretvoriti u drugu zadanu permutaciju koristeći minimalan broj dozvoljenih transformacija. Zanimljivo je što je zadatak za P1 u suštini bio teži od zadatka za P2.

U zadatku Dwight, dozvoljena transformacija bila je odabrati neki element permutacije, sve manje elemente povećati za 1, a odabrani element postaviti na 1. Veličina permutacija bila je N ≤ 10.

U zadatku Trans, dozvoljena transformacija bila je odabrati neki K iz skupa {2, 3, …, N, N+1} i potom svaki element permutacije manji od K promijeniti (istodobno) iz X u K – X. Veličina permutacija bila je N ≤ 8.

Prije komentara o rješenjima ovih zadataka, ubacimo “u igru” još dva zadatka istog tipa, koja se razlikuju samo po vrsti dozvoljenih transformacija:

U zadatku Knjige s natjecanja HONI 2010. dozvoljena transformacija bila je premještanje nekog elementa na početak permutacije. Veličina permutacije bila je N ≤ 300 000.

U zadatku Posloži s natjecanja HONI 2009.  bio je zadan skup dozvoljenih transformacija oblika “zamijeni elemente na pozicijama p1 i p2”, a veličina permutacije bila je N ≤ 12.

U ovom trenutku bilo bi poželjno da pauzirate čitanje i razmislite kako biste riješili ove zadatke (ako još niste) te ih po mogućnosti skodirate. Zadatke s honija možete testirati ovdje i ovdje.

A sada nekoliko zamjedbi. (Htio sam napisati opservacija, ali volio bih da riječ “zamjedba” uđe u širu uporabu.)

Zadatci Dwight i Knjige u suštini su isti. Zašto? U Knjigama premještamo element na poziciju 1, a elementima koji su bili ispred njega povećavamo poziciju za 1. U Dwightu radimo isto, ali ne s pozicijama nego s vrijednostima elemenata. Međutim, lako je promijeniti perspektivu iz pozicija u vrijednosti i obrnuto. Konkretno, napravimo novu permutaciju u kojoj je X-ta vrijednost jednaka poziciji broja X u originalnoj permutaciji (npr. [2, 4, 1, 3] <—> [3, 1, 4, 2]). Čitateljima ostavljam da zaključe koja je perspektiva u ovom zadatku bolja, tj. koji je zadatak “lakši”.

Kako god okrenemo, te zadatke moguće je riješiti u O(N), što se iz ograničenja za Knjige (N ≤ 300 000) moglo i naslutiti. Zadatak Dwight nastao je “drugačijim pakovanjem” zadatka Knjige i besramnim spuštanjem ograničenja na N ≤ 10. Je li to spuštanje pomoglo ili odmoglo, teško je reći. S jedne strane je teže skužiti da postoji linearno rješenje. S druge strane, cilj je bio da brutfors rješenje (BFS po prostoru permutacija) dobije velik broj bodova. On je prolazio na 9/10 primjera.

To nas dovodi do zadatka Trans koji je lakši jer zbog malog ograničenja (N ≤ 8) dopušta upravo takvo rješenje velike složenosti, BFS po grafu čiji su vrhovi permutacije a bridovi transformacije. Zadatak je stavljen u P2 jer takvo rješenje ipak traži više znanja od rješenja Dwighta koje može smisliti i netko tko ne zna ništa o grafovima. (Kad smo već kod zadatka Trans, u službenom Python rješenju koristio sam strukturu queue.Queue koja služi za višedretveno programiranje i za ovu je namjenu (BFS) vrlo neefikasna. Umjesto toga preporučujem uporabu collections.deque.)

Broj pretraženih permutacija u rješenju za Trans iznosi O(ND) gdje je D rješenje. Koliki je najveći mogući D s obzirom na N? Za N = 8 on iznosi 9, tj. najudaljenije dvije permutacije (dijametar grafa) udaljene su za 9 transformacija. A općenito? Nitko ne zna! Naime, ako u zadatku Trans napravimo gore opisanu promjenu perspektive iz vrijednosti u pozicije, dobivamo poznati Palačinkin problem na koji mi je jednom ukazao Patrik Pavić i tako inspirirao ovaj brut-zadatak. Formula za N-ti palačinkin broj je otvoreni problem i još nitko nije izračunao ni dvadeseti. Evo vam prilike da se upišete u povijest matematike.

Je li moguće ubrzati eksponencijalna rješenja u zadatcima Dwight i Posloži tako da dobiju sve bodove, tj. tako da rade za N = 10 u Dwightu odnosno N = 12 u Posloži? Moguće je! U zadatku Posloži to je bila i poanta, koristiti neku od naprednijih metoda pretraživanja grafa: dvosmjerni BFS (istodobno se širimo iz početnog i odredišnog stanja) čime se eksponent smanjuje na D/2, ili algoritam A*. Rješenja svih navedenih zadataka možete pronaći ovdje ili ovdje.

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