Clasa a 7-a lecția 20 - 18 feb 2016
Tema - rezolvări
- Problema extraterestri
- Problema extraterestri1
- Problema flori1
- Problema puncte1
Rezolvări aici [1]
Tema - rezolvări
Problema extratereștri
Problema extratereștri poate părea foarte complicată, dar, în realitate, ea are o rezolvare foarte simplă, de cîteva linii. Să începem cu începutul: enunțul.
Enunțul problemei este încîlcit. OZN-uri, soldați, raze laser. Să-l traducem în limbaj matematic: se dau N segmente în plan prin capetele lor, împreună cu numere întregi asociate. De asemenea se dau K drepte verticale infinite prin intersecția lor cu dreapta Ox. Pentru fiecare din aceste drepte trebuie să răspundem la întrebarea care este suma numerelor segmentelor pe care le intersectează acea dreaptă.
Observație: să facem o observație simplă dar importantă: problema nu este plană (2D) ci este liniară (1D). Observăm că coordonatele y ale segmentelor nu influențează intersecțiile cu dreptele verticale. Drept pentru care putem re-enunța problema pe dreapta Ox: date N intervale, cu numere asociate lor și K puncte, să se calculeze pentru fiecare punct suma numerelor asociate intervalelor care trec prin acel punct.
Soluția forță brută este să verificăm pentru fiecare punct ce segmente trec prin el și să însumăm numerele asociate lor. Această soluție este O(KN) și nu se va încadra în cele 0.2s pentru teste mari.
Soluția forță brută nr. 2 dar care ne duce într-o direcție bună, este următoarea: putem să creăm un vector de frecvență al coordonatelor, care pentru fiecare coordonată va memora numărul de extratereștri ce pot fi doborîți la acea coordonată. Construcția acestui vector se face parcurgînd intervalele și adunînd numărul asociat intervalului la fiecare coordonată de la x1 la x2, capetele intervalului. În final vom afișa valorile din acel vector în cele K puncte. Această soluție este O(CN+K), unde C este coordonata maximă, drept care va depăși timpul pe teste mari.
Optimizarea soluției 2 ne duce la o soluție care se încadrează în timp. Vom încerca să reducem timpul necesar "așezării" fiecărui interval în vectorul de frecvență. Acest timp este O(C) în cazul cel mai rău, adică două milioane. Dar dacă am amîna această așezare? Să presupunem că avem intervalul (a, b, p). Intervalul începe în a și se termină la b, iar numărul asociat este p. Am putea să marcăm în acel vector primul element la care vom începe să adunăm p, adica la v[a]. Apoi vom marca primul element în vector unde nu vom mai aduna p, adica v[b]. Ce înseamnă această marcare? Dacă în elementul v[a] depunem p, aceasta are semnificaţia că v[a] va trebui adunat la toate elementele următoare în vector, v[a+1], v[a+2]... Pînă cînd? Pînă ce vom anula acest efect depunînd la un element valoarea ce anulează efectul, adică -p. Unde trebuie depusă această valoare? La elementul v[b+1], deoarece v[b] trebuie să beneficieze de acest efect. Astfel, pentru fiecare interval (a, b, p) vom avea de făcut două operaţii:
v[a] += p;
v[b+1] -= p;Observăm că putem combina mai multe intervale, iar efectul lor se va însuma corect.
În final vom reconstrui vectorul v aşa cum ar trebui el să arate la finalul soluţiei 2. Pentru fiecare element vom aduna toate elementele anterioare:
for ( i = 1; i <= C; i++ )
v[i] += v[i-1];Continuăm la fel ca în soluţia 2, afişînd valorile din vector în cele K puncte cerute. Această soluţie este O(N+K+C), încadrîndu-se în timpul cerut de 0.2s, avînd avantajul suplimentar al unui program scurt. Iată programul bazat pe această soluţie:
#include <stdio.h>
#define MAX_COORD 2000000
int e[MAX_COORD + 2];
int main() {
FILE *fin, *fout;
int n, k, i;
int x1, x2, y1, y2, nr;
fin = fopen( "extraterestri.in", "r" );
fscanf( fin, "%d%d", &n, &k );
for ( i = 0; i < n; i++ ) {
fscanf( fin, "%d%d%d%d%d", &x1, &y1, &x2, &y2, &nr );
e[x1] += nr;
e[x2+1] -= nr;
}
// recalculare numar total de extraterestri
for ( i = 1; i <= MAX_COORD; i++ )
e[i] += e[i-1];
// citire si afisare query-uri
fout = fopen( "extraterestri.out", "w" );
for ( i = 0; i < k; i++ ) {
fscanf( fin, "%d", &x1 );
fprintf( fout, "%d\n", e[x1] );
}
fclose( fin );
fclose( fout );
return 0;
}Soluţia foloseşte O(C) memorie.
Problema extratereștri 1
Problema extratereștri 1 este exact problema anterioară dar are restricții de memorie.
O soluţie ce foloseşte mai puţină memorie este următoarea: Ordonăm toate coordonatele, începuturile de intervale, sfîrşiturile de intervale şi punctele unde împuşcăm. Apoi pornim cu o sumă de extratereştri, iniţial zero, parcurgînd aceste puncte în ordinea coordonatelor. Dacă întîlnim un început de interval adunăm numărul lui de extratereştri la sumă. Dacă întîlnim un sfîrşit de interval scădem numărul de extratereştri din sumă. Dacă întîlnim un punct de tragere stocăm suma curentă pentru afişare. În final afişăm cele K valori în ordinea iniţială a punctelor. Această soluţie este O((N+K) log (N+K)) și folosește memorie O(N+K).
O altă soluție cu același necesar de timp și memorie folosește tehnica canonizării coordonatelor. Ca și în soluția precedentă sortăm coordonatele și apoi, conceptual, reasignăm fiecărui segment noi coordonate care vor fi în intervalul [0..2N+K]. Apoi aplicăm soluția optimă de la problema extratereștri, folosind vectorul e frecvență.
Iată această ultimă soluție:
#include <stdio.h>
#define MAXN 20000
#define MAXNR 100
#define SHIFT (MAXNR + 1)
int nr[MAXN*3+1]; // 240K
int x[MAXN*3+1]; // 240K
int laser[MAXN]; // 80K
short adun[MAXN*3]; // 120K
int pivot, aux, b, e;
void quicksort( int begin, int end ) {
b = begin;
e = end;
pivot = x[(begin + end) / 2]; // alegem un pivot la jumatea vectorului
while ( b <= e ) {
while(x[b] < pivot) b++;
while(x[e] > pivot) e--;
if ( b <= e ) {
aux = x[b]; x[b] = x[e]; x[e] = aux;
aux = adun[b]; adun[b] = adun[e]; adun[e] = aux;
b++; e--;
}
}
// acum [begin..e] sint mai mici sau egale cu pivotul
// si [b..end] sint mai mari sau egale cu pivotul
if ( begin < e ) quicksort( begin, e );
if ( b < end ) quicksort( b, end );
}
int main() {
FILE *fin, *fout;
int n, k, i, j, y1, y2;
fin = fopen( "extraterestri1.in", "r" );
fscanf( fin, "%d%d", &n, &k );
for ( i = 0; i < n; i++ ) {
fscanf( fin, "%d%d%d%d%hd", &x[2*i], &y1, &x[2*i+1], &y2, &adun[2*i] );
adun[2*i+1] = -adun[2*i];
}
// citire query-uri
for ( i = 0; i < k; i++ ) {
fscanf( fin, "%d", &x[2*n+i] );
adun[2*n+i] = SHIFT + i; // tinem minte numarul laserului
}
fclose( fin );
quicksort( 0, 2*n + k - 1); // sortam perechile de vectori (x, adun)
// asezam numerele in structura precalculata
j = 0;
x[2*n + k] = -1; // coordonata falsa, santinela
for ( i = 0; i < 2*n + k; i++ ) {
if ( adun[i] < SHIFT ) // este un capat de segment, nu un laser
nr[j+(adun[i] < 0)] += adun[i]; // il asezam potrivit in nr[]
else // este laser
laser[adun[i]-SHIFT] = j; // ii pastram pozitia
j += (x[i+1] != x[i]); // incrementam j daca avem coordonata noua
}
// recalculare numar total de extraterestri1 in fiecare punct
for ( i = 1; i < j; i++ )
nr[i] += nr[i-1];
// afisare query-uri
fout = fopen( "extraterestri1.out", "w" );
for ( i = 0; i < k; i++ )
fprintf( fout, "%d\n", nr[laser[i]] );
fclose( fout );
return 0;
}Problema flori
Problema flori este o problemă care la origine a fost intenţionată spre a fi rezolvată cu precalcularea sumelor parţiale pe matrice. Este o soluţie foarte risipitoare de memorie şi nu cu mult mai scurtă decît o soluţie care foloseşte precalcularea sumelor parţiale pe vector (a.k.a şmenul lui Mars), drept pentru care nu voi prezenta acea soluţie. Vezi soluţia problemei flori1, mai jos.
Problema flori 1
Problema flori 1 este intenţionată ca o continuare a problemei flori, în care memoria a fost restricţionată drastic, de la 16MB la 2.5MB.
#include <stdio.h>
#define MAX_COORD 1000
#define MAX_DREPT 10000
short h[MAX_COORD][MAX_COORD];
short start[2 * MAX_DREPT + 1], end[2 * MAX_DREPT + 1],
uda[2 * MAX_DREPT + 1], next[2 * MAX_DREPT + 1];
short ind[MAX_COORD + 1];
int dif[MAX_COORD + 1];
int main() {
FILE *fin, *fout;
int n, m, z, i, j, aloc, p, hc, hmax, nmax, sumdif;
short int l1, c1, l2, c2, x;
aloc = 1;
fin = fopen( "flori1.in", "r" );
fscanf( fin, "%d%d", &n, &m );
for ( i = 0; i < n; i++ )
for ( j = 0; j < m; j++ )
fscanf( fin, "%hd", &h[i][j] );
// citim cele z dreptunghiuri si introducem doua segmente, unul cu +x
// la coordonala l1-1 si unul cu -x la coordonata l2
fscanf( fin, "%d", &z );
for ( i = 0; i < z; i++ ) {
fscanf( fin, "%hd%hd%hd%hd%hd", &l1, &c1, &l2, &c2, &x );
// plasam inceputul dreptunghiului
start[aloc] = c1 - 1;
end[aloc] = c2;
uda[aloc] = x;
next[aloc] = ind[l1 - 1];
ind[l1 - 1] = aloc++;
// plasam finalul dreptunghiului
start[aloc] = c1 - 1;
end[aloc] = c2;
uda[aloc] = -x;
next[aloc] = ind[l2];
ind[l2] = aloc++;
}
fclose( fin );
// parcurgem liniile matricei de flori, plasind segmentele existente
// pe acea linie
hmax = nmax = 0;
for ( i = 0; i < n; i++ ) {
// plasam dreptunghiurile noi (care se termina sau incep) pe vectorul de
// diferente dif[]
p = ind[i];
while ( p != 0 ) {
dif[start[p]] += uda[p];
dif[end[p]] -= uda[p];
p = next[p];
}
// testam florile maxime adunind suma(diff[0..j]) cu h[i][j]
sumdif = 0;
for ( j = 0; j < m; j++ ) {
sumdif += dif[j];
if ( (hc = (sumdif + h[i][j])) > hmax ) {
hmax = hc;
nmax = 1;
} else if ( hc == hmax )
nmax++;
}
}
fout = fopen( "flori1.out", "w" );
fprintf( fout, "%d %d\n", hmax, nmax );
fclose( fout );
return 0;
}Lecţie
Mulţimea maximă de intervale neintersectante pe o axă
Enunţ
Problemă: dată o submulţime de N intervale [ai, bi] să se găsească o submulţime maximală a acestei mulţimi care conţine doar intervale disjuncte (neintersectante).
Idei de soluţie
Această problemă apare destul de des la olimpiade, deghizată într-o formă sau alta. Deşi pare o problemă grea, în realitate ea se rezolvă uşor. O primă idee ar fi să încercăm să ordonăm intervalele după punctul de început, apoi să le luăm în ordine, unul cîte unul. Pentru fiecare interval ne întrebăm dacă îl intersectează pe cel anterior. Dacă da, îl aruncăm şi mergem mai departe. Dacă nu, îl adăugăm la submulţime şi îl reţinem ca interval ultim. Această soluţie nu funcţionează şi e destul de evident de ce: am putea avea un prim interval foarte lung, care acoperă toate celelalte intervale.
Cu toate acestea rezolvarea nu e total greşită. În fapt, ea aproape funcţionează! Are nevoie doar de o modificare ce se impune, analizînd contraexemplul anterior: de ce nu este bun acel prim interval foarte lung? Deoarece el se termină după celelalte. Şi atunci ne putem întreba, în mod natural, ce s-ar întîmpla dacă am alege intervalul care se închide primul, nu care începe primul? Desigur că acest algoritm funcţionează. Vă las vouă să vă luptaţi cu demonstraţia, care decurge cam aşa: să presupunem că soluţia generată de acest algoritm nu e optimă. Înseamnă că există o altă soluţie cu mai multe intervale. Acea soluţie trebuie să difere undeva faţă de cea găsită de noi. Mergeţi pe această cale şi trebuie să ajungeţi la o contradicţie cum că soluţia optimă nu poate avea mai multe segmente.
Soluţie
Care este algoritmul, în mare?
- Ordonează crescător intervalele după punctul de închidere.
- // Incepem alegerea intervalelor
- Iniţial mulţimea M este vidă, adica numarul de intervale este 0
- Consideră ultima închidere la minus infinit. (Ultima inchidere initiala, adica a primului interval fictiv)
- Pentru fiecare interval, în ordine:
- Dacă el conţine ultima închidere
- Ignoră-l.
- Altfel
- Selectează intervalul curent şi adaugă-l la mulţimea M.
- Setează ultima închidere pe închiderea intervalului selectat
- Dacă el conţine ultima închidere
- Afişează mulţimea M.
Ce se întîmplă dacă avem mai multe intervale care se termină în acelaşi punct? Atunci putem reţine intervalul cel mai mic. De ce? Deoarece este cel mai convenabil. Să presupunem că soluţia maximală conţinea un alt interval care se termina în acel punct. Atunci putem înlocui acel interval cu intervalul cel mai mic, obţinînd o altă soluţie maximală.
Considerente de implementare
Implementarea directă: memorăm intervalele ca perechi, prin capetele lor. Sortăm perechile după capătul din dreapta. Apoi facem o parcurgere a perechilor. Această implementare necesită O(N log N) timp şi O(N) memorie.
Implementare relaxată: atunci cînd coordonatele sînt suficient de mici astfel încît să putem folosi un vector care să memoreze un întreg pentru fiecare coordonată, putem încerca o abordare mai simplă: Nu memorăm intervalele. Ci, pentru fiecare interval [ai, bi], vom seta inceput[bi] = ai. Cu alte cuvinte vom memora capetele stînga la poziţia capetelor dreapta. Apoi parcurgem vectorul în ordine, acoperind segmentul de coordonate care acoperă toate intervalele, testînd dacă elementul de la poziţia curentă în vector este mai mic decît ultima închidere memorată. Dacă nu, atunci selectăm intervalul şi mutăm ultima închidere la poziţia curentă în vector. Trebuie să avem grijă la următoarele:
- Să iniţializăm vectorul de coordonate cu o valoare distinctă de capete de interval. Matematic am putea să le iniţializăm cu minus infinit, astfel încît să nu fie selectate niciodată.
- Atunci cînd "aşezăm" intervalele pe vector să avem grijă ca dacă găsim deja o valoare în vector să o înlocuim numai dacă cea curentă este mai mare (intervalul este mai mic).
Această soluţie necesită O(N + CMAX) timp şi memorie, CMAX fiind coordonata maximă. De aici rezultă cînd o putem folosi: atunci cînd CMAX este suficient de mic.
Generalizare
Putem generaliza această problemă: să se calculeze mulţimea maximală de dreptunghiuri neintersectante. Sau de paralelipipede. Sau de paralelipipede n-dimensionale. Cum se rezolvă aceste probleme? Din nefericire aceste probleme fac parte dintr-o clasă de probleme numite NP-hard, pentru care nu se cunoaşte o soluţie bună.
Consurs
Temă
Rezolvări aici [2]
