Da li se nekako moze sqrt resenje za 70 bodova prosiriti da radi I na poslednjem subtasku? Mozda stelovanjem velicine bucketa da se uglavi u TLE? Ili je za 100 bodova drugacije resenje?
Da li mozes da objasnis tvoje resenje. Mislim da je trazena slozenost za 70p O(NlogN), a za 100p O(N+M*log(N)).
U O(bucket_size*M) prekalkulisem promenu niza A u range [1,bucket_size+M], pod time podrazumevam da prekalkulisem koji broj iz tog range ce se nalaziti na kojoj poziciji nakon bucket_size iteracija petlje zadate u zadatku, i ta prekalkulacija je primenljiva na ostatak niza A, obradjujem niz A bucket po bucket, za obradu jednog bucketa mi je potrebno O(M+bucket_size), sto dovodi do complexity ovog drugog dela da je O(N/bucket_size * M)
(N/bucket_size+bucket_size)/2>=sqrt(N) ( A-G nejednakost) slozenost ovog algoritma je najmanje
O(sqrt(N) * M). Ovo resenje je veoma blizu mog resenja u slozenosti O(N+M * logN).
Kada racunas promenu niza nakon x izvrsavanja zadate petlje prvo izracunas promenu niza nakon x/2 izvrsavanja zadate petlje i to iskoristis da nadjes promene u intervalu [x/2,x+m] (slicno kao sto nalazis promene bucketa). Kada trazimo ans(x) mozemo da zanemarimo sve pozicije vece od x+m jer se nece menjati. Slozenost je u tom slucaju T(x)=x+m+T(x/2). Pa je ukupna slozenost(T(N-M)) O(N+M * log(N)). https://pastebin.com/FCesGA74(moje resenje).
2 Likes
Hvala na objasnjenju, skoro da sam se setio toga za vreme takmicenja 
Evo i mog resenja, nazalost nisam uspeo da ga zavrsim do kraja takmicenja https://pastebin.com/dU7FMj7f. slozenost je O(N+M) tako da trebalo bi da prodje za sve test primere
1 Like
Da li moĆŸeĆĄ malo viĆĄe da objasniĆĄ kako dobijaĆĄ vrednosti niza u intervalu [x/2,x+m] iz reĆĄenja u intervalu [0, x/2 - 1], baĆĄ mi i nije jasna relacija âans[i+s/2]=tmp[s/2+tmp[i]];â ?
iz vrednosti niza A u intervalu [0,x/2-1] dobijes vrednost niza A u intervalu [x/2,x] tako sto nakon prve obrade(obrada [0,x/2-1]) ti si dobio resenje za [0,x/2-1] i dodatno jos promenio interval [x/2,x/2+m], zapamtis promenu koja se dogodila i primenis je na interval [x/2,x+m] ovime si dobio resenje za interval [0,x] i ovih preostalih [x+1,x+m] nije jos konacno resenje, konstantnim primenjivanjem ovog postupka ( fakticki prilepljujes interval za interval ) svaki novo nastali interval ce biti duplo veci nego prosli i to ce biti odradjeno u linearnom vremenu
1 Like