Problem S. 73. (September 2012)
S. 73. A table tennis tournament is organized in Noname city. The home address of every player is known, together with the maximal distance the player is willing to walk for the sake of a match. Since the shape of the city is highly elongated, instead of the exact address we only take into account the relative position of the player's home along the long main street, given by a house number. The walking distance, too, is measured only along the main street -- in other words, everybody can reach the main street virtually immediately.
Since a match is always played at a player's place, two given players can play together if at least one of them is willing to walk to the other's place, that is, if the difference between their house numbers is not larger than the distance the more enthusiastic player is willing to walk.
Your program should determine the number of possible matches during the tournament. Two matches are considered to be distinct, if not the same two players participate in it.
Your program reads the number of players () from the first line of the standard input. Then each of the next N lines contains the two known pieces of data for every player as two integers separated by a space: the house address (
), then the maximal distance (
) this player is willing to walk for the sake of a match.
The standard output should contain a single number: the number of possible matches.
The table shows some inputs (``Bemenet'') and the corresponding outputs (``Kimenet'').
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 an arbitrary valid test case within 3 seconds of running time. Partial points can be obtained if your program can solve only the smaller test cases within the allotted time, or those test cases in which all the maximal walking distances are the same.
The source code of your program (s73.pas, s73.cpp ...) - without the .exe or any other auxiliary files generated by the compiler - should be submitted together with a short documentation (s73.txt, s73.pdf, ...) in a compressed folder s73.zip, also describing which developer environment to use for compiling.
(10 pont)
Deadline expired on October 10, 2012.
Sorry, the solution is available only in Hungarian. Google translation
Négyzetes futásidejű megoldások
Az első megoldási lehetőség, hogy megvizsgáljuk az összes játékospárt, és mindegyikre megállapítjuk, hogy tudnak-e játszani (azaz valamelyikük hajlandó-e elmenni a másikhoz), és ha igen, akkor növelünk egy számlálót, amelyben a végén megkapjuk az eredményt. N játékost N(N-1)/2-féleképpen lehet párosítani, tehát ez a megoldás O(N2) futásidejű, ami nagyobb tesztesetekre nem fér bele a futási időlimitbe.
Még mindig négyzetes, de kicsit gyorsabb megoldást kapunk, ha elérjük, hogy csak az eredménnyel legyen arányos a futásidő, vagyis azon párok számával, akik tudnak egymással játszani. Ha gyaloglási hajlandóság szerint növekvő sorrendbe rendezzük a játékosokat, akkor minden olyan pár, aki játszhat egymással, megteheti ezt úgy, hogy a későbbi játékos sétál el a másikhoz, hiszen ha esetleg a korábbi is elsétálhatna a későbbihez, akkor biztosan megtehetik ezt fordítva is. Tehát ha ebben a sorrendben megyünk végig a játékosokon, akkor elég mindig meghatározni az aktuális játékosra azt, hogy ő kikhez tud az eddigiek közül elsétálni.
Ha rendezve vannak a játékosok lakhely szerint is, akkor megtehetjük, hogy ezen a rendezésen elindulunk az aktuális játékostól (ehhez persze el kell tárolnunk egy külön tömbben, hogy a gyaloglási távolság szerinti rendezésben az i. játékos hol van ezen rendezés szerint) mindkét irányba, és addig lépkedünk, ameddig még olyan játékosnál járunk, akihez el tud sétálni, és közben azokat a játékosokat számoljuk, amelyek a gyaloglási hajlandóság szerinti rendezésben korábban vannak. Ennek az algoritmusnak a futásideje az eredménnyel arányos (hiszen minden játszma miatt legfeljebb két lépést teszünk), ami rossz esetben négyzetes lesz, hiszen ha nagyok a gyaloglási hajlandóságok, akkor a játékosok akár N-nel arányos számú másik játékossal is játszhatnak.
Gyorsabb megoldások
Az előbbi megoldást föl lehet gyorsítani: Fenwick fát használva mindig meg tudjuk mondani az aktuális játékosra gyorsan, hogy az eddidiek közül hány van benne az ő intervallumában.
Néhány versenyző lényegében rájött erre a megoldásra, de az implementáció mindenkinél elég bonyolult volt. Ezen az oldalon található egy jó leírás a Fenwick fáról: Fenwick tree. Az itt leírtak alapján leprogramozott mintamegoldás elég egyszerű, a Fenwick fával dolgozó két függvény összesen csak 10 sort tesz ki: S73-Fenwick-tree.cpp
Ennek a megoldásnak a futásideje O(A+Nlog A), ahol A jelöli a maximális lehetséges lakcímet. Mivel az ezt a megoldást implementálók programjainak futásideje sem fért bele a 3 mp-be, ezért végül 5 mp lett az időlimit. (Viszont a fentebbi mintamegoldás 0,8 mp alatt fut a legnagyobb tesztekre.)
Ha A nagyobb is lehetne
Ha a lakcímek mondjuk 1011 nagyságrendűek is lehetnének, akkor a fentebbi megoldás nem működne, hiszen már a Fenwick fa inicializálása is O(A). Ekkor két lehetőség van:
1. Okosabb adatszerkezetet használunk:
a) A Fenwick fához hasonlóan kettőhatvány hosszú intervallumokra eltároljuk az elemek számát, de csak akkor osztunk föl intervallumot, ha egynél több elem van benne. (Ez hasonlítani fog egy Quadtree-hez, csak egydimenziós.) S73-kdtree.cpp
b) Egy bináris keresőfa csúcsaiban eltároljuk még azt is, hogy hány elem van a csúcs bal részfájában. Összeadva egy elemhez az elem mélységét, és a lelépegetés közben a bal részfák elemszámát, megkapjuk, hogy hány nála kisebb elem van. Ezzel a megoldással az a probléma, hogy ahhoz, hogy gyors legyen, ki kéne egyensúlyozni a fát (pl. AVL fa, Piros-fekete fa), viszont bonyolult frissíteni a bal részfák elemszámát a kiegyensúlyozó műveleteknél. Ez a megoldás leprogramozva kiegyensúlyozások nélkül: S73-bst.cpp (Néha bízhatunk abban, hogy ha egy keresőfa véletlenszerűen épül, akkor kiegyensúlyozás nélkül sem lesz túl nagy az átlagos mélység, de sajnos itt pont nem ez a helyzet, úgyhogy ez a program nem fut le a legnagyobb tesztekre időben.)
2. A játékosoknak egy lakcím szerint rendezett tömbje fölé építjük a Fenwick fát, és ebben bináris kereséssel találjuk ki, hogy mi legyen a Fenwick fához intézett intervallumlekérdezés két végpontja.
Statistics:
18 students sent a solution. 10 points: Nagy Róbert. 9 points: Nagy 319 Vendel. 7 points: 2 students. 6 points: 3 students. 5 points: 6 students. 4 points: 3 students. 3 points: 2 students.
Problems in Information Technology of KöMaL, September 2012