Difference between revisions of "Clasa a VII-a lecția 5 - 10 oct 2019"

From Algopedia
Jump to: navigation, search
m (Cristian moved page Next to Clasa a VII-a lecția 5 - 10 oct 2019 without leaving a redirect)
(Lecție)
Line 358: Line 358:
  
 
= Lecție =
 
= Lecție =
 +
 +
<html5media height="720" width="1280">http://algopedia.ro/video/2019-2020/2019-10-10-clasa-7-lectie-info-04-720p.mp4</html5media>
 +
 
== Precalculare ==
 
== Precalculare ==
 
Precalcularea este un termen general pentru folosirea unor structuri auxiliare de date, uneori fără o legătură directă cu problema de rezolvat, care ne ajută în rezolvarea problemei. Aceste structuri de date sînt calculate la început, înainte de calculul propriu zis, ceea ce duce la denumire: precalculare.
 
Precalcularea este un termen general pentru folosirea unor structuri auxiliare de date, uneori fără o legătură directă cu problema de rezolvat, care ne ajută în rezolvarea problemei. Aceste structuri de date sînt calculate la început, înainte de calculul propriu zis, ceea ce duce la denumire: precalculare.

Revision as of 14:45, 12 October 2019

Tema - rezolvări

Onigim

Problema onigim a fost dată la ONI 2013 clasa a 5a. Ea admite o rezolvare foarte scurtă cu liste, desigur peste nivelul clasei a 5a.

Comentarii generale

  • Pare că problema nu v-a pus probleme. Listele au fost cucerite. Ura! :-)
  • Avertismente: Moroșan, Stancu (surse fără liste).

Rezolvare

Observăm că:

  • Toți elevii care au același număr de elevi "sub ei" vor avea același punctaj.
  • Elevii pot fi, deci, împărțiți în grupuri de elevi cu același punctaj.
  • Numărul de grupuri de elevi este exact numărul de punctaje distincte.
  • Deoarece punctajele distincte se dau în ordine crescătoare, un algoritm banal ar fi să parcurgem grupurile de elevi în ordinea crescătoare a numărului de elevi "sub" acel grup.
  • Toți elevii dintr-un grup primesc nota punctajului curent, apoi avansăm la următorul grup.

Cum implementăm acest algoritm destul de ușor? Trebuie să memorăm cumva aceste grupuri. Astfel, un grup este format din ID-uri, iar toate ID-urile au ceva în comun, care este unic: numărul de elevi "sub" acele ID-uri.

Astfel ne vine ideea să folosim liste: ce-ar fi ca pentru fiecare număr posibil de elevi "sub" să menținem cîte o listă de ID-uri? Dacă pentru un număr de elevi "sub" nu există ID-uri lista va fi vidă.

Iată gruparea de ID-uri de elevi pe liste, conform exemplului din problemă:

6 4
100 150 175 200
4 2 0 0 3 4
Exemplul din problema onigim - concept structură de date

Explicații: avem patru punctaje distincte obținute, 100 150 175 și 200. Avem șase elevi numerotați de la 1 la 6. În desen observăm că avem o listă de doi copii care au zero copii "sub" ei, anume cei cu ID-urile 4 și 3. De aceea ei sînt "agățați" la lista zero. Avem alți doi copii care au patru copii "sub" ei, cu ID-urile 1 și 6. Ei sînt "agățați" la lista patru. Și tot așa, mai avem cîte un singur copil în grupurile 2 și 3.

Cum rezolvăm problema pe baza acestei structuri? Printr-o parcurgere a listelor în ordine, de sus în jos și de la stînga la dreapta. Toate ID-urile din prima listă, 3 și 4, vor primi primul punctaj, adică 100. Toate ID-urile din a doua listă, adică 2, vor primi următorul punctaj, adică 150. Și așa mai departe. Printr-o singură parcurgere putem rezolva toate cele trei puncte ale problemei.

Iată un programul bazat pe ideile de mai sus (53 linii, circa 40 linii efective de program):

#include <stdio.h>

#define PMAX 300
#define NMAX 1000

int p[PMAX];       // p[i] = al i-lea punctaj in ordine crescatoare
int l[NMAX];       // l[a] = id primul copil care are a copii strict sub el
int next[NMAX+1];  // next[id] = id urm. copil care are tot atiti copii sub el
int punct[NMAX+1]; // punct[id] = punctajul copilului cu id 'id'

int main() {
  FILE *fin, *fout;
  int n, k, i, a, id, nrlafel, distinctii, maxlafel;

  fin = fopen( "onigim.in", "r" );
  fscanf( fin, "%d%d", &n, &k );
  for ( i = 0; i < k; i++ )  // citim punctajele unice
    fscanf( fin, "%d", &p[i] );
  for ( i = 1; i <= n; i++ ) {
    fscanf( fin, "%d", &a ); // id-ul i+1 are a copii strict sub el
    next[i] = l[a]; // "agatam" lista copiilor pe id-ul curent
    l[a] = i;       // actualizam primul copil care are a sub el
  }
  fclose( fin );

  maxlafel = 0;   // numarul maxim de elevi cu acelasi punctaj este zero
  i = 0;          // indicele celui mai mic punctaj, p[0]
  distinctii = 0; // citi copii au fost distinsi
  for ( a = 0; a < n; a++ ) {   // aflam punctajele - punctul a)
    id = l[a];                  // primul copil care are a copii sub el
    nrlafel = 0;                // citi copii au 'a' copii sub ei
    while ( id > 0 ) {          // cita vreme avem copii cu 'a' copii sub ei
      punct[id] = p[i];         // calculam punctajul copilului 'id'
      nrlafel++;                // inca un copil care are a copii sub el
      id = next[id];            // trecem la urmatorul copil
    }
    if ( nrlafel > 0 ) {        // daca am avut copii cu punctaj p[i]
      i++;                      // avansam punctajul in p[i]
      if ( nrlafel > maxlafel ) // punctul c)
        maxlafel = nrlafel;     // maximul copiilor cu acelasi punctaj
      if ( i > k - 3 )          // daca e unul din primele trei punctaje
        distinctii += nrlafel;  // punctul b), aduna nr copii la cei distinsi
    }
  }

  fout = fopen( "onigim.out", "w" );
  for ( i = 1; i <= n; i++ )
    fprintf( fout, "%d ", punct[i] );
  fprintf( fout, "\n%d\n%d\n", distinctii, maxlafel );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție?

Citirea și construcția listelor este evident O(n + k). Apoi avem o parcurgere a tuturor listelor cu o interclasare cu vectorul punctajelor, din nou O(n + k), care este și complexitatea finală.

Memoria ocupată este, și ea, O(n + k). Mai exact 300 de întregi și încă trei vectori de 1000 de întregi, cu totul circa 13200 octeți.

Macheta

Problema macheta a fost dată la ONI 2011 clasa a 8a. Ea admite o rezolvare foarte scurtă cu liste, care nu apare printre rezolvările oficiale.

Comentarii generale

  • Felicitări celor ce au reușit o soluție foarte bună și ordonată: prea mulți să vă enumăr, bravo tuturor!
  • Pare că majoritatea ați înțeles listele. Felicitări!
  • Dragilor: 101 ≠ 1001 ≠ 10001. Dimensionați corect vectorii! Vă poate costa enorm la olimpiadă. Dacă foloseați constante poate nu greșeați.
  • Unii din voi au avut folosit o sortare a cladirilor vizibile. Nu era necesar, puteați folosi un vector de frecvență.
  • Unii din voi au memorat date nenecesare pentru fiecare clădire, cum ar fi coordonata y și lungimea pe y. Nu rispiți memoria, vă rog.
  • Folosiți vă rog constante, pentru claritate. Chiar dacă unele din exemplele mele nu le folosesc :-).
  • Unii din voi s-au complicat la parcurgerea x-ilor unei clădiri. Cele două while se pot combina într-un singur for deoarece trebuie parcurși toți x-ii.
  • Avertismente: Moroșan (nici o sursă), Stancu (soluție fără liste).

