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ć