Középiskolai Matematikai és Fizikai Lapok
Informatika rovattal
Kiadja a MATFUND Alapítvány
Már regisztráltál?
Új vendég vagy?

Az S. 75. feladat (2012. november)

S. 75. Adott N db (legföljebb 1000000) intervallum: (ki,vi), 1\lei\leN, ahol ki az i-edik intervallum kezdő, vi a végpontját jelöli (0\le
k_{i}< v_{i}\le 1\;000\;000\;000). Intervallumok egy halmaza jó, ha közülük bármelyik kettőt kiválasztva az egyik tartalmazza a másikat. (A (ki,vi) intervallum tartalmazza a (kj,vj) intervallumot, ha ki\lekj és vj\levi.) Készítsünk programot, amely adott intervallumhalmazból meghatározza a legnagyobb elemszámú jó halmazt.

A program olvassa be a standard input első sorából N-et, majd a következő N sorból a ki, vi szóközzel elválasztott egészeket, és írja a standard output első sorába a maximális jó halmaz elemszámát.

Pontozás: A programhoz mellékelt, a helyes megoldás elvét tömören, de érthetően leíró dokumentáció 1 pontot ér. A programra akkor kapható meg a maximális 9 pont, ha bármilyen hibátlan bemenetet képes megoldani az 1 mp futásidőkorláton belül. Kapható részpontszám, ha a program csak kisebb tesztesetekre tud lefutni időben. Az alábbi részpontszámokból tevődik össze a 9 pontos maximális pontszám:

\bullet 1 pontért: 0<N\le150;

\bullet 3 pontért: 200<N<2000;

\bullet 5 pontért: 2000\le N < 100\;000.

Beküldendő egy tömörített s75.zip állományban a program forráskódja (s75.pas, s75.cpp, ...) az .exe és más, a fordító által generált állományok nélkül, valamint a program rövid dokumentációja (s75.txt, s75.pdf, ...), amely a fentieken túl megadja, hogy a forrás mely fejlesztői környezetben fordítható.

(10 pont)

A beküldési határidő 2012. december 10-én LEJÁRT.


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


Statisztika:

9 dolgozat érkezett.
10 pontot kapott:Jákli Aida Karolina, Nagy Róbert.
9 pontot kapott:Szabó 928 Attila.
5 pontot kapott:1 versenyző.
4 pontot kapott:1 versenyző.
1 pontot kapott:1 versenyző.
0 pontot kapott:3 versenyző.

A KöMaL 2012. novemberi informatika feladatai