Problem S. 113. (January 2017)

S. 113. Subscribers can reach the text of the problem after signing in. The text will be public from January 28, 2017.]

(10 pont)

Deadline expired on February 10, 2017.

Sorry, the solution is available only in Hungarian. Google translation

Megállapíthatjuk, hogy ha egy túra kezdő- és végpontja közt megtalálható az összes állat, akkor az összes olyan túra is jó, aminek a kezdőpontja ugyanaz, a végpontja pedig nagyobb. Azaz keressük meg az első elemtől induló túrához az első, feltételeknek megfelelő végpontot. Ha a kezdőpont helyét növeljük, akkor az első lehetséges végpont helye biztosan nem csökken, hiszen

-ha a kezdet növelésével a talált túra során van még ugyanolyan állat, akkor marad a végpont,

-ha nincs, akkor csak továbblépegetve találhatjuk meg az elejéről kieső állatot. Ha elérjük az állatkert végét, akkor nincs több megoldás.

Minden állatfajról tároljuk el, hogy milyen indexű helyeken fordul elő (\(\displaystyle VECTOR\)). Minden állatfajtánál az első indexet a fajtával együtt tegyük be egy \(\displaystyle SET\)-be, ami hely szerint rendez. Ekkor a túrák száma (\(\displaystyle N-az~utolsó~előforduló~index+1\)). Majd vegyük ki a \(\displaystyle SET\) első elemét és az így kieső állatfajt a következő előfordulási helyével tegyük vissza. Az eljárás akkor ér véget, ha a kivett állatfajnak már nincs további előfordulása.

Az algoritmus futásideje \(\displaystyle O(N*log(N))\).

Statistics:

16 students sent a solution.
10 points:	Busa 423 Máté, Csenger Géza, Csertán András, Dóczi András, Gáspár Attila, Horváth Botond István, Janzer Orsolya Lili, Kiss Gergely, Molnár Bálint, Nagy Nándor, Németh 123 Balázs, Szakály Marcell, Vári-Kakas Andor.
8 points:	1 student.
7 points:	1 student.
2 points:	1 student.

Problems in Information Technology of KöMaL, January 2017