Comentarii individuale

Prima grupă

  • Aizic: Program foarte bun, bravo! Nu aveai nevoie de sortare dacă foloseai un vector de frecvență al vizibilității clădirilor.
  • Badea: Program foarte bun, bravo! Observație importantă, nu aveai nevoie de vectorii y[] și Ly[]. E bine să te obișnuiești să nu folosești memorie extra, poți să ai probleme la olimpiadă. Plus, risipa nu e bună :)
  • Benescu: Program foarte bun, bravo! Observație minoră, folosește constante pentru claritatea codului.
  • Burac: Program foarte bun, bravo! Observație minoră, folosește constante pentru claritatea codului.
  • Calotă: Program foarte bun, bravo! Observații minore: denumirea last[] nu e deloc corectă căci nu e ultimul element ci primul, trebuia list[], ai folosit constante dar nu și la numărul de clădiri, iar NIL se scrie cu un singur L :-)
  • Chivu: Program foarte bun, bravo! Observație importantă, nu aveai nevoie de vectorii cy[] și cly[]. În plus, ai declarat vectorul liste[] de 2000 de elemente, sînt doar 1000 de y posibili. E bine să te obișnuiești să nu folosești memorie extra, poți să ai probleme la olimpiadă. Plus, risipa nu e bună :)
  • Cojocariu: Program bun, bravo! Așa da! Observații: la fscanf() nu citi o valoare necesară în aceeași variabilă cu o valoare inutilă. Este riscant. Inserezi la finalul listelor! Inutil și ineficient. Dacă toate clădirile sînt pe aceeași linie citirea ta este O(n2). Vezi inserția la început de listă. Dacă vrei să inserezi la final de listă în mod eficient trebuie să mai ții un vector de legături la ultima celulă a listelor. Parcurgerea listelor conține cod dublat inutil. Nu ai urmărit cu atenție cum se face parcurgerea, nu e bine.
  • Dobre: Program bun. Ai înțeles listele, dar ai unele încîlceli în gîndire. Am următoarele observații: Nu trebuia să memorezi coordonatele y, pentru ca abia apoi să creezi vectorul de liste. Puteai să combini totul la citire, mai simplu. Apoi, Inserezi la finalul listelor! Inutil și ineficient. Dacă toate clădirile sînt pe aceeași linie citirea ta este O(n2). Vezi inserția la început de listă. Dacă vrei să inserezi la final de listă în mod eficient trebuie să mai ții un vector de legături la ultima celulă a listelor. Apoi, parcurgerea listelor și prelucrarea clădirilor este încîlcită. De exemplu ai un steg care este totuna cu rez[nr]. Ai două etape, întîi cauți primul punct vizibil, apoi ai o altă buclă care continuă prima buclă pînă la finalul x-ilor. Puteai combina cele două bucle, oricum trebuie să actualizezi înălțimile vizibile. Nu aveai nevoie de sortare dacă foloseai un vector de frecvență al vizibilității clădirilor.
  • Hossu: Program bun. Observație importantă, nu aveai nevoie de vectorii y[] și Ly[]. E bine să te obișnuiești să nu folosești memorie extra, poți să ai probleme la olimpiadă. Plus, risipa nu e bună :) Ai complicat inutil inserția la început de listă, nu ai caz particular cînd lista e vidă. Atenție la dimensionări, vectorul height[] trebuia să fie de 2000 de elemente. De aceea cred că pici teste.
  • Iordache: Program foarte bun, bravo! Observație minoră, folosește constante pentru claritatea codului. Denumirile variabilelor lasă de dorit. Nu închizi fișiere! Foarte urît!
  • Mocanu: Pare că ai înțeles listele. Dar nu cred că ai înțeles rezolvarea povestită la lecție. Tu nu folosești deloc coordonatele y ale clădirilor. Construiești liste pentru x, pe verticală, trebuia să construiești pentru y, pe orizontală.
  • Mușat: Program bun, folosești corect liste. Observații: de ce faci citirile una cîte una? Folosești 5 fscanf() în loc de unul singur. Atenție la dimensionări! Tu ai dimensionat totul de 1000, dar majoritatea vectorilor sînt de 100, numărul maxim de clădiri! Observație importantă, nu aveai nevoie de vectorii vp[], inceput_l[] și latime[]. E bine să te obișnuiești să nu folosești memorie extra, poți să ai probleme la olimpiadă. Plus, risipa nu e bună :)
  • Nicola: Program foarte bun, bravo! Neimportant, nu aveai nevoie de vectorul val[]. Ai val[i] = i, deci e inutil.
  • Petcu: Program foarte bun, bravo! Observație minoră, folosește constante pentru claritatea codului.
  • Ștefănescu: Program foarte bun, bravo! Atenție la dimensionări! Tu ai dimensionat totul de 1000, dar majoritatea vectorilor sînt de 100, numărul maxim de clădiri! Nu aveai nevoie de sortare dacă foloseai un vector de frecvență al vizibilității clădirilor.
  • Togan: Programul este bun. Dar! Atenție la dimensionări, vectorul next[] are 101 de elemente, nu 1000. Observație importantă, nu aveai nevoie de vectorii y[] și Ly[]. E bine să te obișnuiești să nu folosești memorie extra, poți să ai probleme la olimpiadă. Plus, risipa nu e bună :) Observație minoră, folosește constante pentru claritatea codului. Din nou încîlceală:
      j=liste[i];///merg pe fiecare linie
      while(j!=0){///merg pe lista
        k=x[j-1];
        out=0;
        while(x[j-1]<(lx[j-1]+k)){///actualizez inalt maximale
          if(inaltime[x[j-1]]<h[j-1]){
            inaltime[x[j-1]]=h[j-1];
            out=1;
          }
          x[j-1]++;
        }
        if(out==1){
          output[j]=1;
        }
        j=next[j-1];
      }

