Pomoc przy zrozumieniu zadania z main.edu.pl

Witam, mam problem ze zrozumieniem zadania z kursu: http://main.edu.pl/pl/user.phtml?op=showtask&task=tet&con=ALG
Nie proszę o jego rozwiązanie tylko o jakieś pomocne wskazówki. Np. jaka struktura powinna reprezentować całą platformę, bo gdyby wziąć każdy punt osobno to wychodzi tablica [1000000][20000]. Kurs zrozumiałem, ale jakoś nie potrafię zastosować przedstawionych tam technik. Z góry dziękuję za każdą pomoc.

Do pamiętania istotnych parametrów wystarczy tablica tab typu int[1000000]. tab[k], to wysokość na której znajduje się najwyżej położony kwadracik nad k.

OK, dzięki za pomoc, napisałem program, ale nie wszystko liczy dobrze. W połowie testów jest zła odpowiedź. Może ktoś przeanalizować i powiedzieć co zrobiłem źle:

 
#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

const int LEN = 1000;
int tab[1000000]; // Liczba/wysokość klocków, które nie objęły całego odcinka
int max_odc[LEN]; // Największa wartość na odcinku
int odc[LEN]; // Liczba klocków, które objęły cały odcinek
int d, n, l, x, iMax, h;

// d - szerokość platformy
// n - liczba klocków
// l - szerokość klocka
// x - pozycja klocka
// iMax - największa wartość w danym przedziale [a, b]
// h- wysokość

void find_max(int a, int b) {
	iMax = 0;
	while((a % LEN) != 0 && a <= b) {
		iMax = max(iMax, tab[a] + odc[a/LEN]);
		a++;
	}
	while((b % LEN) != (LEN - 1) && a <= b) {
		iMax = max(iMax, tab[b] + odc[b/LEN]);
		b--;
	}
	while(a <= b) {
		iMax = max(iMax, max_odc[a/LEN]);
		a += LEN;
	}
	iMax++;
}

void insert_block(int a, int b) {
	while((a % LEN) != 0 && a <= b) {
		tab[a] = iMax - odc[a/LEN];
		max_odc[a/LEN] = max(max_odc[a/LEN], tab[a] + odc[a/LEN]);
		a++;
	}
	while((b % LEN) != (LEN - 1) && a <= b) {
		tab[b] = iMax - odc[b/LEN];
		max_odc[b/LEN] = max(max_odc[b/LEN], tab[b] + odc[b/LEN]);
		b--;
	}
	while(a <= b) {
		odc[a/LEN]++;
		max_odc[a/LEN]++;
		a += LEN;
	}
}

int main() {
	scanf("%d%d", &d, &n);
	while(n--) {
		scanf("%d%d", &l, &x);
		find_max(x, x+l-1);
		//cout << "l: " << l << " x: " << x << '\n';
		insert_block(x, x+l-1);
		iMax  > h ? h = iMax  : h;
		//cout << "h: " << h << '\n';
	}
	printf("%d", h);
	//system("pause");
	return 0;
}

Twojego algorytmu nie analizowałem dokładnie, wydaje mi się przekombinowany.
Moja wersja:
Spada nowy klocek, lewy koniec to k, prawy to r. Szukam max(tab[i]) dla k<=i<=r. Zwiększam tab[i] o 1 dla k<=i<=r.
Na końcu szukam max(tab[i]) po wszystkich i.

Początkowo tak zrobiłem, ale wtedy program nie mieści się w czasie. Musiałem zastosować do tego podział na przedziały, tak jak w ostanim zadaniu przykładowym z kursu: http://main.edu.pl/pl/user.phtml?op=lesson&n=30&page=algorytmika i tu właśnie coś jest nie tak.

Odświeżam, proszę o pomoc, bo nie mogę się doszukać błędu w programie, a ciągle źle liczy

Nie znalazłem błędu w Twoim algorytmie. Być może jest, ale mam hipotezę. Problemy może stwarzać to, że tablice max_odc oraz odc nie są wyzerowane na początku działania programu. Gdyby było to prawdą, to dla n > 1000 mogą powstawać losowe wyniki. Dlatego zawsze warto przy takich zadaniach na początku wyzerować używane tablice.

