Anunțuri

Următorii elevi se află în situația de a fi eliminați de la cerc:

Nume	Motiv de îngrijorare	Acțiune urgentă
Ioana Manea	Puține teme rezolvate	Trebuie să încerci/rezolvi toate temele de acum înainte
Rareș Rusu	Puține teme rezolvate	Trebuie să încerci/rezolvi toate temele de acum înainte
Maria Rotaru	Puține teme rezolvate	Trebuie să încerci/rezolvi toate temele de acum înainte
Andrei Dragne	Prea multe surse cu extensia .cpp	Prima sursă cu extensia .cpp te va elimina
Matei Lascu	Prea multe surse cu extensia .cpp	Prima sursă cu extensia .cpp te va elimina

Tema - comentarii

La problema disjoint doar şapte elevi au înţeles algoritmul union-find Timofte, Niţu, Demetriad, Căutiş, Florescu, Magan şi Coman. Pe restul îi sfătuiesc să recitească cu atenţie lecţia şi să înceapă să pună întrebări acolo unde nu înţeleg. Pentru aceasta avem clubul înţelepţilor.

La problema disjoint, mulţi dintre voi au implementat ciudăţenii incorecte. Motivul pentru care fac efortul să scriu lecţiile în format electronic, un efort considerabil, este tocmai pentru ca voi să puteţi consulta notele cînd nu aţi înţeles ceva. Tot pentru acest motiv aveţi şi grupul înţelepţilor. Unii din voi aţi luat punctaj maxim folosind alt organ, nu creierul.

Mohanu: codul tău este încîlcit. Nu ai implementat funcţia find. Algoritmul se cheamă Union-Find, îţi aminteşti? Tratezi o mulţime de cazuri aberante. Cel mai grav, n-ai implementat compresia căii, de aceea ai avut TLE. Ora trecută nu ai fost atent. Mulţumeşte-mi că nu scriu aici ce anume ai făcut de n-ai fost atent.
Priboi: la fel, nu ai facut compresia căii. Uimitor că ai luat 100p, problema are teste simple, probabil.
Ulmeanu: ai implementat compresia căii după ureche, adică greşit.
Timofte: corect, bravo. Implementarea compresiei căii este fără memorie suplimentară, frumos. Ţine cont că este puţin mai lentă din motive de copieri suplimentare de variabile.
Niţu: algoritmul este corect. Dar ca stil, este foarte urît să scrii o funcţie union() fără parametri, dar care acţionează asupra unor variabile globale. Frumos era să trimiţi acele variabile ca parametru. Testezi de două ori cerinţa, în loc să foloseşti else. Noi învăţăm algoritmi avansaţi, dar facem greşeli de clasa a 5^a.
Demetriad: algoritm corect şi frumos implementat. Ai grijă că ai un warning, de ce îl ignori? Funcţia unificare trebuia să returneze void nu int.
Căutiş: codul arată bine. Probabil că ratezi un test din cauza acelui sefi[0]=1; care nu are nici un sens.
Florescu: corect, bravo!
Radu Ana-Maria: compresia căii se face de fiecare dată cînd apelezi find (funcţie pe care nu ai implementat-o). Ce ai făcut tu acolo este o ciudăţenie care nu funcţionează. Motiv pentru care iei TLE la cealaltă problemă.
Magan: corect! Compresia căii fără memorie suplimentară, interesant. Interesant şi modul cum eviţi un test memorînd mesajele într-o matrice. Doar că ai făcut şi tu o greşeală de începător: ai dimensionat vectorul de 100000 de elemente apoi lucrezi cu el începînd cu unu.
Sachelarie: te sfătuiesc să reciteşti lecţia şi să începi să pui întrebări pe grup, sau direct mie pe email. N-ai înţeles mare lucru, iar la problema bile3 ai băgat un fill. Tot e bine, pe ăla pare că l-ai învăţat.
Popovici: cod foarte încîlcit, mi-e greu să-l urmăresc. Compresia căii se face de fiecare dată cînd apelezi find. Nu trebuiau separate în două funcţii. Ai multe teste inutile şi încîlcite. Te sfătuiesc să te uiţi pe soluţiile ce vor fi prezentate pe algopedia.
Păcurar: sîntem clasa a 7^a, nu a 5^a. Ştim funcţii, nu repetăm cod în neştire. Altfel greşim şi luăm 30p. Discuţia de la cerc vă cerea să implementaţi explicit cele două funcţii, de ce te opui?
Crăciun: există şi alte coduri de operaţie decît 1 şi 2? Trebuie să reciteşti algoritmul, nu ai înţeles nimic.
Coman: foarte frumoasă implementarea. Dacă reuşeşti să treci de nivelul clasei a cincea cu acele două if-uri în loc să foloseşti un else.
Stanciu: pe lîngă repetiţia de cod aiurea pe care o faci acolo deşi am cerut funcţii, programul tău nu face compresia căii ci altă ciudăţenie. Noroc că testele sînt greşite şi ai luat puncte cu un algoritm incorect.
Lascu: nu faci compresia căii, algoritm incomplet. Dar asta e ultima ta problemă: tu nu indentezi! Îţi sugerez să vii la cerc la clasa a 5^a. De asemenea îţi reamintesc pentru a 34-a oară că limbajul studiat la acest cerc este C, nu C++. Poate de data asta îmi faci o favoare şi reţii?
Icleanu: tu nu faci compresia căii, dar iei 100p pe teste uşoare. Repeţi cod. Funcţiile union şi find sînt aproape identice. Iar în interiorul lor ai, în fiecare, două bucăţi identice. Eşti copy-paste-rul perfect!
Dragne: sursa este C, nu C++. Ţi-am dat zero la problemă, poate te va ajuta cu problemele de memorie (am auzit că şi Cavit-9 ar fi bun). În rest toate problemele menţionate deja: repeţi cod, nu faci compresia căii. Continuă cu surse C++, următoarea va fi şi ultima ta sursă trimisă.
Diaconu: nu faci compresia căii. Nu era opţională.
Rotaru: matematica ţi-a dat aripi. Bilet gratis să nu-ţi faci temele. Pe care oricum le făceai din doi în trei.
Rusu: ce nu faci, nu poţi greşi.

