SOLUTIE

Problema  2 - pseudobil
                                                                                                                  Autor:  prof. Constantin Gălățan,
	Colegiul Național „Liviu Rebreanu”, Bistrița

Cerința 1     ( 20 puncte)
	Se parcurg segmentele orizontale care conțin numai celule în interiorul pătratului.
Se observă că segmentul de lungime maximă are nr = D – 1 celule. Segmentul aflat imediat de deasupra și cel de dedesupt au fiecare câte (nr – 2) celule. Soluția va fi

nr1 = nr + 2 * ( nr – 2) + 2 * (nr – 4) + ... + 2 * 1

Cerința 2    ( 80 de puncte)
Soluție O(m * n2)
	Pentru fiecare interogare, se parcurg orizontal toate segmentele formate din celule interioare sau traversate pe diagonală de către laturile pătratului.
Acestă soluție obține 30 de puncte din punctajul cerinței 2.

Soluție O(m * K)    (Ciprian Cheșcă)
Se știe că o dreaptă de ecuație ax+by+c = 0 împarte planul în două semiplane cu proprietatea că toate punctele  dintr-un semiplan verifică relația ax+by+c > 0 sau  ax+by+c< 0.
Notând vârfurile cadrului cu ABCD laturile acestuia formează 4 drepte : AB, CD respectiv AD, BC. Putem considera că o bila se găsește în interiorul cadrului dacă bila se găsește în regiunea pozitivă a semiplanului AB și regiunea negativă a semiplanului CD și analog dacă bila se găsește în regiunea pozitivă a semiplanului AD și regiunea negativă a semiplanului BC.
Calculând în ce semiplan se găsește fiecare bilă în funcție de poziția cadrului se poate deduce dacă bila este în interiorul cadrului sau pe una din laturi.
Acestă soluție obține 30 de puncte din punctajul cerinței 2.

Soluție O(n2 + m * n)
	Pentru reducerea complexității la O(n) per interogare, se rețin sumele parțiale pentru fiecare coloană a matricei.
Fie deci matricea a, cu a[i][j] - numărul de bile aflate pe coloana j, până la linia i.
Se parcurge fiecare segment vertical aflat în interiorul cadrului și se calculează numărul de bile ca fiind a[i2][j] – a[i1][j] unde i2 este linia pe care se găsește ultima celulă (cea mai de jos), iar i1 este linia anterioară primei celule a segmentului.
Acestă soluție obține  60 de puncte din punctajul cerinței 2.
			j

i1






i2




Soluție O(n2 + m)    (Constantin Gălățan)
	Se poate răspunde la fiecare întrebare în O(1) dacă se precalculează în O(n * n) sumele parțiale în raport cu diagonalele.
În continuare vom numi diagonală secundară oricare diagonală care e paralelă cu diagonala secundară și vom numi diagonală principală oricare diagonală care e paralelă cu diagonala principală.

Definim matricile: su, sd, pu, pd cu semnificațiile:
su[i][j] – numărul de bile  aflate deasupra și pe diagonala secundară i, pe coloanele 1..j.  (up)
sd[i][j] – numărul de bile  aflate sub și pe diagonala secundară i, pe coloanele 1..j.     (down)
sp[i][j] – numărul de bile  aflate deasupra și pe diagonala principală i, pe coloanele 1..j.   (up)
sd[i][j] – numărul de bile  aflate sub și pe diagonala secundară i, pe coloanele 1..j.      (down)

Diagonalele secundare se numerotează 1, 2, ... 2 * n – 1 începând cu cea de la celula (1, 1)
Diagonalele principale se numerotează 1, 2, ... 2 * n – 1 începând cu cea de la celula (n, 1)
În exemplele de mai jos, su[5][4], pd[5][4], sd[7][5], pu[7][5]  reprezintă numărul de bile care se găsesc în interiorul zonelor hașurate.



			4										5










                 su[5][4]                 sd[7][5]


				4										5
























                  pd[5][4]                 pu[7][5]




	Pentru a afla numărul de bile din interiorul cadrului plasat cu colțul superior în centrul celulei (x, y), se fac sume și diferențe de sume parțiale. Vă puteți gândi la arii și la principiul includerii și excluderii.
		Prin urmare, aria poligonului acoperit de cadru (numărul de bile acoperite) va fi egală cu aria întregii suprafețe, din care se scad ariile poligoanelor marcate cu roșu, verde și albastru:


















Această soluție obține - 80 de puncte, punctajul maxim pentru cerința 2.


Soluție O(n2 + m)   (Eugen Nodea)

Cum putem transforma problema într-o problemă clasică?
Inițial avem o matrice și un cadru pătratic (romb) paralel cu diagonalele matricei.
Dar dacă ”rotim” cu 450 matricea inițială, atunci vom avea un romb în care este inclus un cadru pătrat.
Să privim figura alăturată ce descrie rotația:

inițial	După rotație




Matricea nou creată are (2*N-1)*(2*N-1) elemente.
Astfel problema se reduce la o problemă clasică:
 	”Pentru o matrice pătratică binară (conține valori de 0 și 1) să se determine numărul de valori de 1 aflate în pătratul (rombul) de latura D, pătrat pentru care se cunoaște colțul dreapta sus”.
Astfel, pentru fiecare interogare se va răspunde în O(1).