Problem S. 75. (November 2012)

S. 75. We are given N intervals (at most 1000000) on the real line with starting points and endpoints (k_i,v_i), 1iN and . A set of intervals is referred to as proper, if for any pair of intervals from this set, one is contained in the other. (The interval (k_i,v_i) contains the interval (k_j,v_j), if k_ik_j and v_jv_i.) From an arbitrarily given set of intervals, your program should select a proper subset of intervals with maximal possible cardinality.

Your program should read the value of N from the first line of the standard input, then the values of the integers k_i and v_i (separated by a space) from the next N lines. The program should write the cardinality of the maximal proper subset of intervals to the standard output.

The example contains a sample input (``Példa bemenet'') with the corresponding output (``Példa kimenet'').

Scoring: you can obtain 1 point for a brief and proper documentation clearly describing your solution. The 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 can be obtained if your program can solve only smaller test cases within the allotted time: the 9 points are then divided into the following parts.

1 point for the cases with 0<N150;

3 points for the cases with 200<N<2000;

5 points for the cases with .

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

(10 pont)

Deadline expired on December 10, 2012.

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

Megoldás

Először is azt kell meggondolni, hogy mit is jelent a feladatban leírt jó intervallumhalmaz. Egy jó halmazt sorba tudunk rendezni tartalmazás szerint, hiszen "körbe" nem tartalmazhatják egymást. Ebben a sorban minden intervallum tartalmazza az őt követőt, azaz a kezdőpontok monoton nőnek, a végpontok monoton csökkennek. Ebből keressük a maximálisat.

Négyzetes megoldás: Rendezzük az intervallumokat kezdőpont szerint növekvően. Azonos kezdőpont esetén végpont szerint csökkenően. Ezzel azt értük el, hogy egy intervallum csak a tőle jobbra állókat tartalmazhatja. Ekkor egy egy dinamikus programozási feladatra egyszerűsödött. Minden intervallumhoz tárolunk egy számot, hogy ővele kezdődően milyen hosszú a maximális jó intervallumsor: d[i]. Jobbról malra haladva egyszerűen ki tudjuk tölteni. Megnézzük az i. intervallumra, hogy tőle jobbra melyiket tartalmazza: d[i]=max1, d[j], ahol a j. intervallum része az i.nek. (Az 1 azért kell, mert csak önmaga egy 1 méretű jó halmaz.) A futásidő lépésenként lineáris, így összesen négyzetes.

Egy másik, bonyolultabb megoldás során felépíthetjük azt a gráfot, melyben két intervallum mint csúcsok között irányított él jelzi a tartalmazást. Ebben a gráfban kell maximális utat keresni, ami topologikus rendezéssel is megvalósítható, ám ebből az előző megoldáshoz nagyon hasonlót kapunk.

Gyorsabb (nlogn-es) megoldás: Szintén rendezzük az intervallumokat ugyanúgy mint az előbb, csak most nézzük meg jobban, hogy valójában egy monoton csökkenő részsorozatot keresünk a végpontok között. A végpontokhoz tartozó intervallumok ekkor a fenti meggondolások alapján pont egy jó halmazt alkotnak, így a feladat a maximális monoton csökkenő részsorozat megtalálása. Erre létezik nlogn-es megoldás. Egy tömbben tároljuk, hogy mi a maximális érték, amivel egy k hosszú monoton csökkenő részrozat végződhet. Tehát t[k]=l, ha létezik egy k hosszú monoton csökkenő részsorozat, ami l-re végződik, de nincs olyan, ami l-nél nagyobb számra végződik. A tömbben először minden elem -1. Balról jobbra haladva a végpontokon ezt a tömböt frissítjük. Megkeressük, hogy az adott (i.) végpontot a t tömb melyik eleme után írhatnánk, hogy monoton csökkenő legyen. Nyilván egy adott végpontot (v) csak csak akkor érdemes a t[k]=l után írni, ha t[k+1]<v, hiszen különben csak annyit tudunk mondani, hogy t[k+1]=v is lehet. De mi a maximális ilyen t[k+1]-et szeretnénk. Miután ez megvan, lépünk a következő végpontra. Ha jól megfigyeljük, az így kapott t tömb monoton csökken, hiszen kezdetben az volt, és egyik lépés sem változtat ezen. Ennek köszönhetően binárisan meg tudjuk benne keresni azt a k helyet, amire t[k] után írható az aktuális v. Így a frissítés logn db keresés +1 esetleges átírás idejű. Miután az összes intervallumot sorra vettük, csak annyi a feladatunk, hogy a legnagyobb olyan k-t kiírjuk, amire t[k]>-1, azaz létezik k hosszú monoton csökkenő részsorozat. N db intervallumon megyünk végig, így nlogn-es a futásidő.

Egy másik nlogn-es megoldás intervallumfákat használ, ám mivel ez jóval bonyolultabb (mind az algoritmus, mind a megvalósítása), mint a fentebbiek, így részletes leírását mellőzöm.

Egy nlogn-es példamegoldás: S75.cpp

Statistics:

9 students sent a solution.
10 points:	Jákli Aida Karolina, Nagy Róbert.
9 points:	Szabó 928 Attila.
5 points:	1 student.
4 points:	1 student.
1 point:	1 student.
0 point:	3 students.

Problems in Information Technology of KöMaL, November 2012