Tema - rezolvări

Rezolvări aici [1]

Lecție

BFS Fill (algoritmul lui Lee)

În anul 1961 C. Y. Lee a publicat un algoritm de studiu al căilor de conectare între două puncte în diagrame electronice. Algoritmul original presupune o rețea plană (un circuit electronic) în care, mulțumită proprietăților curentului electric, toate muchiile sînt de lungime unu. De-a lungul timpului (și aparent mai mult în România) acest algoritm a ajuns să fie asociat cu parcurgerea pe lățime a unei matrice, drept pentru care acesta este modul în care îl voi prezenta aici.

Deoarece algoritmul lui Lee este o parcurgere pe lățime ar trebui predat după conceptul de parcurgere pe lățime. De aceea, în această lecţie, voi încerca să prezint ambele.

Aplicații ale parcurgerii pe lățime

Găsirea drumului minim de la un punct la un altul, sau la mai multe puncte finale.
Mai puțin menționat: fill cu mai puțină memorie suplimentară (dar și mai lent)

Pentru exemplificare, să considerăm următoarea problemă: se dă un labirint codificat ca o matrice cu zero și unu, zero semnificînd loc liber și unu fiind element obstacol (zid). Se dau de asemenea un punct de start și unul de final. În matrice ne putem deplasa pe linie sau pe coloană, cu condiția să nu avem un obstacol. Să se calculeze, lungimea drumului minim între cele două puncte, dacă există un astfel de drum.

Parcurgerea în adîncime

Cînd am discutat despre algoritmul flood fill am menționat că el este o parcurgere a matricei în adîncime, deoarece traversarea elementelor matricei se face avansînd din vecin în vecin pînă ce se ajunge la o fundătură (un obstacol, ieșire din matrice, sau element deja parcurs). Am denumit această parcurgere DFS (depth first search), aceasta însemnînd că în alegerea noului element de vizitat preferăm adîncimea. Ne putem imagina această parcurgere cu un fir subțire de apă care curge într-o direcție oarecare, apoi, cînd nu mai poate schimbă direcția. Cînd ramura curentă se "înfundă" apa se va ramifica din firul principal undeva cel mai aproape de fundătură, acolo unde o poate lua pe altă direcție.

Am menționat atunci că pentru acest tip de parcurgere avem nevoie de o stivă pentru memorarea elementelor ce urmează a fi parcurse. Stiva este fie explicită (nu am vorbit despre aceasta), fie implicită, într-o implementare recursivă. Această stivă are consecințe: ea adaugă O(MxN) memorie suplimentară.

Folosind parcurgerea în adîncime, flood fill, putem răspunde la întrebarea dacă există drum între cele două puncte, dar nu putem calcula drumul minim.

Parcurgerea pe lățime

