 |
Az S. 66. feladat (2011. november) |
S. 66. Villámváros különös természeti adottságokkal rendelkezik. Nap mint nap rengeteg furcsa villám csap le házaira: egy-egy ilyen villám egyszerre mindig két házat talál el. Az idők során a lakók rájöttek, hogy ha bizonyos házakat villámvezetékkel kötnek össze úgy, hogy bármely két ház között a vezetékek mentén haladva pontosan egy útvonal legyen, illetve minden házba egy (gyakorlatilag végtelen kapacitású) akkumulátort szerelnek, a villámokkal biztosítani tudják a város elektromosenergia-ellátását. Amikor ugyanis a rendszerbe egy villám csap, a két eltalált ház közötti villámvezeték-útvonalon minden akkumulátor egyenlő mértékben feltöltődik.
A polgármester szeretne egy jelentést kapni a hónap végén arról, hogy melyik ház mennyi energiát nyert a villámokból. Írjunk programot, amely a házak közötti összeköttetések, illetve a villámok célpontjai és energiái ismeretében elkészíti ezt a jelentést.
A standard bemenet első sorában a házak száma szerepel, a következő N-1 darab sorban pedig rendre két olyan ház sorszáma (egy-egy szóközzel elválasztva), amelyek között közvetlen villámvezetékes összeköttetés van. A következő sorban a megfigyelt villámok
száma található. Az ezt követő Q darab sor mindegyike három, szóközzel elválasztott egész számot tartalmaz: a villám Ai és Bi célpontjait, illetve az egyes házakra jutó 1
Ci100 energiáját (azaz az Ai és Bi házakat összekötő villámúton minden akkumulátor Ci többletenergiát kap).
A standard kimenetre pontosan N darab sor kerüljön: az i. sorba az i. ház által összegyűjtött energia.
A maximális pontszám eléréséhez a programnak a legnagyobb méretű bemeneten is legfeljebb 3 másodperc alatt le kell futnia.
Beküldendő a feladat megoldását tartalmazó forrás (s66.pas, s66.cpp, ...) és projektállományok (az .exe és más, a fordító által generált kiegészítő állományok nélkül), valamint a megoldás menetét röviden bemutató dokumentáció (s66.txt, s66.pdf, ...) egy tömörített s66.zip mappában.
(10 pont)
A beküldési határidő 2011. december 12-én LEJÁRT.
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
Statisztika:
16 dolgozat érkezett. 10 pontot kapott: Adrián Patrik. 9 pontot kapott: Strenner Péter. 8 pontot kapott: 6 versenyző. 7 pontot kapott: 1 versenyző. 6 pontot kapott: 2 versenyző. 5 pontot kapott: 3 versenyző. 4 pontot kapott: 2 versenyző.
A KöMaL 2011. novemberi informatika feladatai