Edit: Mam dziwne wrażenie, że zły wynik może powstać także wtedy, gdy maksymalna wysokość wzrosła przy ostatnim klocku. Proponowałbym, by nie liczyć wartości h przy każdym klocku, a dopiero po zakończeniu gry. Wtedy trzeba podać cały przedział 1..n.
Jeszcze jedno, pod koniec edycji znalezione: w C++ numeracja tablic zaczyna się od 0 (czyli numeracja max_odc kończy się na 999 999 oraz odc na 999), zaś w zadaniu od 1 (da nam to numery odpowiednio 1 000 000 oraz 1 000). Przekroczenie zakresu może też tworzyć losowe wyniki. Na Twoim miejscu zwiększyłbym jeszcze zakresy ww. tablic o kilka wartości (nigdy nie zaszkodzi).

Wykorzystałem wszystkie Twoje wskazówki (zwiększenie tablic i ich wyzerowanie, sprawdzanie h na końcu poprzez analizę max_odc), ale nic to nie dało. Połowa zadań cięgle źle. Wyniki różnią się dość znacznie np. " wczytano '3485', a oczekiwano '3675' "

Cały czas niepokoi mnie fragment:

        while(a <= b) {
                odc[a/LEN]++;
                max_odc[a/LEN]++;
                a += LEN;
        }

Mam wrażenie, że np. w takiej sytuacji:

• blok segmentów [1,1000] ma maksymalną wysokość 666
• blok segmentów [1001,2000] ma max wysokość 333
• blok segmentów [2001,3000] ma znowu 666
• kładziemy klocek o położeniu [1,3000]

Mam dziwne wrażenie, że wtedy wysokość każdego segmentu po prostu zwiększy się o 1, czyli blok [1001,2000] otrzyma wysokość 334, nie zaś żądane 667.

Masz rację, już poprawiłem, ale nadal coś jest nie tak, choć wyniki są już bardziej zbliżone ('3530' zamiast '3675'). Teraz jestem pewny, że coś jeszcze jest w tym fragmencie źle i chyba chodzi o tablicę odc. Gdy klocek zajmuje jakiś cały odcinek to odc[a/LEN] + tab[a] powinno być równe max_odc. Myślałem, żeby zmienić wartość tab[a] i powiększyć ją o te puste pola, ale nic to nie dało. Wyniki nawet pozostają te same

 	while(a <= b) {
		odc[a/LEN]++;
		for(int i = a; i < LEN; i++) {
			tab[i] = iMax - odc[a/LEN];
		}
		max_odc[a/LEN] = iMax;
		a += LEN;
	}

Rozwiązanie podane przez Ciebie wyżej raczej nie powinno zmieścić się w czasie przy złośliwych testach.
Myślę obecnie nad taką zmianą:

• wyrzucić tablicę odc
• w tablicy tab przechowywać wysokość w danym segmencie (z późniejszym zastrzeżeniem)
• w tablicy max_odc wciąż przechowywać najwyższą wysokość w danym bloku
• dodać tablicę bool-ową np. wypelnione o rozmiarze LEN. Jeżeli wartość dla i-tego bloku będzie wynosić true, znaczy to, że wszystkie segmenty mają taką samą wysokość (i wtedy posługujemy się tablicą max_odc do wyrażenia dowolnej wysokości w tym bloku zamiast odc); false oczywiście na odwrót. Na początku przypisać wtedy każdemu elementowi tablicy true, bo wszystkie segmenty mają w każdym bloku taką samą wysokość (równą 0).

Zauważ, że:

