Clasa VII/VIII lecția 9 - 3 dec 2013

From Algopedia
Jump to navigationJump to search

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]