Difference between revisions of "Clasa a VII-a lecția 12 - 28 nov 2019"

From Algopedia
Jump to: navigation, search
Line 414: Line 414:
 
Cîtă memorie folosește acest algoritm?
 
Cîtă memorie folosește acest algoritm?
  
''O(N + L)'' memorie, mai exact 4'''·'''32000 = 128KB.
+
''O(N + L)'' memorie, mai exact 4'''·'''32000 = 64KB.
  
 
'''Observații''':
 
'''Observații''':

Revision as of 01:25, 29 November 2019

Anunțuri

Un NU hotărît descărcatului testelor

(Este bine că nu știți de unde vine expresia un nu hotărît și nici nu va trebui să știți vreodată.)

Unii din voi descarcă testele. Acest lucru este evident după numărul de punctaje perfecte. Problemele sînt suficient de grele pentru a nu permite un punctaj de 100p din prima încercare. Sigur, unii din voi muncesc și își creează teste proprii amănunțite. Dar nu toți. După doi ani vă cunosc suficient de bine. Știu cine este disperat după puncte dintre cei ce au luat punctaje perfecte.

Testele pot fi găsite. Sînt descărcabile pe diverse site-uri. Cei care le descărcați vă furați singuri căciula. Nu veți învăța să vă testați programele, iar la concurs nu veți avea testele. În plus, riscați să mă supărați. Deocamdată nu mă urnesc să fac investigații. Vă rog nu treziți gigantul care doarme. Dacă mă siliți să fac pe detectivul, pentru a merita așa un efort neplăcut, va trebui să iau măsuri punitive la final.

Un NU hotărît copiatului surselor

Repet: este interzis să copiați surse ca atare, chiar și de la cei mai buni dintre cei buni. Este drept că imitația este cea mai înaltă formă de compliment. Sînt măgulit cînd îmi văd sursa trimisă de voi. Nu mă măguliți prea tare, căci nu e bine, mi-o iau în cap.

Întrebare: credeți că există un grad de transformare a propriului meu cod astfel încît să nu mi-l recunosc?

Răspuns: nu.

Sînt extrem de dezamăgit că un elev sclipitor, ca Tudor Voicu, se pretează la a copia cu nerușinare surse.

Tema - rezolvări

De data aceasta am corectat temele celor de la topul clasamentului (dintr-un spirit de fair play).

Tower

Problema tower a fost dată la concursul de la Shumen din 2016, secțiunea juniori.

Comentarii individuale

  • Asgari: programul pare corect, dar te complici. Cred că din cauză că nu ai gîndit bine algoritmul, sau ai gîndit un algoritm complicat.
  • Calotă: Program foarte bun! Numai că nu este al tău, este al meu. M-am uitat pe programul tău, era cu totul altfel. Jenant.
  • Dobre: nu mi-e clar ce face programul tău. Pare bine, dar fără comentarii nu pot să comentez :-) În mod cert te complici, deci vezi soluția de mai jos.
  • Fares: algoritm corect, dar oarecum încîlcit, pare același ca la mulți alții. Menții numărul de clădiri vizibile într-un mod complicat. Vezi soluția de mai jos.
  • Mușat: algoritmul pare corect, dar încîlcit. Nu am stat prea mult să îl studiez, vezi te rog mai jos un algoritm mai simplu. Vezi că ai avertisment de compilare. Nu unul grav, dar mi-e teamă că nu te uiți la ele, ceea ce este grav.
  • Nicu: Program foarte bun, bravo! Ca idee, cîtă vreme accesezi direct vectorul stiva[] nu ai o implementare "curată" a stivei cu funcții, ca tip de date abstract.
  • Rebengiuc: Program foarte bun, bravo! Drăguț! Ai implementat stiva ca tip de date abstract :)
  • Tatomir: program bun! Are o mică complicație, pui pe stivă înălțimi mai mari decît cea a turnului. Vezi soluția de mai jos.
  • Togan: Multe, multe cazuri particulare inutile. Program necitibil. Măcar dacă puneai comentarii.
  • Voicu T: Program perfect! Doar că nu este al tău. Este al meu.

Soluție

Soluția este clasică, semănînd cu problema clădirilor vizibile prezentată la curs. Vom avea o stivă de înălțimi descrescătoare, iar clădirea curentă va elimina de pe stivă înălțimile mai mici ca ea.

