Mathematical and Physical Journal
for High Schools
Issued by the MATFUND Foundation
Already signed up?
New to KöMaL?

Problem S. 81. (May 2013)

S. 81. You are going to build a house, where the name of each work phase (e.g., window glazing, installing electrical wiring, wall coating) is known. It is also known for each work phase that they can be started only a certain number of days after another given phase has started (for example, before installing electrical wiring, walls must be built, which takes x days). It is possible to carry out several work phases simultaneously.

Moreover, you should also rent equipment: until the first day of the last work phase (we can suppose that the last work phase lasts for only 1 day). Hence, if the last work phase begins on the T^{\mathrm{th}} day, then we should pay T.P HUF as a rental fee.

Beside the above, we have to buy also raw materials for each phase. As a simplifying assumption, we suppose that the cost function of the raw materials is a monotone decreasing (more precisely, non-increasing) function of time, being constant on each neighboring time interval. As an example, the cost is 30 HUF between the 1st and 10th days; 20 HUF between the 11th and 20th days; and 15 HUF between the 21st and 40th days.

Write your program that - knowing the dependence of the work phases, the equipment rental fee P, and the cost function for the raw materials for each phase - calculates the minimal cost of building the house provided that the scheduling of the work phases is optimal.

The first line of the standard input contains the number of work phases (1\le N\le
30\;000), the number of dependencies (0\le E\le 100\;000) between the phases, and the rental fee (0\leP\le1000), separated by a space. Then each of the following E lines contains a triplet, say (ai,bi,ci), describing a dependency: phase bi can be started only ci days after starting phase ai (1\lei\leE). The next N lines contain the costs of raw materials for each phase in the following format: in each line (corresponding to one phase) the first number is K (1\leK\le100), then K pairs, (fj,vj), are listed (1\lej\leK, 0\lefj\le1000, 1\levj\le109). Each such pair describes one of the consecutive time intervals: day vj is the last day of the actual interval when the cost of raw materials is still fj for the current work phase. The first interval starts on the first day, the next interval starts the next day after the previous interval has ended, and so on.

The only line of the standard output should contain the minimal cost of building the house.

You can suppose that the dependencies are consistent, that is, the house can be built. Raw materials should be bought on the first day of the corresponding work phase. For each phase, the last time interval of the raw material cost function ends on the same D^{\mathrm{th}} day (1\leD\le109). The construction of the house can begin no sooner than the first day, and should be finished no later than the D^{\mathrm{th}} day.

In the example, ``Példa bemenet'' is the sample input, while ``Példa kimenet'' is the corresponding output. An explanation to the example is given as follows: starting dates for the work phases in an optimal schedule can be 1, 2, 4, 8 (or 1, 2, 3, 8). Then the cost of raw materials is 3+2+3+3=11, plus 8 HUF rental fee, yielding 19 HUF as a total cost. (If starting dates were 1, 2, 3, 7, then the total cost would be 3+2+3+10+7=25.)

Scoring. You can obtain 1 point for a brief and proper documentation clearly describing your solution. The remaining maximal 9 points for your program can only be obtained if it can solve an arbitrary valid input within 1 second of running time. Partial points of the above 9 points can be obtained if your program can solve test cases within the allotted time only with parameters orders of magnitude smaller than in the maximal inputs (e.g., with smaller N, E, vj or K values).

The source code (s81.pas, s81.cpp, ...) without the .exe or any other auxiliary files generated by the compiler but together with a short documentation (s81.txt, s81.pdf, ...) - also describing which developer environment to use for compiling, further a brief description of your solution - should be submitted in a compressed file s81.zip.

(10 pont)

Deadline expired on June 10, 2013.


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

Ha az alapanyagárak nem változnának, akkor ez a feladat a jól ismert kritkus út probléma lenne: adottak részmunkák egymásra épülései időközökkel, és számítsuk ki, hogy mikor végezhetünk a leghamarabb az összes munkával (hiszen a bérleti díjból származó kiadás az idő előrehaladtával nő).