• jeżeli jakiś klocek przykryje cały blok o numerze i, można ustawić wypelnione[i] = true oraz max_odc[i] = iMax. I to jest "synonimem" przykrycia całego bloku jednym odcinkiem.
• jeżeli klocek zachodzi tylko częściowo na blok i i już wszystkie wysokości nie są sobie równe, to uaktualniasz tablicę odc dla danego bloku (chyba odc[LEN*i]=max_odc[i], potem tak samo dla LEN*i+1, LEN*i+2 itd. - pętla). Potem zrobisz wypelnione[i] = false i wszystko jest już gotowe do położenia naszego klocka w danym fragmencie bloku. Zauważ, że dla każdego klocka będziemy musieli robić te czynności nie więcej niż 2 razy - dla każdego końca.

Uff.. rzadko się tak rozpisuję :D

Zrobiłem tak jak mówisz choć nie wiem czy dobrze wszystko zrozumiałem. W ostatnim punkcie chyba chodziło Ci o tablicę tab i zamiast max_odc[i] to iMax(wysokość na której jest nowy klocek). Jeszcze bardzie zbliżyłem się wyniku, ale ciągle to nie to (3620' zamiast '3675'). Za to program znacznie przyspieszył. Przedtem przy ostatnim teście ~0,41s, a teraz 0,12s. Oto jak to rozumiem:

#include <cstdio>
#include <iostream>
#include <algorithm>

using namespace std;

const int LEN = 1000;
int tab[1000001];
int max_odc[LEN+1];
bool wypelnione[LEN+1];
int d, n, l, x, iMax, h;

// d - szerokość platformy
// n - liczba klocków
// l - szerokość klocka
// x - pozycja klocka
// h- wysokość

void find_max(int a, int b) {
	iMax = 0;
	if(wypelnione[a/LEN] == true)
		iMax = max_odc[a/LEN];
	else 
		while((a % LEN) != 0 && a <= b) {
			iMax = max(iMax, tab[a]);
			a++;
		}
	///////////////////////////////
	if(wypelnione[b/LEN] == true)
		iMax = max_odc[a/LEN];
	else 
		while((b % LEN) != (LEN - 1) && a <= b) {
			iMax = max(iMax, tab[b]);
			b--;
		}
	///////////////////////////////
	while(a <= b) {
		iMax = max(iMax, max_odc[a/LEN]);
		a += LEN;
	}
	iMax++;
}

void insert_block(int a, int b) {
	if((a % LEN) != 0) {
		wypelnione[a/LEN] = false;
		max_odc[a/LEN] = max(max_odc[a/LEN], iMax);
		while((a % LEN) != 0 && a <= b) {
			tab[a] = iMax;
			a++;
		}
	}
	if((b % LEN) != (LEN - 1)) {
		wypelnione[b/LEN] = false;
		max_odc[b/LEN] = max(max_odc[b/LEN], iMax);
		while((b % LEN) != (LEN - 1) && a <= b) {
			tab[b] = iMax;
			b--;
		}
	}
	while(a <= b) {
		wypelnione[a/LEN] = true;
		for(int i = a; i < LEN; i++) {
			tab[i] = iMax; }
		max_odc[a/LEN] = iMax;
		a += LEN;
	}
}

int main() {
	scanf("%d%d", &d, &n);
	for(int i = 0; i < LEN + 1; i++) {
		max_odc[i] = 0;
		wypelnione[i] = true;
	}
	for(int i = 0; i < 1000001; i++) {
		tab[i] = 0;
	}
	while(n--) {
		scanf("%d%d", &l, &x);
		find_max(x, x+l-1);
		insert_block(x, x+l-1);
	}
	for(int i = 0; i <= LEN+1; i++) {
		h = max(h, max_odc[i]);
	}
	printf("%d", h);
	return 0;
}

Ha!
LEN+1 == 1001 :D
Oczywiście zamiast <= LEN+1 powinno być < n (bo analizujemy wszystkie segmenty od 0 do n-1). Tylko w tym razie musisz zamienić jeszcze fragment while(n--) na odpowiednią pętlę for, żeby pozostawić wartość n nienaruszoną; przykładowo for(int i = 0; i < n; i++) {. Powinno zadziałać.

Gdzie powinno być "< n" ? n to jest liczba klocków i nie pasuje to do ostatniej pętli, chyba, że znowu nie rozumiem ;)

#include <iostream>
using namespace std;

int main(){
    unsigned int d,n,l,x, line=1;
    cin>>d>>n; //width platform & number of blocks
    bool b,arr[d+1][d+1];
    for(int i=0; i<=d; i++)
      for(int j=0; j<=d; j++)
           arr[i][j]=false;
    for(int i=0; i<n; i++){
       cout<<line<<endl;
       cin>>l>>x; //width block & vertices of the platform block line
         do{
             for(int j=x; j<=(l+x); j++){
               if(arr[line][j]==false){ 
                  arr[line][j]=true;
                  b=true;
                  arr[line][x]=false;
                  arr[line][l+x]=false;
               }
               else{b=false; line++; break;}}
            int c=0;
            while(b==true && (line-c)>0){
                 c++;
               for(int j=x; j<=(l+x); j++){
                 if(arr[line-c][j]==false){ 
                   arr[line-c][j]=true;
                   b=true;
                   arr[line-c][x]=false;
                   arr[line-c][l+x]=false;
                 }              
                 else{b=false; break;}}
               if(b==true)
                 for(int j=x; j<=(l+x); j++)
                     arr[line-(c-1)][j]=false;
               else{b=true; break;}
            }
             cout<<line;
         }while(b==false);
    }
    cout<<line;
    return 0;
}

Ja rozwiązałem to tak, ale coś spieprzyłem... :]

