Fulgerică - rezolvare

Problema cere să se spună dacă dintr-un milion de numere avem maxim 1000 de valori distincte.

Comentarii

Mulți ați dat soluția forță brută.
Majoritatea care ați dat o soluție, forță brută sau nu, nu ați analizat, sau ați analizat parțial complexitatea în timp. Nu ați făcut înlocuiri, sau le-ați făcut dar nu ați făcut calculele. Nu ați tras o concluzie, intră în timp sau nu?
După aproape doi ani de analiză la fiecare algoritm și problemă prezentată, este inacceptabil să nu fiți în stare să analizați un algoritm simplu.
Mulți dintre voi nu ați făcut analiza memoriei algoritmului vostru. Intră în memorie sau nu?
Unii dintre voi nu știu că un long long are 8 bytes, nu 4 bytes. Și vreți să fiți la IQ Academy? Vă admir voința, în acest caz :-)
Mulți dintre voi mi-ați scris că 8·1000=8KB. Ar trebui să știți că nu este așa. 8KB=8192B. Dacă scriați "aproximativ" era OK.
Concluzia dureroasă este că unii din voi nu sînt capabili să facă calcule de memorie.
Din cei care ați găsit un algoritm bun, cu căutări binare și deplasări, doar Ghica s-a prins că deplasările nu sînt K² operații, ci K²/2 ceea ce înjumătățește numărul de operații.

Clasament

Nr.	Nume	F1	F2	Total
1	Ghica	85	95	180
1	Petrescu	100	80	180
3	Ipate	100	50	150
4	Tatomir	90	45	135
5	Voicu M	100	15	115
6	Dobre	95	15	110
6	Iordache	100	10	110
6	Rebengiuc	10	100	110
9	Mușat	0	95	95
10	Nicu	0	90	90
11	Voicu T	0	80	80
12	Nicola	0	50	50
13	Fares	0	45	45
14	Ruginiș	15	20	35
15	Badea	10	15	25
16	Stancu	0	20	20
17	Petcu	5	14	19
18	Grecu	0	18	18
19	Ilie	0	15	15
19	Marcu	5	10	15
19	Mocanu	0	15	15
19	Ștefănescu	0	15	15
23	Aizic	0	10	10
23	Asgari	0	10	10
23	Cadîr	0	10	10
23	Calotă	0	10	10
23	Dimulescu	0	10	10
23	Teodorescu	0	10	10
29	Benescu	0	5	5
29	Chivu	0	5	5
31	Burac	0	0	0
31	Cojocariu	0	absent	0
31	Hossu	0	motivat	0
31	Popescu	0	0	0
31	Togan	0	0	0

Tema - rezolvări

Disjoint

Problema disjoint este educativă. Rostul ei este să vă puteţi testa implementarea algoritmului union-find.

Channels

Problema channels a fost dată la concursul de la Shumen 2012, juniori.

Comentarii generale

V-ați descurcat bine, bravo! Pare că ați înțeles algoritmul union-find.
Foarte mulți dintre voi ați numărat la final cîțe mulțimi disjuncte rămîn. Acest număr se putea calcula pe parcurs.

Soluţia union-find

Vom parcurge muchiile în orice ordine, folosindu-le doar dacă au lăţimea cel puţin k şi dacă nu creează cicluri. De fiecare dată cînd folosim o muchie numărul de componente disjuncte scade cu unu. În final, numărul rămas minus unu este chiar răspunsul căutat. Folosind union-find complexitatea este aproximativ O(m). Este cea mai simplă soluţie.

Iată o soluţie bazată pe union-find (35 linii de cod efectiv):

#include <stdio.h>

#define WSHIFT (1024*1024)
#define NSHIFT 1024

int sef[1001];     // vectorul de sefi ai nodurilor
int canal[100000]; // vector de stocare a muchiilor: 8 biti latimea, iar
                   // nodurile cite 10 biti fiecare, 28 de biti total

// algoritmul clasic de find (folosim zero ca marker pentru sef suprem)
int find( int nod ) {
  if ( sef[nod] == 0 )
    return nod;
  return sef[nod] = find( sef[nod] );
}

