Fibonaci

U zadatku Fibonacijev podniz u Uvodu u algoritme sam primetio da su mi svi test primeri OK samo tri zadnja TLE, kada sam ubacio https://pastebin.com/rdzEBDCi kod izbacio mi je TLE, prakticno je nemoguce napraviti program koji zadovoljava ovaj uslov ako samo za input prekoraci TLE, probao sam i sa scanf isto izbacuje TLE.
Mislim da trazeno vreme nije u redu.

Koliko ja znam, new se izbegava jer je veoma sporo, da nije zbog toga TLE?

TLE ce dobiti i bez dinamicke alokacije, problem je u pretvaranju tipova.

for(unsigned short i = 0; i < n; ++i)

n je unsigned int, i je unsigned short. U svakom ciklusu se tip od i pretvara u unsigned int, sto izaziva TLE.
Ako eksplicitno castujes, dobije se isto.
Ovako ce valjati. Unsigned short je svejedno premali da bi cuvao 10.000.000:

for(unsigned int i = 0; i < n; ++i)

edit:

Vreme se trosi samo kada pretvaras iz manjeg tipa u veci (npr. iz short u int).
To je zato sto short cuva 2 bajta a int 4, pa onda ovi novi bitovi moraju prvo da se popune.
Kada pretvars iz veceg u manji, npr. iz int u short, onda se veci bitovi prosto ne gledaju.
Ako ubacis:

for(unsigned short i = 0; i < (unsigned short)n; ++i)

neces dobiti TLE, mada zadatak nece proci za 100% test primera.

3 Likes

Hvala puno izbavivalo mi je TLE za tri zadnja primera i nisam znao sta ne valja 10 kodova sam pisao ispravljao sam na drugim mestima short u int ali ovde sam zaboravioā€¦ sad je sve OK.

Problem jeste u tome Å”to je i tipa unsigned short, ali TLE se ovde ne javlja zbog konverzije tipova (koja, čak i u slučajevima kada menja vrednost broja, obično ā€œkoÅ”taā€ samo jednu procesorsku instrukciju i neće drastično usporiti program).

U većini slučajeva, unsigned short je tip koji sadrži neoznačene brojeve dužine dva bajta (ā€œu većiniā€ jer standard ne garantuje tačnu Å”irinu tipa, ali svi popularni kompajleri se ponaÅ”aju isto). Samim tim, u promenljivu tipa unsigned short možemo upisati broj u intervalu [0, 2^{16} - 1], tj. najviÅ”e 65535. Ako je rezultat izračunavanja izraza veći od ove granice, dolazi do ā€œoverflow-aā€ i dobijamo rezultat kao da su brojevi poređani u krug ā€“ rezultat 65535 + 1 će biti 0.

Zbog toga, ako je n veće od 65535, petlja

for(unsigned int i = 0; i < n; ++i)

je beskonačna. Brojač i će uzimati vrednosti od 0 do 65535, pa onda opet od 0 do 65535, i tako daljeā€¦ U svakom trenutku će važiti $$, tako da se petlja neće prekinuti.

Svakako, reŔenje ovde jeste da se tip i promeni u int (ili unsigned int) da ne bi doŔlo do overflow-a.

2 Likes

Da, to ima vise smisla.
Nisam znao da integer overflow spada u undefined behaviour, bio sam ubedjen da program u tom slucaju izbacuje error. Hvala na ispravci!

Ipak stojim iza toga da konverziji tipova nije mesto u samoj petlji, pogotovo ako se petlje granaju i pogotovo ako je u pitanju pretvaranje izmedju celobrojnog tipa i decimalnog - jer ono ā€œkostaā€ mnogo vise (naravno u zavisnosti od procesora) od jedne instrukcije.

Integer overflow jeste nedefinisano ponaÅ”anje, ali samo za označene tipove (za unsigned tipove ovo ā€œkružnoā€ ponaÅ”anje je definisano standardom). Za označene brojeve je ponaÅ”anje obično isto, ali kompajleru je dozvoljeno da uradi bilo Å”ta i moderni kompajleri ovo koriste za optimizacije ā€“ ponekad se i na takmičenju nekome ovo desi pa izgubi poene.

Slažem se da retko ima potrebe za konverzijom u takmičarskim programima (obično je na raspolaganju dovoljno memorije da nema potrebe za kraćim tipovima), ali ne zbog efikasnosti, već samo da se ne bi deÅ”avale slučajne greÅ”ke. Čak i konverzija int u double je samo jedna instrukcija na modernim procesorima (i kompajleri ovo stvarno koriste), tako da ovo nema potrebe izbegavati zbog efikasnosti, ali opet nema ni potrebe da kod bez potrebe komplikujemo.