Pozdrav,
http://www.spoj.pl/problems/LPERMUT/
Trebam pomoc oko ovog zadatka. Nista sto napravim nije dovoljno brzo.
Pozdrav,
http://www.spoj.pl/problems/LPERMUT/
Trebam pomoc oko ovog zadatka. Nista sto napravim nije dovoljno brzo.
Pošalji ovdje source pa ćemo optimizirati.
Moj algoritam gleda sljedeće.
Ukoliko je broj jedinstvenih elemenata nekog intervala( L ) jednaka duljini tog intervala,
te suma članova jednaka L * ( L / 2 ) / 2 tada je L rjesenje.
Da bi gledao broj jedinstvenih elemenata implementirao sam BIT( binary indexed tree, Fenwick tree ) ili logaritamsku strukturu kako je zovu kod nas.
Sada sam razmatrao još 2 rješenja.
Da tražim "1" i razrađujem elemente oko njih.
Da trazim do kojeg indexa neki element vrijedi.
val : 1 2 4 2 5 4 2 3
idx : 3 3 5 6 8 8 8 8
2 se pojavljuje na 7 mjestu te zbog toga svi brojevi koji prethode dvojci na poziciji 4 mogu vrijediti samo do 6 pozicije nakon toga sigurno se događa repeticija.
nakon toga razrađujem intervale.
Idem kroz array te za svaki element radim sljedeće.
neka je x - idx[x] + 1 duljina intervala gdje idx označuje do kojeg elementa vrijedi.
gledam koliko mi fali ili nedostaje do sume x - idx[x] + 1 brojeva te se za toliko pomaknem.
Ovo rješenje ne znam efikasno implementirati, ali mislim da se da u O( n^2 ) za razliku od onog prvog sa O( n^2 log^2 n )