int main() {
  FILE *fin, *fout;
  int n, m, i, j, w, k, c, conexe;

  fin = fopen( "channels.in", "r" );
  fscanf( fin, "%d%d", &n, &m );
  for ( c = 0; c < m; c++ ) {
    fscanf( fin, "%d%d%d", &i, &j, &w );  // citim o muchie
    canal[c] = w * WSHIFT + i * NSHIFT + j; // o stocam in vector, codata
  }
  fscanf( fin, "%d", &k );
  fclose( fin );

  conexe = n; // numarul curent de componente conexe (disjuncte)
  for ( c = 0; c < m; c++ ) // parcurgem muchiile
    if ( (canal[c] / WSHIFT) >= k ) { // daca latimea >= k, muchie folosibila
      i = find( (canal[c] / NSHIFT) % NSHIFT ); // reprezentantul primului nod
      j = find( canal[c] % NSHIFT );            // reprezentantul nodului 2
      if ( i != j ) { // daca nu fac parte din aceeasi componenta conexa
        sef[j] = i;   // le unim
        conexe--;     // numarul de componente conexe se micsoreaza
      }
    }

  fout = fopen( "channels.out", "w" );
  fprintf( fout, "%d\n", conexe - 1 ); // atitea muchii mai avem de largit
  fclose( fout );

  return 0;
}

Ce complexități avem?

Citirea canalelor este O(m). Apoi, pentru fiecare canal vom efectua două operații find(), care au complexitate practică O(1). Rezultă că timpul de execuție este O(m). În realitate inițializarea vectorului de șefi durează și ea, deci mai corect ar fi O(m + n).

Dar memoria?

În mod normal am avea nevoie doar de vectorul de șefi, adica circa 4KB. Din nefericire, deoarece k se dă la final, sîntem nevoiți să memorăm canalele. Stocarea din programul de mai jos încearcă să economisească spațiu, folosind un întreg per canal. Astfel, avem O(m + n) memorie, sau, mai precis, circa 400KB.

Pentru cei avansați și curioși, voi discuta mai jos două soluții care ies din cadrul lecțiilor noastre.

Soluţia forţă brută

Această problemă poate fi rezolvată cu forță brută! Deoarece avem suficientă memorie la dispoziție putem să memorăm graful, în ce formă dorim. Vom ignora muchiile care au lățime mai mică decît k. Pe acest graf trebuie să aflăm numărul de componente conexe. Este clar că numărul de muchii ce trebuie lărgite este numărul de componente conexe minus unu. Cum aflăm componentele conexe? Printr-o parcurgere DFS (parcurgere în adîncime, ca la flood-fill).

Complexitatea acestei soluţii este O(m + n) dacă reprezentăm graful cu liste de adiacenţă, sau O(n²) cînd reprezentăm graful matricial. Ambele se vor încadra în timp.

Soluţia comisiei

Se construieşte un arbore parţial de cost maxim (nu minim). Pentru aceasta folosim unul din algoritmii clasici, de exemplul algoritmul lui Kruskal. Vom sorta muchiile şi le vom parcurge după lăţime, în ordine descrescătoare. Vom alege o muchie doar atunci cînd nu creează un ciclu. Ne oprim atunci cînd arborele este complet (are n-1 noduri). De asemenea contorizăm cîte muchii am ales care au lăţimea mai mică strict decît k. Acela este numărul muchiilor care trebuie lărgite.

Acest algoritm are complexitatea O(m log m) pentru sortare şi apoi aproximativ O(m) pentru parcurgerea muchiilor, folosind algoritmul union-find. Deoarece lăţimile sînt mici (maxim 200) putem face o sortare mai eficientă, gen bucket sort, ceea ce reduce complexitatea sortării la O(m + k).

Soluția comisiei este cea mai complicată, ceea ce ne arată că și la case mari se mai întîmplă.

Bile3

Problema bile3 a fost preluată de pe site-ul infoarena. Este o problemă de Union-Find în sens invers.

Comentarii generale

A fost o problemă ceva mai grea.
Unii din voi nu au folosit vectori de direcție și au duplicat mult cod.

Tema opțională - rezolvări

Flota

Problema flota a fost dată la cercul de informatică, clasa a 10^a. Ea este o aplicație poate nu chiar evidentă de union-find.

Ruine

Problema ruine a fost dată la cercul de informatică, clasa a 10^a. Este o problemă clasică de Union-Find invers.

Rezolvări aici [1]

Lecţie - Tehnici de programare: divide et impera