Prin contrast, ne putem imagina o parcurgere pe lățime. În această parcurgere vom traversa mai întîi elementele vecine cu elementul de start. Apoi vom continua cu elementele vecine cu ele. Și apoi cu elementele vecine cu vecinele, și așa mai departe. Putem vizualiza această parcurgere dacă ne imaginăm că turnăm apă în punctul de pornire. Ea se va împrăștia uniform în toate direcțiile. Dacă va da de obstacole ea va merge de-a lungul lor și le va ocoli. La orice moment distanța între orice punct de pe frontiera apei și punctul de start este aceeași.

Denumim această parcurgere BFS (breadth first search), deoarece în alegerea noului element de parcurs vom prefera lățimea. La fiecare iterație k vom trata elementele aflate la distanță k de punctul original. Ele formează frontiera (marginea) apei, în exemplul nostru. După fiecare iterație frontiera va fi înlocuită cu o nouă frontieră aflată la distanță mai mare cu unu decît vechea frontieră.

Precum vom vedea mai jos această parcurgere este similară cu cea în adîncime, diferența fiind că ea folosește o coadă în loc de stivă pentru memorarea elementelor ce urmează a fi parcurse. Spre deosebire de flood fill, coada trebuie să fie explicită. De aceea algoritmul poate părea foarte diferit de flood fill, dar, în realitate nu este.

Implementarea parcurgerii pe lățime în matrice

Cum implementăm parcurgerea pe lățime? Cum memorăm frontiera? O idee imediată ar fi să ținem două frontiere: cea curentă, în curs de procesare, și cea nouă, în curs de generare. La fiecare iterație calculăm o nouă frontieră pe baza celei din-nainte. Apoi comutăm pe frontiera cea nouă. Ce conțin frontierele (ce stocăm)? Vom păstra identificatorii unici ai elementelor matricei, respectiv linia și coloana. Frontierele vor fi vectori de perechi (linie, coloană). Această metodă funcționează, dar nu este nici cea mai simplă și nici cea mai economică ca memorie.

În practică nu vom face distincția între frontiera veche și cea nouă. Elementele din frontiera nouă vor fi adăugate la frontiera veche, la sfîrșit. Vom avea astfel o singură frontieră de elemente de procesat. Vom procesa elementele de la începutul frontierei și vom adăuga elementele noi, vecinii, la finalul frontierei. În imaginea noastră cu apa punctele procesate vor descrie o spirală în jurul punctului de pornire.

În acest fel ajungem la structura de date pe care o vom folosi pentru stocarea punctelor de frontieră: coada. Așa cum am menționat mai sus, în loc de stivă vom folosi o coadă de perechi (linie, coloană) pentru stocarea elementelor ce urmează a fi parcurse. La un pas vom extrage din coadă primul element și vom adăuga elementele vecine lui la finalul cozii, cîtă vreme ele nu se află deja în coadă (coada conține numai elemente unice).

Algoritmul de parcurgere BFS

Iată o schiță de algoritm, care nu este neapărat universal valabil, dar poate fi adaptat diverselor situații:

Inițializează matricea labirint L[][] cu 0 pentru loc liber și -1 pentru obstacol Marchează cu 1 punctele de final (destinație) în matricea T[][] (restul sînt zero) Inițializează coada cu elementul de pornire (lstart, cstart) Setează L[lstart][cstart] <- 1 // distanța inițială Execută: Scoate primul element din coadă. Fie el linia (lin, col) Setează dist <- L[lin][col] // distanța acestui element Pentru fiecare vecin (l, c) al lui (lin, col) Dacă L[l][c] = 0 // nu se află în coadă și nici nu este obstacol Adaugă (l, c) în coadă Setează L[l][c] <- dist + 1 Cîtă vreme coada nu este vidă și T[lin][col] == 0 Afișează L[lin][col] // distanța pînă la cel mai apropiat punct destinație

Note de implementare

