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.