<html5media height="720" width="1280">https://www.algopedia.ro/video/2019-2020/2020-01-30-clasa-7-lectie-info-19-720p.mp4</html5media> Denumită și divide and conquer sau dezbină și stăpînește, este o tehnică cunoscută de mii de ani conducătorilor. Este o tehnică de cucerire sau menținere a puterii asupra unui grup care ar avea putere mai mare dacă s-ar uni. Ținînd acel grup dezbinat, fiecare facțiune în parte are putere mică și poate fi cucerită, sau condusă. Tehnica a fost aplicată de Cezar, Napoleon, iar, mai recent, de către Britanici în Africa și de către Stalin în Rusia. Dintre tehnicile folosite în lumea reală putem menționa:

Ajutorarea și promovarea celor care cooperează cu puterea, pedepsirea celor ce nu cooperează.
Încurajarea cheltuielilor prostești, pentru a reduce capitalul disponibil organizării sau luptei.
Încurajarea divizării oamenilor pentru a preveni formarea alianțelor.
Încurajarea turnătorilor, cei care trîmbițează orice alianță posibil periculoasă.
Sădirea de neîncredere între oameni.

O parte din aceste tehnici se regăsesc și în țara noastră, precum și în majoritatea țărilor lumii, inclusiv cele dezvoltate. De exemplu, toate țările lumii folosesc un număr uriaș de taxe și impozite, fiecare din ele relativ mici. Cînd le însumăm constatăm că în jur de 90% din banii noștri se duc pe aceste taxe și impozite. Dacă ar exista o taxă unică de 90%, oamenii s-ar revolta. Astfel, tehnica de împărțire a unor taxe mari în mai multe taxe mici îi face pe oameni să nu le observe și să nu se revolte.

Pentru exemple clasice de folosire a acestei tehnici în lumea reală vizitați pagina de divide et impera a wikipediei.

Tehnica divide et impera (divide and conquer) în informatică

În informatică divide et impera constă în împărțirea problemei în subprobleme mai mici, nesuprapuse (o tehnică în care subproblemele sînt suprapuse este programarea dinamică). Fiecare din aceste subprobleme se rezolvă separat, mai ușor, deoarece sînt mai mici. Rezultatul final se obține din combinația rezultatelor subproblemelor.

Tehnica divide et impera simplă (decrease and conquer)

În următoarele exemple de divide et impera problema se reduce la o singură problemă, mai mică. Este un caz degenerat, în care implementarea poate fi iterativă (nu necesită recursivitate).

Algoritmul lui Euclid

Și acest binecunoscut algoritm poate fi văzut ca un exemplu de divide et impera. El reduce problema de la cmmdc(a, b) la o problemă mai mică, cmmdc(b, a mod b). Complexitate: O(log min(a, b)).

Căutare binară

Precum știm, căutarea binară împarte vectorul original în două, apoi decide care din cele două jumătați ar putea să conțină elementul căutat. Apoi rezolvă problema mai mică. Complexitate: O(log n).

Căutare punct fix

Se dă un vector sortat de n elemente întregi distincte. Să se găsească dacă există indicele i astfel încît v[i] == i. Găsiți un algoritm divide et impera care are complexitate O(log n).

Puzzle balanţă

Avem 25 de bile care arată identic, una este ceva mai ușoară. Avem la dispoziție o balanță. Găsiți bila mai ușoară din trei cîntăriri.

Selecția

Complexitate: pe medie O(n), în cel mai rău caz O(n²). Este necesară la problema antitir.

Probleme vianuarena

Următoarele probleme de la vianuarena sînt de divide et impera degenerat:

Tehnica divide et impera propriu zisă

În următoarele exemple de divide et impera problema se reduce la două sau mai multe probleme mai mici. Implementarea este mult mai simplă dacă folosim recursivitate.

Puzzle pavare

Se dă o grilă de 2ⁿ x 2ⁿ pătrate din care lipsește un pătrat. Să se acopere cu piese formate din 3 pătrate aranjate în formă de litera L.

Problema pare destul de grea, nu? În realitate, odată ce încercăm să folosim divide et impera ea devine destul de ușoară. Cum putem împărți problema în probleme mai mici?

Să definim o problemă astfel:

P(n, gol) = pavează un pătrat de latură 2ⁿ care are un pătrățel lipsă (un gol).

O primă idee ar fi să încercăm să împărțim pătratul în patru pătrate de latură 2^n-1 și să rezolvăm acele probleme. Avem, însă, o dificultate: doar unul din pătrate va avea un pătrățel lipsă. Celelalte trei vor fi pline. Ce ne facem?

Am putea încerca să eliminăm artificial cîte un pătrățel din celelalte trei pătrate. Cum putem face acest lucru? Cu condiția ca cele trei pătrățele să fie în formă de L și să le acoperim cu o piesă elementară. Ei bine avem cum să alegem pătratele în acest fel: le vom selecta pe cele de la centru! Astfel vom obține subproblemele:

