Kružni intervali

[Osvrt na ovosezonske zadatke – 4. dio]

O većini zadataka s proteklog Državnog natjecanja 2018. nemam mnogo zanimljivog za napisati. Neke poluanegdote koje bih mogao spomenuti uključuju:

  • Graf iz najlakšeg zadatka Trek izravno je preuzet sa slike iz zadatka Jezero s DMIH-a 2008.
  • Zadatak Infokuhar predložio sam još 2015. godine kad se natjecanje zvalo Infokup, kao jedan od najtežih zadataka za osnovne škole. Zbog određenih manjkavosti (“previše matematički”) zadatak je tri godine bio rezerva sve dok ga ove godine nisam napokon (i sa zadovoljstvom) zadao.
  • Predikcija iz teksta zadatka Ikebana, ona o Paoli koja se priprema za IOI 2018. u Japanu, skoro je bila istinita (fulali smo jedno slovo).
  • Zadatak TurboExcel uopće nije toliko težak.

No, zadatak koji sam zapravo htio komentirati je Pjege (1. i 2. razred, 2. dan natjecanja). On je u potpunosti nastao večer prije samog natjecanja, nakon što smo odustali od jednog zadatka koji je trebao biti na njegovom mjestu. Tada smo odlučili da je, iako smo bili jako umorni, svakako mudrije odmah smisliti i pripremiti novi zadatak, nego to učiniti sljedeći dan (prije 14 sati kada je počinjalo natjecanje).

Iskoristili smo ideju iz zadatka Kugloboćanje koji je bio pripremljen za isto natjecanje za 3. i 4. razred. Kao dio rješenja tog zadatka trebalo je pronaći minimalan broj polupravaca iz ishodišta tako da svaki od zadanih kutnih intervala bude pogođen barem jednim polupravcem. Budući da u zadatku promatramo samo I. i II. kvadrant koordinatnog sustava, to se svodi na 1D problem gdje treba pronaći minimalan broj točaka tako da svaki od zadanih intervala sadrži barem jednu točku.

Rješenje je relativno jednostavno: uvijek se isplati kao točku odabrati prvi završetak intervala (dokažite!); točnije, interval koji prvi završava a da nije “riješen” prethodnom točkom. Problem nastaje ako intervali u uniji pokrivaju cijeli krug: tada problem postaje kružni i više ne znamo odakle početi. U zadatku Kugloboćanje to se nije moglo dogoditi, no tu mogućnost dopustili smo u novom zadatku Pjege koji je dobio drugačije “pakovanje”, prebačen je iz geometrije u drugu domenu i na prvi pogled nema mnogo sličnosti sa zadatkom Kugloboćanje.

No što je rješenje? Jedna je mogućnost provesti isti greedy postupak za svaki mogući odabir granice od koje ćemo redom promatrati intervale, pamteći onaj postupak koji je dao najbolje rješenje. To rješenje ima kvadratnu složenost i zato smo stavili manje ograničenje (N ≤ 1000). Dokaz točnosti temelji se na činjenici da optimalni odabir točaka sigurno sadrži takvu “granicu”, jednu za svaku od odabranih točaka.

Razmišljali smo, naravno, o rješenju koje bi bilo linearno (točnije loglinearno) kao i u zadatku Kugloboćanje. Neke ideje su sljedeće.

  • Heuristika koja na slučajan način bira 5, 10 ili 30 početaka i provodi spomenuti greedy postupak, pamteći najbolji rezultat. Tek sada, nakon dosta razmišljanja, mislim da znam kojim primjerom ju je moguće srušiti.
  • Kretanje od jednog, bilo kojeg početka i biranje točaka na spomenuti način. Nakon što napravimo dva puna kruga, dobili smo niz točaka koji je redundantan jer smo većinu intervala pokrili dvaput. U tom nizu odabiremo minimalni uzastopni podniz točaka koji pokriva više od punog kruga, te iz njega izbacujemo jednu točku. Ne znam je li točno.
  • Biranje točke koja upada u najveći broj još neriješenih intervala. Ne znam je li točno, a i ne znam može li se ostvariti u sub-kvadratnoj složenosti.

Iz ovoga je jasno zašto smo se odlučili za popustljivo ograničenje N ≤ 1000. Ograničenje N ≤ 100 000 imalo bi smisla samo kada bismo a) imali dokazano rješenje, b) znali koja su rješenja pogrešna i kako ih srušiti. No mene i dalje zanima može li netko dokazati ili kontraprimjerom opovrgnuti neko od gore navedenih rješenja.

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.