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

Problem S. 64. (September 2011)

S. 64. The position of K elements is given in an array of length N. These elements are deleted one after another from the array. As usual in the context of arrays, after performing a deletion, elements following the actually deleted element are shifted back by one position, so the position of the next element to be deleted is understood relative to the new array, see the example.

Your program should determine the sum of the elements in the final array of length N-K, if the original array and a list of positions to be deleted are given.

The first line of the standard input contains two integers separated by a space: the length of the original array 1\le N\le 1\;000\;000, and the number of elements 0\leK\leN to be deleted. The second line of the input contains the original elements of the array x1,x2,...,xN (0\lexj\le232-1, integers), again, separated by a space, while the third line of the input the indices i1,i2,...,iK (1\leik\leN-k+1) to be deleted.

The only line of the standard output should be a single number: the sum of the elements of the array after deletion.

In the example, ,,Példa bemenet'' is the sample input, ,,Példa kimenet'' is the output, and ,,Lépések'' is steps.

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

(10 pont)

Deadline expired on October 10, 2011.


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

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 \lceil\sqrt{n}\rceil darab, egyenként \lfloor\sqrt{n}\rfloor 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 O(\sqrt{n}) 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 O(\sqrt{n}) megintcsak, hiszen legfeljebb ennyi elem van egy töredékben.

Így tehát egy törlést O(n) helyett O(\sqrt{n}) időben meg tudunk valósítani, k darab törlés pedig O(k\sqrt{n}) 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 \sqrt{n}-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 \Theta(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


Statistics:

26 students sent a solution.
10 points:Adrián Patrik, Nagy Róbert, Szabó 928 Attila.
9 points:Strenner Péter.
8 points:4 students.
7 points:9 students.
6 points:5 students.
4 points:2 students.
3 points:2 students.

Problems in Information Technology of KöMaL, September 2011