Problem S. 78. (February 2013)

S. 78. In a remote country scientists would like to investigate a new plant with very special needs.

They want to grow them on a connected field, that is, on adjacent parcels. They are given N consecutive parcels (), however, there are sometimes large differences in the parcel levels. The elevation of each parcel is determined by a positive integer a_i () relative to the sea level. A further restriction is that the plant can be grown only on a group of parcels with the property that the elevation difference between any two parcels in the group is at most T . Scientists want to maximize the number of parcels to grow the plant. Your task is to find this maximal number.

Your program should read the values of N and T from the first line of the standard input, then the integers a_i each separated by a space from the next line. Your program should print the maximal parcel number in the only line of the standard output.

Example:

because parcels with elevation 7, 10, 8, 8 are acceptable (or even parcels with elevation 10, 8, 8, 11 would form a proper sequence of length 4), but no 5 adjacent parcels exist with the required properties.

Scoring and bounds. You can obtain 1 point for a brief and proper documentation clearly describing your solution. The maximal 9 points for your program can only be obtained if it can solve an arbitrary valid input within 2.5 seconds of running time. Since the input files may be huge, the reading operation alone may take 2 seconds for the largest test cases. Partial points can be obtained if your program can solve only smaller test cases within the allotted time, according to the following rules:

2 points for the interval ;

3 more points for ;

finally, 4 more points for the cases .

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

(10 pont)

Deadline expired on March 11, 2013.

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

Megoldás

Négyzetes futásidejű megoldás: Minden kezdőparcellára megkeressük a leghosszabb parcellasorozatot, amely megfelel a feladat feltételeinek.

nlogn-es megoldás: Intervallumfával megoldható, hogy minden intervallumra meg tudjuk határozni a minimális és a maximális elemet logn időben. Ezt most nem részletezem, de bármilyen intervallumfa megoldja ezt. Ennek segítségével a következőképp oldjuk meg a feladatot. FIGYELEM, ez egy általánosan hasznos módszer: Felveszünk két változót, i-t, j-t, i=1, j=1 kezdetben. Az algoritmus egy általános lépése: ha az (i,j) intervallum megfelel a feladat feltételeinek, akkor j-i egy lehetséges megoldás, j-t növeljük; ellenkező esetben i-t. Egy ilyen ellenőtzés logn idejű, mert megkeressük a minimális és a maximális elemet, a különbségüket vesszük, utána meg könnyen eldönthető, hogy ez kisebbegyenlő, vagy nagyobb, mint a megengedett határ. Már csak azt kellene látnunk, hogy így a legnagyobb intervallumot valóban megkapjuk, az meg teljesülni fog, hiszen i előbb utóbb a legjobb intervallum kezdőpontjára áll, és akkor j-vel megkapjuk a végét.

Viszont nem ez a legjobb megoldás! Van lineáris idejű is! Erre egy mintamegoldást töltök fel, ami erősen kihasználja a double ended queue-t, azaz egy olyan sorszerű adatszerkezetet, melynek az elejére és a végére is beszúrhatunk elemet, és törölhetünk is konstans időben. Az alapötlet a következő: végigmegyünk egy index-szel 1-től n-ig, és tároljuk az összes legkisebb és legnagyobb elemet. Amíg a legeslegkisebb és a legeslegnagyobb elem közt nincs T-nél nagyobb távolság, addig jó, utána meg töröljük a sorrendben legkorábbi extrém elemet. Azért használható a double ended queue, mert mindig monoton lesz a szóba jöhető legkisebb és legnagyobb elem.

A mintamegoldás: S78.cpp

Statistics:

5 students sent a solution.
9 points:	Vályi András.
8 points:	1 student.
5 points:	1 student.
3 points:	1 student.
0 point:	1 student.

Problems in Information Technology of KöMaL, February 2013