Az S. 64. feladat (2011. szeptember)

S. 64. Egy kezdetben N hosszú tömbből egymás után kitöröljük összesen K darab, pozíciójával megadott elemét. Minden törlés után -- a tömböknél megszokott módon -- a törölt elemet követő elemek eggyel előrébb csúsznak: a rákövetkező törlendő pozíció az így kapott új tömb vonatkozásában értendő (ld.: példa).

Írjunk programot, amely az eredeti tömb és a törlendő pozíciók ismeretében meghatározza az eljárás végén megmaradt N-K hosszú tömbben az elemek összegét.

A standard bemenet első sorában két, szóközzel elválasztott szám, az eredeti tömb hossza, majd a törlendő elemek 0KN száma található. A bemenet második sorában egy-egy szóközzel elválasztva az eredeti x₁,x₂,...,x_N (0x_j2³²-1, egész) tömbelemek, míg harmadik sorában rendre a törlendő i₁,i₂,...,i_K (1i_kN-k+1) indexek szerepelnek.

A standard kimenet egyetlen sorába egyetlen szám, a törlések elvégzése után kapott tömb elemeinek összege kerüljön.

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

(10 pont)

A beküldési határidő 2011. október 10-én LEJÁRT.

Bevezető

A feladat a két talán legalapvetőbb adatszerkezet, a tömb és a láncolt lista egy-egy meglehetősen konok és már-már hírhedt rossz tulajdonságára kívánt rávilágítani, jelesül, hogy mindkét adatszerkezetből meglehetősen költséges az i-edik elemet törölni.

Persze -- rendkívül elegáns módon -- a két adatszerkezetben ennek tökéletesen más az oka. Egy tömbben konstans időben megtalálhatjuk az i-edik elemet, viszont a törléshez az azt követő n-i darab elemet előre kell mozgatni. A láncolt listában ezzel szemben i lépésből tudunk csak eljutni a keresett elemhez, kiláncolni a listából viszont konstans lépésben megvan.

Mindkét esetben a teljes lépésszám átlagosan és legrosszabb esetben is az elemszámmal, n-nel arányos, általában O(n) ("egyenlő ordó n" -- felülről becsülhető n konstansszorosával). Egymás után k elem törlésének költsége ezek szerint O(kn).

A természetesen adódó megoldás

Az S.64. feladat megoldására természetesen adódott a naiv, szimulációs megoldás: vegyük fel a számokat egy tömbben vagy láncolt listában, és végezzük el egymás után a törléseket. A fentiek szerint ennek komplexitása O(kn), ez az n=1000000, k=n méretű, legnagyobb bemenetek esetén nem fért bele az előírt 5 perces futásidőbe.

Egy kis javítás

A tömbös megoldásnál maradva, azt kéne valahogy elkerülnünk, hogy ne kelljen annyi rákövetkező elemet előremozgatni, de ne is legyen sokkal költségesebb az i-edik elem megtalálása.

Ennek érdekében bontsuk az n-elemű tömböt darab, egyenként méretű tömbtöredékre (az utolsó töredékben esetleg kevesebb elem lesz). Minden töredékre tartsuk nyilván, hogy benne hány darab (még nem törölt) elem van összesen.

Ekkor a törlés algoritmusa a következő: ha az i-edik elemet kell törölni, először meghatározzuk, ez melyik töredékben van -- ezt időben megtehetjük, hiszen ismerjük, egy adott töredékben még hány elem van, és egyszerűen addig lépegetünk a töredékeken, és vonjuk le az elemszámokatt i-ből, amíg az már a jelenlegi töredékbe címez bele, legyen ez az index i'. Ezek után a kiválasztott töredékből a klasszikus "tömbös" módon töröljük az i'-edik elemet, az utána következő elemek eggyel előre csúsznak. Ennek költsége legfeljebb megintcsak, hiszen legfeljebb ennyi elem van egy töredékben.

Így tehát egy törlést O(n) helyett időben meg tudunk valósítani, k darab törlés pedig időben megoldható, ami a legnagyobb teszteset esetén is kb. 3 mp-en belül lefutott.

A C++ forráskód letölthető innen: mmo.cpp

Egy még jobb megoldás

A feladat O(k^.log n) időben is megoldható, a fenti ötletet -- miszerint vezessük vissza a feladatot több kisebb méretű tömbből való törlésre -- rekurzívan alkalmazva. Itt most ne -felé, hanem mindig ketté osszuk a tömböt, egészen addig, amíg a legalsó szinten az egyetlen elemből álló tömbökig nem jutunk. A felsőbb szinteken ismét csak annyit tároljunk, hány elem van azokban a kisebb tömbökben, amelyre egy adott tömböt felosztottunk.

Így a törlendő elem megkereséséhez minden szinten legfeljebb egyet kell lépni, majd törlés után minden szinten egyetlen tömbtöredékre kell módosítani, hogy hány elem van még benne. Mivel (log n) szint van, az algoritmus komplexitása O(k^.log n).

Ugyanez a komplexitás elérhető azáltal is, ha például bináris keresőfákat, ugrólistákat (skiplist), vagy egyéb fejlett adatszerkezetet használunk.

Előbbire láthatunk egy rendkívül elegáns implementációt, fórumozónk, Róbert Gida tollából: s64.cpp.

Utóbbit pedig Adrián Patrik versenyző (Baross Gábor Középiskola, Szakiskola és Kollégium, Debrecen, 12. évf) munkája demonstrálja: s64.zip

A beérkezett megoldásokról

Többségében jó megoldások érkeztek. A két legjellemzőbb hiányosság/hiba a következő volt.

Nem hatékony algoritmus használata: sokan az O(kn)-es algoritmust implementálták, ezek a megoldások a legnagyobb bemenetre nem futottak le 5 percen belül. Az ilyen megoldásokra legfeljebb 8 pontot lehetett kapni.

A bemeneti/kimeneti specifikáció be nem tartása, a bemenet hibaellenőrzése, túlbonyolítása. Erről bővebben itt olvashattok: stdio.pdf

Statisztika:

26 dolgozat érkezett.
10 pontot kapott:	Adrián Patrik, Nagy Róbert, Szabó 928 Attila.
9 pontot kapott:	Strenner Péter.
8 pontot kapott:	4 versenyző.
7 pontot kapott:	9 versenyző.
6 pontot kapott:	5 versenyző.
4 pontot kapott:	2 versenyző.
3 pontot kapott:	2 versenyző.

A KöMaL 2011. szeptemberi informatika feladatai