Takmicenje iz programiranja 2017 - Kvalifikacije - 2. krug - Zadatak 2 - Trivijalan broj - Resenje - Verzija 2 - Prva optimzacija - Umesto For - While

Dragi takmičari,

 

U prilogu se nalazi 2 verzija rešenja 2. zadataka sa 2. kruga kvalifikacija - Trivijalan broj, odnosno prva optimizacija:

1. Algoritamsko rešenje 2. verzije koja daje tačne rezultate za sve test primere, ali je vremenski optimizovana (FlowGorithm).
2. Odgovarajući programski kod u Pascal-u (.pas).
3. Slika punih povratnih informacija sa sistema, nakon postavljanja programskog koda - rešenje se boduje sa 100 bodova (.png).
4. Link: https://arena.petlja.org/Competitions/Competition/171

Kao što možete da primetite razmišljali smo na sledeći način:

• Posebnu pažnju obratite na proste brojeve. Primetićete da prosti brojevi imaju najmanje količnike koji su uvek (1+x)/x, odnosno 1 + 1/x.
• Takođe, primetićete da, naročito za velike brojeve x, da je glavni deo zadatka da pronađemo prvi prost broj koji je manji od x.

Iz ovoga izvlaćimo sledeće zaključke:

1. Izgleda da uopšte nije potrebno da izraćunavamo sumu svih delilaca, a još manje da tražimo (upoređujemo) čija je suma najmanja.
2. Umesto toga potrebno je da pronađemo prvi (najveći) prost koji je manji od X i to je sve.
3. Da bi pronašli prvi (najveći) prost broj koji je manji od X bilo bi dobro (i zbog vremenske optimizacije) da brojač te petlje krene sa provreom od broja X (da li je prost), pa ako nije da proveri prvi sledeći manji (X=X-1) i tako redom sve dok ne naiđe na prvi prost broj (ili dođe do broja 2).
4. Za ovakvu cikličnu stukturu (petlju) mnogo je bolje i efikasnije da koristimo ciklus sa uslovom (While) umesto brojačkog ciklusa (For), s tim što obavezno moramo samo da vodimo računa o uslovu petlje, odnosno brojaču, kako ne bi napravili večnu (mrtvu) petlju.
5. Takođe, dodatno smo malo ubrzali algoritam, tako što smo zaključili da parni brojevi (veći od 2) nisu prosti, pa je bolje da ispitujemo samo neparne. Dakle, prvo proverimo da li je broj X paran, pa ako jeste odmah mu smanjimo vrednost za 1 (odnosno uzimamo prvi sledeći manji), pa tek onda počinjemo petlju.
6. Radi lakšeg praćenja i provere, uveli smo i logičku promenljivu Prost, koju inicijalno postavljamo na True, a ako naiđemo na prvi delilac postavljamo na False.
7. Promenljiva P će imati vrednost prvog najvećeg pronađenog prostog broja, manjeg (ne većeg) od X, te na početku postavljamo vrednost 0 ovoj promenljivoj (umesto nule, mogli smo i 1, radilo bi ispravno).
8. Dodatno smo ubrzali cikličnu strukturu sa uslovom (While), jer na ona to omogućava, tako što smo za uslov da se izvršava stavili sve dok ne pronađemo P (odnosno P=0) i za svaki slučaj dok X ne smanjimo toliko da dođe do 2.
9. Dodatno smo ubrzali cikličnu strukturu sa uslovom (While), jer na ona to omogućava, tako što smo brojač X koji učestvuje u uslovu petlje u svakom prolasku kroz petlju smanjili za 2 (a ne za 1 kao kod for), odnosno ispitivaćemo samo neparne brojeve (svaki drugi).
10. Ovaj programski kod nije maksimalno vremenski optimizovan, ali jeste sasvim dovoljno da prođe sve test primere i osvoji 100 bodova na kvalifikacijama.
11. Svi test primeri se izvršavaju za manje od 2 sekunde, što možete proveriti i kroz FlowGortithm i kroz programski kod u razvojnom okruženju, ali na samom sistemu.
12. Ipak, obratite pažnju na test primere 10 i 11. Za izvršavanja ova dva test primera bilo je potrebno 0,63 i 0,48 sekundi (jer se ispituju brojevi veći od milion). Recimo da nismo ispitivali samo neparne brojeve, već sve (duplo sporije) i/ili da nismo u uslovu petlje stavili i (P=0) ova dva test primera bi bila duža od 2 sekunde, pa ne bi bili bodovani.
13. Za još bolju, siigurniju i bržu vremensku optimizaciju, odnosno brže izvršavanje programskog koda, potrebno je da se upoznamo sa matematičkim osnovama teorije brojeva i deljivosti celih brojeva, kao i algoritamskim metodama za primenu tih matematičkih osnova. O tome, nešto detaljnije možete pronaći na:
    https://petljamedia.blob.core.windows.net/root/Media/Default/Lecture/Matematicki%20Algoritmi%201/Matematicki%20algoritmi%20I%20-%20Deljivost.pdf
    Ipak, nemojte previše žuriti sa čitanjem ovih materijala, naročito ukoliko još uvek niste dobro proučili ovu prvu vremensku optimizaciju, koja osvaja maksimalan broj bodova na kvalifikacijama.
