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

From Algopedia
Jump to: navigation, search
(Problema bile1)
(Temă)
 
(3 intermediate revisions by the same user not shown)
Line 812: Line 812:
  
 
== Aplicație: problema onigim ==
 
== Aplicație: problema onigim ==
Problema [[http://varena.ro/problema/onigim onigim]] a fost dată la ONI 2013 clasa a 5<sup>a</sup>. Ea admite o rezolvare foarte scurtă cu liste, desigur peste nivelul clasei a 5<sup>a</sup>.
+
Problema [http://varena.ro/problema/onigim onigim] a fost dată la ONI 2013 clasa a 5<sup>a</sup>. Ea admite o rezolvare foarte scurtă cu liste, desigur peste nivelul clasei a 5<sup>a</sup>.
  
 
Observăm că:
 
Observăm că:
Line 844: Line 844:
  
 
== Aplicație: problema macheta ==
 
== Aplicație: problema macheta ==
Problema [[http://varena.ro/problema/macheta macheta]] a fost dată la ONI 2011 clasa a 8<sup>a</sup>. Ea admite o rezolvare foarte scurtă cu liste, care nu apare printre rezolvările oficiale.
+
Problema [http://varena.ro/problema/macheta macheta] a fost dată la ONI 2011 clasa a 8<sup>a</sup>. Ea admite o rezolvare foarte scurtă cu liste, care nu apare printre rezolvările oficiale.
  
 
Observăm că:
 
Observăm că:
Line 898: Line 898:
 
* [http://varena.ro/problema/onigim onigim] dată la ONI 2013 clasa a 5<sup>a</sup> rezolvată cu liste
 
* [http://varena.ro/problema/onigim onigim] dată la ONI 2013 clasa a 5<sup>a</sup> rezolvată cu liste
 
* [http://varena.ro/problema/macheta macheta] dată la ONI 2011 clasa a 8<sup>a</sup> rezolvată cu liste
 
* [http://varena.ro/problema/macheta macheta] dată la ONI 2011 clasa a 8<sup>a</sup> rezolvată cu liste
 +
* '''Opțional''': gîndiți-vă la problema din curs, cum detectăm dacă o listă are o buclă în ''O(n)''
  
Rezolvări aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_VII-a_lec%C8%9Bia_1_-_19_sep_2019]
+
Rezolvări aici [http://solpedia.francu.com/wiki/index.php/Clasa_a_VII-a_lec%C8%9Bia_3_-_3_oct_2019]

Latest revision as of 23:07, 9 October 2019

Anunțuri

  • Avertisment ultimatum următorilor elevi: Dragoș Cojocariu. Dragoș, atitudinea ta este aceeași de la finalul anului trecut. Nu poți continua așa. Temele tale sînt forță brută, la minima rezistență. Mă refer la selecție rezolvată prin sortare și la bile1 rezolvată fără liste, cu o matrice ce depășește memoria. Cu părere de rău, la prima temă în batjocură îți vei pierde calificarea la IQ Academy.

Tema - rezolvări

Selecție

Selecția este o problemă clasică de teoria informaticii.

Comentarii generale

  • Timpul problemei este cam strîns, iar unii din voi ați avut TLE-uri. Iertare, dar altfel nu aveam cum să diferențiez între o sortare bine scrisă, O(n log n) și algoritmul quickselect.
  • Felicitări celor ce au reușit o soluție proprie!
  • Pentru cei ce au implementat pivotarea Lomuto: atenție, este lentă. Folosiți pivotarea Hoare, pe care o vedeți mai jos.
  • Avertismente: Cojocariu (rezolvare prin sortare), Grecu (nici o sursă) Moroșan (nici o sursă)

Rezolvare

Vom prezenta mai jos soluția originală quickselect, a lui [Tony Hoare].

Idee algoritm: aplicăm pivotarea, ea rezultînd în două partiții ale vectorului. Vom alege partiția din care face parte indicele k dorit și reluăm pivotarea pentru acel subvector. Algoritmul se continuă pînă cînd vectorul se reduce la un singur element, care este și răspunsul dorit.

Idee pivotare: alegem ca pivot orice număr din vector (eu am ales un număr la jumatea vectorului). Pornim cu doi indici, unul de la stînga către dreapta numit b și unul de la dreapta către stînga numit e. Vom avansa b cîtă vreme elementele vectorului sînt strict mai mici decît pivotul. Similar, vom avansa e cîtă vreme elementele vectorului sînt strict mai mari ca pivotul. Interschimbăm valorile aflate la cei doi indici, apoi avansăm indicii cu o poziție. Reluăm.

Observație: cînd avansăm indicii de pivotare nu este necesar să testăm că ei nu depășesc vectorul. Prin natura sa algoritmul se asigură că există un element egal cu pivotul între cei doi indici.

Iată programul bazat pe implementarea lui Hoare, transformată să fie structurată:

#include <stdio.h>

int v[1000000];

int main() {
  FILE *fin, *fout;
  int n, k, i, begin, end, b, e, pivot, aux;

  fin = fopen( "selectie.in", "r" );
  fscanf( fin, "%d%d", &n, &k );
  for ( i = 0; i < n; i++ )
    fscanf( fin, "%d", &v[i] );
  fclose( fin );

  k--;
  begin = 0;   // inceputul partitiei curente de cautare
  end = n - 1; // sfirsitul partitiei curente de cautare
  while ( begin < end ) { // cita vreme partitia are macar doua elemente
    pivot = v[(begin + end) / 2];; // alegem un pivot la mijlocul partitiei
    b = begin; // pornim cu b de la stinga spre dreapta
    e = end;   // si cu e de la dreapta spre stinga
    while (v[b] < pivot) // cautam primul element >= pivot
      b++;
    while (v[e] > pivot) // cautam primul element <= pivot
      e--;
    while( b < e ) { // cita vreme indicii nu s-au "incalecat"
      aux = v[b];    // interschimbam valorile la pozitiile b si e
      v[b] = v[e];
      v[e] = aux;

      do  // cautam primul element >= pivot pornind de la urmatorul element
        b++;
      while (v[b] < pivot);
      do  // cautam primul element <= pivot pornind de la urmatorul element
        e--;
      while (v[e] > pivot);
    }

    // la final e <= b
    // acum [begin..e] sint mai mici sau egale cu pivotul
    // si [e+1..end] sint mai mari sau egale cu pivotul
    if ( k <= e ) // selectam partitia [begin..e] daca contine pozitia k
      end = e;
    else          // selectam partitia [e+1..end] daca contine pozitia k
      begin = e + 1;
  }

  // partitia de final are un singur element, pe pozitia k; il afisam
  fout = fopen( "selectie.out", "w" );
  fprintf( fout, "%d\n", v[k] );
  fclose( fout );

  return 0;
}

Swap

Problema swap a fost dată la ONI 2013 baraj gimnaziu.

Rezolvare

Problema pare destul de grea, la prima vedere. În realitate, odată ce lămurim cerințele, ea este foarte simplă.

Punctul a

Se cere costul parantezării. El se face banal (sper) cu o stivă în care ținem pentru fiecare paranteză deschisă indicele ei în expresie. Cînd vom închide acea paranteză, vom avea al doilea indice. Diferența lor este suma perechii. Suma perechilor este costul parantezării.

Punctul b

Acest punct pare mai greu. Oare este? Condițiile sînt puțin încîlcite, să le descîlcim:

  • Operațiunea swap se face numai între poziții consecutive în șir.
  • Operațiunea swap trebuie să rezulte în cost mai mic al parantezării. Ce înseamnă acest lucru? Că întotdeauna trebuie să înlocuim o pereche (). În cazurile (( și )) costul va fi același, iar în cazul )( el se mărește, deoarece creștem gradul de imbricare (paranteze una în alta), deci îndepărtăm parantezele una de alta.
  • Operațiunea swap trebuie să se poată face. Ce înseamnă acest lucru? Ca înaintea grupului () să mai existe paranteze deschise și neînchise. Cu alte cuvinte ca stiva de paranteze să conțină cel puțin două paranteze deschise, una fiind cea din grupul ().
  • Atunci cînd executăm un swap costul parantezării scade cu 2. De ce? Desenați și veți vedea!

Cu alte cuvinte, minimul care se poate obține este, în fapt o păcăleală: el este întotdeauna același și este mai mic cu 2.

Cum vom proceda? Folosind aceeași stivă și aceeași parcurgere de la punctul (a) vom verifica, atunci cînd la intrare avem o paranteză închisă, că:

  • Exact înaintea ei în șir am avut o paranteză deschisă - indicele pe stivă este mai mic cu unu față de cel curent
  • Numărul de elemente pe stivă este măcar 2 (sau unu după ce scoatem paranteza curentă)

Punctul c

Acest punct cere, în fapt, să contorizăm cîte swap-uri putem face. Banal.

Programul este, în fapt, extrem de scurt, circa 30 de linii. Iată-l:

#include <stdio.h>

int stiva[45000];

int main() {
  FILE *fin, *fout;
  int n, i, np, suma, min, nswap;

  fin = fopen( "swap.in", "r" );
  fscanf( fin, "%d ", &n );
  nswap = suma = np = 0; // nr swap posibile, suma si nr paranteze deschise
  for ( i = 0; i < n; i++ ) {   // citim fiecare paranteza
    if ( fgetc( fin ) == '(' )  // este paranteza deschisa?
      stiva[np++] = i;          // adaugam pe stiva indicele ei
    else {                      // daca este paranteza inchisa
      suma += i - stiva[--np];  // adunam diferenta la suma
      if ( np > 0 &&            // mai avem paranteze deschise?
           stiva[np] + 1 == i ) //   si ultima este '('?
        nswap++;                // daca se poate face swap, contorizam
    }
  }
  fclose( fin );

  min = nswap > 0 ? suma - 2 : -1; // daca avem swap costul va fi mai mic cu 2
  
  fout = fopen( "swap.out", "w" );
  fprintf( fout, "%d\n%d\n%d\n", suma, min, nswap );
  fclose( fout );

  return 0;
}

Ce complexitate are soluția?

Ea este O(n) atît ca timp cît și ca memorie. Mai exact, memoria ocupată este de 45000 de întregi, adică 360 000 de octeți.

Reducere la O(1) memorie

Avem nevoie de stivă pentru a putea calcula diferențele de indici și costurile perechilor de paranteze, nu-i așa? Însă să observăm un lucru: toți indicii parantezelor deschise se scad și toți indicii parantezelor închise se adună. Putem, deci, să îi scădem, respectiv adunăm, la momentul cînd întîlnim parantezele, nemaiavînd nevoie de o stivă. Va trebui, în schimb, să memorăm ultimul caracter primit la intrare pentru a testa dacă avem cazul '()'.

Felicitări celor care s-au prins de acest lucru!

Problema bile1

Problema bile1 a fost dată la ONI 2012 clasa a 7a. Ea poate fi rezolvată folosind o matrice caracteristică a obstacolelor. Dar dacă memoria permisă ar fi fost mai mică nu o puteam rezolva în acest fel. Rezolvarea cu liste necesită doar O(m+n+p) memorie.

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!
  • Mulți dintre voi au testat finalul de listă astfel: while ( l > 0 ). Este greșit conceptual să comparăm aritmetic un terminator. El este terminator sau nu este. Comparația corectă este cu inegalitate: while ( l != 0 ).
  • Avertismente: Aizic (sursă în batjocură, fără liste), Burac (nici o sursă), Chivu (nici o sursă), Cojocariu (rezolvare fără liste), Dobre (rezolvare fără liste), Hossu (nici o sursă), Mușat (rezolvare fără liste), Moroșan (nici o sursă).

Comentarii individuale

Prima grupă

  • Aizic: Sursă trimisă în ultima clipă, nu are treabă cu ce se cere, o rezolvare cu liste. Scopul problemei este exact să învățam liste. În plus tratezi obstacolele ca și cînd ar fi ordonate după linii, evident incorect. Foarte urît, dacă începi iar cu d-astea ne supărăm.
  • Badea: Program foarte bun, bravo! Observație minoră, testul față de NIL este inegalitate, nu de comparație, mai mare, altfel presupui că NIL este zero.
  • Benescu: Rezolvarea din temă e ciudată, am discutat. Cea din afara temei este foarte bună, bravo! Linia col[0]=list[0]=next[0]=-1; este inutilă, nu ajută la nimic. Observație minoră, testul față de NIL este inegalitate, nu de comparație, mai mare, altfel presupui că NIL este zero.
  • Burac: nimic? Ne supărăm.
  • Calotă: Program foarte bun, bravo! Observație minoră, testul față de NIL este inegalitate, nu de comparație, mai mare, altfel presupui că NIL este zero. Ce este un spațiu în loc de un \n? Este diferența între 0 și 100p.
  • Chivu: nimic? Ne supărăm.
  • Cojocariu: soluție care nu are nici o treabă cu listele. Scopul este să învățăm liste. Mai mult, e forță brută. Nu te-ai obosit măcar să găsești o soluție care se încadrează în memorie.
  • Dobre: Rezolvarea ta nu folosește liste, exact scopul problemei. Ne supărăm!
  • Hossu: Nimic? Ne supărăm!
  • Iordache: Program foarte bun, bravo! Linia li[0]=col[0]=next[0]=-1; este inutilă, nu ajută la nimic.
  • Mocanu: Grijă mare, nu ai înțeles listele. Atenție maximă atît la rezolvare, cît și la lecția de azi!
  • Mușat: Apreciez străduința. Nu apreciez dopajul și mai ales nu apreciez că nu ai folosit liste în rezolvare, care este scopul acestei probleme.
  • Nicola: Program foarte bun, bravo! Atenție la neatenție: numărul de obstacole este 10000, nu 2000. De aceea pici teste.
  • Petcu: Program foarte bun, bravo!
  • Ștefănescu: Construcția listelor este bună, te-ai încîlcit la parcurgerea lor. Cred că mai ai de lămurit puțin listele astea :) Urmărește te rog cu atenție atît rezolvarea problemei cît și lecția de azi.
  • Togan: Program corect. Dar încîlcit, stilul tău :-) Scrii liste[l-1]=i+1; pentru ca mai tîrziu să scrii i=liste[l]-1;. Asta pentru că vrei ca zero să se transforme în -1, terminatorul de listă. Era mai normal să setezi explicit terminatorul, în next[]. Ai grijă la repetiția inutilă de cod la actualizarea vectorului de bile, vezi soluția de mai jos.
  • Voicu: Program foarte bun, bravo!

A doua grupă

  • Asgari: Program foarte bun, bravo! Singura observație de finețe, la "while ( j > NIL )" comparația cu NIL este de egalitate, altfel presupui a priori că NIL este zero :-) Corect: "while ( j != NIL )".
  • Cadîr: Program foarte bun, bravo!
  • Dimulescu: Program foarte bun, bravo! Atenție la indentare! Nu este opțională, este obligatorie!
  • Fares: Program foarte bun, bravo! Din categoria simpatic:
      v[c - 1] += v[c] / 2;
      if (v[c] % 2 == 1)
        v[c - 1]++;

Dacă e 1, adunăm 1. Avem grijă să nu aplicăm matematica decît la orele de mate, nu? :-)

  • Ghica: Ai complicat soluția introducînd cazuri particulare care nu există. Pare că ai înțeles ceva din liste, dar nu complet. Urmărește lecția de azi, sper să te lămurești. Vezi și rezolvarea pe care o voi prezenta. O complicație, de exemplu, e faptul că ai tratat special obstacolele pe prima și ultima linie. Citește cu atenție enunțul: "Pe prima şi ultima linie, respectiv prima şi ultima coloană, nu există obstacole".
  • Grecu: Program foarte bun, bravo, se vede că ai înțeles listele. Observațiile sînt la alt capitol: unu, nu aveai nevoie de un al doilea vector pentru bile, deoarece obstacolele sînt distanțate între ele și valorile din vector nu se influențează una pe alta. Doi, dacă totuși folosești al doilea vector, copierea este ineficientă. Trebuia să folosești o matrice de două linii și să calculezi dintr-o linie în alta, așa cum am făcut anul trecut.
  • Ilie: Program foarte bun, bravo! Ca observație, te-ai complicat adăugînd la coada listei. Era mai simplu să adaugi la începutul listei, cod mai scurt. Obstacolele nu se dau într-o ordine anume.
  • Ipate: Program foarte bun, bravo! Ca observații minore:
    • inițializarea legăturilor cu NIL este inutilă:
  for ( i = 0; i < p; i++ )
    next[i] = -1;
    • Testul de NIL la începutul parcurgerii listei este inutil, el e preluat de "while":
    if (x != -1 ) {
      b[col[x] - 1] = b[col[x] - 1] + (b[col[x]] + 1) / 2;
      b[col[x] + 1] = b[col[x] + 1] + b[col[x]] / 2;
      b[col[x]] = 0;
      x = next[x];
      while ( x != - 1 ) {
        b[col[x] - 1] = b[col[x] - 1] + (b[col[x]] + 1) / 2;
        b[col[x] + 1] = b[col[x] + 1] + b[col[x]] / 2;
        b[col[x]] = 0;
        x = next[x];
      }
    }
  • Marcu: Program foarte bun, bravo! Observație minoră, i și j merg sincron (au aceleași valori) deci nu ai nevoie de ambele:
    i=0;
    for(j=0;j<p;j++) {
        fscanf(fin,"%d%d",&l,&c);
        l--;
        c--;
        col[i]=c;
        next[i]=liste[l];
        liste[l]=i;
        i++;
    }
  • Moroșan: Nimic? Ne supărăm!
  • Nicu: Program foarte bun, bravo!
  • Petrescu: Program foarte bun, bravo! Gîndești puțin încîlcit, e bine sa înveți să simplifici. Iată, la parcurgerea unei liste tu scrii:
        if(liste[i]!=0) {
          colv=liste[i];
          nexti=-1;
          while(nexti!=0) {
            v[col[colv]-1]=v[col[colv]-1]+v[col[colv]]-v[col[colv]]/2;
            v[col[colv]+1]=v[col[colv]+1]+v[col[colv]]/2;
            v[col[colv]]=0;
            nexti=next[colv];
            colv=nexti;
          }
        }

Probleme: acel if nu este necesar, el este preluat de while. Iar colv și nexti merg în paralel, ele au exact aceleași valori cu excepția începutului de parcurgere. Puteai să folosești doar colv. Dacă vei simplifica codul vei obține:

          colv=liste[i];
          while(colv!=0) {
            v[col[colv]-1]=v[col[colv]-1]+v[col[colv]]-v[col[colv]]/2;
            v[col[colv]+1]=v[col[colv]+1]+v[col[colv]]/2;
            v[col[colv]]=0;
            colv=next[colv];
          }
  • Popescu: Program foarte bun, bravo!
  • Rebengiuc: Program foarte corect. Este clar că ai înțeles listele. Comentarii bune, mi-au ușurat înțelegerea codului. Te-ai complicat. Nu e necesar să copiezi obstacolele într-un vector. Poți folosi chiar lista, ea ține locul unui vector. Și deoarece obstacolele sînt distanțate unul de altul nu ai nevoie de un al doilea vector de bile.
  • Rughiniș: Program foarte bun, bravo! Ca observație minoră, nu ai nevoie de if la începutul parcurgerii listei, el este acoperit de while:
    if(list[i]!=NIL){
      a=list[i];
      while(a!=NIL){
        b[col[a]-1]+=b[col[a]]/2+b[col[a]]%2;
        b[col[a]+1]+=b[col[a]]/2;
        b[col[a]]=0;
        a=next[a];
      }
    }
  • Stancu: Program foarte bun, bravo! Atenție la dimensionarea vectorilor! Dacă îi folosești de la 1 pentru a avea NIL zero este în regulă, dar atunci trebuie să îi dimensionezi cu un element în plus! Atenție la greșelile astea, de clasa a cincea :-)
  • Tatomir: Program foarte bun, bravo! Observație minoră, cînd testezi finalul de listă folosești inegalitate (!=) nu comparație. Altfel presupui că el este zero.
  • Teodorescu: Program foarte bun, bravo!
  • Voicu: Ideea programului este bună. Dacă repari obesrvațiile cu grav de mai jos programul tău trece toate testele. Ia aminte la observații, trebuie să îți corectezi stilul de programare. Iată observațiile:
    • Grav: ai denumit greșit fișierul de intrare! Atenție la greșeli de gîgă!
    • Grav: nu ai afișat rezultatul în formatul cerut în enunț!
    • Indentarea! Atenție, nu ai voie să ai greșeli de indentare.
    • Denumirile variabilelor sînt greoaie și greu de urmărit. În loc de vlist[] era mai bine col[] sau coloane[]. În loc de nnlist[] era mai bine next[] care este o denumire clasică.
    • Atenție la dimensionări! Vectorul de bile v[] are doar 2000 de elemente, nu 10000! Așa ceva te poate costa la olimpiadă. Dacă declarai constante cu #define poate nu aveai problema asta.
    • Minor: te-ai complicat adăugînd la coada listei. Este mai ușor să adaugi la început. Scăpai de vectorul finish[].
    • Minor: ar fi bine sa nu declari variabile prin cod, doar la început.

Rezolvare cu liste

Vom memora atîtea liste cîte coloane avem. Fiecare listă va stoca numerele de coloane la care avem obstacole în acea listă. Liniile ce nu au obstacole vor fi reprezentate ca liste vide.

Iată conceptul structurii de date pe care o vom folosi.

Exemplul din problema bile1
Exemplul din desenul problemei - concept structură de date

Pentru implementare vom folosi ca structuri de date:

  • un vector b[n] care memoreaza linia cu bile,n fiind numărul de coloane
  • un vector liste[m] care pentru fiercare linie pointează la o listă de coloane pe care se află obstacole, m fiind numărul de linii.
  • doi vectori col[p] și next[p] care memorează coloanele obstacolelor și următorul obstacol pe linie, p fiind numărul de obstacole.

Algoritmul folosit este următorul:

1. Citește m, n și p, setează i la zero
2. Citește fiecare obstacol (l, c) si:
  2.1 col[i] = c
  2.2 adaugă coloana c la lista de pe linia l, liste[l]:
    2.2.1 next[i] = liste[l]
    2.2.2 liste[l] = i
  2.3 i = i + 1
3. Citește vectorul de bile
4. Pentru fiecare linie l de la 1 la m
  4.1 parcurge lista de coloane liste[l] si pentru fiecare obstacol col[i] din listă:
    4.1.1 actualizează vectorul de bile la indicele coloanei, col[i]

Cum se compară cu algoritmul inițial care folosește o matrice caracteristică?

Structură de date Complexitate timp Complexitate memorie Explicații
Matrice de frecvență a obstacolelor O(m\times n+p) O(m\times n) Parcurgerea matricei de frecvență este O(m\times n), iar prelucrarea obstacolelor este O(p)
Vector de liste de coloane ale obstacolelor O(m+n+p) O(m+n+p) Vom parcurge strict obstacolele, de unde rezultă complexitatea O(p). Parcurgem și numerele inițiale, pentru citire, deci O(n). Parcurgem și toate liniile matricei, pentru a verifica dacă avem o listă cu obstacole, deci O(m).

Observăm că atît timpul cît și memoria se îmbunătățesc substanțial. Problema fiind dată la clasa a șasea este puțin probabil că aceasta a fost soluția dorită. Cu toate acestea este un caz de studiu interesant unde o structură simplă de date, pe care olimpici și profesori o ignoră adesea în rezolvarea problemelor de olimpiadă, poate duce la un algoritm simplu și foarte eficient.

Iată o implementare posibilă:

#include <stdio.h>

int lin[2001];               // capetele de lista
int col[10001], next[10001]; // celulele listelor
int bile[2000];              // bilele ce vor fi redistribuite

int main () {
  FILE *fin, *fout;
  int m, n, p, i, pc, l, c;

  fin = fopen( "bile1.in", "r" );
  fscanf( fin, "%d%d%d", &m, &n, &p );
  for ( i = 1; i <= p; i++ ) {      // citire obstacole
    fscanf( fin, "%d%d", &l, &c );
    col[i] = c;         // asezam coloana c in lista liniei l
    next[i] = lin[l];   // coloana noua vine la inceputul listei liniei l
    lin[l] = i;
  }
  for ( i = 0; i < n; i++ )        // citire bile pe prima linie
    fscanf( fin, "%d", &bile[i] );
  fclose( fin );

  // parcurgem liniile in ordine si cautam coloane cu obstacole
  for ( l = 1; l <= m; l++ ) {
    pc = lin[l];
    while ( pc != 0 ) { // cita vreme mai avem elemente in lista
      c = col[pc] - 1; // avem obstacol la coloana c
      bile[c-1] += bile[c] / 2 + bile[c] % 2; // n/2 + 1 in stinga
      bile[c+1] += bile[c] / 2;               // n/2 in dreapta
      bile[c] = 0;
      pc = next[pc];   // trecem la urmatorul element din lista
    }
  }

  fout = fopen( "bile1.out", "w" );
  for ( i = 0; i < n; i++ )
    fprintf( fout, "%d\n", bile[i] );
  fclose( fout );

  return 0;
}

Tema opțională - rezolvări

Zigzag

Problema zigzag a fost dată la ONI 2012 clasa a 7a.

Rezolvare cu liste

Problema are o rezolvare foarte ușoară cu liste. Ca și la bile1, vom ține minte pentru fiecare linie a matricei de codificare cîte o listă cu coloanele unde apar litere. Vom genera aceste liste parcurgînd în matrice pozițiile (l, c) unde s-ar afla textul (înainte de a citi acel text!) și adăugînd coloana c la lista liniei l. Apoi vom parcurge aceste liste, în ordine, și vom atașa fiecărei celule, pe lîngă coloană, o literă din text. De fapt vom vedea că nici nu avem nevoie să stocăm coloanele, ci doar literele. În final vom parcurge celulele în ordinea alocării lor, deoarece ea este chiar ordinea textului decodificat.

Iată conceptul structurii de date pe care o vom folosi:

Exemplul din problema zigzag
Exemplul din desenul problemei - concept structură de date

O diferență față de bile1 este că va trebui să ținem nu numai vectorul cu începutul listelor ci și un vector cu ultimul element din listă pentru a putea face adăugarea la coadă foarte rapid. O alternativă ar fi să parcurgem pozițiile in ordine inversă (pare mai complicat, însă). Să denumim vectorii prim[] și ultim[].

Iată o implementare posibilă:

#include <stdio.h>

#define MAXCOL 50000
#define MAXLIN 5000

int prim[MAXLIN], ultim[MAXLIN];
int next[MAXCOL + 1];
char car[MAXCOL + 1];

int main() {
  FILE *fin, *fout;
  int n, cheie, l, c, pas;
  int i;

  fin = fopen( "zigzag.in", "r" );
  fscanf( fin, "%d%d", &cheie, &n );
  fgetc( fin );

  // pregatim listele cu pozitiile in matricea cheie
  // cheie este cheia, iar n este numărul de caractere al mesajului, 
  // c aloca celulele listei si este si coloana in acelasi timp
  l = 0;
  pas = 1; // initial linia creste din unu in unu
  // nu putem avea celule pe indexul 0 deoarece cu zero codificam finalul 
  // de lista, deci codificam coloanele incepind cu 1, no biggie
  for ( c = 1; c <= n; c++ ) { 
    // pentru fiecare coloana a matricei calculam 
    // linia corespunzatoare literei (este una singura!)
    // liniile vor fi de la zero, nici un motiv sa le numerotam de la 1
    // avem perechea (l, c): aseaza c in lista l
    next[c] = 0;          // nu urmeaza nimeni după mine, sint ultima celula
    if ( prim[l] == 0 )   // lista este vida
      prim[l] = ultim[l] = c;
    else                  // avem un ultim element
      ultim[l] = next[ultim[l]] = c;// atasam celula la coada ultimului element

    // avanseaza linia
    l = l + pas;
    if ( l < 0 || l >= cheie ) { // daca am depasit marginea inversam pasul
      pas = -pas;
      l = l + pas + pas; // adunam de doua ori pasul pentru a ne intoarce
    }
  }

  // parcurgem listele pe linii si completam cu caractere citite de la intrare
  for ( l = 0; l < cheie; l++ ) {
    c = prim[l];
    while ( c != 0 ) {
      car[c] = fgetc( fin );
      c = next[c];
    }
  }
  fclose( fin );

  fout = fopen( "zigzag.out", "w" );
  // afisam caracterele in ordinea lor naturala din vector
  for ( c = 1; c <= n; c++ )
    fputc( car[c], fout );
  fputc( '\n', fout );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție?

Este, sper, destul de clar că atît timpul cît și memoria vor fi liniare în numărul de caractere de la intrare și mărimea cheii, adică O(n + c). Din nou, folosirea unei liste rezultă într-un algoritm simplu și eficient.

La coadă

Problema lacoada a fost dată la cercul Vianu 2014 clasele 9/10. Este o problemă grea prin gradul de detaliu atît la elaborarea algoritmului, cît și la implementare.

Comentarii generale

  • Este o problemă foarte grea. Felicitări celor ce au reușit să o rezolve: Asgari, Ilie, Voicu.
  • Extra felicitări celor ce au dat o rezolvare ne-dopată, gîndită chiar de ei, cu liste simplu înlănțuite: Ilie. Sfatul meu pentru ceilalți doi: gîndiți cu capul vostru, este în general util.

Rezolvare

Vom memora coada ca pe o listă. O celulă a listei va conține numărul persoanei și o legătură către următoarea persoană.

Vom memora, de asemenea, o a doua listă, a celulelor "libere". Pe măsură ce persoanele sînt servite, ele pleacă și celulele lor trebuie eliberate pentru a fi folosite.

Cel mai simplu este ca lista celulelor libere să fie legată în continuarea listei cu persoane.

Vom menține de asemenea două legături speciale: una la începutul listei și una la începutul listei de celule libere. Le vom memora într-o celulă santinelă, aflată pe poziția zero.

Vom mai avea nevoie de un vector care, pentru fiecare număr de persoană x va memora celula din listă anterioară celulei care conține persoana x. Astfel vom putea afla imediat care este celula (și deci și persoana) din-naintea persoanei x.

Cu aceste structuri de date cele trei operații, servire, venire și îmbrîncire se pot efectua în O(1). Va trebui să avem grijă ca pe tot parcursul algoritmului să menținem cele trei structuri de date astfel încît ele să fie permanent corecte.

Iată o implementare posibilă (circa 100 de linii de cod efectiv):

#include <stdio.h>
#include <ctype.h>

#define MAXN 60000
#define MAXPERS 500000
#define HEAD_PERS 0

// celulele listelor
int pers[MAXN + 2]; // cheia este numarul persoanei
unsigned short next[MAXN + 2];

// prev_cell[x] = indicele celulei din fata persoanei cu numarul x
unsigned short prev_cell[MAXPERS + MAXN + 2]; 

FILE *fin, *fout;

// citeste un intreg la intrare si-l returneaza
int readInt() {
  int ch, n = 0;
  
  while ( isdigit( ch = fgetc( fin ) ) )
    n = n * 10 + ch - '0';

  return n;
}

// - initializeaza o lista cu numerele de la 1 la n, in aceasta ordine
// - foloseste o santinela pe pozitia 0. In acest fel orice element din lista
//   are un element anterior
// - foloseste si o santinela de final, pentru a avea mereu o celula libera
// - dupa ultima celula din lista se afla lista celulelor nefolosite
// - pers[0] memoreaza indicele primei celule din lista celulelor nefolosite
void initQueue( int n ) {
  int i;
  
  // initializam lista persoanelor
  for ( i = 1; i <= n + 1; i++ ) {
    pers[i] = i;
    next[i - 1] = i;
    prev_cell[i] = i - 1; // celula din-naintea persoanei i este i-1
  }
  pers[n + 1] = MAXPERS + MAXN + 1; // persoana imposibil de atins
  prev_cell[pers[n + 1]] = n;       // celula anterioara lui pers[n + 1]
  pers[HEAD_PERS] = n + 1;          // legatura la prima celula libera
}

void printQueue( FILE *fout ) {
  int l = next[HEAD_PERS]; // prima celula

  while ( l != pers[HEAD_PERS] ) {   // cita vreme mai avem elemente in lista
    fprintf( fout, "%d ", pers[l] ); // afiseaza elementul curent
    l = next[l];                     // avanseaza la elementul urmator
  }
  fputc( '\n', fout );
}

int main() {
  int n, k, i, ch, aux, pos, qlen;

  fin = fopen( "lacoada.in", "r" );
  fscanf( fin, "%d%d ", &n, &k );
  initQueue( n ); // initializare coada cu n oameni
  qlen = n;       // numarul de persoane la coada
  for ( i = 0; i < k; i++ ) { // citim k operatii
    ch = fgetc( fin );
    fgetc( fin );             // citeste spatiu sau \n
    switch ( ch ) {
    case '1': // servire prima persoana - eliminam prima celula din lista
      qlen--; // numarul de persoane scade
      aux = next[HEAD_PERS];       // memoram celula eliminata
      next[HEAD_PERS] = next[aux]; // eliminam primul element al listei
      prev_cell[pers[next[HEAD_PERS]]] = HEAD_PERS; // anterior primei persoane

      // adaugam celula aux la lista celulelor libere, la inceput
      pos = prev_cell[pers[pers[HEAD_PERS]]]; // anterior primei celule libere
      next[aux] = pers[HEAD_PERS]; // ii atasam capul listei de celule libere
      prev_cell[pers[next[aux]]] = aux; // anteriorul persoanei este chiar aux
      next[pos] = aux;          // legam ultima celula ocupata la prima libera
      prev_cell[pers[next[pos]]] = pos; // noul anterior al lui pers[aux]
      pers[HEAD_PERS] = aux;
      break;
    case '2': // adaugare persoana la coada - adaugam o celula la coada listei
      qlen++; // numarul de persoane creste
      n++;    // eticheta urmatoarei persoane ce vine la coada
      pos = prev_cell[pers[pers[HEAD_PERS]]]; // ultima celula ocupata
      pers[pers[HEAD_PERS]] = n;              // noua persoana
      prev_cell[n] = pos; // memoram persoana din-naintea ei
      // memoram n ca fiind anteriorul celui de dupa el
      prev_cell[pers[next[pers[HEAD_PERS]]]] = pers[HEAD_PERS];
      pers[HEAD_PERS] = next[pers[HEAD_PERS]]; // actualiz. prima celula libera
      break;
    default: // imbrincire
      pos = prev_cell[readInt()]; // celula anterioara celulei persoanei x
      aux = next[pos];            // legatura la celula de scos din lista
      next[pos] = next[aux];      // eliminam celula aux
      // actualizam cine este inaintea persoanei de dupa aux
      prev_cell[pers[next[pos]]] = pos; // actualiz. anteriorul lui next[pos]

      next[aux] = next[HEAD_PERS]; // punem persoana imbrincita in capul listei
      prev_cell[pers[next[aux]]] = aux; // memoram anteriorul lui next[aux];
      next[HEAD_PERS] = aux;            // memoram capul listei
      prev_cell[pers[aux]] = HEAD_PERS; // memoram anteriorul lui aux
    }
  }
  fclose( fin );

  fout = fopen( "lacoada.out", "w" );
  fprintf( fout, "%d\n", qlen );
  printQueue( fout );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție?

Deoarece orice operație se execută în O(1) vom avea o complexitate în timp de O(n + k).

Memoria folosită este cea pentru listă și vectorul de poziții în listă ale persoanelor, adică O(n + k).

Rezolvări aici [1]

Lecție

Liste - continuare

Să vedem cîteva exemple de manipulare a listelor. În toate aceste exemple vom considera liste de întregi reprezentate astfel:

int key[MAXL];  // valori intregi memorate de lista
int next[MAXL]; // următorul element in lista

Lista este definită de prima sa celulă:

int l;

Lungimea unei liste

Să se calculeze lungimea unei liste.

// returneaza numarul de elemente al unei liste
int listLen( int l ) {
  int len = 0;         // initial lungimea este zero

  while ( l != NIL ) { // l pointeaza la o celula?
    len++;             // numaram acea celula
    l = next[l];       // si avansam la urmatoarea celula
  }

  return len; // returnam numarul de celule numarate
}

Cautare liniară element in listă

Să se caute indicele (pointerul) primei celule ce conține un element.

// returneaza indicele celulei care contine elementul e
// sau NIL daca el nu exista
int listFind( int e, int l ) {
  while ( l != NIL && key[l] != e ) // avem o celula in l si nu contine e?
    l = next[l];                    // avansam la urmatoarea celula

  return l; // l va fi fie celula elementului gasit, fie NIL cind negasit
}

Răsturnare listă

Să se răstoarne o listă. La final lista inițială va fi distrusă. Lista cea nouă va conține exact celulele listei originale, dar cu elementele în ordine inversă.

// rastoarna lista primita si returneaza lista rasturnata
// distruge lista initiala
int listReverse( int l ) {
  int cell,  // pointer la o celula
    r = NIL; // lista noua, cea rasturnata
    
  while ( l != NIL ) {
    cell = l;       // memoram celula curenta, capul listei l
    l = next[l];    // avansam in lista l
    next[cell] = r; // adaugam celula curenta in capul listei r
    r = cell;       // cell devine lista r
  }

  return r;
}

Eliminare duplicate în listă sortată crescător

Dată o listă ale cărei elemente sînt ordonate crescător, să se transforme în listă mulțime prin eliminarea duplicatelor.

// transforma o lista ordonata crescator intr-o lista multime
// prin eliminarea duplicatelor
// nu schimba elementul initial al listei
void listSet( int l ) {
  if ( l != NIL ) {
    while ( next[l] != NIL )
      if ( key[next[l]] == key[l] ) // elementul urm este egal cu cel curent?
        next[l] = next[next[l]];    // daca da, elimina elementul urmator
      else
        l = next[l];                // altfel avanseaza la elementul urmator
  }
}

Exemplu de folosire a funcțiilor de mai sus

Iată un program care folosește funcțiile de mai sus:

// Exemple de implementare diverse operatii elementare pe liste
#include <stdio.h>

#define NIL -1
#define MAXL 1000

int key[MAXL];  // valori intregi memorate de lista
int next[MAXL]; // următorul element in lista

// returneaza numarul de elemente al unei liste
int listLen( int l ) {
  int len = 0;         // initial lungimea este zero

  while ( l != NIL ) { // l pointeaza la o celula?
    len++;             // numaram acea celula
    l = next[l];       // si avansam la urmatoarea celula
  }

  return len; // returnam numarul de celule numarate
}

// returneaza indicele celulei care contine elementul e
// sau NIL daca el nu exista
int listFind( int e, int l ) {
  while ( l != NIL && key[l] != e ) // avem o celula in l si nu contine e?
    l = next[l];                    // avansam la urmatoarea celula

  return l; // l va fi fie celula elementului gasit, fie NIL cind negasit
}

// rastoarna lista primita si returneaza lista rasturnata
// distruge lista initiala
int listReverse( int l ) {
  int cell,  // pointer la o celula
    r = NIL; // lista noua, cea rasturnata
    
  while ( l != NIL ) {
    cell = l;       // memoram celula curenta, capul listei l
    l = next[l];    // avansam in lista l
    next[cell] = r; // adaugam celula curenta in capul listei r
    r = cell;       // cell devine lista r
  }

  return r;
}

// transforma o lista ordonata crescator intr-o lista multime
// prin eliminarea duplicatelor
// nu schimba elementul initial al listei
void listSet( int l ) {
  if ( l != NIL ) {
    while ( next[l] != NIL )
      if ( key[next[l]] == key[l] ) // elementul urm este egal cu cel curent?
        next[l] = next[next[l]];    // daca da, elimina elementul urmator
      else
        l = next[l];                // altfel avanseaza la elementul urmator
  }
}

// tipareste elementele unei liste cu un spatiu intre ele
void listPrint( int l, FILE *f ) {
  while ( l != NIL ) {
    fprintf( f, "%d ", key[l] );
    l = next[l];
  }
}

int main() {
  FILE *fin, *fout;
  int n, i, e1, e2, l, r;

  fin = fopen( "lista.in", "r" );
  fscanf( fin, "%d%d%d", &n, &e1, &e2 );
  if ( n == 0 )
    l = NIL;
  else {
    l = 0;
    for ( i = 0; i < n; i++ ) {
      fscanf( fin, "%d", &key[i] );
      next[i] = i + 1;
    }
    next[n - 1] = NIL;
  }
  fclose( fin );
  
  fout = fopen( "lista.out", "w" );
  fprintf( fout, "lista citita: [" );
  listPrint( l, fout );
  fprintf( fout, "]\n" );

  fprintf( fout, "lungime: %d\n", listLen( l ) );

  fprintf( fout, "celula cu cheie %d are indice %d\n", e1, listFind( e1, l ) );
  fprintf( fout, "celula cu cheie %d are indice %d\n", e2, listFind( e2, l ) );

  r = listReverse( l );

  fprintf( fout, "lista inversata: [" );
  listPrint( r, fout );
  fprintf( fout, "]\n" );

  listSet( r );

  fprintf( fout, "lista multime: [" );
  listPrint( r, fout );
  fprintf( fout, "]\n" );

  fprintf( fout, "lungime: %d\n", listLen( r ) );
  fclose( fout );

  return 0;
}

Programul de mai sus a fost executat pe următorul fișier de intrare, lista.in:

10 6 1
9 9 7 7 6 5 5 4 3 3 2

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[].

Vă rămîne ca temă de gîndire:

  • Ușor: O(n2) - unde n este numărul de elemente al listei
  • Greu: O(n)

Aplicație: problema 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.

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. Succes! :-)

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

Aplicație: problema 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.

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.

Temă

Tema 3 clasa a 7a

  • onigim dată la ONI 2013 clasa a 5a rezolvată cu liste
  • macheta dată la ONI 2011 clasa a 8a rezolvată cu liste
  • Opțional: gîndiți-vă la problema din curs, cum detectăm dacă o listă are o buclă în O(n)

Rezolvări aici [2]