Acel while este de fapt for. Folosești o variabilă de ciclu k, dar ea este doar pentru inducerea în eroare a adversarului (cititorul de cod)! Tu de fapt variezi limita inițială a for-ului! Togan, exercițiu: scrie acest cod normal, vezi dacă poți.

  • Voicu: Program foarte bun, bravo! Observație minoră, folosește constante pentru claritatea codului.

A doua grupă

  • Asgari: Program foarte bun, bravo!
  • Cadîr: Construiești corect listele de clădiri, mai puțin faptul că ai dimensionat pe greșit vectorii liste[] și next[], dimensiunile lor sînt invers. Parcurgerea listelor este greșită. Straniu, căci ai făcut-o bine la onigim. Vezi soluția mai jos.
  • Dimulescu: Atenție la indentare! Nu pot urmări programul tău și nici tu. Dacă continui așa nu poți continua la IQ Academy. Indentarea e ceva ce înveți la începuturile programării, este ridicol să îți tot fac observație pentru ea. Programul pare bun, motivul pentru care pici teste este dimensionarea lui h[], el are 2000 de elemente căci o clădirea poate să înceapă la x=1000 și să aibă Lx=1000. Elementele c[i][1] și c[i][3] sînt inutile, puteai să nu le stochezi degeaba. În acest caz matricea c[][] complică mult înțelegerea programului tău. Corect era să folosești cinci vectori cu denumiri diferite, altfel cum pot eu să-mi dau ușor seama ce reprezintă c[i][1]?
  • Fares: Program bun, bravo! Din categoria 'lenea gîndirii', toți vectorii sînt dimensionați la 1001, să nu ne batem capul, chit că mulți din ei au nevoie doar de 101 elemente.
  • Ghica: Nu înțeleg cum creezi listele. Aloci celule cînd la indicele i, cînd la indicele k. Denumirile de variabile nu ajută deloc la înțelegere. Pare că inserezi un element nou la finalul listelor, cînd inserarea la început e ușoară. Atenție la dimensionările de vectori! next[] și cel[] sînt prea mari, 2100 în loc de 101 și 2001, în vreme ce v[], lun[], și f[] sînt de 100 în loc de 101. Astea sînt greșeli de începători! Calculează cu atenție dimensiunea. Pentru viitor atenție mai mare la enunț, la dimensiuni, la calcule, la denumirile variabilelor.
  • Grecu: Program foarte bun, bravo! Mulțumesc pentru comentarii. Atenție, key[] este folosit pentru valoarea dintr-o celulă de listă. Tu îl folosești ca vector de liste. E confuzant. Atenție la dimensionările de vectori! cldH[1001], lx[1001], coordx[1001] sînt în realitate de 101 elemente. Folosește constante pentru claritatea codului, poate nu te mai încurci la dimensionări.
  • Ilie: Program foarte bun, bravo! Observație minoră, te-ai complicat la parcurgerea x-ilor unei clădiri. Cele două while se pot combina într-un singur for deoarece trebuie parcurși toți x-ii. Observație importantă, nu aveai nevoie de vectorii y[] și Ly[]. E bine să te obișnuiești să nu folosești memorie extra, poți să ai probleme la olimpiadă. Plus, risipa nu e bună :)
  • Ipate: Program foarte bun, bravo! Atenție la dimensionări, ai făcut un artificiu să lucrezi cu NIL = 0 drept care ai folosit vectorul next[] de la 1, ceea ce înseamnă că trebuia să îl dimensionezi de 101, nu 100. Artificiile de genul acesta nu sînt bune. Însă îmi place lejeritatea cu care jonglezi cu indici de la zero sau de la unu, arată că ai control și nu ți-e teamă să calculezi. Atenție, key[] este folosit pentru valoarea dintr-o celulă de listă. Tu îl folosești ca vector de liste. E confuzant.
  • Marcu: Program foarte bun, bravo! Observație minoră, folosește constante pentru claritatea codului.
  • Moroșan: Nimic? Este a doua temă la care nu trimiți nimic la una din probleme.
  • Nicu: Programul tău ar fi putut fi foarte bun. Dar are prea multe bube. Ce este asta: int num_y[10001], next[10001], h[10001], vx[10001], vlx[10001], h1[10001], poz[10001];? o glumă? În primul rînd numărul de clădiri este 100, iar coordonatele sînt maxim 1000. În al doilea rînd tu ai pus un zero în plus la toate. Asta nu e nici măcar programare aproximativă, este o grosolănie! Nu înțeleg de ce apelezi num_y[y - 1]; atunci cînd y poate fi zero. Observație minoră, te-ai complicat la parcurgerea x-ilor unei clădiri. Cele două while se pot combina într-un singur for deoarece trebuie parcurși toți x-ii.
  • Petrescu: Program foarte bun, bravo! În continuare le încîlcești :) În dorința de a folosi NIL=0 și a nu folosi vectori de la 1 te-ai complicat la parcurgerea listelor. Stegulețe degeaba, aux este, de fapt, o legătură la celula curentă și nu o variabilă auxiliară, iar while-l interior este de fapt un for. Dar, una peste alta, văd o îmbunătățire.
  • Popescu: Program foarte bun. Atenție la dimensionări! Tu ai dimensionat totul de 1000, dar majoritatea vectorilor sînt de 100, numărul maxim de clădiri! E bine să te obișnuiești să nu folosești memorie extra, poți să ai probleme la olimpiadă. Plus, risipa nu e bună :) Dacă foloseai constante poate nu greșeai.
  • Rebengiuc: Program foarte bun, bravo! Atenție mare la define-uri: #define MAX_POZ MAX_XY + MAX_LX, poți avea probleme dacă undeva în cod ai MAX_POZ * 10, deoarece doar MAX_LX se va înmulti cu 10. Corect era #define MAX_POZ (MAX_XY + MAX_LX)
  • Rughiniș: Nu ai înțeles rezolvarea din clasă. Degeaba scriu lecția, degeaba ai video. Ai făcut liste pe coordonata x. Soluție ineficientă, ce folosește și mult mai multă memorie. Partea bună este că pare că ai înțeles bine inserările în liste.
  • Stancu: Program fără liste. E clar că nu ai înțeles deloc listele, ceea ce mi-ai scris și în comentariile programului. Ce nu înțeleg este de ce stai cumințel. Ai lecția scrisă, ai filmul lecției. Dacă totuși nu înțelegi, ai clubul curioșilor, mai ai și emailul meu personal. Nu este OK să spui "nu înțeleg" și atît. Vreau să văd că nu ai înțeles după ce ai făcut efortul. Părerea mea e că nu l-ai făcut.
  • Tatomir: Program foarte bun, bravo!
  • Teodorescu: Program foarte bun, bravo! Atenție mare la dimensionări! Majoritatea vectorilor erau de 100 de elemente, tu i-ai declarat pe toți de 1000.
  • Voicu: Program bun, bravo! Nu aveai nevoie de sortare dacă foloseai un vector de frecvență al vizibilității clădirilor.