P(n, l, c) se descompune în:
   P(n-1, gol) (golul original)
   P(n-1, gol1)
   P(n-1, gol2)
   P(n-1, gol3)

Mergesort

Algoritmul mergesort, sau sortare prin interclasare, funcționează astfel:

Divide vectorul de sortat în două părți egale (sau aproape egale)
Reapelează mergesort pe acele părți
La revenire avem două jumătăți sortate, deci putem sorta vectorul interclasînd cei doi vectori în timp liniar

Iată un algoritm:

mergesort( V[], i, j )
  mij = (i + j) / 2;
  daca i < mij
    mergesort( V[], i, mij )
  daca mij + 1 < j
    mergesort( V[], mij + 1, j )
  merge( V[], i, mij, j )

merge( V[], i, mij, j ) interclasează vectorii sortați V[i..mij] și V[mij+1..j].

Ce complexitate are mergesort?

Să calculăm numărul de operații, T(N), pentru a sorta un vector de N elemente:

T(N) = 2 · T(N/2) + N
T(N) = 2 · (2 · T(N/4) + N/2) + N
T(N) = 4 · T(N/4) + 2 · N
T(N) = 4 · (2 · T(N/8) + N/4) + 2 · N
T(N) = 8 · T(N/8) + 3 · N
...
T(N) = N · T(N/N) + log N · N
T(N) = N · T(1) + log N · N

Deoarece T(1) este O(1) rezultă o complexitate O(N + N log N) = O(N log N).

Cîtă memorie suplimentară folosește algoritmul?

Pentru interclasarea clasică avem nevoie de un alt vector, deci O(N).

În concluzie avem complexitățile:

timp: O(n log n)
memorie suplimentară: O(n) (aceasta e problema principală a algoritmului).

Există variante ale algoritmului care folosesc mai puțină memorie (o idee evidentă este să folosim doar jumate din memorie deoarece în timpul interclasării putem suprascrie una din jumătăți).

Aplicație mergesort - inversiunile unei permutări

O problemă care apare uneori la concursuri este următoarea: se dă o permutare a numerelor de la 1 la N. Să se numere cîte inversiuni are ea. O inversiune este o pereche de indici (i, j) astfel încît i < j și P[i] > P[j].

În linii mari, algoritmul este următorul:

Sortăm prima jumate a vectorului folosind un mergesort special, care ne returnează numărul de inversiuni din vectorul de sortat.
Sortăm a doua jumate a vectorului.
În acest moment știm inversiunile din cele două jumătăți - le adunăm.
Interclasăm cele două jumătăți. În timpul interclasării cînd selectăm un număr din prima jumătate știm că numerele deja selectate din jumătatea a doua sînt mai mici, deci putem aduna numărul lor la numărul total de inversiuni.

Quicksort

Algoritmul quicksort, sau sortare rapidă, inventat în 1959 de informaticianul britanic Tony Hoare, funcționează astfel:

Alege o poziție la întîmplare din vectorul de sortat. Vom denumi valoarea de la acea poziție pivot.
Rearanjează vectorul astfel încît în prima parte să avem elemente mai mici sau egale cu pivotul iar în a doua parte elemente mai mari sau egale cu pivotul. Vom denumi acest pas pivotare.
Reapelează quicksort pe acele două părți

Din acest algoritm avem de lămurit pasul de pivotare. El este același ca la quickselect, prezentat într-o lecție anterioară. El procedează astfel:

Pornește cu doi indici, unul la începutul vectorului și unul la final de vector, să le spunem b si e.
Avansează indicele b pînă la primul element mai mare sau egal cu pivotul
Devansează (merge înapoi) indicele e pînă la primul element mai mic sau egal cu pivotul
Interschimbă elementele din vector de la pozițiile b și e
Repetă pînă ce indicii se ating, b >= e

Iată o implementare posibilă. Ea este implementarea originală a lui Hoare, transformată pentru a fi structurată:

