Clasa a VII-a lecția 12 - 28 nov 2019

From Algopedia
Jump to navigationJump to search

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.

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.


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.

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ă

<html5media height="720" width="1280">https://www.algopedia.ro/video/2019-2020/2019-11-28-clasa-7-lectie-info-12-720p.mp4</html5media>

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

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 o înălțime h vom închide toate dreptunghiurile de înălțimi mai mari de pe stivă. Apoi depunem pe stivă dreptunghiul curent.

Avem două cazuri, dacă dreptunghiul curent este de înălțime strict mai pare vom crea un nou dreptunghi pe stivă de lățime 1 + lățimea însumată a dreptunghiurilor eliminate. Altfel, în caz de egalitate, vom mări lățimea dreptunghiului din vîrful stivei cu același număr, 1 + lătimea însumată a dreptunghiurilor eliminate.

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]