@mnbvcX nie może być
for(int i = 0; i < n; i++){...} i
for(int i = 0; i < n; i++) {...}
próbowałem i nie działa, a poza tym nie pasuje, bo trzeba sprawdzić wszystkie elementy max_odc.
@:] zmień strukturę danych i algorytm, bo w najgorszym przypadku będziesz mieć tablicę arr[1000001][1000001] co jest niewykonalne.

EDIT: Zauważyłem literówkę w pętli:

for(int i = a; i < (a + LEN); i++) {
			tab[i] = iMax; 	
		}

Ale nic to nie dało, wyniki są ciągle złe i do tego program w dwóch ostatnich testach nie mieści się w czasie

EDIT2: W końcu udało mi się to rozwiązać :D Dzięki za pomoc ;)
Zamieszczam listing jakby kogoś interesowało:

#include <cstdio>
#include <algorithm>

using namespace std;

const int LEN = 1000;
int tab[1000000];
int max_odc[LEN];
int podstawa[LEN];
int d, n, l, x, iMax, h;

// d - szerokość platformy
// n - liczba klocków
// l - szerokość klocka
// x - pozycja klocka
// h- wysokość

void find_max(int a, int b) {
	iMax = 0;
	while((a % LEN) != 0 && a <= b) {
		iMax = max(iMax, tab[a]);
		iMax = max(iMax, podstawa[a/LEN]);
		a++;
	}
	while((b % LEN) != (LEN - 1) && a <= b) {
		iMax = max(iMax, tab[b]);
		iMax = max(iMax, podstawa[b/LEN]);
		b--;
	}
	while(a <= b) {
		iMax = max(iMax, max_odc[a/LEN]);
		a += LEN;
	}
	iMax++;
}

void insert_block(int a, int b) {
	max_odc[a/LEN] = max(max_odc[a/LEN], iMax);
	while((a % LEN) != 0 && a <= b) {
		tab[a] = iMax;
		a++;
	}
	max_odc[b/LEN] = max(max_odc[b/LEN], iMax);
	while((b % LEN) != (LEN - 1) && a <= b) {
		tab[b] = iMax;
		b--;
	}
	while(a <= b) {
		max_odc[a/LEN] = max(max_odc[a/LEN], iMax);
		podstawa[a/LEN] = max_odc[a/LEN];
		a += LEN;
	}
}

int main() {
	scanf("%d%d", &d, &n);
	for(int i = 0; i < n; i++) {
		scanf("%d%d", &l, &x);
		find_max(x, x+l-1);
		insert_block(x, x+l-1);
		iMax  > h ? h = iMax  : h;
	}
	printf("%d", h);
	return 0;
}