Vecinii unui element din matrice pot fi fie cei adiacenți pe linie și coloană, fie și cei pe diagonală, algoritmul funcționează la fel.
De obicei vom folosi tehnicile invățate:
- Bordarea matricelor pentru a scăpa de testul de ieșire din matrice
- Vectorii de direcție pentru a genera ușor vecinii
Problema poate fi considerată una de simulare: simulăm parcurgerea tuturor traseelor în același timp.
Dacă nu există drum între cele două puncte algoritmul se va termina cînd coada devine goală.
Coada poate fi parcursă pînă la final, sau ne putem opri cînd anumite condiții ale simulării au fost îndeplinite, cum ar fi atingerea punctului destinație.
Cum știm dacă un element se mai află deja în coadă? Printr-o matrice de frecvență: la momentul adăugării în coadă vom marca aceasta în matrice. De cele mai multe ori putem combina matricea de frecvență cu matricea de distanțe: un element diferit de zero semnifică distanța acelui element la punctul de start. În această notație obstacolele trebuie memorate ca numere negative pentru a nu fi confundate cu distanțe.
Cum știm că am ajuns în punctul final? Putem să testăm explicit linia și coloana. Dar dacă avem mai multe puncte finale trebuie să le marcăm într-o matrice. Această matrice se poate de obicei combina cu matricea de frecvență și cu cea de distanțe, deoarece avem nevoie doar de un bit unu sau zero.
Pentru a reconstitui un drum minim vom porni de la destinație și vom avansa în L[][] pe elemente descrescătoare din unu în unu, pînă ce ajungem la sursă. Atenție, drumul nu este neapărat unic.
Algoritmul poate fi adaptat să calculeze drumul minim de la mai multe puncte de pornire la mai multe puncte destinație. În acest caz vom inițializa coada cu toate punctele de pornire.

Implementarea cozii de coordonate

Vezi și lecția din urmă despre coadă.

Pentru coadă vom folosi un vector circular de mărime 2(M+N) (vezi explicația la capitolul de complexități). Vom avea o variabilă, prim care păstrează indicele de adăugare în coadă, precum și o variabilă ultim care păstrează poziția primului element "gol", în afara cozii. Acești doi indici vor avansa circular, modulo mărimea cozii.

Coada poate să fie un vector de elemente tip struct, sau doi vectori separați. Prima variantă este mai bună din punct de vedere cache, dar poate duce la risipă de memorie în anumite situații, dacă elementul de tip struct nu ocupă un număr de octeți divizibil cu patru (sau cu lungimea cuvîntului de memorie).

Vom folosi trei funcții:

enqueue( lin, col ) care adaugă elementul (lin, col) în coadă
dequeue( lin, col ) care extrage elementul (lin, col) din coadă
emptyqueue() care returnează 1 dacă coada este vidă

Iată o posibilă implementare:

int prim, ultim;
struct cel { int l, c; } coada[NCOADA];

// adauga coordonate in coada
void enqueue( int l, int c ) {
  coada[ultim].l = l;
  coada[ultim].c = c;
  ultim = (ultim + 1) % NCOADA;
}

// scoate primul patrat din coada
void dequeue( int *l, int *c ) {
  (*l) = coada[prim].l;
  (*c) = coada[prim].c;
  prim = (prim + 1) % NCOADA;
}

// returneaza 1 cind coada este goala
inline int emptyqueue() {
  return prim == ultim;
}

Complexități în timp și spațiu

Timpul de execuție este O(MxN) deoarece fiecare element al matricei va fi luat în calcul cel mult o dată.

Memoria necesară este O(MxN) deoarece avem nevoie de matricea de distanțe, matricea de frecvențe și cea de puncte terminale, precum și memoria ocupată de coadă. În realitate, de cele mai multe ori putem unifica matricele suplimentare, unindu-le cu matricea labirint. În acest caz memoria suplimentară este cea a cozii. La momentul cînd scriu aceste rînduri nu am găsit o estimare asupra dimensiunii maxime a cozii necesare. Intuitiv ea este O(M+N), deoarece frontiera, într-un labirint fără obstacole, cînd punctul de pornire este în mijloc, nu va depăși M+N. Este neclar dacă o altă matrice și un alt punct de pornire o poate face să depășească M+N și cu cît. Ca practică de implementare sfatul meu este să o dimensionați de 2(M+N), acoperitor, deoarece este un număr oricum mult mai mic decît matricea deja stocată, MxN.

Datorită consumului atît de mic de memorie suplimentară, algoritmul lui Lee poate fi folosit ca și ca algoritm de fill pe matrice mari, sau cînd memoria suplimentară este mică. El va fi însă mai lent decît flood fill, de obicei de multe ori (20-30 de ori), ceea ce dovedește încă o dată că, pentru unii algoritmi, memoria suplimentară se traduce în timp de execuție mai mic.

Tema

Clasa a 7-a

Tema 26 clasa a 7^a
Opţional: participaţi la concursul de clasa a 8^a. Rezolvaţi apoi tema de clasa a 8^a.

Clasa a 8-a

Concurs clasa a 8^a
Tema 26 clasa a 8^a (aceleaşi probleme de la concurs)

Clasa VII/VIII lecția 26 - 24 mar 2015

Contents