Problem S. 150. (February 2021)

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

(10 pont)

Deadline expired on March 16, 2021.

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

Azonosítsuk a játék állapotait (gráf csúcsait) a legkisebb koordinátájú mezővel , amit a téglatest lefed (bal felső), illetve a téglatest orientációjával. Ez felülről nézve lehet álló, vízszintesen fekvő vagy függőlegesen fekvő. Vegyük észre, hogy ha a egy \(\displaystyle A\) állapotból eljuthatunk egy \(\displaystyle B\) állapotba, akkor \(\displaystyle B\)-ből is eljuthatunk \(\displaystyle A\)-ba, azaz a gráf irányítatlan. Ennek az a következménye, hogy bármely két, egy komponensbe tartozó csúcs elérhető egymásból.

Így a kérdések megválaszolásához csak azt kell megmondanunk, egy komponensbe tartoznak-e. A komponenseket irányítatlan gráfnál mélységi bejárással meghatározhatjuk. A bejárás során minden csúcsot felcímkézünk a komponens sorszámával, majd a kérdések megválaszolásakor ezt \(\displaystyle O(1)\) alatt lekérdezzük.

Komplexitás: \(\displaystyle O(3*N*M)\) a bejárásokra és \(\displaystyle O(Q)\) a kérdésekre. Összesen: \(\displaystyle O(N*M+Q)\)

Statistics:

7 students sent a solution.
10 points:	Horcsin Bálint, Kovács Alex, Sándor Péter, Varga 256 Péter.
5 points:	2 students.
0 point:	1 student.

Problems in Information Technology of KöMaL, February 2021