Problem sa zadatkom PopulacijaGrada


#1

Da li neko ima ideju kako moze da se resi ovaj zadatak ,a da se ne pojavi greska TLE.

https://petlja.org/biblioteka/r/Problems/PopulacijaGrada


#2

Evo nekih smernica (slican pristup radi i u ovom zadatku), pa ako ne bude islo javi pa cu napisati detaljnije o ovom:

Zamisli isti zadatak, ali matrica je dimenzija 1 x N, tj. samo niz A, a upiti "saberi brojeve od A_i do A_j. Mozemo unapred (pre svih upita) izracunati sledeci pomocni niz:

S_i = A_0 + A_1 + A_2 + \dots + A_i

Ako ovo imamo, zbir od A_i do A_j mozemo zapisati kao:

A_i + A_{i+1} + \dots + A_j = (A_0 + \dots + A_j) - (A_0 + \dots + A_{i-1}) = S_j - S_{i-1}

(u specijalnom slucaju i = 0 druga zagrada “nestaje” i rezultat je samo S_j)

Dakle, u konstantnom vremenu (jedno oduzimanje) mozemo sabrati sve elemente od i-tog do j-tog. Ostaje samo da brzo izracunamo niz S, jer “naivno” racunanje (gde prolaskom kroz A sabiramo elemente) zahteva \mathcal{O}(N^2) operacija. Umesto toga, mozemo primetiti da vazi sledece:

S_0 = A_0
S_{i+1} = S_i + A_{i+1}

Primenom ova dva mozemo izracunati sve elemente S jednim prolaskom kroz A (u \mathcal{O}(N)), tako da je ukupno vreme (ako ima Q upita) \mathcal{O}(N + Q).

Slican pristup se moze iskoristiti i u dve dimenzije – detalje za sada prepustam tebi, a ako ne bude islo slobodno pitaj za pomoc.


#4

Hvala, probao sam da uradim zadatak na osnovu te ideje i radi.