14. Povratne informacije o rezultatima programskog koda možete proveriti na: https://arena.petlja.org/Competitions/Competition/171

Dodatni materijali za nastavak poboljšanja vremnske optimizacije:

• https://petljamedia.blob.core.windows.net/root/Media/Default/Lecture/Matematicki%20Algoritmi%201/Matematicki%20algoritmi%20I%20-%20Deljivost.pdf
• https://petljamedia.blob.core.windows.net/root/Media/Default/Lecture/Matematicki%20Algoritmi%201/Matematicki%20algoritmi%20I%20-%20Brojni%20sistemi.pdf
• https://petlja.org/BubbleBee/r/Lectures/matematicki-algoritmi-1

Pozdrav,
Dragan Ilić

 

 

----- Original Message -----

From: Dragan Ilic

Sent: Sunday, January 28, 2018 12:11 PM

Subject: Takmicenje iz programiranja 2017 - Kvalifikacije - 2. krug - Zadatak 2 - Trivijalan broj - Resenje - Verzija 1 - Nije optimizovano

Dragi takmičari,

 

U prilogu se nalazi 1 verzija rešenja 2. zadataka sa 2. kruga kvalifikacija - Trivijalan broj:

1. Ceo tekst zadatka (png slika).
2. Algoritamsko rešenje 1. verzije koja daje tačne rezultate za sve test primere, ali nije vremenski optimizovana (FlowGorithm).
3. Odgovarajući programski kod u Pascal-u (.pas).
4. Slika punih povratnih informacija sa sistema, nakon postavljanja programskog koda - rešenje se boduje sa 30 bodova (.png).
5. Link: https://arena.petlja.org/Competitions/Competition/171

Većina takmičara je došla do sličnih rešenja. Ovo je objedinjeno rešenje svih verzija rešenja naših takmičara. Takođe, ovo bi bilo najjednostavnije rešenje zadatka koje daje tražene tačne rezultate za sve unapred pripremljene test primere. Međutim, ovo rešenje ne osvaja maksimalni broj bodova na takmičenju, jer ne ispunjava sve navedene uslove u takmičarskom zadatku, tačnije ne ispunjava vremenska ograničenja.

 

Ako pažljivo pogledate povratne informacije sa sistema, primetiće sledeće:

1. Rešenje zadatka vraća statuse OK za prva 4 test primera, s tim što se prvi (iz teksta zadatka) ne boduje (boduje se 10 test primera od rb 2 do 11 po 10 bodova).
2. Vreme izvršavanja programskog koda za prva 4 test primera je po oko 0,02 sekunde, što je sasvim pristojno. Međutim, to je zato što se radi o relativno malim brojevima (manjim od 1000).
3. Za sve ostale test primere statusi su TLE, što znači da je došlo do vremenskog prekoračenja (Time Limit Excided), odnosno da je za svaki test primer bilo potrebno više od po 2 sekunde za izvršavanje.
4. Do vremenskog prekoračenja dolazi zbog velikih brojeva (preko hiljadu, tačnije nekoliko desetina i stotina hiljada), jer imamo 2 ugnježdene petlje obe po nekoliko hiljada (zajedno preko milion prolazaka kroz petlje).
5. Program u odnosu na algoritam smo malo ubrzali (prva petlja ne ide do N nego do N/2) što je duplo smanjilo vreme izvršavanja, ali očigledno ne dovoljno.
6. Kako bi se sami uverili koliko je izvršavanje ovakvog algoritamskog rešenja sporo za velike brojeve, možete da iskoristite algoritam iz priloga u FlowGoritthmu i da unesete najpre male brojeve, zatim oko hiljadu, pa oko 10 hiljada, pa 100 hiljada. Zatim slično uradite sa programskim kodom iz razvojnog okruženja.
7. Vremenska optimizacija programskog koda je možda najteža, jer zahteva puno rada, vežbi, testiranja, proučavanja, analize, kao i dobro poznavanje matematike i algoritamskih metoda. Iskoristićemo ovo takmičenje da postepeno počnemo da učimo i vremensku optimizaciju, posebno kroz ovaj zadatak/primer i veoma važan primer za proste brojeve.
8. Za početak, još jednom pročitajte uputstva koja sam vam poslao pre nekoliko dana, a naročito poslednje korake.
9. Takođe, nije loše da još jednom pregledate osnovne informacije o prostim brojevima i na vikipediji:
   https://sr.wikipedia.org/sr-el/%D0%9F%D1%80%D0%BE%D1%81%D1%82_%D0%B1%D1%80%D0%BE%D1%98
10. U narednim mejlovima poslaću vam prva uputstva za vremensku optimizaciju ovog zadatka, postepeno korak po korak.

Pozdrav,
Dragan Ilić

 

 

----- Original Message -----

From: Dragan Ilic

Sent: Thursday, January 25, 2018 10:47 PM

Subject: Takmicenje iz programiranja 2017 - Kvalifikacije - 2. krug - Zadatak 2 - Trivijalan broj - Algoritamsko resenje (nije optimizovano)

Dragi takmičari,

U prilogu se nalazi algoritamsko rešenje 2. zadataka, ali potpuno neoptimizovano, ipak, najjednostavnije za razumevanje šta se zapravo traži u zadatku.

 

Organizatori takmičenja u ovom zadatku traže vremensku optimizaciju programskog koda, a za tako nešto je potrebno iskustvo, vežba, vereme i poznavanje posebnih alogoritamskih metoda, koje ćemo postepeno početi da učimo od ovog zadatka.

 

Programski kod u prilogu daje tačne rezultate za sve test primere, ali veoma sporo, tako da će osovojiti bodove samo za prva 3 test primera, odnosno 30 bodova, što se možete i sami uveriti do 28.01, tako šte ćete postaviti programski kod iz priloga na:

• https://arena.petlja.org/Competitions/Competition/171

Kako onda da naučimo vremenskiu optimizaciju?

 

Postepeno i polako. Za sam početak koristićemo recimo Excel kao pomoć da bolje uočimo neke nove sličnosti i mešusobnu zavisnost traženih brojeva u zadatku.

 

U prilogu se nalazi i Excel fajl kao pomoć pri rešanju drugog zadatka Trivijalan broj:

