Da li neko moze da mi objasni D - Plus-Minus? Nije mi bas jasno sta se radi.
Koristimo ovo tvrdjenje: suma svih elemenata u opsegu [l,r] je jednaka sumi u opsegu [0,r] - suma u opsegu [1, l-1] … tj ako je s[i] = a[0] + a[1] + … + a[i], onda za sumu u opsegu [l,r] vazi: sum = s[r] - s[l-1]. Ovaj niz s se inace naziva niz prefiksnih suma. Sada uocimo da ako je suma [l,r] strogo manja od 0, vazi da je s[r] < s[l-1], a ako je veca, onda vazi s[r] > s[l-1]. Kako ovo pomaze?
Konstruisimo graf (ima mng implementacija na netu) gde veza izmedju cvora u i cvora v oznacava da je s[u] > s[v]. Proverimo da li u ovom grafu postoji ciklus, ako postoji to znaci da je odgovor -1 (neki broj treba da bude veci od samog sebe, sto je zbog axioma nemoguce 
).
Dalje mozemo da napravimo niz s i da ga prvo popunimo nulama na onim indexima cvorova koji imaju out degree 0 (to jest to su oni cvorovi u grafu koji nemaju vezu ni ka jednom cvoru, iliti prefixne sume koje su manje od svih ostalih). Dalje definisimo rekurzivnu funkciju nadji(int x) koja vrace s[x] ako je on izracunat, a ako jos nije podesen racuna s[x] kao:
max{s[u]} + 1 za svako u tako da je cvor x povezan sa cvorom u, to jest da je s[x] > s[u].
Ovo i jeste minimalna vrednost prefixne sume s[x] jer uzimamo najveci broj od onih od kojih je strogo veci, i dodajemo mu 1.
Sada imamo niz s i na osnovu njega konstruisemo svaki element ovako:
a[i] = s[i] - s[i-1]
Potrudio sam se da sto bolje objasnim, ali mozda sam negde pogresio ili nesto ispustio, zamolio bih nekog koji je uradio ovaj zadatak na samom krugu da me ispravi ako sam negde pogresio ali ovo je ideja.
1 Like
Tacno ti je sve, samo sto mora sve da se brise, zbog T. Zbog toga imam 10 a ne 100 i bio bih drugi a ne 10. … (ako neko ima problema, a siguran je da mu je tacno, zbog ovoga vam ne radi) Inace, moze i topolosko sortiranje
2 Likes