Problem S. 152. (April 2021)

S. 152. Subscribers can reach the text of the problem after signing in. The text will be public from April 28, 2021.]

(10 pont)

Deadline expired on May 17, 2021.

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

A feladat a tournament fából nyert inspirációt, így a leghatékonyabb megoldások ezt az adatszerkezetet használták. Megjegyezzük, hogy a feladat megoldható hagyományos szegmensfával is. A csúcsokba érdemes eltárolni a győztest és egyéb adatokat, amik a megoldás során kellhetnek. (A nyertes aznapi rajtszáma stb.) Ha a levelekbe a versenyzőket írjuk, a fát felépítve a gyökérbe a győztes kerül. Ezután a fában a győztes meccsein visszalépkedve kioszthatjuk az aznapi pontokat és felvesszük, ki helyére kell új versenyzőt hívni. Ezután a megfelelő versenyzők helyére újakat teszünk és jön a következő versenynap. Figyeljünk, hogy csak azokat a csúcsokat számoljuk újra, amik alatt változás történt.

Így az amortizált futási idő nem lesz túl nagy, hiszen minden versenyző kivételekor legfeljebb \(\displaystyle log(N)\le 16\) lépést teszünk lefelé és minden csere után legfeljebb ugyan ennyi csúcsot kell újraszámolni.

Komplexitás: \(\displaystyle O(N*log(N))\)

Statistics:

5 students sent a solution.
10 points:	Horcsin Bálint, Varga 256 Péter.
5 points:	2 students.
4 points:	1 student.

Problems in Information Technology of KöMaL, April 2021