Rezolvare

Observăm că:

  • O clădire C este vizibilă dacă există o coordonată x pe care se află numai clădiri mai mici, în fața clădirii C.
  • Putem, astfel, verifica vizibilitatea unei clădiri verificînd vizibilitatea fiecărei coordonate x acoperite de ea.

Deja avem un algoritm rezonabil: pentru fiecare clădire C, parcurgem fiecare coordonată x a ei, iar pentru fiecare coordonată verificăm toate clădirile B dacă:

  • B este în fața lui C (y mai mic)
  • B acoperă coordonata x
  • B are înălțime mai mare ca C

Ce complexitate are acest algoritm?

Pentru fiecare clădire vom parcurge fiecare coordonată a ei, apoi fiecare altă clădire. Rezultă o complexitate O(N2 Lx). După înlocuiri rezultă circa 10 milioane de operații, pare că algoritmul acesta banal s-ar încadra în timp.

Dar să mergem mai departe cu observațiile:

  • Deoarece vom verifica doar clădirile din fața lui C, ne interesează doar clădirile cu y mai mic.
  • Pare a fi util să parcurgem clădirile în ordinea crescătoare a lui y.
  • Pentru fiecare coordonată x a clădirii C curente ne interesează maximul de înălțime de pînă acum, la acea coordonată.
  • Astfel, putem memora un vector de înălțimi maxime, care pentru fiecare coordonată x memorează cea mai înaltă clădire vizibilă la coordonata x, pînă la acest moment.

Cum implementăm acest algoritm?

Cumva trebuie să parcurgem clădirile în ordinea crescătoare a lui y. Soluțiile oficiale sar imediat la sortare. Dar să nu ne grăbim! Sortarea este lentă, ar fi bine să o evităm dacă putem.

Și desigur că putem: ce-ar fi să păstram pentru fiecare coordonată y o listă de clădiri ce încep la acea coordonată? Apoi parcurgem clădirile în ordinea lui y.

Iată gruparea de clădiri pe liste, conform exemplului din problemă:

Exemplul din problema macheta - desen
Exemplul din problema macheta - concept structură de date

Explicații: avem o clădire care începe la y=1 - clădirea 3. Avem o clădire care începe la y=2 - clădirea 2. Avem două clădiri care încep la y=3 - 4 și 5. Și o clădire care începe la y=6 - clădirea 1.

Cum rezolvăm problema pe baza acestei structuri? Printr-o parcurgere a listelor în ordine, de sus în jos și de la stînga la dreapta. Pentru fiecare clădire C parcurgem coordonatele ei x, verificînd vectorul de înălțimi h[x]. Dacă măcar una din înălțimi este mai mică, clădirea este vizibilă. Atenție, înălțimile trebuie actualizate dacă înălțimea lui C este mai mare decît cea a lui h[x].

De remarcat: o implementare îngrijită a acestui algoritm va avea circa 50 de linii, iar ca linii de program efectiv probabil 40.

Ce complexitate are acest algoritm?

Construcția listelor este O(N), numărul de clădiri. Parcurgerea listelor este O(N + Ly). Pentru fiecare clădire vom prelucra în timp constant fiecare coordonată x a sa. Rezultă complexitatea finală O(N Lx + Ly). După înlocuiri rezultă circa 100 000 de operații. Memoria va fi O(Lx), adică neglijabilă.

Din nou, o problemă intenționată spre a fi grea devine simplă prin folosirea listelor.

Iată un program bazat pe ideile de mai sus (48 linii, din care circa 36 linii efective de program):

#include <stdio.h>

#define NIL 0
#define MAXCLAD 100
#define MAXCOORD 1000

char vizibil[MAXCLAD+1];  // vizibil[i]=1 daca cladirea i este vizibila
short hmax[2 * MAXCOORD]; // hmax[x] = inaltimea vizibila la coordonata x
char lista[MAXCOORD + 1]; // capetele liste cladiri care incep la coordonata y
short x[MAXCLAD+1], lx[MAXCLAD+1]; // x-ul de inceput si lungimea cladirilor
short h[MAXCLAD+1];   // inaltimile cladirilor
char next[MAXCLAD+1]; // urmatoarea cladire in lista, pe aceeasi linie

