Danas je završeno 2. kolo ljetne lige C++ za kadete. Zadaci su ovog puta malo pojačani, što možemo i pročitati iz samih rezultata :-).

Ponovno smo naišli na različite i zanimljive pristupe, posebice u trećem zadatku "otoci". 🙂
Isto tako, drago nam je da su nekim natjecateljima svi "pravci" uvijek paralelni :-P, iako nam nije drago da se još uvijek pokušava dijeliti s nulom 🙁
Što se tiče sortiranja stringova, ono je leksičko, te duljina niza nije primarni kriterij (zadatak "Max-suma"), tako da bi poravnanje sa prefiksnim nulama bilo od pomoći, a ne bi bio niti veliki problem uvesti vlastiti kriterij usporedbe…

Slijedi nekoliko dobrih praksi i pravila kojih bi se trebali pridržavati svi natjecatelji pri riješavanju zadataka i predaji rješenja:

1) Valja pripaziti na imenovanje datoteka, ime datoteke s rješenjem se uvijek nalazi pri samom dnu teksta zadatka.
2) Preporuka je radi uniformnosti, prije predavanja rješenja zakomentirati ili obrisati svaku pojavu system("pause"); 
3) Ispis valja završiti u novom retku, dakle zadnji znak koji bi trebalo ispisati je endl. Drugim riječima korisite cout << endl; ili printf("\n");
4) U svakom zadatku su zadana ograničenja (tipovi podataka i veličina podataka), te iste uvijek valja uzeti u obzir.
5) Memorijsko ograničenje je u pravilu 32 MB po zadatku, a vremensko je do 30 sekundi po test primjeru. 

Evo i nekoliko prijedloga koji se tiču tipova podataka te njihovog unosa i ispisa:
– Za cijele brojeve koristimo int (%d)
– Za racionalne brojeve koristiom float (%f), a za racionalne brojeve dvostruke preciznosti double (%lf), koristimo izraz "racionalni", jer realni brojevi ne mogu biti pokriveni budući sadrže i iracionalne brojeve koje u stvarnosti i ne možemo točno zapisati u računalu (ograničeni smo veličinom registra …), a niti na papiru (izuzev simboličkih zapisa)
– za formatirani ispis valja koristiti printf naredbu: npr za racionalni broj zaokružen na 2 decimale pišemo printf("%.2f");
– kada želimo napraviti desno poravnanje brojeva (npr. na 10 mjesta) onda pišemo printf("%10f"); ili printf("%10d");

Za semdaše, a pogotovo osmaše, bilo bi dobro da prouče i izvježbaju određene algoritme,
posebice su zanimljivi BFS: http://en.wikipedia.org/wiki/Breadth-first_search i DFS: http://en.wikipedia.org/wiki/Depth-first_search

Od ostalih, svakako bi trebalo poznavati sljedeće strukture podataka i algoritme:
– Apsolutno sve što se tiče stringova i charova
– Stack, Queue, FIFO i LIFO, vezane liste, cirkularne liste, …
– Longest Common Substring (algoritam za najdulji zajednički podniz)
– Euklidov algoritam najveće zajedničke mjere
– Eratostenovo sito za mapiranje prostih brojeva od 2 – N.
– Rastav brojeva na proste faktore
– Binarno pretraživanje i binarna stabla
– Formule za sumu i pronalazak članova aritmetičkih i geometrijskih nizova
– Algoritam za pronalak težišta poligona
– Algoritmi za izračun presjeka, unije i razlike realnih intervala
– Algoritmi za računanje s velikim brojevima, odnosno zbrajanje, oduzimanje i množenje "stringova"
– Algoritmi za kriptiranje podataka, barem oni najosnovniji – bazirani na XOR-u 🙂
– Dvodimenzionalne matrice su uvijek posebno zanimljive, kretanje čovječuljka i izbjegavanje prepreka je česta pojava 🙂
– C++ strukture pair, vector i map te pripadne metode i iteratore nad tim objektima
– zatim uporaba funkcija sort i reverse (i ostalo iz <algorithm>), kod sort funkcije svakako obratiti pažnju na mogućnost uvođenja vlastite funkcije za usporedbu elemenata (compare function)
– uvođenje vlastitih struktura podataka (typedef struct { .. } )
– kod rekurzivnih rješenja, valja se zapitati da li postoji dinamički pristup (mapiranje izračuna)
– kada sve ostalo zakaže, valja krenuti heurističkim putem :-), a kada i to zakaže, uvijek preostaje brute force i mapiranje rješenja 🙂
…

Evaluacija na ovoj Ljetnoj ligi te na IBT-u za mlađe kadete se vrši pomoćnim evaluatorom, koji radi sljedeće zadaće:

1) Prevodi natjecateljska riješenja sa g++ compiler-om
2) Poziva natjecateljske izvršne verzije (.exe) sa preusmjerenim ulazom na test primjere, te nakon toga se poziva u istom režimu službeno rješenje
3) Test primjeri se izmišljaju ručno ili sa pomoćnim programom koji ih generira, a tada su oni posve nasumični te u granicama zadanim u tekstu zadatka.
4) Provjera ispravnosti rješenja se radi ručnim putem: usporedbom natjecateljskih izlaza sa službenim izlazima
5) Bodovi se mogu dijeliti na način da se priznaju samo potpuno ispravni izlazi, ili se mogu dijeliti djelomični bodovi za djelomična rješenja, a to ovisi isključivo o prirodi samog zadatka. Tako recimo za zadatke koji traže 3 izlaza, može se davati po trećina ili polovina bodova za djelomična rješenja. 

Toliko u ovom osvrtu, puno sreće na preostalim kolima!

Autor zadataka C++