void myqsort( int begin, int end ) {
  int aux, b = begin, e = end,
    pivot = v[(begin + end) / 2]; // poate fi orice pozitie intre begin si end - 1

  while (v[b] < pivot) // cauta primul element mai mare sau egal cu pivotul
    b++;

  while (v[e] > pivot) // cauta primul element mai mic sau egal cu pivotul
    e--;

  while( b < e ) { // daca indicii nu s-au atins
    aux = v[b];    // interschimba elementele la pozitiile b si e
    v[b] = v[e];
    v[e] = aux;
    
    do // cauta primul element mai mare sau egal cu pivotul
      b++;
    while (v[b] < pivot);

    do // cauta primul element mai mic sau egal cu pivotul
      e--;
    while (v[e] > pivot);
  }

  // acum [begin..e] sint mai mici sau egale cu pivotul
  if ( begin < e )
    myqsort(begin, e);
  // si [e+1..end] sint mai mari sau egale cu pivotul
  if ( e + 1 < end )
    myqsort(e + 1, end);
}

Ce complexitate are quicksort?

Deoarece pivotarea este liniară, calculele sînt similare cu cele de la mergesort. Avem două diferențe:

Procesarea liniară se face la început, înainte de recursie.
Împărțirea vectorului nu este neapărat în două părți egale, ceea ce duce la o complexitate O(N²) pe cazul cel mai rău.

Pentru cazul mediu, cînd împărțirea este în două părți aproximativ egale, rezultă aceeași complexitate O(N log N).

Cîtă memorie suplimentară folosește algoritmul?

Memoria este cea necesară stivei. E va fi, deci, proporțională cu cel mai lung lanț de apeluri recursive imbricate. Pe cazul cel mai rău el este O(N), iar pe cazul mediu este O(log N)

Optimizare: putem reduce cazul cel mai rău astfel:

Observăm că al doilea apel recursiv este recursiv la coadă.
Precum știm, el nu va consuma memorie.
Putem reduce memoria stivei apelînd mai întîi pentru partea mai mică ce rezultă după pivotare.
În acest fel chiar și în cazul cel mai rău memoria suplimentară necesară va fi O(log N).

În concluzie avem complexitățile:

timp: O(N log N)
memorie suplimentară: O(log N)

Atenție: deși putem selecta ca pivot orice element din vector, nu putem selecta ca pivot ultimul element. Aceasta ar duce la o buclă infinită.

Pivotarea Lomuto

În școli, de multe ori se predă un alt algoritm de pivotare, probabil deoarece este considerat mai simplu. Nu o vom discuta aici, deoarece este foarte ineficientă. Iată diferențele față de pivotarea Hoare:

Lomuto este ceva mai simplu de reținut și ceva mai scurtă.
Ambii algoritmi sînt cache friendly deoarece parcurg liniar vectorul.
Lomuto face de trei ori mai multe interschimburi.
Lomuto face O(N²) operații pe un vector sortat, Hoare doar O(N log N)
Lomuto face O(N²) operații pe un vector cu elemente egale, Hoare doar O(N log N)

Concluzie: Pivotarea Lomuto este un algoritm didactic, bun pentru înțelegerea pivotării, dar este contraindicat într-o implementare practică.

Randomizarea pivotului

Dacă alegem ca pivot prima poziție din vector, sau cea din mijloc, "adversarul" poate, studiind algoritmul, să găsească un vector special pe care implementarea noastră să intre pe cazul cel mai rău, O(N²). Putem lupta cu aceasta, alegînd pivotul pe o poziție aleatoare din intervalul [begin..end-1].

Probleme quicksort

Atenție! Algoritmul este celebru pentru bug-urile pe care le putem introduce la implementare. Un semn mai mic transformat în mai mic sau egal poate duce la bucle infinite sau la un vector nesortat.

Soluție: pentru olimpiadă este bine să memorați algoritmul pe din-afară.

Ați putea spune "hei, dar la olimpiadă pot folosi algorithms!" Este opțiunea voastră, dar eu nu aș risca. Motivele împotriva folosirii funcției de sortare de bibliotecă:

Ea primește ca parametru o funcție de comparație. Apelul acelei funcții este lent, fiind vorba de accesul unui pointer pentru a obține adresa funcției, apoi de punerea pe stivă a parametrilor. Toate acestea se reduc la o comparație sau două în codul nostru.
Funcția de bibliotecă este o cutie neagră. Ea depinde de compilator și de biblioteca de funcții a acestuia. Ea este scrisă de alți oameni. Aveți mai multă încredere în cod scris de alții, care variază în funcție de calculatorul pe care se face evaluarea?
În mod uzual funcțiile de bibliotecă consumă mai multă memorie, iar uneori mult mai multă. De ce? Bună întrebare. Nu știu.
Algoritmul de mai sus are 23 de linii de cod efectiv. El este simplu și eficient și poate fi adaptat să sorteze orice tip de date, cu mici modificări. De ce am risca să apelăm o funcție de bibliotecă despre care nu știm nimic, cînd în 3 minute am scris acest cod?