int main() {
  FILE *fin, *fout;
  int n, i, xx, y, ly;

  fin = fopen( "macheta.in", "r" );
  fscanf( fin, "%d", &n );
  for ( i = 1; i <= n; i++ ) {
    fscanf( fin, "%hd%d%hd%d%hd", &x[i], &y, &lx[i], &ly, &h[i] ); // cladirea
    next[i] = lista[y]; // inseram cladirea la inceputul listei liniei y
    lista[y] = i;
  }
  fclose( fin );

  // asezam cladirile in vectorul de vizibilitate, din fata in spate
  for ( y = 0; y <= MAXCOORD; y++ ) {
    i = lista[y];
    while ( i != NIL ) { // parcurgem cladirile care incep la coordonata y
      for ( xx = x[i]; xx < x[i] + lx[i]; xx++ )
        if ( hmax[xx] < h[i] ) { // este vizibila?
          vizibil[i] = 1;        // marcheaz-o ca vizibila
          hmax[xx] = h[i];       // marcam noua inaltime
        }
      i = next[i];               // trecem la urmatoarea cladire de pe linia y
    }
  }

  fout = fopen( "macheta.out", "w" );
  for ( i = 1; i <= n; i++ )     // afisam cladirile vizibile
    if ( vizibil[i] == 1 )
      fprintf( fout, "%d ", i );
  fprintf( fout, "\n" );
  fclose( fout );

  return 0;
}

Memoria folosită este sub 6000 octeți.

Detecție listă cu buclă

Să se determine dacă o listă se întoarce la ea însăși (unul din elemente pointează la o celulă din-naintea lui). Nu aveți voie să vă legați de valorile memorate, ele pot fi duplicat. Vă puteți folosi strict de legătuirile listei, vectorul next[].

Aceasta este o problemă făcută celebră de faptul că a fost dată o vreme la interviuri de angajare la firma Micro$oft.

Soluție O(n2) timp și O(n) memorie suplimentară

Parcurgem lista. La fiecare celulă vom memora indicele ei (pointerul ei) într-un vector. Înainte de a o adăuga la acel vector vom verifica dacă ea nu există deja. Avem două cazuri, fie găsim celula în vector, caz în care ea are o buclă, fie ajungem la final de listă, caz în care nu are buclă.

Soluție O(n2) timp și O(1) memorie suplimentară

Procedăm similar cu soluția anterioară, dar folosim chiar lista însăși pentru a memora legăturile la celule. Mai exact, parcurgem lista, pentru fiecare element ținem minte al cîtelea element în listă este el, folosind un contor. Pentru fiecare element parcurgem din nou lista, de la început, pînă ajungem la prima apariție a elementului curent. Contorizăm cîte elemente am parcurs cu un al doilea contor. Dacă al doilea contor este mai mic, înseamnă că lista are o buclă, deoarece am întîlnit elementul curent mai devreme decît trebuia. Dacă ajungem la finalul liste, lista nu are buclă.

Soluție O(n) timp și O(1) memorie suplimentară

Pornim cu doi indici din prima celulă a listei, i1 și i2. La fiecare pas avansăm i1 cu o poziție în listă, iar i2 cu două poziții. La fiecare avans testăm dacă i1 și i2 devin egali. Dacă lista nu are buclă, i2 va ajunge la final de listă în O(n). Dacă are buclă, atunci i2 va parcurge maxim de două ori lungimea buclei pînă îl ajunge din urmă pe i1, deci din nou în O(n).

Concurs - rezolvări

Criptic

Problema criptic a fost dată la cercul de informatică din liceul Tudor Vianu în 2013 la clasa a 7a.

Rezolvare

Problema admite o rezolvare foarte scurtă, relativ ușoară cu liste: pentru fiecare cod posibil vom construi o listă cu caracterele ce apar la acel cod. Caracterele ce apar cu același cod vor fi inserate la începutul listei, deoarece ele trebuie afișate în ordine inversă.

Iată un program posibil (51 linii, din care 40 de linii de program efectiv):

#include <stdio.h>

#define MAXCAR 1000000
#define MAXORD 3844

int val[128];
char litera[MAXCAR+1];
int next[MAXCAR+1];
int lista[MAXORD]; // 62 * 62 = 3844

