Problem S. 155. (October 2021)

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

(10 pont)

Deadline expired on November 15, 2021.

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

Egy \(\displaystyle (i,j)\) pár akkor jó megoldás, ha a köztük lévő élek behúzásával körmentes gráfot kapunk.

Minden \(\displaystyle i\) számra meg kell határoznunk a legnagyobb \(\displaystyle j\) értéket, melyre a feltétel teljesül. A megoldás ezen intervallumok hosszának összege lesz.

Egy pár leellenőrzése megtehető bejárással vagy unió-holvan adatszerkezettel.

A teljes pontszámot több módszerrel is el lehet érni. Ilyen például a gyökös felbontás, mely sok hasonló problémát fel tud gyorsítani. (A 10 000-es felső korlát gyakori árulkodó jel ilyen feladatoknál.)

Megjegyezzük, hogy a feladat megoldására kész adatszerkezet is létezik, mely sok helyen elérhető online is. (link: Link/cut tree) Ennek implementálása nem volt elvárt!

Statistics:

6 students sent a solution.
5 points:	4 students.
4 points:	1 student.
Not shown because of missing birth date or parental permission:	1 solutions.

Problems in Information Technology of KöMaL, October 2021