• Prikazani su podaci za prvih 1050 (počev od 2) brojeva u 3 kolone: X - prirodan broj (Ai),  S - zbir svih jnegovih pozitivnih delilaca i TB - trivijalnost broja X, odnosno količnih S / X (prikaz podataka u ovoj koloni je na 3 decimale, ali možete namestiti na više 5 ili 6 da bi bolje uočili razlike).
• U samom zadatku X može biti do 5 miliona, a ovde smo prikazali samo do 1050, ali je princip isti.
• Ovaj zadatak možemo da rešimo bez upotrebe nizova i relativno jednostavno, ako ne vodimo računa o vremenskoj optimizaciji, tako što ćemo za svaki broj x pronaći i sabrati sve njegove delioce, a zatim podeliti zbir sa samim brojem i taj količnik proveriti da li je manji od do tada najmanjeg (početni najmanji je 1,5 za broj 2).
• Sve promenljive su celobrojne (LongInt) osim promenljive za količnik i najmanji količnik koje su Real (ne moraju biti double). 
• Tek kada tako rešite zadatak, testirajte za nekoliko test primera i proverite sa podacima u ovoj tabelu u Excel-u (u prilogu).
• Rešenje (bez vremenske optimizacije) će verovatno proći sve test primere, međutim zbog vremenskog ograničenja, sigrno sporo, što znači da će bodove imati samo za nekoliko jednostavnih test primera (sa ne mnogo velikim brojevima).

Tek kada ovako rešite zadatak, ako imate vremena, možete da počnete da razmišljate o vremenskoj optimizaciji postepeno po sledećim koracima:

• Obratite pažnju da su svi količnici u opsegu između 1 i 4, tačnije 3,5.
• Kako se uvek kreće od broja 2, to znači da treba tražiti najmanji količnik u opsegu između 1 i 1,5.
• Obratite pažnju na cikličnu strukuturu za izračunavanje zbira delilaca ne mora da kreće od 1 i da ide do broja x, jer svaka suma u stratu ima početni zbir 1+x, jer je svaki broj deljiv sa 1 i samim sobom. Dakle brojač petlje ne ide od 1 do X, već od 2 do x-1, mada to i nije neka velika vremenska ušteda, ali u ovom slučaju nije ni zanemarljiva, jer za svaki broj x ponavljamo ovu unutrašnju petlju.
• Takođe obratite pažnju da prilikom izračunavanja zbira delilaca nema potrebe da ispitujemo da li je broj x deljiv sa brojevima koji su veći od x/2, jer sigurno nije. To znači da brojač ciklusa može da ide od 2 do x / 2, odnosno x div 2, što već donosi dvostruku uštedu u brzini rada.
• Zatim pređite na Excel fajl i posmatrajte količnije parnih i neparnih brojeva. Šta primećujete?
• Možete i da sortirate podatke po TB u rastućem redosledu, pa ponovo pregledajte sve podatke.
• Posebnu pažnju obratite na proste brojeve. Primetićete da prosti brojevi imaju najmanje količnike koji su uvek (1+x)/x, odnosno 1 + 1/x.
• Takođe, primetićete da, naročito za velike brojeve x, da je glavni deo zadatka da pronađemo prvi prost broj koji je manji od x.
• S obzirim da je trivijalnost broja 2 (kolčinik) 1.5, a broja 3 1,33, sledećeg neparnog i prostog broja 5 1,2 i 7 1,143, a već broja 13 1,077, teško da ćemo naići na neki broj veći od 1000 koji nije prost a čija je trivijanost manja od 1,1, tačnije od 1,077. Pa čak i da postoji, u prvih 1000 brojeva najveći prost broj je 997 čija je trivijalnost 1,001. Dakle, i bez previše matematičkih alata (teorema, dokaza), ali uključujući logiku, testiranje i matemtićko poznavanje prostih brojeva, količnika i uočvanja pravila (rasta ili opadanja vrednosti) možemo prilčno da ubrzamo agloritamsko rešenje.

Pozdrav,

Dragan Ilić