Problem S. 66. (November 2011)
S. 66. Weird lightning strikes occur in Lightning City day by day: a lightning always blasts into 2 houses simultaneously. Inhabitants realized that they can make use of this phenomenon and cover the electric energy demand of the city by the following construction. They connect certain houses with (lightning-proof) electrical wirings in such a way that there is exactly one path between any two houses, moreover, they install a battery into each home with (effectively) infinite capacity: when a lightning strikes the two houses, all the batteries along the path between the two affected homes are charged evenly.
At the end of the month, the mayor needs a report about the amount of energy each home obtained from the lightning strikes. Your program is to create such a report, provided that the wiring paths between the homes, further the destination and energy of each strike are known.
The first row of the standard input contains the number of homes 1
N50000, then each of the next N-1 lines contains the number of two homes (separated by a space) that are directly connected with a wire. The next line contains the number of lightning strikes 1Q50000. Then each of the following Q lines contains 3 integers (separated by a space): the destination homes Ai and Bi of the actual strike together with the additional energy 1Ci100 each battery gets during this strike between homes Ai and Bi.
The standard output should contain exactly N lines: the ith line shows the total energy collected by the ith home during the month. In the example, ``Példa bemenet'' is a sample input, while ``Példa kimenet'' is the corresponding output.
In order to obtain the maximal number of points, your program should give the solution within 3 seconds even on the largest input.
The source code (s66.pas, s66.cpp, ...) and project files -- without the .exe or any other auxiliary files generated by the compiler but together with a short documentation (s66.txt, s66.pdf, ...) -- should be submitted in a compressed folder s66.zip.
(10 pont)
Deadline expired on December 12, 2011.
Sorry, the solution is available only in Hungarian. Google translation
A bemenetben megadott házakat, és a köztük húzódó vezetékeket fölfoghatjuk egy gráfként, ahol a házak a csúcsok, a vezetékek pedig az élek. Így egy fát kapunk, mivel a feladat feltétele szerint bármely két ház között pontosan egy útvonal van.
Ez alapján rögtön adódik egy egyszerű megoldás. Először olvassuk be a gráfot, és vegyünk föl egy N hosszú tömböt, amelynek minden eleme a megfelelő sorszámú házban felhalmozódott töltésmennyiséget fogja tárolni. Ezután minden villámnál határozzuk meg a két eltalált ház közötti útvonalat valamilyen szokásos bejárással (mélységi vagy szélességi), és egyenként végigmenve az útvonal pontjain adjuk hozzá a tömb megfelelő eleméhez a villám töltését. Ennek a megoldásnak a futásideje azonban nem megfelelő a nagyobb tesztesetekhez. Q darab bejárást csinál, és egy bejárás ideje N-nel arányos, tehát az átlagos futásideje is O(NQ).
Jobb megoldást találhatunk, ha a bejárást lecseréljük olyan algoritmusra, ami kihasználja, hogy a gráfunk fa. Ha kijelöljük egy tetszőleges csúcsát gyökér csúcsnak, akkor természetesen adódnak irányok a fában: Ha egy csúcsból olyan szomszédjába lépünk, ami közelebb van a gyökérhez, akkor mondhatjuk, hogy felfelé léptünk, ellenkező esetben pedig lefelé. A gyökér csúcs kivételével minden csúcsra teljesül, hogy pontosan egy olyan szomszédja van, ami fölfelé van tőle, amit nevezhetünk az apjának. A kijelölt gyökérből indítva egy bejárást, minden csúcs apját meghatározhatjuk. (Többen is voltak, akik úgy vették, hogy a bemenetben az élek úgy vannak megadva, hogy az első végpont apja a másodiknak, pedig ezt nem kötötte ki sehol a feladat.)
Észrevehetjük, hogy bármely két csúcs közti útvonal olyan, hogy először valamennyit (esetleg egyet se) fölfelé lép, aztán valamennyit lefelé lép. Azt a csúcsot, amitől kezdve lefelé kell lépegetni, a két csúcs legalacsonyabb közös ősének (LCA - Lowest Common Ancestor) nevezzük. Ezen a ponton sokféle hasonló gyorsaságú megoldás adódik. Pl.: Lépegessünk föl a villám egyik végpontjából a gyökérig, és jelöljük meg az összes csúcsot útközben (mondjuk egy N hosszú bool tömbben állítsuk igazra a neki megfelelő elemet), és aztán a másik csúcsból is lépegessünk felfelé addig, amíg elérünk egy olyan csúcsot, amit már megjelöltünk az előbb (ez lesz az LCA). Ezután, végigjárva a két útvonalat az LCA-ig, megnöveljük a csúcsok töltéseit.
Másik lehetőség, hogy a kezdeti mélységi bejárás közben eltároljuk a csúcsok elérési és elhagyási idejét, vagyis elérjük azt, hogy bármely két csúcsról meg tudjuk mondani konstans időben, hogy melyiket értük el hamarabb, illetve melyiket hagytuk el hamarabb. Ezt az információt arra tudjuk fölhasználni, hogy megmondjuk (konstans időben) két tetszőleges x és y csúcsról, hogy az x gyökerű részfában benne van-e y. Így amikor a villám egyik végpontjából lépegetünk fölfelé, akkor azonnal észrevesszük, amikor elérjük az LCA-t, hiszen ekkor jelenik meg az aktuális csúcs részfájában a villám másik végpontja. Ennek a megoldásnak a bemutatására Nagy Róbert megoldását tesszük közzé. NagyRobert.zip
Leitereg András megoldása is hasonló, azonban ő egy másik módszert választott a legalacsonyabb közös ős megtalálására. LeiteregAndras.zip
Elemezzük ennek a megoldásnak a futási idejét! Itt lényeges különbséget tennünk a legrosszabb, és az átlagos eset között. Legrosszabb esetben az algoritmus futási ideje az első megoldásunkhoz hasonlóan O(NQ), hiszen végigjárjuk az összes villám útvonalának összes pontját, és előfordulhat, hogy a bemenet egyetlen hosszú lánc, a villámok pedig mindig két távoli házba csapnak le. Az átlagos esetben viszont az algoritmus sokkal jobb. Tegyük fel, hogy a bemenetet olyan módon generálták, hogy minden új csúcs hozzávételekor egy véletlenszerűen választott korábbi csúcsból húztak egy élet az új csúcsba. Ekkor egy csúcs átlagos mélysége log N-nel lesz arányos. Mivel tetszőleges két csúcs közötti útvonal hosszát felülről becsülhetjük a két csúcsból a gyökérig menő útvonalak hosszainak összegével, ezért a megoldás átlagos esetben O(Qlog N) lesz, ami már egészen jónak tekinthető. Ennek a megoldásnak a hatékony implementálásával 8 pontot lehetett szerezni.
Azonban ha a maximális pontszám elérésére törekszünk, akkor valahogy lejjebb kell vinnünk a legrosszabb esethez tartozó futási időt is. Először is, az LCA megtalálására többféle gyors algoritmus létezik. A beküldött megoldások közül többen a Tarjan algoritmust használták, ami le van írva pl. az Új Algoritmusok c. könyvben, de akár a Wikipedia alapján is feldolgozható. Az alábbi oldalon le van írva egy olyan (eléggé bonyolult) megoldás is, ami lineáris idejű előfeldolgozás után konstans időben képes megtalálni az LCA-t: Range Minimum Query and Lowest Common Ancestor.
Az egyik legegyszerűbb LCA algoritmus a következő: A mélységi bejárás során minden csúcshoz eltároljuk az összes, fölfelé kettőhatvány távolságra lévő csúcs sorszámát (ez legföljebb log N bejegyzés csúcsonként). Ezután már a fentebbi, Nagy Róbert megoldásában látott feltételt használva végezhetünk bináris keresést a villám egyik végpontjának szülőláncán (Használhatnánk a Leitereg András megoldásában lévő módszert is: Egy bináris kereséssel azonos szintre hozzuk őket, aztán egyszerre végezve a bináris keresesést a két csúcsból megkapjuk az LCA-t). (Vegyük észre, hogy ezzel a módszerrel tulajdonképpen láncolt listákon végeztünk bináris keresést! Ennek általában nem lenne értelme (különálló láncolt listák esetén), mivel O(Nlog N) idejű előfeldolgozásra van szükségünk. Viszont most sok láncvég közös volt, és így a kereséseink össz időigényét csökkentettük, mivel lineáris keresés esetén a közös láncvégeket újra és újra végigjárnánk, de az előfeldolgozást csúcsonként csak egyszer végezzük el.)
Azt kell még kitalálnunk, hogy hogyan tudjuk az LCA-t felhasználva a villámok hatásait ügyesen összegezni. Erre egy dinamikus programozásnak tekinthető gondolatmenet a következő: Gondoljuk meg, hogy egy tetszőleges x csúcs energiája hogyan függ a gyerekeinek az energiájától! Az x egy y gyerekéből pontosan azoknak a villámoknak az energiája fog továbbterjedni x-re, amelyeknek az LCA-ja nem az y. (Továbbá az x csúcs energiáját befolyásolják még az x-ben induló villámok is.) Tehát postorder bejárva a csúcsokat (vagyis egy mélységi bejárásban a rekurzív hívás visszatérése után végezve a számolást) meghatározhatjuk minden csúcs energiáját. Ehhez előtte kétféle értéket kell eltárolni a csúcsokban: minden ott induló villám energiájának az összegét, és minden olyan villám energiájának az összegét, aminek az LCA-ja ez a csúcs (a példamegoldásban ezek az add és a levon tömbök). Ennek a megoldásnak az implementációja a fentebbi bináris kereséses LCA algoritmussal: LCABinker.cpp
Adrián Patrik megoldását is közzétesszük. Ez az egyetlen 10 pontos megoldás, és a dokumentációja is példaértékű. AdrianPatrik.zip A lényege ugyanaz, mint a fentebbi gondolatmenetnek, de más megközelítésben tárgyalja, és az implementáció pedig a Tarjan-féle LCA algoritmusba van beleszőve, továbbá külön levon tömb helyett - ravasz módon - az LCA szülőjéből vonja le a villám töltését.
Van egy teljesen más megközelítési módja is a feladatnak. Minden csúcshoz tároljuk egy halmazban az ott végződő villámokat. Minden lépésben levágjuk egy levelét a fának, és az ott végződő villámok végeit áttesszük az egyetlen szomszédos y csúcsba. Ha egy adott villámnak volt már végződése y-ban, és most be akarjuk szúrni újra, akkor ezt a villámot törölhetjük. Ezen a megoldáson sokat gyorsít, ha figyelünk arra, hogy a két halmaz összeolvasztásakor mindig a kisebben iteráljunk végig, és a nagyobba szúrjuk be az elemeket. A halmazt implementálhatjuk pl. a C++ set-jét használva. Ez a megoldás ugyan lefut az összes tesztesetre időlimiten belül, de kb. 10-szer lassabb az LCA-s megoldásnál, és valószínűleg lehetne olyan tesztesetet találni, amire túl lassú. Olvasztos.cpp
Statistics:
16 students sent a solution. 10 points: Adrián Patrik. 9 points: Strenner Péter. 8 points: 6 students. 7 points: 1 student. 6 points: 2 students. 5 points: 3 students. 4 points: 2 students.
Problems in Information Technology of KöMaL, November 2011