Először gondoljuk végig a kritikus út probléma megoldását. Adódik, hogy a probléma modellezésére egy élsúlyozott, irányított gráfot használjunk: az u->v él jelentse azt, hogy az u munka elkezdése után az él súlyának megfelelő időt kell várni a v munka elkezdése előtt. Az egyes munkák leghamarabbi lehetséges elkezdési idejére adható egy rekurzív összefüggés, amelyben a befutó élek másik végpontjainak leghamarabbi elkezdési idejei, és az éleken lévő késleltetések szerepelnek: tekintsük azokat a munkákat, amelyekre épül az aktuális (x) munka, és adjuk hozzá mindegyiknek a minimális elkezdési idejéhez azt az időt, amennyinek el kell telnie az x elkezdéséig, majd ezeknek vegyük a maximumát. Ezt implementálhatjuk memorizáló rekurzióval (azaz egy olyan rekurzív függvénnyel, ami csak akkor számítja ki a paraméterül kapott csúcsra a leghamarabbi kezdési időt, ha még nem számította ki korábban), vagy kiszámolhatjuk az értékeket rekurzív függvény nélkül is, ha mindig figyelünk arra, hogy egy olyan csúcsnak számoljuk ki az értékét, amelybe befutó összes él másik végpontjának az értékét már kiszámoltuk (ehhez pl. számon tarthatjuk minden csúcsra, hogy hány kiszámolatlan közvetlen őse van, és a nullát elért számlálójú csúcsokat egy sorba tehetjük). Ennek az algoritmusnak a futásideje a csúcsok plusz élek számával arányos.

Most térjünk vissza az eredeti feladathoz. Itt az alapanyagárak csökkennek, ami arra késztet bennünket, hogy minél később kezdjük el az egyes munkákat. Ha az összes részmunka minden lehetséges elkezdési idejeinek minden kombinációját kipróbálnánk, az nyilvánvalóan nagyon lassú programot eredményezne. Azonban vegyük észre, hogy ha rögzítjük a teljes munka elkészülési idejét, akkor megoldhatjuk az alapanyagárak minimalizálását a kritikus út probléma megoldási algoritmusával, hiszen ekkor minden munkát a lehető legkésőbb érdemes elkezdenünk (hiszen az alapanyagárak monoton csökkennek) annak figyelembe vételével, hogy nem dolgozhatunk a rögzített nap után. Ez pont a kritikus út probléma időbeli fordítottja: olyan, mintha a rögzített időpont lenne a 0 pont (az eredeti kritikus út problémában ugyebár a 0 időpont előtt nem dolgozhatunk), és az élek fordítva lennének.

A határokat megnézve kiderül, még mindig nem elég gyors az algoritmusunk: Az árintervallumok lehetnek akár 109 nagyságrendűek is, tehát nem próbálhatjuk ki az összes lehetséges rögzítését a teljes munka elkészülési idejének. Viszont most kihasználhatjuk azt a tényt, hogy az alapanyagárak szakaszonként konstans függvények: ha elképzelünk egy munkatervet az egész munkára, majd ezt elkezdjük időben mozgatni, akkor csak olyankor változhat az alapanyagok beszerzési ára, amikor valamelyik munka éppen egy intervallumhatárhoz ér. Ez alapján a következő megoldás adódik: számoljuk ki a lehető leghamarabbi munkabefejezést, és a hozzá tartozó ütemezést, majd toljuk el az egész munkatervet minden lépésnél pont annyival, hogy már megváltozzon az össz alapanyagár, és közben végezzünk minimumkeresést az össz alapanyagár és a bérlési költség összegére. (A kezdeti munkatervünket a fentebbi fordított kritikus út algoritmussal számítjuk ki, vagyis az egyes munkák a lehető legkésőbbre kerülnek.)

A valóban hatékony implementáció eléréséhez még alakítani kell a fentebbi algoritmuson: nem szeretnénk minden lépésben az egész munkaterv módosításával tölteni az időt, továbbá a legközelebbi intervallumhatár megkeresésére is kell egy hatékony módszer. Valójában két dolog számon tartására van szükségünk: az aktuális eltolás (a 0 ponthoz képest), és az aktuális eltoláshoz tartozó össz alapanyagár. Ha először kiszámolunk egy kezdeti munkatervet, akkor már minden egyes munka összes intervallumhatárára kiszámolhatjuk, hogy mikor érjük el, hiszen csak a munkatervbeli eltolását kell alkalmaznunk. Így kapjuk alapanyagár-változási eseményeknek egy gyűjteményét. Ha ezt rendezzük a bekövetkezési idő szerint, akkor már csak ezeken kell végiglépegetnünk, és közben minimumkeresést csinálnunk az aktuális árra. Ennek az algoritmusnak a futásideje O(NKlog (NK)), mivel az események (intervallumhatárok) rendezése a leglassabb művelet.

Mintamegoldás: S81.cpp


Statistics:

2 students sent a solution.
10 points:Szabó 928 Attila.
4 points:1 student.

Problems in Information Technology of KöMaL, May 2013