Ziua regelui

Un rege organizează o petrecere mare de ziua lui. Petrecerea începe peste 24 de ore. Regele află că una din cele 1000 de sticle de vin pe care le va servi este otrăvită. Otrava acționează ciudat: omul care bea chiar și cea mai mică cantitate din această otravă nu are nici un simptom vreme de 24 de ore, apoi moare subit. Regele are sclavi la dispoziție pe care îi poate folosi. Lui nu îi pasă cîți sclavi mor, dar îi pasă cîți sclavi beau vin, deoarece un sclav care a băut vin nu poate fi folosit la treabă, ci trebuie izolat spre observare. Care este numărul minim de sclavi cu care regele poate afla sticla otrăvită?

Probleme temă

Problemele de la temă sînt probleme de divide et impera propriu zise:

latin dată la cercul de informatică Vianu, gimnaziu 2013
pav dată la Lot IS 2008
forma dată la olimpiada pe sector 2012, clasa a 8^a
hanoi1

Fulgerică (test fulger)

Găsiți un algoritm la următoarea problemă și explicați-l pe o foaie de hîrtie. Dacă nu vă descurcați să îl explicați puteți scrie cod. Sau formule matematice. Sau puteți scrie din toate trei. Important este ca algoritmul să se înțeleagă și să fie corect. Atenție! Spre deosebire de varena, vi se cere un algoritm corect, echivalentul unei rezolvări care să treacă toate testele. Nu gîndiți la modul "cum fac să iau cît mai multe puncte". Nu se acceptă "mînăreli". Voi corecta lucrările personal. Nu vă concentrați pe citire, sau scriere.

Problema Gigel

Fie următorul număr în baza 16:

X = 123456789ABCDEF

Gigel vă ia din acest număr un subnumăr de K cifre contigue (una după alta). Gigel fiind lacom, el va lua cel mai mare număr posibil de K cifre. De exemplu, pentru K=6 el va lua numărul ABCDEF.

Voi vreți ca Gigel să ia un număr cît mai mic. Pentru aceasta puteți reordona cifrele numărului X. Cum îl veți reordona pentru aceasta?

La intrare veți citi numărul K (1 ≤ K ≤ 14).

Se cere să afișați două numere:

Numărul minim de K cifre pe care îl poate lua Gigel.
O rearanjare a lui X care duce la acel număr minim.

Exemplu

Pentru K=2 putem rearanja X astfel:

X = 68D57E19A23BC4F

Ceea ce duce la faptul că Gigel va lua numărul de două cifre

E1

el fiind și cel mai mic număr de două cifre pe care îl poate lua din toate posibilitățile de a rearanja X.

Deci, dacă ați determinat cele două valori, veți afișa:

E1
68D57E19A23BC4F

Restricţii

timp de execuție: 0.1s.
memorie disponibilă: 64MB.

Temă

Tema 19 clasa a 7^a
- latin dată la cercul de informatică Vianu, gimnaziu 2013
- pav dată la Lot IS 2008
- forma dată la olimpiada pe sector 2012, clasa a 8^a
Opţional: Tema 19 clasa a 7^a opţională
- hanoi1 dată la concursul .campion 2003
Opţional: încercaţi să găsiţi rezolvări la problemele enunţate în lecţia aceasta, inclusiv la puzzle-uri:

Rezolvări aici [2]

Clasa a VII-a lecția 19 - 30 ian 2020

Fulgerică - rezolvare

Comentarii

Clasament

Tema - rezolvări

Disjoint

Channels

Comentarii generale

Soluţia union-find

Soluţia forţă brută

Soluţia comisiei

Bile3

Comentarii generale

Tema opțională - rezolvări

Flota

Ruine

Lecţie - Tehnici de programare: divide et impera

Tehnica divide et impera (divide and conquer) în informatică

Tehnica divide et impera simplă (decrease and conquer)

Algoritmul lui Euclid

Căutare binară

Căutare punct fix

Puzzle balanţă

Selecția

Probleme vianuarena

Tehnica divide et impera propriu zisă

Puzzle pavare

Mergesort

Aplicație mergesort - inversiunile unei permutări

Quicksort

Pivotarea Lomuto

Randomizarea pivotului

Probleme quicksort

Ziua regelui

Probleme temă

Fulgerică (test fulger)

Problema Gigel

Exemplu

Restricţii

Temă

Navigation menu

Search