Ce diferă (sau ce avem în plus) față de problema clădirilor vizibile?

  • Nu vom așeza pe stivă clădiri mai înalte decît turnul, deoarece ele nu văd turnul.
  • Dar vom elimina clădirile mai mici ca ea, deoarece ea blochează acele clădiri din stivă, ele devenind nevizibile.

Observații de implementare:

  • Primul element pe stivă este o santinelă, mai mare decît orice clădire (denumită INFINIT). Motive:
    • Program mai scurt și mai simplu, ne scutește de a trata cazul particular cînd stiva este goală.
    • Program mai eficient, vom avea un singur test (în loc de două) în bucla de eliminare a clădirilor mai mici.

Iată o soluție posibilă:

#include <stdio.h>

#define MAXN 1000000
#define INFINIT 1000000001

int stiva[MAXN + 1]; // stiva de cladiri in ordine descrescatoare

int main() {
  FILE *fin, *fout;
  int n, i, ht, h, sp, max;

  fin = fopen( "tower.in", "r" );
  fscanf( fin, "%d%d", &n, &ht ); // numarul de bete, inaltimea turnului
  stiva[0] = INFINIT; // santinela pentru a avea mereu un element pe stiva
  sp = max = 0;       // sp = pozitia virfului stivei, max = rezultatul cerut
  for ( i = 0; i < n; i++ ) {
    fscanf( fin, "%d", &h ); // turnul curent din sir
    while ( h > stiva[sp] )  // eliminam din stiva elementele mai mici
      sp--;
    if ( h <= ht ) {   // daca inaltimea curenta e mai mica decit turnul
      stiva[++sp] = h; // o punem pe stiva 
      if ( sp > max )  // toate elementele de pe stiva vad turnul
        max = sp;      // verificam daca numarul lor e mai mare decit maximul
    }
  }
  fclose( fin );

  fout = fopen( "tower.out", "w" );
  fprintf( fout, "%d\n", max );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție?

Precum am prezentat la curs ea este O(n) amortizat.

Iar memoria?

Stiva este și ea O(n) pe cazul cel mai rău. Mai exact vom folosi un milion de întregi, deci circa 4MB.

Maxp

Problema maxp a fost dată la OJI 2013 clasa a 8a.

Comentarii individuale

  • Asgari: program foarte bun, bravo! O îmbunătățire ar fi să folosești două santinele în capetele vectorului.
  • Calotă: Program foarte bun. Dar dacă nu este al meu, este inspirat major după al meu. Programul tău original nu avea nici o treabă cu ceea ce ai trimis la temă. Jenant.
  • Dobre: ideea de calcul este bună, codul de asemenea. Dar felul cum o faci nu are nici o legătură cu ceea ce am făcut la curs (nu ai o stivă) ceea ce mă face să mă întreb a cui este soluția. Știi să demonstrezi că este O(n)?
  • Fares: Program bun. Partea cea mai simplă, codul de calcul al puterilor, are probleme. Să vedem:
  max1 = cnt = 0;
  for (i = 1; i <= n; i++) {
    s = st[i] + 1;
    d = dr[i] - 1;
    nr = (d - i + 1) * (i - s + 1);
    if (nr > max1) {
      max1 = nr;
      cnt = 1;
    }
    else if (nr == max1)
      cnt++;
  }

În primul rînd că înmulțirea dă depășire. Trebuia să o faci pe long long. Ai avut noroc. Doi, aduni unu pentru ca apoi să îl scazi? Ce sens are? Codul pieptănat arată așa:

  max1 = cnt = 0;
  for (i = 1; i <= n; i++) {
    s = st[i];
    d = dr[i];
    nr = ((long long)(d - i)) * (i - s);
    if (nr > max1) {
      max1 = nr;
      cnt = 1;
    }
    else if (nr == max1)
      cnt++;
  }

Moment la care poți să renunți la variabilele s și d și să scrii direct:

  max1 = cnt = 0;
  for (i = 1; i <= n; i++) {
    nr = ((long long)(dr[i] - i)) * (i - st[i]);
    if (nr > max1) {
      max1 = nr;
      cnt = 1;
    }
    else if (nr == max1)
      cnt++;
  }
  • Mușat: Algoritmul este foarte bun. Te-ai complicat. Setarea unui element din stivă la zero este inutilă. La fel și zeroizarea stivei între cele două parcurgeri. Dacă "overflow sucks" învață să scrii mai frumos. În loc de
        aux = st[i];
        aux *= dr[i]; /// Overflow sucks

puteai scrie:

        aux = ((long long)st[i]) * dr[i]; /// Overflow sucks less
  • Nicu: programul arată rezonabil. În mod straniu cele două treceri prin vector nu arată la fel. De ce? Te-ai complicat puțin, vezi soluția de mai jos.
  • Rebengiuc: Program aproape perfect, bravo! Ai noroc că nu dă depășire la calculul efectiv al puterilor: p = len_st[i] * len_dr[i];
  • Tatomir: ideea de calcul este bună, codul de asemenea. Dar felul cum o faci nu are nici o legătură cu ceea ce am făcut la curs (nu ai o stivă) ceea ce mă face să mă întreb a cui este soluția. Știi să demonstrezi că este O(n)? La final ai o complicăreală:
  for(i=0;i<n;i++){
    st1[i]=i-st1[i]-1;
    st2[i]=st2[i]-i-1;
    nr=st1[i]*st2[i];
    nr=nr+st1[i]+st2[i]+1;

Scazi unu pentru a adăuga înapoi unu. Dacă aplici matematică de bază codul de mai sus se poate înlocui cu:

  for(i=0;i<n;i++){
    st1[i]=i-st1[i];
    st2[i]=st2[i]-i;
    nr=st1[i]*st2[i];
  • Togan: ideea de calcul este bună, codul de asemenea. Dar felul cum o faci nu are nici o legătură cu ceea ce am făcut la curs (nu ai o stivă) ceea ce mă face să mă întreb a cui este soluția. Știi să demonstrezi că este O(n)? Asta, plus simplitatea codului mă face să cred că nu este complet scris de tine.
  • Voicu T: Program bun. Nu declara variabile cu același nume dar cu litere mici schimbate în mari. Este periculos, greu de citit, duce la buguri. Codul while(v[i]>v[st[k]] && k>0) este periculos, inversează testele. Dacă foloseai santinele puteai elimina complet testul k>0. Exemplu de cod neelegant:
        st[++k]=i;
        Dr[i]=st[k-1];

Puteai scrie mai elegant:

        Dr[i]=st[k];
        st[++k]=i;

Noroc cu compilatoarele, că se prind și ne repară greșelile.

Soluție

Problema tradusă în limbaj informatic sună astfel: se dă un vector de maxim 200000 de elemente naturale. Să se găsească pentru fiecare element indicii celor mai apropiate elemente mai mari sau egale cu elementul, atît la stînga cît și la dreapta. Avînd acești indici, precum și indicele elementului curent, putem calcula puterea elementului folosind o formulă relativ simplu de dedus.

Această problemă este similară cu problema clădiri vizibile prezentată la curs. Trebuie să parcurgem vectorul de două ori, odată într-o direcție și apoi în cealaltă, aflînd indecșii ceruți.

Să presupunem că avem i < k < j astfel încît v[i] >= v[k] <= v[j], iar i este maximal și j este minimal. Care este numărul de secvențe din care face parte v[k]? Orice secvență din care face parte v[k] va avea indicele capătului din stînga în intervalul (i..k]. Similar, ea va avea capătul din dreapta în intervalul [k..j). Orice secvență care respectă aceste capete este una din care v[k] poate face parte. Cîte astfel de secvențe avem? În mod clar (k-i)·(j-k).

Iată o soluție posibilă:

#include <stdio.h>

#define MAXN 200000
#define INFINIT 1000000

int v[MAXN+2], ist[MAXN+2], idr[MAXN+2], stiva[MAXN+1];

int main() {
  FILE *fin, *fout;
  int n, i, sp, nmax;
  long long p, pmax;

  fin = fopen( "maxp.in", "r" );
  fscanf( fin, "%d", &n );
  v[0] = v[n+1] = INFINIT; // santinele la capetele vectorilor
  for ( i = 1; i <= n; i++ )
    fscanf( fin, "%d", &v[i] );
  fclose( fin );

  // pentru fiecare poz calculam prima poz la stinga cu valoarea >=
  stiva[sp = 0] = 0; // indicele valorii infinite
  for ( i = 1; i <= n; i++ ) {
    while ( v[stiva[sp]] < v[i] ) // scoatem elementele mai mici din stiva
      sp--;
    ist[i] = stiva[sp];
    stiva[++sp] = i;
  }

  // pentru fiecare poz calculam prima poz la dreapta cu valoarea >=
  stiva[sp = 0] = n + 1; // indicele valorii infinite
  for ( i = n; i > 0; i-- ) {
    while ( v[stiva[sp]] < v[i] ) // scoatem elementele mai mici din stiva
      sp--;
    idr[i] = stiva[sp];
    stiva[++sp] = i;
  }

  // calculam puterea maxima a unui numar
  pmax = nmax = 0;
  for ( i = 1; i <= n; i++ ) {
    p = ((long long)(i - ist[i])) * (idr[i] - i); // nr secvente ce-l contin
    if ( p > pmax ) {
      pmax = p;
      nmax = 1;
    } else if ( p == pmax )
      nmax++;
  }

  fout = fopen( "maxp.out", "w" );
  fprintf( fout, "%lld\n%d\n", pmax, nmax );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție?

Ea este O(n) amortizat ca timp și memorie.

Memoria folosită de această soluție este patru vectori de întregi a maxim 200 000 elemente, aproximativ 3.2MB.

Observăm o repetiție de cod. Cum putem factoriza? Iată o factorizare simplă folosind funcții:

#include <stdio.h>

#define MAXN 200000
#define INFINIT 1000000

int v[MAXN+2], ist[MAXN+2], idr[MAXN+2], stiva[MAXN+1];

// pentru fiecare pozitie calculam prima poz la stinga/dreapta cu valoarea >=
void calcPrimulMaiMare( int start, int stop, int pas, int rez[] ) {
  int i, sp;

  v[start - pas] = INFINIT;       // santinela de la capatul vectorului
  stiva[sp = 0] = start - pas;    // indicele valorii infinite
  for ( i = start; i != stop; i += pas ) {
    while ( v[stiva[sp]] < v[i] ) // scoatem elementele mai mici din stiva
      sp--;
    rez[i] = stiva[sp];
    stiva[++sp] = i;
  }
}

int main() {
  FILE *fin, *fout;
  int n, i, nmax;
  long long p, pmax;

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

  calcPrimulMaiMare( 1, n + 1, 1, ist ); // valorile mai mari la stinga
  calcPrimulMaiMare( n, 0, -1, idr );    // valorile mai mari la dreapta

  // calculam puterea maxima a unui numar
  pmax = nmax = 0;
  for ( i = 1; i <= n; i++ ) {
    p = ((long long)(i - ist[i])) * (idr[i] - i); // nr secv ce-l contin
    if ( p > pmax ) {
      pmax = p;
      nmax = 1;
    } else if ( p == pmax )
      nmax++;
  }

  fout = fopen( "maxp.out", "w" );
  fprintf( fout, "%lld\n%d\n", pmax, nmax );
  fclose( fout );

  return 0;
}

Nrtri

Problema nrtri a fost dată la pregătire Vianu clasa a noua. Este, din nou, o problemă tipică de soluție amortizată.

Comentarii individuale

  • Asgari: program foarte bun, bravo! if( poz - j - 1 > 0 ) este inutil, condiția va fi mereu adevărată.
  • Calotă: cam aceeași soluție ca a lui Mușat, deci cam aceleași și comentariile. Aș fi vrut să văd măcar o soluție a ta la tema asta. O idee interesantă, nu sortezi bețele. Dar aceasta duce la mai multe teste necesare. Nu ai nevoie de tipul long long pentru calcule.
  • Dobre: idee excelentă. Cred că luai cu ea 100p la tema opțională dacă declarai în funcție variabila rez ca long long.
  • Fares: Felicitări! Ai reușit o soluție la nrtri1. Ca și observații:
    • redundanță: if (v1[v[i] + v[j]] - j > 0) este inutil, va fi mereu adevărat.
    • tipărire optimizată inutil: nu are sens să optimizezi tipărirea unui singur număr :-) Nu este evident?
    • variabile denumite neclar
    • sortare prin numărare în loc de prin selecție, este mai lentă, nu?
  • Mușat: O idee interesantă, nu sortezi bețele. Dar aceasta duce la mai multe teste necesare. Nu ai nevoie de tipul long long. M-ai fentat declarînd constanta VALMAX ca 60000, am avut senzația că depășești vectorul. E un nume care induce în eroare, trebuia să o declari 30000 și să folosești VALMAX*2 acolo unde aveai nevoie de dublu.
  • Nicu: idee foarte bună și implementare la fel. De ce sortare prin selecție și nu prin numărare?
  • Rebengiuc: Idee foarte bună, program bun. Se putea simplifica. Uneori funcțiile maschează informații importante. Funcția nu își are rostul, ea are o linie. În loc de:
  nrtri = 0;
  for( i = 0 ; i < n ; i++ )
    for( j = 0 ; j < i ; j++ )
      nrtri += nmmse[lat[i] + lat[j] - 1] - nmmse[lat[i] - lat[j]] - (2 * lat[j] > lat[i]) - 1;

Puteai scrie ceva în genul (nu sînt absolut sigur de ajustare, dar formula poate fi făcută să meargă):

  nrtri = 0;
  for( i = 0 ; i < n ; i++ )
    for( j = 0 ; j < i ; j++ )
      nrtri += nmmse[lat[i] + lat[j] - 1] - i; // toate betele mai mici sint bune, dar trebuie sa fie mai mari ca i
  • Tatomir: Program foarte bun, bravo! Ideea de parcurgere inversă, de la mic la mare, duce la timpi mai mici. Din păcate nu suficient de mici pentru nrtri1.
  • Togan: Algoritm foarte bun! Implementat corect poate să rezolve nrtri1. Nu știu de ce nu iei 100p la nrtri1, dar bănuiala mea este că în funcția de numărare faci prea multe calcule pe long long. Programul este un pic încîlcit, introduci cazuri particulare inexistente. De exemplu, dacă n<=2 de ce mai citești numerele din fișier? :-)
  • Voicu T: Program foarte bun. Doar că nu este al tău. Este al meu. "Pentru orice eventualitate"? Cum ar fi eventualitatea că matematica se schimbă și deodată numărul de tripleți depășește int? Măcar dacă reparai acea greșeală, să nu fie codul identic.

Soluție forță brută

Putem genera toți tripleții de numere, testîndu-i dacă pot forma un triunghi. Pentru o testare mai simplă vom sorta numerele crescător. Astfel, pentru trei indici i < j < k testul de triunghi va fi bete[i] + bete[j] > bete[k].

Ce complexitate are această soluție?

Sortarea prin numărare va fi O(L) unde L este lungimea maximă a unui băț. Numărul de tripleți este combinări de N luate cîte 3, adică N·(N-1)·(N-2)/6, adică O(N3). Complexitatea totală este O(N3 + L). Ea nu se va încadra în timp pentru teste mari.

Soluție optimizată numărul unu

Pentru o soluție mai bună trebuie să ne dăm seama de următoarele lucruri:

  • Pentru indicii i și j fixați va exista un ultim indice k în vectorul ordonat astfel încît bete[i] + bete[j] > bete[k].
  • Toți indicii între j și k pot forma triunghiuri. Pentru i și j fixați, odată descoperit k maxim, vom avea k-j triunghiuri posibile.

Putem găsi k rapid? Deoarece vectorul este ordonat putem folosi căutarea binară. Algoritmul va fi: pentru fiecare pereche (i, j) caută binar k apoi adună k-j la numărul de triunghiuri.

Ce complexitate are această soluție?

Partea de sortare este aceeași, iar partea de numărare este O(N2log N). În continuare va pica teste mari.

Soluție optimizată numărul doi

Pentru a optimiza în continuare, mai avem nevoie de o observație în legătură cu ce se întîmplă cu k atunci cînd îl mărim pe j.

  • Să presupunem că avem indicii i < j, iar k este ultimul indice care poate forma un triunghi cu i și j.
  • Important: (i, j+1, k) pot forma un triunghi.

De ce? Deoarece suma bete[i] + bete[j+1] > bete[i] + bete[j] > bete[k]

Deci, atunci cînd mărim j nu trebuie să micșorăm k ci putem căuta un nou k mai mare.

Care este algoritmul rezultat?

Pentru fiecare indice i vom porni cu j și k poziții consecutive. Apoi vom mări k pînă la ultima poziție posibilă. Adunăm k-j la numărul de triunghiuri. Apoi incrementăm j și din nou mărim k pînă la ultima poziție posibilă și apoi adunăm k-j la sumă. Și tot așa pînă ce j ajunge la poziția n-2, ultima poziție. În acest moment incrementăm i și reluăm (j și k pe poziții consecutive).

Ce complexitate are acest algoritm?

La prima vedere el este la fel cu forța brută, avem trei bucle una în alta, deci O(N3). În realitate nu este așa. Analiza amortizată ne învață să ne uităm la numărul global de operații. Este drept că oricare din incrementările lui k se poate întîmpla de O(N) ori. Dar numărul total de incrementări ale lui k pentru i fixat este O(N). Deci numărul de incrementări total al lui j și k este maxim 2N, ceea ce înseamnă că pentru i fixat vom face O(N) operații. Deoarece i se va incrementa de N-2 ori complexitatea totală a numărării triunghiurilor este O(N2).

Complexitatea algoritmului este O(N2 + L). El se va încadra lejer în timpul alocat.

De reținut - aceasta este o tehnică des întîlnită:

  • Înlocuirea căutărilor binare multiple cu căutări liniare
    • Dacă problema se rezolvă cu N căutări binare
    • Și dacă rezultatul căutărilor binare este un indice nedescrescător de la o căutare la alta
    • Atunci putem înlocui căutările binare cu căutări liniare
    • Complexitatea se reduce cu O(log N)

Stați, cum? Adică înlocuim o tehnică mai rapidă cu una mai lentă și obținem un algoritm mai bun? Cum se poate așa ceva?

Da, exact așa este. Rezultă un algoritm mai bun deoarece căutarea binară este neinformată, pornește mereu de la zero, pe cînd căutarea liniară este una informată, știe de la început că va efectua maxim N operații.

Iată o soluție posibilă, bazată pe algoritmul de mai sus:

#include <stdio.h>

#define NMAX 2000
#define LMAX 30000

unsigned short lungimi[LMAX + 1], bete[NMAX + 1];

int main() {
  FILE *fin, *fout;
  int n, i, j, k, nrtri;

  // intializam vectorul frecventa al lungimilor (maxim LMAX)
  fin = fopen( "nrtri.in", "r" );
  fscanf( fin, "%d", &n );
  for ( i = 0; i < n; i++ ) {
    fscanf( fin, "%d", &j );
    lungimi[j]++;
  }
  fclose( fin );

  // sortam crescator lungimile betelor (maxim NMAX)
  n = 0;
  for ( i = 1; i <= LMAX; i++ )
    for ( j = lungimi[i]; j > 0; j-- )
      bete[n++] = i;

  // calculam numarul de triunghiuri
  nrtri = 0;
  for ( i = 0; i < n - 2; i++ ) {       // primul bat
    k = i + 2;                          // al treilea bat
    for ( j = i + 1; j < n - 1; j++ ) { // al doilea bat
      while ( k < n && bete[i] + bete[j] > bete[k] )
        k++;
      // acum k este prima pozitie care nu formeaza triunghi
      nrtri += k - j - 1;
    }
  }
  
  fout = fopen( "nrtri.out", "w" );
  fprintf( fout, "%d\n", nrtri );
  fclose( fout );

  return 0;
}

Cîtă memorie folosește acest algoritm?

O(N + L) memorie, mai exact 4·32000 = 64KB.

Observații:

  • Am folosit cei mai mici întregi pentru vectori, adică unsigned short int.
  • Acest lucru este important cînd memoria folosită este relativ mică, reducînd accesele la memorie în afara cache-ului
  • Pentru variabilele simple am folosit întregi, deoarece cele mai rapide operații vor fi pe întregi.
  • Concluzie: reducem întregii pe cît posibil, dar doar la vectori, nu și la variabile simple.

Tema opțională - rezolvări

Nrtri1

Problema nrtri1 este derivată din problema nrtri. Ea nu cere un algoritm de complexitate mai bună, ci o optimizare a constantei. Acest lucru necesită îmbunătățiri ale algoritmului, noi structuri de date și o implementare îngrijită.

Ați pescuit problema aceasta de ați înnebunit-o! Nu sînteți în stare să măsurați timpul propriului cod, deși v-am învățat cum anul trecut. Drept care folosiți varena drept tester. Urît!

Avem mai multe posibilități de a optimiza algoritmul anterior. Voi descrie aici ceea ce am văzut la voi, idei excelente ce duc la algoritmi care iau 100p. Nu voi menționa un algoritm și mai rapid, deoarece îl voi lăsa ca temă opțională (problema nrtri2.

Toate soluțiile se bazează pe aceeași idee, anume folosirea unui vector de sume parțiale ale lungimilor perechilor de bețe. Să vedem.

Soluție Yusuf Fares / Luca Ilie

Ideea de îmbunătățire este următoarea:

  • Pentru fiecare lungime posibilă între 1 și 2L calculăm cîte bețe au lungime strict mai mică decît acea lungime.
  • Pentru fiecare sumă de două bețe,

Arăt mai jos soluția lui Yusuf, care deși nu este cea mai scurtă este cea mai didactică dintre cele două, cu cîteva eliminări de redundanțe, tipărire optimizată inutil, variabile denumite mai clar, sortare prin numărare în loc de prin selecție, etc.

#include <stdio.h>

#define MAXN 6000
#define MAXL 60000

int bete[MAXN + 1], f[MAXL * 2 + 1];

int main() {
  FILE *fin, *fout;
  int n, i, j;
  long long nrsol;

  // citire si depunere in vector de frecventa
  fin = fopen("nrtri1.in", "r");
  fscanf(fin, "%d", &n);
  for (i = 0; i < n; i++) {
    fscanf(fin, "%d", &j );
    f[j]++;
  }
  fclose( fin );

  // sortare folosind vectorul de frecventa
  n = 0;
  for ( i = 1; i <= MAXL; i++ )
    for ( j = 0; j < f[i]; j++ )
      bete[n++] = i;

  // calcul numar bete pina la fiecare lungime posibila, i <= MAXL
  for (i = 1; i < n - 1; i++)
    for (j = bete[i] + 1; j <= bete[i + 1]; j++)
      f[j] = i;

  // calcul numar bete pina la fiecare lungime posibila, i <= 2*MAXL
  for (i = bete[n - 1] + 1; i <= MAXL * 2; i++)
    f[i] = n - 1;

  // calcul numar de solutii
  nrsol = 0;
  for (i = 0; i < n; i++)
    for (j = i + 1; j < n; j++)
      nrsol += f[bete[i] + bete[j]] - j;

  fout = fopen("nrtri1.out", "w");
  fprintf( fout, "%lld\n", nrsol );
  fclose( fout );
  return 0;
}

Soluție Armin Asgari / Yusuf Fares / Luca Ilie

Armin are aceeași idee de soluție, cu mici diferențe de implementare. Însă a adus și o modificare de algoritm, esențială pentru mărirea vitezei.

Modificare Armin: în loc să calculăm numărul de tripleți ce pot forma triunghiuri, vom calcula pe aceia ce nu pot forma triunghiuri.

La prima vedere nu este clar ce ne aduce această modificare. Nu este evident, dar numărul de tripleți ce nu pot forma triunghiuri este mult mai mic decît numărul de tripleți ce pot forma triunghiuri. Aceasta duce la mai puține calcule.

Din nou, iată soluția lui simplificată. Am eliminat redundanțe, santinele inutile, am redenumit variabilele mai clar, am simplificat anumite calcule, etc.

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

#define MAXN 6000
#define MAXL 60000

int f[MAXL + 1];
unsigned short int bete[MAXN + 1];

int main() {
  FILE *fin, *fout;
  int n, i, j, maxlen;
  long long nrsol;

  // citire
  fin = fopen( "nrtri1.in", "r" );
  fscanf( fin, "%d", &n );
  maxlen = 0;
  for( i = 0; i < n; ++i ){
    fscanf( fin, "%d", &j );
    ++f[j];
    if ( j > maxlen )
      maxlen = j;
  }
  fclose( fin );

  // sortare bete si resetare vector de frecventa a lungimilor
  n = 0;
  for( i = 1; i <= maxlen; ++i )
    while( f[i] ){
      bete[n++] = i;
      --f[i];
    }

  // calcul numar perechi de anumite lungimi
  for( i = 0; i < n - 1; i++ ){
    j = i + 1;
    while( bete[i] + bete[j] <= maxlen )
      ++f[bete[i] + bete[j++]];
  }

  // sume partiale: f[x] = numar de perechi cu suma mai mica sau egala cu x
  for( i = 1; i <= maxlen; ++i )
    f[i] += f[i - 1];

  nrsol = (((long long)n) * (n - 1) * (n - 2)) / 6; // numarul de tripleti

  // pentru fiecare betisor scadem numarul de perechi a caror suma este
  // mai mica sau egala cu acel betisor - ele nu pot forma triunghiuri
  for( i = 0; i < n; ++i )
    nrsol -= f[bete[i]];

  fout = fopen( "nrtri1.out", "w" );
  fprintf( fout, "%lld", nrsol );
  fclose( fout );
  return 0;
}

Ambele soluții sînt O(L + N2). Soluția a doua este ceva mai rapidă, deoarece calculează doar perechile a căror sumă este mai mică sau egală cu MAXL.

Pentru o soluție mai rapidă încercați să rezolvați problema nrtri2.

Rezolvări aici [1]

Lecție - probleme cu analiză amortizată

Problema unific

Problema unific a fost dată la OJI 2013 clasa a 7-a. Problema definește o procedură prin care două numere pot fi unificate, dacă au măcar o cifră în comun. Apoi cere să se aplice pe un vector unificări de elemente adiacente pînă ce nu se mai poate unifica nimic. Întotdeauna se va face prima unificare posibilă de la începutul vectorului.

Soluția forță brută este să căutăm prima pereche unificabilă de la începutul vectorului și să o unificăm. Apoi reluăm, de la începutul vectorului. Ea este pătratică, deci va depăși timpul pe teste mari.

O soluție mai bună este ca la momentul citirii unui număr nou să îl unificăm cu el din-nainte, apoi rezultatul cu cel din-nainte și tot așa pînă ce nu mai putem unifica. Apoi citim următorul număr și reluăm.

Ce complexitate are această soluție? La prima vedere un număr nou poate fi unificat de cel mult n ori, ceea ce duce la o complexitate pătratică. Desigur că nu e așa. Deoarece fiecare număr poate fi adăugat o singură dată și eliminat o singură dată (prin unificare) rezultă că numărul de operații este maxim 2n. Analiza amortizată ne spune că soluția este liniară.

O parte grea este unificarea propriu zisă. Deși algoritmul este clar, există destule cazuri particulare, iar implementarea dă suficiente bătăi de cap, așa încît mulți elevi au greșit-o la olimpiadă, denumind-o "problemă tractor". În realitate nu este chiar așa, ea putîndu-se implementa în circa 90 de linii de cod.

Problema maxarea

Problema maxarea a fost dată la Shumen 2015 juniori. Este o problemă clasică. Ea cere să se determine dreptunghiul de arie maximă într-un skyline, unde un skyline este o înșiruire de blocuri de lățime unu și diverse înălțimi.

Rezolvarea folosește o stivă, similar cu problemele tower sau maxp. Vom memora o stivă înălțimi din ce în ce mai mari. Cînd adăugăm o înălțime h vom închide toate înălțimile mai mari de pe stivă, avînd grijă să le înlocuim cu un înălțimi egale cu h.

Complexitatea este O(n) prin analiză amortizată și O(n) memorie.

De remarcat că problema cere citirea a un milion de întregi de 5 cifre. Incluzînd separatorul, spațiu, aceasta înseamnă circa 6MB. Soluția fiind O(n), la fel ca și citirea, este clar că ea va fi dominată ca timp de citire. De aceea este important să nu citim cu fscanf ci cu fgetc (parsing în limbajul olimpicilor).

Observație: spre finalul numerelor pe stivă se vor afla foarte multe înălțimi egale. O optimizare ar fi, deci, să "grupăm" acele înălțimi. În loc de o înălțime putem stoca o pereche (h, ap) unde ap ne spune numărul de apariții ale acelei înălțimi. Cînd adăugăm o înălțime egală la stivă vom aduna de fapt 1 la ap. Astfel mărimea stivei rămîne mică.

Problema skyline

Problema skyline este o problemă clasică. Cere să se găsească dreptunghiul de arie maximă într-un skyline, unde un skyline este linia lăsata de zgîrie-nori. Cu alte cuvinte o secvență de dreptunghiuri aliniate cu axa Ox.

Rezolvarea folosește o stivă, similar cu problemele tower sau maxp. Vom memora o stivă de dreptunghiuri de înălțimi din ce în ce mai mari. Cînd adăugăm un dreptunghi de înălțime h vom închide toate dreptunghiurile de înălțime mai mare de pe stivă, avînd grijă să le înlocuim cu un dreptunghi egal cu suma lungimilor lor și de înălțime egală cu h.

Complexitatea este O(n) prin analiză amortizată și O(n) memorie.

Temă

Rezolvări aici [2]