Problem S. 109. (September 2016)
S. 109. Subscribers can reach the text of the problem after signing in. The text will be public from September 10, 2016.]
(10 pont)
Deadline expired on October 10, 2016.
Sorry, the solution is available only in Hungarian. Google translation
Használjuk a dinamikus programozás módszerét. Az első fa minden \(\displaystyle i\) pontjára és a második fa minden \(\displaystyle j\) pontjára tároljuk az \(\displaystyle i\)-edik pont által meghatározott részfának a \(\displaystyle j\)-edik pont által meghatározott részfává alakítás minimális költségét (dp[i][j]).
Ha az üres részfát felvesszük egy speciális pontként, akkor összesen három eset van:
1) Üres részfát üres részfává ingyen átalakíthatjuk
Ha valamelyik részfa nem üres, akkor
2) a bal részfát a bal részfává, a jobb részfát a jobb részfává alakíthatjuk, vagy
3) a jobb részfát a bal részfává a bal részfát a jobb részfává alakíthatjuk
A második és a harmadik eset függ a fában a két pont gyerekeire kiszámított értékektől. (A pontos képletek a mintamegoldásban olvashatók)
A kiszámítás sorrendjére használhatjuk a mélységi bejárás szerinti elhagyási sorrendet (mivel így a gyerekekre előbb számítódik ki az érték, mint a szülőre), vagy még egyszerűbb, ha dinamikus programozás helyett rekurzívan oldjuk meg a feladatot memorizálással. A mintamegoldás az utóbbi módon működik.
A futási idő \(\displaystyle O(n\cdot m)\), a megoldás \(\displaystyle O(n\cdot m)\) memóriát használ.
Statistics:
17 students sent a solution. 10 points: Alexy Marcell, Bálint Martin, Busa 423 Máté, Csenger Géza, Gáspár Attila, Gergely Patrik, Horváth 546 János, Janzer Orsolya Lili, Kovács 246 Benedek, Nagy Ábel, Németh 123 Balázs, Noszály Áron, Olexó Gergely, Szakali Benedek. 6 points: 1 student. 3 points: 1 student. 1 point: 1 student.
Problems in Information Technology of KöMaL, September 2016