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.

2 misli o “Kružni intervali

  1. Vjerujem da je službeno rješenje TurboExcela pogrešno, možda se zato ne čini teškim

    Tvrdi se da je nemoguće da je optimalno imati Upper(Concat(…)), no zapravo je vrlo moguće da je to optimalno

    Liked by 2 people

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