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

Problem I. 175. (January 2008)

I. 175. We are given N closed intervals on the number line. Determine all intervals on the line which are contained in an odd number of the given ones. The endpoints of the intervals do not need to be considered. Your solution should consist of the minimal number of intervals, that is, the intervals should be disjoint and neighbouring ones should be merged.

The name of the input and output files are given as the first and second command line arguments of your program (e.g. i175 in.txt out.txt). The first line of the input file is the number of intervals (0\leN\le7000), then each of the next N lines contains two integers X and Y (separated by a space) describing the endpoints of an interval (0\le
X<Y\le 1\;000\;000). The first line of the output file should contain the number of intervals M, then each of the next M lines should describe these intervals (with endpoints in increasing order) in the same format as the input.

The source code of your program (i175.pas, i175.cpp, ...) together with a short documentation (i175.txt, i175.pdf, ...) should be submitted, also containing a short description of your solution and the name of the developer environment to use.

(10 pont)

Deadline expired on February 15, 2008.


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

A megoldás menete

A feladatra nagyon sokféle megoldás érkezett. A következőkben N-nel fogjuk jelölni az intervallumok maximális számát, és L-lel azok maximális hosszát. Feltesszük, hogy minden szám ábrázolható egyetlen gépi szóban.

Tálcán kínálta magát a következő módszer: vegyünk egy L hosszú tömböt, melynek minden eleme azt reprezentálja, hogy az [i,i+1] szakasz felett hány intervallum fut. Kezdetben a tömböt nullázzuk, majd minden intervallumra az összes olyan tömbelem értékét eggyel növeljük, amely felett az adott intervallum átmegy. Ezután a tömbön végigfutva már csak ki kell olvasni azon szakaszait, melyben a értékek paritása páratlan. A módszer kétségkívül helyes megoldást ad, viszont mind tárigénye, mind időigénye nagyon magas. Tárigénye L-nel arányos a tömb miatt, futásideje pedig N.L-lel. (Ha például mind az N intervallum a [0,L], tömbhozzáférés ennyi lesz).

Ennél egy fokkal jobb megoldás, ha változatlanul felvesszük az L hosszú tömböt, de nem a számegyenes egységhosszú szakaszaihoz, hanem az egész számértékekhez. Kezdetben a tömböt itt is nullázzuk, majd minden intervallum feldolgozásakor a kezdőpont indexű tömbelem értékét 1-gyel növeljük, a végponthoz tartozóét pedig eggyel csökkentjük. Miután ezt minden intervallumra megtettük, a tömb minden eleme azt fogja tartalmazni, hogy az adott pontban az intervallumok száma mennyivel változott. A tömb egyszeri végigolvasással ismét könnyen meghatározhatóak a páratlan intervallumok. A módszer tárigénye változatlanul O(L), azonban műveletigénye O(N+L)-re csökkent, hiszen az intervallumok feldolgozása most már csak 2 tömbhozzáférést jelent, függetlenül a hosszuktól, a végeredmény pedig a tömb egyszeri végigolvasásával megkapható.

Egy, még ennél is jobb megoldáshoz az előzőben már megjelent "csak az intervallumok végpontjai számítanak" ötletet kell továbbgondolni: azt kell észrevenni, hogy teljesen mindegy, hogy egy kezdő- vagy végpont melyik intervallumhoz tartozik. Másképp fogalmazva, teljességgel közömbös, hogy egy kezdőpontnak melyik végpont a "párja", a lényeg csupán annyi, hogy egy kezdőpontban az intervallumok száma 1-gyel nő, egy végpontban pedig 1-gyel csökken. Tegyük tehát minden [a,b] intervallum esetén egy tömbbe az (a,1) párt, mely a kezdőpontot, és a (b,-1) párt, mely a végpontot reprezentálja. A párok első tagja tehát azt jelenti, hogy hol, míg utolsó tagja, hogy mennyivel változott az intervallumok száma. A párokat az első tag szerint sorba rendezve, az azonos koordináták szerint csoportosítva, majd a tömböt sorban végigolvasva ismét könnyen adódik a megoldás: azokban a pontokban kezdődik vagy végződik egy páratlan intervallum, melyek szerepelnek a tömbben, és mellettük második tagként a változások összege páratlan. A módszer tárigénye N-nel arányos, míg műveletigénye az alkalmazott rendezési algoritmustól függ, így akár O(N.log (N)) is lehet. Megjegyezzük, hogy igazából a 2. algoritmus is e utolsó módszer egy speciális, ú.n. ládarendezést használó változata.

A megoldások értékelése

A legtöbb versenyző az első módszert választotta, de érkezett egy-egy megoldás a második és harmadikra is. A pontozást illetően figyelembe vettük, hogy az utóbbi két módszer műveletigénye nagyságrendileg kevesebb, ugyanakkor azt is, hogy a feladat szövegében megadott korlátokkal az első módszer szerinti megoldások is lefutottak legfeljebb 1 percen belül (és természetesen utóbbiak a másodperc törtrésze alatt), így hossza vívódás után úgy döntöttünk, hogy az első módszert legfeljebb 9 ponttal jutalmaztuk.

Mintamegoldások

Mintamegoldásként közöljük a hivatalos megoldást C++ nyelven, mely a harmadik módszert implementálja, illetve Fábián András (Szeged, Radnóti Miklós Kísérleti Gimnázium, 11. osztály) versenyző Pascal nyelven írt munkáját (második módszer).

interval.cpp

fabian.zip

Engedy Balázs


Statistics:

8 students sent a solution.
10 points:Fábián András, Véges Márton.
9 points:Adrián Patrik, Földes Imre.
8 points:2 students.
6 points:1 student.
3 points:1 student.

Problems in Information Technology of KöMaL, January 2008