int main() {
  FILE *fin, *fout;
  int n, i, p, ch, nOrd;

  for ( ch = '0'; ch <= '9'; ch++ ) // valorile cifrelor
    val[ch] = ch - '0';
  for ( ch = 'a'; ch <= 'z'; ch++ )
    val[ch] = ch - 'a' + 10;
  for ( ch = 'A'; ch <= 'Z'; ch++ )
    val[ch] = ch - 'A' + 36;

  fin = fopen( "criptic.in", "r" );
  n = 0;
  while ( (ch = fgetc( fin )) != EOF ) {
    nOrd = 0;
    while ( ch != ' ' ) {
      nOrd = nOrd * 62 + val[ch];
      ch = fgetc( fin );
    }
    // generam o noua celula si o asezam in lista corespunzatoare
    next[++n] = lista[nOrd];
    litera[n] = fgetc( fin ); // caracterul mesajului
    lista[nOrd] = n;
    fgetc( fin ); // sfirsit de linie
  }
  fclose( fin );

  // parcurgem listele in ordinea numerelor de ordine
  fout = fopen( "criptic.out", "w" );
  for ( i = 0; i < MAXORD; i++ ) {
    p = lista[i];
    while ( p ) {
      fputc( litera[p], fout );
      p = next[p];
    }
  }
  fputc( '\n', fout );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție?

Cred că este clar că timpul este O(CodMax + NrLin) unde CodMax este codul maxim la intrare, iar NrLin este numărul de linii.

Memoria? Similar, aceeași complexitate. Mai exact vom avea nevoie de ceva mai puțin de 5MB.

Observație: pentru eficiența programului am precalculat valorile cifrelor în vectorul char val[128];. Calculăm valorile necesare la inițializare, înainte de a începe procesarea intrării. El scutește pînă la patru teste de inegalitate.

Rezolvări aici [1]

Lecție

Precalculare

Precalcularea este un termen general pentru folosirea unor structuri auxiliare de date, uneori fără o legătură directă cu problema de rezolvat, care ne ajută în rezolvarea problemei. Aceste structuri de date sînt calculate la început, înainte de calculul propriu zis, ceea ce duce la denumire: precalculare. De obicei precalcularea reduce complexitatea anumitor pași din algoritm, prețul ei fiind un calcul mic la început, astfel încît, per total, algoritmul va fi mai rapid.

În continuare vom vorbi despre cîteva exemple clasice de precalculare.

Santinela în căutarea liniară

Precum știm, codul clasic de căutare a elementului e în vectorul v[] de n elemente este:

i = 0;
while ( i < n && v[i] != e )
  i++;
if ( i < n ) // ... testul daca am gasit elementul

Am discutat cum putem elimina unul din testele din while folosind o santinelă. Vom așeza e pe prima poziție în afara vectorului. Astfel, ne asigurăm că vom găsi elementul în vector. Putem, deci, să nu mai testăm condiția i < n. Noul cod va fi:

v[n] = e;
i = 0;
while ( v[i] != e )
  i++;
if ( i < n ) // ... testul daca am gasit elementul

Așezarea santinelei în vector poate fi un exemplu foarte simplu de precalculare. Ea va folosi un element al vectorului, ce va trebui dimensionat cu unu în plus.

  • Avantaje: cod mai rapid și mai scurt.
  • Schimbă complexitatea algoritmului: nu.
  • Memorie extra folosită: O(1) (un element în plus).

Bordarea

Bordarea, tehnica prin care "înconjurăm" matricea cu elemente distincte, ar putea fi și ea considerată o precalculare. În loc de o santinelă avem acum multiple santinele. Codul de testare al depășirii matricei se simplifică și devine mai eficient.

  • Avantaje: cod mai rapid și mai scurt.
  • Schimbă complexitatea algoritmului: nu.
  • Memorie extra folosită: O(n) (unde n este dimensiunea matricei).

Precalculare tip caracter

Dacă avem nevoie să aflăm dacă un caracter dat este cifră, testul clasic este:

if ( ch >= '0' && ch <= '9' )
  // ...

Putem elimina un test dacă precalculăm un vector de stegulețe, pentru toate caracterele, care să aibă 1 pe pozițiile caracterelor cifre și 0 în rest. Astfel:

char ecifra[128];

// precalculare: initializare ecifra[]
for ( ch = '0'; ch <= '9'; ch++ )
  ecifra[ch] = 1;

// test cifra
if ( ecifra[ch] )
  // ...

Vom calcula la început cîte o valoare per cifră. Apoi, în algoritm vom scuti unul din teste.

Din fericire nu trebuie să facem explicit acest lucru. Biblioteca <ctype.h> ne oferă funcția:

int isdigit( int ch )

care face exact ce ne dorim. Există și alte funcții, cum ar fi isalpha() (testare literă) și isalnum() (testare cifra sau litera).

  • Avantaje: cod mai rapid și mai scurt.
  • Schimbă complexitatea algoritmului: nu.
  • Memorie extra folosită: O(Σ) (unde Σ este numărul de caractere).

Precalculare valori cifre în baze de numerație

Să luăm ca exemplu problema criptic. La intrare se aflau numere în baza 62, ce trebuiau citite ca întregi în memorie. Pentru aceasta trebuia să calculăm valoarea unei cifre. Codul simplu și direct va fi:

char ch;
// ...
ch = fgetc( fin );
if ( ch >= '0' && ch <= '9' )
  v = ch - '0';
else if ( ch >= 'a' && ch <= 'z' )
  v = ch - 'a' + 10;
else
  v = ch - 'A' + 36;

El va face 2 sau 4 teste de inegalitate. Pentru a nu avea nici un test putem precalcula într-un vector valorile cifrelor în baza 62:

  int val[128];
  // ...
  for ( ch = '0'; ch <= '9'; ch++ ) // valorile cifrelor
    val[ch] = ch - '0';
  for ( ch = 'a'; ch <= 'z'; ch++ )
    val[ch] = ch - 'a' + 10;
  for ( ch = 'A'; ch <= 'Z'; ch++ )
    val[ch] = ch - 'A' + 36;

Apoi, la folosire:

char ch;
// ...
ch = fgetc( fin );
v = val[ch];
  • Avantaje: cod mai rapid și mai scurt.
  • Schimbă complexitatea algoritmului: nu.
  • Memorie extra folosită: O(Σ) (unde Σ este numărul de caractere).

Ciurul lui Eratostene

V-aţi gîndit vreodată că ciurul lui Eratostene este de fapt o precalculare a unui vector de frecvenţă ciur[], care, pentru fiecare număr p, calculează ciur[p] care ne spune dacă p este prim?

Cum am calcula primalitatea tuturor numerelor pînă la n în absența ciurului? Am verifica de primalitate fiecare din numere, în O(p). Complexitatea algoritmului ar fi:

{\sqrt  {1}}+{\sqrt  {2}}+{\sqrt  {3}}+...+{\sqrt  {n}}

Această sumă este O(n{\sqrt  {n}}) (demonstrația depășește nivelul cercului nostru). În realitate lucrurile stau puțin mai bine, în sensul că nu vom ajunge cu divizorii pînă la {\sqrt  {k}} decît pentru k prim. O estimare a numerelor prime pînă la n este

{\frac  {n}{log{n}}}

De aceea, o estimare ajustată a complexității ar fi

O({\frac  {n{\sqrt  {n}}}{log{n}}})

Am putea face și o altă optimizare: să împărțim k doar la numerele prime de pînă la el. Aceasta mai reduce complexitatea într-un mod ce ar complica și mai mult formula.

Să nu uităm un lucru important: factorizarea folosește împărțiri. Ceea ce, pentru numerele cu care lucrăm noi, introduce o constantă multiplicativă foarte mare, circa 15 pînă la 30, comparabilă cu optimizări de tipul O(log n).

Prin comparație, ciurul lui Eratostene general are complexitatea O(n log n) și nu folosește împărțiri, iar pentru cazul testului de primalitate el poate fi adus la O(n log log n).

Să ne reamintim unele din aplicațiile ciurului lui Eratostene:

  • Numărul de divizori primi (unici sau neunici) ai tuturor numerelor pînă la n
  • Suma divizorilor primi (unici sau neunici) ai tuturor numerelor pînă la n
  • Numărul de divizori ai tuturor numerelor pînă la n
  • Suma divizorilor tuturor numerelor pînă la n
  • Descompunerea în factori primi a tuturor numerelor pînă la n
  • Numărul de numere prime cu fiecare din numerele pînă la n

Concluzii:

  • Avantaje: cod mai rapid și mai scurt.
  • Schimbă complexitatea algoritmului: da.
  • Memorie extra folosită: O(n).

Suma între i şi j

În multe probleme apare următoarea subproblemă: dat un vector v[] de n elemente întregi, să se răspundă la multe întrebări de forma care este suma elementelor vectorului între poziţiile i şi j?. În acest caz vom precalcula o structură de date auxiliară, şi anume un vector s[], astfel încît s[i] este suma elementelor de la 0 pînă la i (inclusiv). El se mai numeşte şi vectorul sumei prefixelor lui v[]. Construcția acestui vector se poate face liniar deoarece avem relaţia

s[i] = s[i-1] + v[i]

Odată calculat acest vector putem răspunde în timp constant la întrebări. Suma elementelor între i şi j este s[j] - s[i-1]. Complexitatea algoritmului forță brută de calcul al unei sume ar fi O(n), pe medie. Precalcularea o reduce la O(1).

  • Avantaje: cod mai rapid și mai scurt.
  • Schimbă complexitatea algoritmului: da.
  • Memorie extra folosită: O(n).

Suma între (l1, c1) şi (l2, c2)

Este problema anterioară extinsă la matrice: avem o matrice de numere întregi şi întrebări de forma: care este suma elementelor matricei în dreptunghiul care are drept colţuri opuse (l1, c1) şi (l2, c2)?.

În mod similar vom precalcula o matrice auxiliară cu suma elementelor matricei originale între (0, 0) şi (i, j). Ea poate fi calculată în timp constant per element, astfel:

Calcul matrice sume parțiale în dreptunghiuri care pornesc în origine
s[l][c] = s[l][c-1] + s[l-1][c] - s[l-1][c-1] + m[l][c]

Odată calculată matricea s[][] putem răspunde în timp constant la întrebări. Suma elementelor între (l1, c1) şi (l2, c2) este:

S = s[l2][c2] - s[l2][c1-1] - s[l1-1][c2] + s[l1-1][c1-1]
Calcul suma numerelor în orice dreptunghi

Complexitatea algoritmului forță brută de calcul al unei sume ar fi O(n2), pe medie. Precalcularea o reduce la O(1).

  • Avantaje: cod mai rapid și mai scurt.
  • Schimbă complexitatea algoritmului: da.
  • Memorie extra folosită: O(n2).

Numărul de biţi 1 într-un întreg

Cum putem calcula numărul de cifre 1 din reprezentarea în baza 2 a unui număr?

  • Direct: shift and mask. Complexitate O(nr. biţi)
  • Folosind expresia x & (x - 1). Complexitate O(nr. biţi)
  • Cu precalculare: ţinem un vector în care elementul v[x] este numărul de biţi 1 din reprezentarea în baza 2 a lui x.

Concluzii precalculare număr de biți 1:

  • Avantaje: cod mai rapid.
  • Schimbă complexitatea algoritmului: da.
  • Memorie extra folosită: O(2nr. biți), sau O(xMax). Poate fi prohibitiv dacă xMax este mare.

Întrebări:

  • Se poate mai bine decît O(nr. biţi) fără memorie suplimentară (adică O(1) memorie suplimentară)?
  • Putem adapta metoda precalculării și la numere xMax mari, gen numere întregi pe int?

Sume de intervale

Se dă un vector cu n elemente, iniţial zero. O operaţiune pe acest vector constă în incrementarea fiecărui element între indicii i şi j. Se dau m operaţiuni de executat. Să se afişeze valorile finale ale vectorului.

Soluţia forţă brută implică execuţia celor m operaţiuni. O operaţiune constă în incrementarea a maxim n elemente din vector, deci avem n x m operaţii, plus afişarea elementelor finale. Complexitatea totală este O(mn).

Exemplu

În următorul exemplu avem un vector inițial zero și se cere să executăm două operațiuni: operațiunea a va incrementa elementele de la pozițiile 2 la 13 și operațiunea b care va incrementa elementele de la pozițiile 6 la 9.

Operațiuni aplicate cu metoda forță brută

Îmbunătățire

Se poate mai bine? Putem optimiza timpul unei operaţiuni. Ideea este următoarea: în loc să incrementăm pe rînd elementele vectorului, am putea să le grupăm. Pentru aceasta vom întîrzia incrementarea, marcînd doar locurile unde trebuie să adunăm.

Cu alte cuvinte: am putea considera intervalele ca pe nişte paranteze aşezate pe o dreaptă. O paranteză deschisă înseamnă că de acum înainte trebuie să adunăm 1 la toate elementele care urmează. O paranteză închisă înseamnă că ne putem opri din adunat 1. Să presupunem că nu avem capete de interval suprapuse. Atunci am putea memora parantezele într-un vector separat. Vom memora 1 pentru o paranteză deschisă, -1 pentru o paranteză închisă şi 0 în caz că nu avem nici un capăt de interval în acel element.

Ipoteză: vectorul s[] de sume parţiale ale acestui vector constituie chiar rezolvarea problemei.

Avem, deci:

s[i] = v[0] + v[1] + ... + v[i]

Înseamnă că v[k] se va aduna la toate sumele s[k], s[k+1], ..., s[n]. Ceea ce înseamnă că dacă pe poziția k în vectorul v[] avem valoarea unu, acea valoare se va propaga în toate elementele lui s[] începînd cu poziția k.

Dorim să aplicăm un interval [2, 13], deci vom plasa 1 pe poziția 2. El se va propaga pîna la finalul vectorului s[]. Dar noi vrem ca începînd cu poziția 14 acel 1 să nu se mai propage. Deoarece nu putem acest lucru, vom face altceva: vom plasa valoarea -1 pe poziția 14. Ea se va propaga, și ea, pînă la final de vector s[], adunîndu-se la fiecare element o singură dată. Ea va anula propagarea elementului 1 plasat la poziția 2.

Similar, dacă dorim să aplicăm intervalul [6, 9] vom plasa 1 pe poziția 6 în v[] și -1 pe poziția 10.

După ce am plasat toate intervalele, vom calcula în s[] sumele parțiale ale lui v[]. Vectorul s[] este răspunsul, valorile finale cerute.

În fapt, nu avem nevoie de doi vectori. Putem suprascrie vectorul v[], deoarece nu mai avem nevoie de elementele marker.

Operațiuni aplicate prin precalculare

Funcţionează acest algoritm dacă avem capete de interval suprapuse? Da, cu condiţia ca elementul în care se suprapun capete să fie suma acelor capete, adică o sumă de 1 şi -1. Aceasta înseamnă că atunci cînd generăm vectorul de paranteze nu vom scrie s[i] = 1 ci s[i]++ (la fel şi pentru -1, vom decrementa).

Generalizare 1: putem generaliza această metodă pentru problema în care intervalele nu adună 1, ci orice număr, constant pe parcursul intervalului. Cum generalizăm? O paranteză deschisă nu va aduna 1 ci constanta respectivă.

Generalizare 2: dar dacă vectorul iniţial are valori diferite de zero? În acest caz vom calcula un vector separat, iniţializat cu zero, pe care facem calculul sumelor parţiale. Acest vector ne va spune cu cît s-a mărit fiecare element zero. În final vom aduna acest vector de sume parţiale la vectorul iniţial.

Acest exemplu de precalculare, este cunoscut printre unii din voi drept "șmenul lui Mars", denumire care îmi displace deoarece sugerează că informatica este o colecție de șmenuri.

Cînd nu funcţionează această soluţie? Atunci cînd coordonatele intervalelor sînt prea mari pentru ca vectorul de sume parţiale să încapă în memorie. Să presupunem că ni se cere numărul maxim din vectorul de sume parţiale. În acest caz există o soluţie alternativă, mai generală (în sensul în care rezolvă o clasă mai mare de probleme cu intervale), care nu folosește precalculare: putem memora capetele de intervale, pe care apoi le ordonăm crescător, ţinînd minte de ce tip sînt, închis sau deschis. Apoi le parcurgem în ordine, calculînd sumele parţiale fără să le stocăm. Suma parţială maximă este răspunsul cerut.

Desigur că atunci cînd vectorul încape în memorie, e mai uşoară precalcularea.

Sume de dreptunghiuri

Acest tip de precalculare se poate extinde în două dimensiuni, pe matrice: se dau m dreptunghiuri care adună 1 la toate elementele respective dintr-o matrice. De data aceasta vom folosi o matrice de sume parțiale, ce necesită O(n2) memorie.

Nu voi detalia algoritmul, iată partea de plasare a unui dreptunghi (l1, c1) -> (l2, c2). Desenul arată punctele unde se adună/scade 1:

Operațiuni aplicate prin precalculare

Această metodă nu se justifică decît în măsura în care este facil de programat, deoarece avem o soluție de aceeași complexitate care folosește varianta 1D, pe vector, folosind doar O(n) memorie, ca la problema flori1.

Exemple de probleme cu precalculare

  • paisprezece: necesită un vector ce păstrează numere prime, ciurul lui Eratostene.
  • intervale: ciurului lui Eratostene, sume parţiale.
  • reginald, o optimizare a problemei anterioare.
  • puncte1: o rezolvare posibilă folosește precalcularea sumelor parţiale ale unei matrice
  • extraterestri precalculare vector sume prefixe parțiale (a.k.a. șmenul lui Mars)
  • extraterestri1 Mars + normalizare coordonate
  • flori precalculare matrice sume prefixe parţiale (a.k.a. şmenul lui Mars 2D)
  • flori1 exemplu de problemă nerezolvabilă cu precalculare 2D din lipsă de memorie

Concluzii

  • Precalcularea foloseşte atunci cînd avem de răspuns la mai multe întrebări costisitoare. Aceste întrebări pot fi explicite, cerute de enunţ, sau implicite, decurgînd din metoda de rezolvare.
  • Precalcularea poate folosi şi atunci cînd numărul de întrebări este mult mai mare decît numărul de răspunsuri posibile, caz în care putem precalcula toate răspunsurile într-un tabel înainte de a răspunde la întrebări. Această precalculare seamănă cu memoizarea. Diferența constă în faptul că precalcularea este executată explicit înainte de calcul, pe cînd memoizarea ține minte valori calculate în timpul calculului.
  • Precalcularea foloseşte o structură de date adiţională şi memorie suplimentară. Uneori putem economisi memorie folosindu-ne chiar de structura de date iniţială.

Discuții probleme tema opțională

Următoarele observații s-ar putea să vă ajute:

  • Cine rezolvă problema reginald automat rezolvă problema intervale (cu schimbarea numelor fișierelor de intrare/ieșire, desigur).
  • Problema flori1 este foarte grea ca structură de date. Veți avea nevoie de un vector de liste, cîte o listă pentru fiecare linie. Pe o linie veți memora dreptunghiuri care încep pe acea linie, precum și dreptunghiuri care se termină pe linia anterioară. Ce anume aveți nevoie să memorați într-o celulă? Trei valori, coloana de început a segmentului, cea de final, și valoarea de adăugat. Apoi veți "plimba" de sus în jos vectorul de markeri (v[] din varianta 1D a lui Mars). El se va actualiza cu perechile din lista liniei curente. Pe baza lui v[] calculați s[] într-un vector diferit, pentru a nu îl influența pe v[], de care aveți nevoie la linia următoare. În final veți vedea că nici nu aveți nevoie de s[] deoarece vi se cere să calculați un maxim.

Temă

Tema 5 clasa a 7a

  • intervale dată pregătire OJI 2013 clasa a 9a la Vianu
  • patrate1 dată la cercul de informatică Vianu 2013 clasa a 6a rezolvată în cel mult O(n3)!
  • extraterestri dată la OJI 2012 clasa a 8a

Tema 5 opțională clasa a 7a

  • reginald dată la pregătire olimpiadă 2013 clasele 7/8/9/10 la Vianu
  • flori1 dată la pregătire baraj gimnaziu 2013 la Vianu

Opțional, gîndiți-vă la întrebările din curs - calcul număr biți 1 în reprezentarea binară a unui întreg:

  • Se poate mai bine decît O(nr. biţi) fără memorie suplimentară (adică O(1) memorie suplimentară)?
  • Putem adapta metoda precalculării și la numere xMax mari, gen numere întregi pe int?


Rezolvări aici [2]