Clasa VII/VIII lecția 9 - 3 dec 2013
Tema - rezolvări
Rezolvări aici[1]
Lecție
Elevii în probe au trimis teme astfel:
Nume | Problema 1 | Problema 2 |
---|---|---|
Bonciocat Ciprian | decodare | pom |
Cioltan Alex | ||
Coman Mara | decodare | pom |
Enache Adelina | decodare | pom |
Ionescu Victor | ||
Moanță Victor | ||
Moroianu Theodor | ||
Niculescu Tudor | pom | |
Vasilescu Andreea | decodare (cu probleme) | |
Vecerdea Dragoș | decodare (cu probleme) | |
Zaharia Andreea |
Comentarii rezolvări
General
- Vasilescu, Vecerdea: vreau sursa C (nu C++) elegant. Fără freopen, indentată corect, etc. Citiți regulamentul cercului pentru lămuriri suplimentare.
Decodare
- Mucenic: calcul combinări cu înmulțiri, riști depășire, folosește triunghiul lui Pascal.
- Vasilescu: e OK să te ajute cineva, dar trebuie să înțelegi rezolvarea. Codul trebuie să fie în stilul cercului, fără freopen și cu indentare! Ai warnings de compilare!
Pom
- A fost greu și v-ați complicat cu toții. Este OK, e primul vostru program de parsing. Cine vrea să încerce, ca distracție, implementați evaluarea unei expresii cu paranteze. Este un program clasic care apare la olimpiadele de liceu.
- Enache: stiva. Merge pe cazuri simple. Dar programul iese greoi de scris, greoi de depanat și usor de greșit. Atitudinea ta trebuie să fie să îți dorești să înveți ceva nou. Altfel de ce mai vii la cerc?
Rezolvări probleme date la barajele Șumen, în continuare.
Problema avioane
Problema avioane este o problemă tipică de analiză amortizată. Folosește o stivă standard de maxime văzute pînă în prezent pentru a determina limitele înălțimilor vizibile. Singura adăugare față de standard este căutarea în stiva de maxime a înălțimii avionului, care trebuie făcută prin căutare binară, deoarece căutarea liniară ar duce la depășirea timpului. Vom face două treceri prin vector, una într-o direcție și cealaltă în cealaltă direcție, pentru a determina, pe rînd, limitele stînga-dreapta. Desigur că va trebui să stocăm întrebările într-o structură care să ne permită să le parcurgem în ordine crescătoare și descrescătoare. O soluție e să le sortăm, o soluție mai bună este să le memorăm într-o listă de înălțimi per poziție.
O optimizare importantă de implementare este ca cele două treceri, fiind foarte similare, să le scriem într-o bucla for cu două iterații, una cu direcție pozitivă, alta cu direcție negativă. Țineți minte această regulă, nu este bine să duplicați cod cu copy/paste. Este o practică inacceptabilă în industrie, iar la olimpiadă este foarte riscantă, deoarece adesea se va întîmpla să aveți nevoie de modificări ale codului ulterioare copy/paste și veți uita să faceți modificările în toate copiile. 'Mie nu mi se poate întîmpla așa ceva'. Sînteți siguri? Mai bine obișnuiți-vă să codați corect, cu aceste obișnuințe veți rămîne toată viața.
Complexitatea timpului de rulare este O(n + q log n). În varianta cu liste memoria folosită este O(n + q).
Problema capitala
Problema capitala este o problemă destul de clasică de arbori fără rădăcină și parcurgere pe lățime, numită și BFS (breadth-first search). Vom porni cu toate frunzele in coadă, frunzele avînd distanță zero. Apoi vom procesa coada în mod clasic. Pentru fiecare nod adăugat în coadă vom calcula distanța la frontieră ca distanța nodului tată plus unu. Ne oprim cînd coada este goală pentru că am procesat toate nodurile. În timpul parcurgerii BFS putem calcula și distanța maximă precum și nodurile aflate la distanță maximă. La final facem o parcurgere suplimentară pentru a afișa nodurile aflate la distanță maximă. Soluția este O(n) atît ca timp cît și ca memorie și deci va trece toate testele.
O soluție alternativă, care aproape trece toate testele, se bazează pe DFS (depth-first search): ea pornește o primă parcurgere dintr-un nod interior, calculînd în postordine distanțele: fiecare nod va avea ca distanță la frontieră minimul dintre distanțelor copiilor plus 1. După această parcurgere avem distanțele corecte pentru toate nodurile mai puțin cele a căror distanță minimă se realizează prin părinte. Drept care vom efecuta o a doua parcurgere DFS în care propagăm distanțele din părinte în copii și le actualizăm dacă sînt mai mici. La final distanțele calculate sînt cele finale. Deși această rezolvare este tot O(n) atît ca timp cît și ca memorie ea depășește cu puțin memoria permisă din cauza stivei DFS.
Temă
Problemele discutate în clasă:
Rezolvări aici[2]