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

Problem S. 74. (October 2012)

S. 74. We are heading toward another galaxy on our nuclear-powered spaceship and the goal is to collect as much titanium as possible during the journey. Our map contains all known galaxies connected by one-way wormholes, further, it is known that if we leave a galaxy through a wormhole, we will not be able to return there.

We also know for each galaxy the amount of uranium and titanium that can be mined there upon visiting. Uranium is used as a propellant, but its storage is quite involved, therefore only a limited amount of uranium is stored on our ship. For each wormhole it is known how much uranium is needed to pass through. Fortunately we can refill our uranium supplies in any galaxy for one unit of titanium. At the beginning of our journey we have no titanium, but our uranium supplies are full.

Your program should read the map together with the number of the starting and destination galaxies from the standard input, then compute the amount of titanium we can collect during our intergalactic space journey at the maximum, and give the corresponding itinerary.

Input: The first line of the standard input contains 5 integers, separated by a space: the number of galaxies (2\le N\le 10\;000), the number of wormholes (1\le M\le 200\;000), the number of our departure and destination galaxies (galaxies are numbered from 1 to N), and the capacity of the uranium tank of our spaceship (1\le K\le 1\;000\;000).

Then each of the following N lines describes the 1st, 2nd, ..., Nth galaxy by two integers separated by a space: giving the amount of titanium and uranium that can be mined there (0\le T,U\le 1\;000\;000). Finally, each of the last M lines describes the 1st, 2nd, ..., Mth wormhole by three integers: the number of the starting and final galaxies connected by this wormhole, and the required amount of uranium (0\le W\le 1\;000\;000) to pass through the wormhole.

We make three natural assumptions: the departure and destination galaxies are different, no two wormholes connect the same two galaxies, further, for each wormhole its entry point and exit point do not coincide.

Output: In the first line of the standard output your program should display the maximal amount of titanium we can arrive at the destination galaxy with. The second line should contain the corresponding route in the following form: the first number is the number of galaxies visited during our journey (including the starting and final galaxies as well), then the numbers of the visited galaxies should follow.

If the target galaxy cannot be reached, the standard output should only contain the number -1.

In the Examples, ``Bemenet'' is input, while ``Kimenet'' is the corresponding output.

Scoring: You can obtain 2 points for a brief and proper additional documentation clearly describing your solution. The maximal 8 points for your program can be obtained only if it can solve each valid test case within the 3 seconds time limit. Partial points can be obtained if your program can solve only smaller test cases within the allotted time, or those test cases in which the amount of fuel to pass through a wormhole is always 0.

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

Based on the idea of Gábor Danner

(10 pont)

Deadline expired on November 12, 2012.


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

Általánosságban elmondható a beérkezett megoldásokról, hogy nagyon sok bennük a hiba. Egyetlen tökéletes megoldás sem érkezett. Egy olyan versenyen, ahol csak a kimeneteket nézik meg (pl. OKTV), sokan még több pontot vesztettek volna. A weboldalra általában szoktak felkerülni tesztadatok a feladatokhoz, amelyekre érdemes letesztelni a programjaitokat beküldés előtt. Példaképpen néhány olyan buktató, amely szerepelt a bemenetekben: nem 1-es kezdőcsúcs, sallang csúcsok, használhatatlan él, bányászható kezdő- és célrendszer, fölöslegesen sok uránium, vásárlásra kényszerítés, "hitelezést" megengedő bug esetén eltérő optimum.

A bemenetet felfoghatjuk egy körmentes, irányított gráfként, amelyben a csúcsok a csillagrendszerek, és az élek a féregjáratok.

Backtrack

A feladatot megpróbálhatjuk egy olyan backtrackkel megoldani, amely minden lehetséges útvonalat végignéz, és ezek közül kiválasztja a legjobbat. Ez a megoldás nem fut le időben a nagyobb tesztesetekre, hiszen előfordulhat, hogy nagyon sokféle úton juthatunk el a célhoz. (n-nel exponenciálisan arányos futásidejű) Ennek az algoritmusnak a hibátlan megvalósításával 6 pontot lehetett szerezni.

S74Backtrack.cpp

Dinamikus programozás rekurzióval és memorizálással

Először is vegyük észre, hogy ha egy adott csúcsba vezető két különböző útvonal olyan, hogy az elsővel kevesebb titánnal érkezünk meg, mint a másodikkal, akkor az urán mennyiségétől függetlenül biztosan a második a jobb. Más szóval egy olyan teljes rendezés adható az adott végpontú útvonalak között, amely egyszerűen egy kétkulcsos rendezés a végpontban lévő titán- és uránmennyiségre. (Hiszen egy egységnyi titánért bármikor feltölthetjük a tankunkat.) Ezt figyelembe véve adódik egy dinamikus programozásos megoldás: jelöljük opt[i]-vel az i. csúcsba vezető optimális útvonal végén a titán és uránmennyiségünket. Ekkor opt[i] értéke csak azon csúcsok opt értékétől fog függeni, amelyekből közvetlenül vezet él i-be. Két lehetőségünk van a fenti ötletből konkrétabb algoritmust gyártani:

1. Az opt-ra felírt rekurzív összefüggést közvetlenül implementáljuk egy rekurzív függvénnyel. Ehhez mindenképpen használnunk kell memorizálást, ami azt jelenti, hogy a függvény első dolga ellenőrizni, hogy nem számolta-e már ki az opt értéket a paraméterben kapott csúcsra, és ha igen, akkor nem számolja ki újra, hanem csak visszatér a már korábban kiszámolt értékkel. (Memoization oldala a Wikipedián) (Memorizálás nélkül ekvivalens lenne ez a megoldás a fentebbi backtrackkel: az útvonalak számával arányos ideig futna.)

S74DP.cpp

2. Csinálunk először egy topologikus rendezést a csúcsokra, azaz olyan sorrendbe tesszük őket, hogy nem vezet későbbiből korábbiba él (a körmentesség miatt ilyen sorrend biztosan van). Ezt elvégezhetjük egy olyan mélységi bejárással, amelynek a rekurzív függvénye a visszatéréskor hozzáfűzi egy lista végére az aktuális csúcsot. Végiggondolható, hogy ha végül megfordítjuk ezt a listát, akkor valóban egy topologikus sorrendet kapunk (ld. pl. a Topologikus rendezés oldala a Wikipedián). Ezután ebben a sorrendben meghatározhatjuk az opt értékeket, mivel minden olyan csúcs már "készen van", amelyből vezet él az aktuális csúcsba.


Statistics:

11 students sent a solution.
9 points:Szabó 928 Attila.
8 points:2 students.
6 points:1 student.
5 points:2 students.
3 points:3 students.
2 points:2 students.

Problems in Information Technology of KöMaL, October 2012