Da li neko ima resenje 4. zadatka sa prvog kruga kvalifikacija koje je na svih 10 test primera radilo?
Ako je figura sklopljena iz više delova, rešavaš svaki deo za sebe
f(x,y) = f(x,i-1) + f(i+1,y), za svako a[i] = 0
Ako je figura predstavlja samo iz jednog stub širine 1, rešenje je trivialno:
f(x,x) = 0, ako je a[i] = 0
f(x,x) = 1, ako je a[i] > 0
Ako imaš figuru koja je iz jednog dela, pronađeš min_a kao najmanji broj a[i] za i na intervalu [x…y] i za tu vrednost umanjiš sve vrednosti u a[i] na tom istom intervalu i rekurzivno pozoveš ponovno za taj interval i dodaš 1 (zbog tog poteza umanjivanja vrednosti).
f(x,y) = umanjiš a[i] (i u intervalu x do y) za vrednost min_a, rezultat = f(x,y) + 1
Međutim taj algoritam je kod 50% primera ok, a kod 50% vraća TLE. Izgleda da je malo prespor za proporcije tog zadatka pa npr za random generisan niz od n=300000 vrati rezultat za oko 0,3-0,4s , što je sporije od ograničenja 0,2s, što objašnjava TLE. Probao sam i neke manje optimizacije, recimo se da kod čitanja ignoriše a[i] ako je jednak prethodnom broju a[i-1] ali nije bilo dovoljno, da se dobije koji poen više.
1 Like