Clasa a VI-a lecția 18 - 14 feb 2019

From Algopedia
Jump to: navigation, search

Anunțuri

Pescuitul interzis

În continuarea anunțului din lecția trecută, 'Zero toleranță copiatorilor la varena', adaug restricții suplimentare:

Constat un lucru îngrijorător: exact în perioada temelor IQ Academy trimiteți rezolvările la problemele de la temă la alte site-uri, cum ar fi campion, pbinfo, infoarena. Foarte interesant, cum vă apucă dorința de a lucra pe acele site-uri la fix aceleași probleme și în același timp. Sper că nu vreți să vă bănuiesc că evitați penalizările la teme pescuind pe alte site-uri, nu?

Regulă: deoarece nu am dorința să fiu împăratul muștelor, să fac poliție între puști de clasa a șasea, din momentul cînd începe tema vă interzic să trimiteți surse la problemele din temă la alte site-uri. Interdicția este pînă ce începe lecția următoare (nu după încetarea temei). Cine încalcă această regulă prima oară va primi zero la respectiva problemă. Cine o încalcă a doua oară poate să nu mai vină la noi.

Se pare că a fi informatician este ușor, a fi om este mai greu. Legea a doua a lui Ohm spune 'fii ohm cu mine ca să fiu ohm cu tine'. Vă rog să o aplicați.

Pericol de pierdere calificare IQ Academy

Cu părere de rău trebuie să vă anunț că în urma revizuirii semestriale a participanților la cursul IQ Academy unii copii și-au pierdut calificarea. Nu este deloc ușor să iau astfel de măsuri, dar ele sînt strict necesare.

Mai sînt printre voi copii care sînt în continuare în pericol să își piardă calificarea. Îi voi anunța aici pentru ca ei să poată lua măsuri: Cadîr, Hossu, Stancu, Stoian. Ce înseamnă acest lucru? Înseamnă că suma activității voastre constînd din teme, concursuri, atenție și activitate la curs precum și atitudinea generală, lasă de dorit. Unii dintre voi aveți discrepanțe prea mari între teme și concursuri, ceea ce înseamnă că nu vă faceți voi temele. Înseamnă, de asemenea, că sînteți în pericol de a vă pierde calificarea la IQ Academy. Ce aveți de făcut? Trebuie să urmați strict instrucțiunile primite în comentariile la teme și să le respectați, precum și ceea ce vă comunic verbal la ore. Vreau să vă văd atenți la curs, vreau să văd absolut toate temele trimise și muncite, nu în bătaie de joc, un punctaj rezonabil la concursuri și să vă văd dornici să învățați. Este un moment bun să anunțați părinții despre aceasta, dacă nu sînt deja în temă, să nu aibă o surpriză dacă nu rectificați problemele.

Tema - rezolvări

Problema roboți

Comentarii generale

  1. Soluțiile sînt foarte variate: de la programe care nu folosesc decît matrice, la programe ce folosesc doar vectori. O soluție elegantă și eficientă folosește și vectori și o matrice.
  • Am văzut și soluții elegante.
  • Multe din soluții sînt ineficiente. Dacă datele de intrare ar avea valori mai mari ar pica la timp. De exemplu Armin are o soluție O(k·n4).
  • Multe soluții foarte lungi, peste 120 de linii (Chivu 130 de linii, Ipate 127, de exemplu). O soluție rezonabilă are între 60 și 80 de linii. Nu uitați: numărul de bug-uri crește exponențial cu numărul de linii de cod. Vă ia mult mai puțin să depanați un cod scurt.
  • În continuare mulți dintre voi nu folosiți corect bordarea și vectorii de direcție. De exemplu, unii din voi, pentru a întoarce robotul, fac teste, dacă direcția este atît, fă-o atît. Unul din rosturile vectorilor de direcție este ca direcția să poată fi avansată fără test.
  • În continuare văd vectori de direcție cu 5 poziții. Avem cumva cinci direcții cardinale?
  • În continuare văd matrice de bordare declarate cu un element în plus, în loc de două. Programul a funcționat pentru că matricea este mică, asta nu înseamnă că este corect.
  • Unii ați verificat fiecare robot cu fiecare pentru coliziuni. Nu foarte eficient, nu?
  • Mulți dintre voi scriu cod de genul (Tatomir):
  for(l=1;l<=n;l++){
    for(c=1;c<=n;c++){
      if(m[l][c]==1)
        fputc('U',fout);
      else if(m[l][c]==2)
        fputc('R',fout);
      else if(m[l][c]==3)
        fputc('D',fout);
      else if(m[l][c]==4)
        fputc('L',fout);
      else
        fputc('.',fout);
    }
    fprintf(fout, "\n");
  }

Ar trebui să vă zgîrie la ochi. Fie folosiți un switch. Fie, și mai bine, un vector:

fputc(m[l][c],out);
  • În continuare unii din voi scriu căutarea prost. Iată ce scrie maestrul Togan:
          for(i=0;imax>i;i++){
            if(d[i]!=0){
              if((c==coorc[i])&&(l==coorl[i])){
                aux=i;
                i=imax;
              }
            }
          }

Ce probleme are acest cod? Cum se scrie mai simplu și mai citibil? Iată:

  i = 0;
  while ( dir[i] == 0 || l != coorl[i] || c != coorc[i] )
    i++;
  • Unii din voi au anulat roboții într-un mod incorect: au căutat toate perechile de roboți neanulați și au verificat dacă au aceleași coordonate, caz în care îi anulau pe loc. Acest algoritm nu funcționează dacă se întîlnesc un număr impar de roboți în același loc. Din fericire nu există astfel de teste.
  • În continuare majoritatea dintre voi spun 'matrici', în ciuda faptului că am spus de multe ori forma corectă, 'matrice'. Da, obișnuiți-vă cu limba română, este 'o matrice' - 'două matrice'.
  • Avertismente celor ce nu au trimis nici o soluție la această problemă: Cojocariu, Rughiniș, Cadîr. Nu ați rezolvat nici ce-a de-a doua problemă. Înțeleg că a fost vacanță, dar ați avut o săptămînă suplimentară!

Rezolvare

Problema roboți a fost dată la ONI 2006, clasa necunoscută. Este o problemă de simulare similară cu problema ouă. Vom proceda similar:

  • Vom memora o matrice de frecvență pentru a detecta coliziunile roboților.
  • Vom borda matricea pentru testul de ieșire din tablă.
  • Vom folosi vectori de direcție pentru deplasarea roboților
  • Vom folosi trei vectori ce memorează pentru fiecare robot linia, coloana și direcția sa.
  • La fiecare mutare vom considera ca tabla este inițial goală. Pe măsură ce mutăm roboții, îi vom așeza pe tablă. La finalul mutării vom "șterge" tabla.
  • Unui robot ce nimerește în aceeași căsuță cu alt robot îi vom modifica direcția în '4', pentru a ști că nu mai trebuie mutat.
  • Unui robot care iese de pe tablă îi vom schimba direcția (dir = (dir + 2) % 4), iar apoi îl vom muta în direcția cea nouă de două ori: prima mutare pentru a-l readuce în poziția veche, iar a doua mutare este mutarea propriu zisă.
  • La finalul simulării vom așeza roboții rămași pe tablă, în vederea afișării.

Există o diferență importantă față de problema ouă: dacă doi sau mai mulți roboți ajung simultan în aceeași căsuță, ei dispar de pe tablă. Cum implementăm acest lucru?

O variantă neoptimă ar fi ca, după fiecare mutare, să comparăm fiecare robot cu toți ceilalți. Dacă detectăm cel puțin doi la aceeași linie și coloană, îi anulăm pe toți.

O variantă mai bună și mai simplu de implementat folosește chiar matricea de frecvență. Vom memora în ea, la linia l și coloana c, numărul robotului de la acele coordonate. Înainte de a memora numărul robotului verificăm dacă mai este un robot acolo. Avem două cazuri:

  • tabla[l][c] este 0. În acest caz vom memora numărul robotului: tabla[l][c] = r.
  • tabla[l][c] este diferit de zero. Avem un robot deja acolo. În acest caz anulăm ambii roboți, și cel deja pe tablă și cel pe care voiam să îl plasăm: dr[tabla[l][c]] = dr[r] = 4. Anularea se face, așa cum am spus, setînd direcțiile roboților la ceva invalid. Am ales numărul 4.

Ce complexitate are această soluție?

Citirea datelor de intrare este O(n2), deoarece citim fiecare poziție a tablei. Bucla de simulare se va executa de k ori. Pe cazul cel mai rău putem avea O(n2) roboți. Fiecare robot este mutat în O(1), mulțumită matricei de frecvență. Rezultă că bucla de simulare are complexitate O(k·n2). Înlocuind cu valorile maximale obținem 100·20·20 adică 40000, un număr de operații ce se încadrează ușor în timp.

Se poate atinge acel număr de roboți pe toată perioada simulării? Da, se poate. Demonstrați, găsind un exemplu de dispunere a O(n2) roboți inițiali din care să nu dispară nici unul oricît i-am muta.

Complexitatea memoriei este, evident, O(n2 + k).

#include <stdio.h>

#define MAXN 20
#define MAXROB (MAXN * MAXN)

char dr[MAXROB];  // directie robot
char lr[MAXROB];  // linie robot
char cr[MAXROB];  // coloana robot
char dir[128];    // directiile R, U, L, D - dir['R'] = 0, dir['U'] = 1, etc
char dlin[4] = { 0, -1, 0, 1 };  // diferenta pe linie pentru R, U, L, D
char dcol[4] = { 1, 0, -1, 0 };  // diferenta pe coloana pentru R, U, L, D
char tip[4] = { 'R', 'U', 'L', 'D' }; // tip[d] = notatia directiei d

short tabla[MAXN + 2][MAXN + 2]; // tabla pe care se misca robotii

int main() {
  FILE *fin, *fout;
  int n, k, l, c, i, j, nrob, nr, ch;

  for ( i = 0; i < 4; i++ ) // directia literei robotilor
    dir[tip[i]] = i;

  fin = fopen( "roboti.in", "r" );
  fscanf( fin, "%d%d ", &n, &k );
  nrob = 0;
  for ( l = 1; l <= n; l++ ) {
    for ( c = 1; c <= n; c++ )
      if ( (ch = fgetc( fin )) != '.' ) { // citim caracterul din matrice
        dr[nrob] = dir[ch]; // cream un nou robot, tinem dir, lin, col
        lr[nrob] = l;
        cr[nrob] = c;
        nrob++;
      }
    fgetc( fin ); // citeste in gol '\n'
  }
  fclose( fin );

  // bordam tabla pentru simplificarea testului de iesire
  for ( i = 0; i < n + 2; i++ )
    tabla[i][0] = tabla[i][n+1] = tabla[0][i] = tabla[n+1][i] = -1;

  for ( i = 0; i < k; i++ ) {     // executam k pasi
    for ( j = 0; j < nrob; j++ )  // pentru fiecare robot
      if ( dr[j] < 4 ) {          // daca mai este pe tabla
        lr[j] += dlin[dr[j]];     // actualizam coordonatele
        cr[j] += dcol[dr[j]];
        if ( tabla[lr[j]][cr[j]] == -1 ) { // am iesit afara?
          dr[j] = (dr[j] + 2) % 4;         // schimbam directia
          lr[j] += 2 * dlin[dr[j]];        // facem doi pasi inapoi
          cr[j] += 2 * dcol[dr[j]];
        }
        if ( tabla[lr[j]][cr[j]] == 0 )    // daca nu e nimeni aici
          tabla[lr[j]][cr[j]] = j + 1;     // ma pun pe mine (+1 sa nu fie 0)
        else { // cineva e aici, ne anulam amindoi
          dr[tabla[lr[j]][cr[j]] - 1] = 4; // intii pe el
          dr[j] = 4;                       // apoi pe mine
        }
      }
    // curatam tabla
    for ( j = 0; j < nrob; j++ )  // pentru fiecare robot
      tabla[lr[j]][cr[j]] = 0;    // curata locul unde a stat
  }

  // numaram robotii ramasi si ii plasam pe tabla, in vederea afisarii
  nr = 0;
  for ( j = 0; j < nrob; j++ )    // pentru fiecare robot
    if ( dr[j] < 4 ) {            // daca mai este in viata
      nr++;                       // il numaram
      tabla[lr[j]][cr[j]] = tip[dr[j]]; // si il asezam pe tabla
    }

  fout = fopen( "roboti.out", "w" );
  fprintf( fout, "%d\n", nr );
  for ( l = 1; l <= n; l++ ) {
    for ( c = 1; c <= n; c++ )
      fputc( tabla[l][c] == 0 ? '.' : tabla[l][c], fout );
    fputc( '\n', fout );
  }
  fclose( fout );

  return 0;
}

Remarcați eleganța citirii și a afișării, la care mulți dintre voi ați petrecut mare parte din cod. Ea se face folosind doi vectori complementari:

char dir[128];    // directiile R, U, L, D - dir['R'] = 0, dir['U'] = 1, etc
char tip[4] = { 'R', 'U', 'L', 'D' }; // tip[d] = notatia directiei d

Astfel poziția pe care se află 'R' în vectorul tip este chiar direcția în vectorul de direcții:

char dlin[4] = { 0, -1, 0, 1 };  // diferenta pe linie pentru R, U, L, D
char dcol[4] = { 1, 0, -1, 0 };  // diferenta pe coloana pentru R, U, L, D

Vectorul dir este inversul lui tip, el ne dă pentru o literă direcția ei. De exemplu tip['U'] va fi 1, direcția asociată lui 'U'. Vectorul dir nu este inițializat la început. Cum îl inițializăm? Folosindu-ne de vectorul tip, astfel:

  for ( i = 0; i < 4; i++ ) // directia literei robotilor
    dir[tip[i]] = i;

Problema xy

Comentarii generale

  1. Felicitări celor ce au reușit o soluție foarte bună: Voicu.
  2. Mențiune specială: Tatomir, singurul care a dat soluția optimă la calculul dreptunghiului maximal. Felicitări!
  3. Am desenat multe table de joc depanînd programele voastre. Sper că ați desenat și voi în timpul depanării propriilor soluții!
  4. Numărul de pătrate libere la final se putea calcula pe parcurs. O piesă pusă este un pătrat liber mai puțin, nu-i așa?
  5. Unii din voi nu ați folosit nici bordare nici vectori de direcție: Benescu, Chivu, Hossu, Iordache, Mușat, Togan. De ce? Acesta este scopul temei, nu?
  6. Avertismente celor ce nu au trimis nici o soluție la această problemă: Aizic, Cojocariu, Coman, Dragomir, Rughiniș, Stoian, Cadîr.

Comentarii individuale

Grupa de dimineață

  • Aizic (0p): nimic?
  • Badea (50p-85p): Simularea este foarte frumos scrisă, bravo! Folosești bordare, parțial, ai și locuri unde testezi ca coordonatele să nu depășească, pare că uiți de bordare. Nu folosești vectori de direcție, ceea ce îți complică codul. La X ai folosit formulă pentru piesele puse pe tablă. La Y nu. Se putea și acolo folosi, deoarece știi că vei aduna elemente 2 sau zero. Deci puteai să aduni suma lor împărțită la doi. Ușoară neatenție :-) Calculul ariei maxime are cinci bucle una într-alta! Deci O(n5). Uimitor că se încadrează în timp, felicitări!
  • Benescu (90p): Nu folosești nici bordare nici vectori de direcție. Scopul tău este să iei 100p, nu să exersezi cunoștințele învățate. Codul se complică mult. Ai o redundanță în testul de final. Una peste alta partea de simulare pare să meargă. Nu înțeleg de ce preferi să folosești i și j în loc de l și c cum ar fi mai clar. La aria maximă nu înțeleg algoritmul, ar fi fost bine să pui cîteva comentarii. Din cîte îmi dau seama nu cred că este corect, deoarece are complexitate O(n2) dar nu pare a folosi o stivă.
  • Burac (20p-47p): Simulare scrisă foarte îngrijit, cu vectori de direcție și bordare, bravo! Totuși tratezi diferit piesele X și Y, ceea ce duce la repetiție de cod. Pui piese pe tablă, apoi mergi înapoi și le ștergi dacă constați că nu le-ai pus pentru toate ramurile lui X sau Y. O idee interesantă, dar care nu funcționează pentru că este posibil să întîlnești piese deja puse, care nu trebuie șterse. Trebuia să testezi toate cele patru vîrfuri (sau trei la Y) că pot fi puse înainte să le pui. Sau să notezi într-un vector de frecvență de patru elemente (trei la Y) ce piese ai pus și ce nu, pentru a le putea șterge doar pe cele puse. Calculul ariei maximale este greșit conceptual: tu cauți din fiecare punct cea mai lungă coloană ocupată, în jos, apoi cauți la dreapta cît mai multe astfel de coloane. E posibil să nu găsești dreptunghiul maxim astfel, încearcă să găsești contra exemple.
  • Calotă (80p) : Simulare scrisă curățel. Nu folosești vectori de direcție, ceea ce duce la repetiție de cod. Una peste alta un program corect. Greșeala este la aria maxima. În primul rînd este destul de clar că te-ai uitat pe sursele comisiei pentru inspirație. Faci o precalculare a înălțimii coloanelor, pe care o fac și ei. Bun, nu-i grav. Dar comisia nu face bordare cu -1. Tu faci. Ceea ce înseamnă că vei calcula greșit prima linie, căci vei aduna -1. Păcat că nu folosești bordarea la căutările laterale. În loc de:
           /// cautam lungima maxima
           while ( j2 > 0 && a[i1][j2] >= a[i1][j1] )
             j2--;
           while ( j3 <= m && a[i1][j3] >= a[i1][j1] )
              j3++;

puteai să scrii mai simplu:

           /// cautam lungima maxima
           while ( a[i1][j2] >= a[i1][j1] )
             j2--;
           while ( a[i1][j3] >= a[i1][j1] )
              j3++;
  • Chivu (60p): La simulare nu folosești nici bordare nici vectori de direcție. Acesta este scopul lecțiilor, nu să luăm 100p. Ai mult cod duplicat și de aceea și greșești, la mutarea unui Y, la final, unde scrii a[l-1][c-1]=a[l-1][c+1]=a[l+1][c]='y';. Corect era x în loc de 1. Căutarea dreptunghiului maximal este necitibilă. Multe căutări cu două stegulețe. Nu am cum să îmi dau seama de ce nu funcționează, dar cred că metoda nu poate fi făcută să funcționeze deoarece are cinci bucle imbricate, adică probabil este O(n5), iar felul cum încerci să rezolvi necesită o complexitate O(n6). Chiar și așa, programul corectat ia 90p.
  • Cojocariu (0p): nimic? La nici una din probleme?
  • Coman (0p): nimic?
  • Dragomir (0p): nimic?
  • Grecu (20p): Simularea este oarecum încîlcită. Calculezi din start dimensiunea maximă a piesei puse, frumos! Folosești vectori de direcție. Dar ai destul de mult cod duplicat. Puteai să combini codul pentru X și Y dacă puneai vectorii de direcție în două matrice cu două linii fiecare. Tu plasezi fiecare ramură a unui X, separat, ceea ce nu este corect, căci poți avea ramuri de lungimi diferite. Poate nu ai citit cu atenție enunțul? Căutarea dreptunghiului maximal este greu de înțeles fără comentarii. Cred că, principial, nu poate fi făcută să funcționeze deoarece pare a fi O(n5), iar felul cum încerci să rezolvi necesită o complexitate O(n6).
  • Hossu (10p-51p): avertisment grav de compilare, variabilă neinițializată, de ce ignori așa ceva? La simulare nu folosești nici bordare nici vectori de direcție. Acesta este scopul lecțiilor, nu să luăm 100p. Ai mult cod duplicat. Ai și greșeli de logică și algoritmică:
    • Pui condiția să ai 4 spații pentru a pune piese. Este incorect, poți să ai și mai puține, atunci cînd avansezi peste piese de tipul celui care e la mutare.
    • Recalculezi la fiecare pas numărul de spații în O(n2). Este risipitor, putea duce la TLE.
    • Nu calculezi numărul de piese puse pe tablă, ci numărul pieselor din X sau Y, care poate fi diferit. Ai citit cu atenție enunțul?

La calculul dreptunghiului de arie maximă: ideea pare bună, cu o precalculare a marimilor coloanelor nenule. Cred, însă, că acolo unde ai zero trebuia să lași zero, nu să pui 1. E greu de verificat dacă punctul doi funcționează, cîtă vreme primul punct nu funcționează.

  • Iordache (40p): avertisment grav de compilare, variabilă neinițializată, de ce ignori așa ceva? La simulare nu folosești nici bordare nici vectori de direcție. Acesta este scopul lecțiilor, nu să luăm 100p. Ai mult cod duplicat. Mai mult, deși nu folosești bordare, declari matricea de dimensiune 101. Din ciclul 'perlele gîndirii': if(i==0 || i%2==0). Nu testezi dacă poți plasa piesa inițială, n-ai citit cu atenție enunțul? Odată ce am corectat acest test simularea a mers perfect. La calculul dreptunghiului maximal, ideea este bună, este una din ideile comisiei, cu precalcularea sumelor tuturor dreptunghiurilor. Dar implementarea iese din matrice, apelează cu indicele -1. Ai grijă, mai multă atenție!
  • Mocanu (80p): la simulare ai folosit bordare, bravo! Dar nu ai folosit vectori de direcție, ceea ce îți lungește codul. Simularea este scrisă ordonat. Calculezi mai întîi lungimea minimă dintre brațe, interesant. Apoi avansezi toate brațele cu acea lungime. Din nefericire nu ai tratat corect cazul cînd există deja piesă în locul de pornire. Oare nu ai citit bine enunțul? Odată ce am pus corect testul ca prima piesă pusă să fie pusă pe tabla goală, programul tău a luat 100p. Felicitări, aproape bine. La calculul dreptunghiuluui maximal ai folosit precalcularea sumei tuturor dreptunghiurilor, una din posibilele soluții ale comisiei, foarte bine. Din ciclul 'amuzamente informatice', ai scris:
      if(v[i][j]==2 || v[i][j]==1)
        v[i][j]=1;
  • Mușat (10p-64p): La simulare nu folosești nici bordare nici vectori de direcție. Acesta este scopul lecțiilor, nu să luăm 100p. Ai mult cod duplicat. Din cîte înțeleg programul tău tu nu calculezi numărul de piese puse pe tablă, ci numărul pieselor din X sau Y, care poate fi diferit. Ai citit cu atenție enunțul? La calculul dreptunghiului maximal programul este destul de încîlcit, nu-mi dau seama ce faci acolo. Niște comentarii ar fi ajutat. Însă am remarcat o ciudățenie:
            i = l;
            j = 0;
            while ( i >= 0 && mat[i][c] > 0 ) {
                i ++;
                j ++;
            }

Cum ar putea i să nu fie mai mare ca zero din moment ce pornește pozitiv și continuă să crească? Mai multă atenție!

  • Nicola (0p): nimic, dar bănuiesc care a fost problema.
  • Petcu (90p-95p): La simulare folosești bordare, dar nu și vectori de direcție, ceea ce îți lungește codul. Altfel ea este bine scrisă, ordonată, clară. Te complici la testul de extindere al pieselor, pui condiții inutile de test în matrice cu zero, cu operații 'sau' între ele. Calculul dreptunghiului maximal pare corect, dar mi-e greu să citesc codul, ar fi ajutat enorm o linie în care să descrii metoda. Dacă înțeleg bine pornești din fiecare punct și cauți în jos și la dreapta linii maximale pline, luînd minimul dintre ele. Caz în care nu înțeleg de ce nu cauți doar pînă la minim. Pare să meargă și este O(n4), încadrîndu-se în cerințele comisiei.
  • Rebengiuc (0p-85p): Simulare foarte deosebită. Exagerezi puțin cu matricele și nici complexitatea nu e optimă, căci parcurgi un șablon în O(n2), dar metoda este deosebită. Bordezi, nu folosești vectori de direcție, dar compensezi parțial prin tratarea comună a ramurilor de sus ale X și Y. Totuși, vectorii de direcție ar fi fost mai eleganți. Nu prea am înțeles comparația matricelor. La calculul dreptunghiului maximal ai reușit o soluție de excepție în O(n3), felicitări!
  • Rughiniș (0p): nimic :-( Înțeleg că ai fost în vacanță. Dar ai mai avut încă o săptămînă după terminarea temei. Ai fi putut să trimiți ceva la arhivă, măcar la una din probleme. Remus, dacă vrei să scapi de teme există un mod foarte simplu.
  • Stoian (0p): nimic? Daria, tu poți mai mult. De tine depinde.
  • Ștefănescu (0p-19p): Simularea este solid scrisă, bravo! Ai folosit bordare, dar nu și vectori de direcție. Din această cauză repeți foarte mult cod. Ceea ce este foarte grav pentru că de aceea ai greșit. Ai făcut copy/paste și ai uitat să modifici un '1' în 'i'. O greșeală extrem de greu de remarcat și de corectat, pe care tocmai de aceea nu trebuie să o faci. Iată codul tău la plasarea unui 'Y':
                    i = 2;
                    while (( (a[lin-i][col-i] == 0) || (a[lin-i][col-i] == 2) ) &&
                           ( (a[lin-i][col+i] == 0) || (a[lin-i][col+i] == 2) ) &&
                           ( (a[lin+i][col] == 0)   || (a[lin+i][col] == 2)  ) ) {
                        // verifcam daca se poate forma un y mare
                        
                        sum += 3 -(a[lin-1][col-1] + a[lin-1][col+1] +
                                   a[lin+1][col]) / 2;
                        
                        a[lin-1][col-1] = a[lin-1][col+1] =
                        a[lin+1][col]   = 2;
                        
                        i++;
                    }

Remarci acei +1 și -1. Dacă vei corecta acei 1 simularea va fi corectă. Nu uita: copy/paste este inamicul tau! Nu repeta cod! Te rog nu scrie for (u=0; u<k && ok == 0; u++). Folosește while. for este rezervat pentru bucle cu număr cunoscut de pași. Calculul dreptunghiului maximal este încîlcit. Iar ai scris căutări cu stegulețe, ceea ce îl face greu de înțeles. Începem să ne supărăm! Iată, tu scrii:

                    while (ultlin<=antl && ok == 0) {
                        if (a[ultlin][ultcol] == 0) {
                            ok = 1;
		        }
                        ultlin++;
                    }

Corect și mai simplu, fără steguleț, era:

                    while (ultlin<=antl && a[ultlin][ultcol] != 0)
                        ultlin++;

Te rog să scrii doar așa de acum înainte, atunci cînd scrii o căutare. M-ar fi ajutat mult un comentariu cu metoda folosită. După părerea mea metoda este greșită, în fapt probabil că te puteai prinde și singură dacă îți dădeai cîteva exemple doar pentru această parte a programului.

  • Togan: (60p-90p): La simulare nu folosești nici bordare nici vectori de direcție. Acesta este scopul lecțiilor, nu să luăm 100p. Ai mult cod duplicat. Altfel simularea este scrisă solid, gîndirea este bună, doar oarecum încîlcită. Unele teste puteau fi înlocuite cu formule, cum ar fi calculul lui max. În mod hilar, max nu este variabila care ține maximul, ci a. În loc să denumești indicii de linie și de coloană cu l și c, îi denumești p1 și p2. Toate astea fac codul greu citibil (și corectabil). De aceea nu mă prind dacă la partea a doua, dreptunghiul maximal, algoritmul tău este corect sau nu. Este posibil să fie, deoarece faci sume parțiale, dar nu am cum să fiu sigur, iar corectura lui mi-ar lua prea mult timp.
  • Voicu (90p): Un program foarte bun! Folosești în mod elegant atît bordarea cît și vectorii de direcție! Bravo! Nu mi-e clar de ce ai trimis ulterior un program mai lung și mai urît, la arhivă. Ai lăsat printf-uri de depanare în sursă. Probabil că de aceea iei TLE la ultimul test, în rest programul este perfect. Încă o dată felicitări!

Grupa de după-amiază

  • Asgari (100p): La simulare folosești bordare, bravo! Dar nu folosești vectori de direcție, de aceea ai cod duplicat. Simularea e scrisă ordonat și frumos. Dar! Ai scris o funcție test() în loc să folosești o formulă matematică elegantă. Ai și o funcție min() nefolosită. Ce înseamnă asta: for( k1= 0; k1 < n1 && cnt > 1; ++k1 )? Înseamnă că dăm cu for-ul, nu gîndim. De asemenea, la finalul simulării:
    if( maxx == 0 )
        fprintf( fout, "%d %d ", maxx + 1, n * m - spatii - 1 );
    else
        fprintf( fout, "%d %d ", maxx, n * m - spatii );

Cum ar putea maxx să fie zero? Întotdeauna se va putea face o primă mutare! Calculul dreptunghiului maximal este foarte bine, una din soluțiile comisiei. Cu mențiunea că ar fi fost elegant și eficient să nu continui să muți colțul de jos către dreapta dacă ai descoperit un dreptunghi ne-plin. Similar la mutarea în jos dacă ai descoperit pe coloană un zero.

  • Cadîr (0p): nimic?
  • Dobre (50p): n-ai folosit nici bordare, nici vectori de direcție. Nu te avertizez doar pentru că ai înlocuit bordarea cu un calcul matematic al segmentului minim care atinge o margine, interesant. De ce ai declarat matricea de dimensiuni 102x101? Nu are sens. Simularea este aproape bună. Ai ratat teste pentru că ai pus greșit condiția de oprire a simulării. Dacă cel care trasează o piesă X dă de piesă Y, el nu doar se oprește din trasare, ci se oprește complet jocul. Oprirea se face doar dacă a dat de un Y imediat ce a pus prima piesă, nu întotdeauna. Am corectat oprirea și iei 80p, pierzînd 20p din cauza punctului 2. Calculul dreptunghiului maximal pare corect, dar nu este, deoarece tu forțezi minimul la cea mai mică coloană din linie. Ar trebui ca la fiecare avans de coloană (j față de cj) să testezi dacă ai un dreptunghi maximal. Astfel, în loc de
    for(l=0;l<m;l++){
      for(c=0;c<n;c++){
        j=c;
        while(j<n){
          while( j<n && v[l][j] == 0 )
            j++;
          min=1000;
          cj=j;
          while( j<n && v[l][j] > 0 ){
            if(v[l][j] < min )
              min=v[l][j];
            j++;
          }
          if(min*(j-cj) > patrate)
            patrate=min*(j-cj);
        }
      }
    }

trebuia să scrii:

    for(l=0;l<m;l++){
      for(c=0;c<n;c++){
        j=c;
        while(j<n){
          while( j<n && v[l][j] == 0 )
            j++;
          min=1000;
          cj=j;
          while( j<n && v[l][j] > 0 ){
            if(v[l][j] < min ) {
              min=v[l][j];
            }
            j++;
            if(min*(j-cj) > patrate)
              patrate=min*(j-cj);
          }
        }
      }
    }

O singură acoladă mutată mai la vale cu două linii era deajuns :)

  • Fares (30p-85p): Atenție, ai un avertisment de variabilă neinițializată! Nu ignora, este grav! Folosești bordare, dar nu folosești vectori de direcție, drept care ai mult cod care se repetă. Atenție la bordare! Ai declarat matricea de dimensiune 101, trebuia 102! La nrc1 aduni cu formulă în cazul lui X dar cu teste în cazul lui Y. Nu ai găsit formula și la Y, pentru că nu ai căutat-o. Altfel simularea este scrisă destul de îngrijit și ordonat, bravo! Ca fapt divers, ai scris două funcții care arată aproape identic și pe care le apelezi o singură dată. Unul din rosturile funcțiilor este să nu repeți cod, iar tu exact asta faci scriind două funcții aproape identice. Ca și în alte dăți ai folosit prost funcțiile. De ce insiști? La calculul dreptunghiului maximal: atenție, modifici variabila de ciclu, j! Nu ai voie așa ceva, chiar dacă la final ai grijă să o pui la loc. De ce nu faci pe dos, în loc să o salvezi în cj și apoi să o pui la loc, nu era mai bine să lucrezi direct cu cj? Îmi pare rău, mi-e imposibil să înțeleg calculul ariei maxime. Trebuia să pui niște comentarii. Senzația mea este că este incorect deoarece are complexitate O(n3), iar codul nu pare că face tot ce trebuie pentru această complexitate.
  • Ilie (0p-95p): Un program foarte bun. La simulare folosești și bordare și vectori de direcție, bravo! Păcat că nu ai observat că puteai să nu scrii cod separat pentru X și Y. Pentru asta trebuia să declari vectorii de direcție ca matrice cu două linii, 0 pentru X și 1 pentru Y. Oricum, o simulare foarte frumoasă. Calculul dreptunghiului pare a fi O(n3). Pe lîngă că e de mirare că se încadrează în timp, nu mi-e clar dacă este corect. Ar fi ajutat un comentariu cu o mică descriere a metodei, așa nu pot să îmi dau seama.
  • Ipate (80p-90p): Programul este ordonat și inteligibil. La simulare bordezi matricea, bun! Nu folosești vectori de direcție, rău! Bordarea e un pic ciudată. Piesele sînt codate cu 2 și 3 iar bordarea e cu 1. Toate astea ca să faci doar un test per celulă. Dar folosești operații modulo 3 pentru teste, ceea ce nu e bine pentru că e lent. În schimb tratezi separat pornirea, cînd nr este 1, ceea ce mărește artificial codul. Trebuia să trasezi atît cît puteai, iar la final să te întrebi cîți pași ai făcut. La calculul dreptunghiului maximal ai folosit o precalculare drăguță. Nu știu dacă ți-a venit chiar ție ideea, este și una din soluțiile comisiei. Păcat că aici nu ai mai folosit bordarea matricei pentru a scăpa de un test atunci cînd cauți limitele stînga-dreapta. Un program bun, bravo!
  • Marcu (0p-81p): Ilinca: La simulare programul arată destul de ordonat. Folosești bordare. Bun. Nu folosești vectori de direcție, rău. Codul este destul de repetitiv între X și Y. Calculul cîte piese am pus se putea face cu formulă, evitînd testele. Dar în mare este bine. Calculul dreptunghiului maximal pare bine. Mi-aș fi dorit un comentariu cu o mică explicație a metodei, pentru a putea înțelege codul care nu e deloc simplu. De exemplu, cs nu se modifică, deci de ce nu ai folosit j în locul ei? La fel și ls, este de fapt i. Apoi scrii lj-- numai ca pe linia următoare să poți scrie (lj-ls+1). Nu era mai simplu să scrii direct (lj-ls)? Nici indicii nu sînt clari, care sînt linie și care sînt coloană. Toate astea fac codul greu citibil și te încurci și tu. L-am descîlcit și l-am depanat, în final aveai două greșeli: nu testai suficient de multe dreptunghiuri (de fiecare dată cînd mergi în jos pe linie trebuie să testezi dreptunghiul curent) și inițializai minimul cu o valoare prea mică (m în loc de m+1). Iată codul tău inițial:
    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(mat[i][j]>0){
                lj=ls=i;
                t=cs=j;
                cd=m;
                while(mat[lj][cs]>0){
                    while(mat[lj][t]>0)
                        t++;
                    if(cd>t-1)
                        cd=t-1;
                    t=cs;
                    lj++;
                }
                lj--;
                if((cd-cs+1)*(lj-ls+1)>max)
                    max=(cd-cs+1)*(lj-ls+1);
            }

și cel modificat de mine:

    for(i=1;i<=n;i++)
        for(j=1;j<=m;j++)
            if(mat[i][j]>0){
                lj=i;
                cd=m+1; // in loc de m
                while(mat[lj][j]>0){
                  t=j;
                  while(mat[lj][t]>0)
                    t++;
                  if(cd>t) { // in loc de t-1
                    cd=t;    // in loc de t-1
                  }
                  lj++;
                    
                  if((cd-j)*(lj-i)>max) // mutata de sub acolada
                    max=(cd-j)*(lj-i);
                }
            }
  • Nicu (70p-66p): La simulare nu ai folosit bordarea, deși ar fi fost tare utilă. Mai mult, folosești indici de la unu, ca toți mediocrii. Nicu', ți s-a urît de IQ Acadmey? Interesant cum te-ai descurcat să oprești toate ramurile unui X atunci cînd una din ele se oprește: ai rulat simularea de două ori, odată fără să pui piese, o dată punînd piese. Ar fi fost frumos să îmi scrii un comentariu despre asta, mi-am bătut capul ceva vreme să înțeleg. Greșeala la simulare constă în faptul că nu te oprești atunci cînd piesa inițială (centrul X-lui sau Y-ului) se află peste o piesă de același tip. Cred că nu ai citit cu atenție enunțul, nu poți pune piesa inițială decît pe o căsuță goală. Calculul dreptunghiului maximal este aproape bine. Ai folosit o precalculare pe coloane, una din metodele propuse de comisie. Ai și o greșeală de neatenție, variezi și liniile și coloanele pînă la n. Dacă variai coloanele pînă la m luai 100p. Una peste alta un program foarte bun, pe care nu l-ai dus pînă la capăt. Trebuie să fii mai atent și să programezi mai ordonat puțin. De exemplu inițializările vectorilor xl și xc sînt lungi. Fie scriai o buclă for, fie scriai două linii și le inițializai înlănțuit. Nu este bine să lungești programul pe verticală în mod artificial, căci vezi mai puțin din el pe ecran, ceea ce îngreuiază depanarea.
  • Stancu (0p): David, programul tău este îngrijit și are sens. L-am executat pentru a vedea cîte teste treci la partea de simulare, pe care ai rezolvat-o: treci 7 din 10 teste, nu e rau! Ultimul punct era destul de greu, dar ar fi trebuit să încerci măcar o forță brută. Ai avertismente de compilare, variabilă neinițializată, este grav să îl ignori! Motivul pentru care treci doar 7 din 10 teste este pentru că nu testezi ca prima piesă trasată dintr-un X sau Y să fie pusă pe o căsuță goală. Atenție, citește cu grijă enunțul! Nu folosi indici de la 1 în vector, te rog.
  • Tatomir (100p): La simulare ai folosit bordare și vectori de direcție. Cu toate acestea ai reușit să scrii un program mai lung decît dacă nu le foloseai! E o performanță! :-) Programul este ordonat și clar. Dar repetă cod de multe ori. Mai întîi ai repetiția codului între piesele X și Y. Apoi, în cadrul pieselor, ai repetiția faptului că tratezi special prima trasare de piese, exact același cod care se repetă în while mai jos. Teo, am pretenții mai mari de la tine. Copy/paste știe să facă orice mediocru. Nu ai nevoie să vii la IQ Academy să practici copy/paste! În schimb, la calculul dreptunghiului maximal ai folosit o metodă optimă, O(n2)! Excepțional, cum se împacă cele două? Strălucești la probleme grele și o dai în bară la cele ușoare?
  • Teodorescu (30p-75p): Ai luptat mult cu problema. Dar decît să pescuiești, mai bine teste să-ți faci. Este imnul IQ Academy. Știu că nu îți place, dar cu lene nu devii un bun informatician. Programul tău final arată foarte bine. Este solid, clar, simplu. La simulare folosești bordare, dar nu și vectori de direcție. De aceea ai cod ce se repetă, atît în cadrul unei piese, cît și între piese. La calculul dreptunghiului maximal ai folosit o metodă bună, una din soluțiile comisiei, în O(n3). Un program bun, se vede că te îmbunătățești, bravo!

Rezolvare

Problema xy a fost dată la ONI 2011 clasa a 6a. Ea este o problemă de un tip diferit de alte probleme de simulare. Ea conține, de asemenea, un ultim subpunct care nu are nici o legătură cu primele două. În mod ciudat problema nu acordă punctaje parțiale pentru subpuncte.

Problema are două cerințe mari:

  • Simularea plasării unor forme de tip X și Y, maximale.
  • Găsirea unui dreptunghi de arie maximă completat cu caractere x sau y.

Soluția primei cerințe - simulare

Pentru aceasta vom folosi tehnicile clasice de bordare a matricei tablă și vectori de direcție pentru ramurile figurilor de trasat. De menționat:

  • Vom borda matricea cu ceva diferit de zero sau de piesele celor doi jucători (în soluția de mai jos am ales 3).
  • Deoarece X are patru ramuri, deci plasăm patru piese la o extindere, pe cînd Y are doar trei ramuri, deci plasăm trei piese la o extindere, am folosit un artificiu: am păstrat tot patru ramuri și pentru Y, două dintre ele fiind identice și suprapuse. Aceasta nu influențează jocul, deoarece a patra ramură se va trasa peste prima, ceea ce jocul permite. Nu vor fi influențate nici posibilitatea de a extinde și nici numărul total de piese plasat.
  • Vom memora "vîrfurile" ramurilor în doi vectori de patru elemente, ce vor stoca linia și coloana fiecărui vîrf.

Mai departe simularea este relativ ușoară, trebuind să avem grijă la condițiile de oprire, oarecum încîlcite.

Soluția celei de-a doua cerințe - arie dreptunghi

Aceasta este o problemă grea la clasa a șasea, poate chiar prea grea, soluția cerută necesitînd cunoștințe avansate. Să vedem diverse soluții:

Soluție forță brută

O idee simplă ar fi următoarea: luăm toate dreptunghiurile posibile și le verificăm să fie "pline".

Ce complexitate are această soluție? Să observăm următoarele:

  • Un dreptunghi este definit de colțul din stînga sus și cel din dreapta jos.
  • Fiecare din colțuri poate varia liber, deci va avea O(n2) posibilități.
  • De aici rezultă că numărul de dreptunghiuri este O(n4).
  • Verificarea faptului că un dreptunghi este "plin" este O(n2).

Rezultă complexitatea totală a forței brute: O(n6). Înlocuind n cu 100 obținem o mie de miliarde, soluția va depăși timpul pe teste mari.

Soluție ușor optimizată

O idee de optimizare ar fi să încercăm să verificăm dacă un dreptunghi este plin în O(1). Acest lucru este posibil cu o structură clasică de precalculare. Deoarece este de nivelul clasei a șaptea, consider că ea reprezintă dopaj. Nu vom vorbi despre ea, deoarece avem o soluție tot cu dopaj, dar mai bună. Este însă clar că complexitatea ei va fi O(n4). Aceasta este una din soluțiile acceptate de comisie, care se încadrează în timp.

Soluție optimizată mai mult

Pentru a obține o soluție mai rapidă este necesar să schimbăm algoritmul. Vom răspunde la întrebarea:

  • Care este dreptunghiul de arie maximă "așezat" pe linia l? Cu alte cuvinte, un dreptunghi maximal ce are latura de jos pe linia l.

Cum rezolvăm această problemă? Să considerăm dreptunghiul maximal, pe care vrem să-l găsim. Atunci el va fi limitat superior, la linia de sus, de una din coloanele sale, așezate pe linie. Dacă nici una din coloanele sale nu ar fi exact de înălțimea acelui dreptunghi ar însemna că l-am putea înălța cu o unitate.

Înseamnă că putem folosi următorul algoritm: pentru fiecare coloană c de pe linia l, căutăm în stînga și în dreapta ei extinzîndu-ne cîtă vreme avem coloane de înălțime cel puțin egală cu coloana curentă.

Ce complexitate are acest algoritm? Dacă fixăm linia l și coloana c găsirea extinderilor maximale la stînga și la dreapta va fi O(n2). Deoarece avem n linii și n coloane pe care le putem fixa rezultă o complexitate totală de O(n4). Am obținut, deci, o soluție cu aceeași complexitate ca cea anterioară, dar fără dopaj.

Am putea îmbunătăți această soluție dacă am răspunde rapid la întrebări de genul:

  • Dată o linie l și o coloană c, care este numărul de elemente non-zero continue pe coloana c începînd la linia l?

Pentru a răspunde la astfel de întrebări în O(1) putem face o precalculare în matricea noastră. Aceasta este partea de dopaj. Astfel, elementul tab[l][c] va stoca "înălțimea" coloanei c, pornind de la linia l. Această precalculare se poate face într-o parcurgere a matricei.

Cu această modificare putem calcula, dacă fixăm linia l și coloana c, extinderile maximale la stînga și la dreapta O(n), ceea ce va duce la o complexitate totală de O(n3).

Soluție optimă O(n2)

Nu vom vorbi despre această soluție. Ea necesită cunoștințe de precalculare și analiză amortizată. Pentru curioși: trebuie să rezolvați mai întîi problema skyline. Apoi calculați acel skyline pentru fiecare din liniile matricei, folosind și precalcularea din soluția anterioară.

Iată un program posibil care implementează soluția O(n3):

#include <stdio.h>

char tab[102][102]; // tabla de joc
int lv[4], cv[4];   // lin si col virfurilor celor patru ramuri ale X si Y
                    // La Y fom considera doua ramuri suprapuse
// diferentele pe linii si coloana ale celor patru ramuri
// dl[0] memoreaza pentru X
// dl[1] memoreaza pentru Y, ultimele doua ramuri fiind identice si suprapuse
int dl[2][4] = { { -1, -1, 1, 1 }, { -1, -1, 1, 1 } };
int dc[2][4] = { { -1, 1, 1, -1 }, { -1, 1, 0, 0 } };

int main() {
  FILE *fin, *fout;
  int n, m, k, i, j, l, c, pas, puse, maxpuse, rind, totpuse, maxaria, st, dr, ok;

  fin = fopen( "xy.in", "r" );
  fscanf( fin, "%d%d%d", &n, &m, &k );
  // bordam matricea cu -1
  for ( l = 0; l <= n+1; l++ )
    tab[l][0] = tab[l][m+1] = -1;
  for ( c = 0; c <= m+1; c++ )
    tab[0][c] = tab[n+1][c] = -1;
  // continuam simularea, citim mutari si plasam piese pe tabla
  i = maxpuse = totpuse = rind = 0;
  pas = 2;
  while ( pas >= 2 && i < k ) { // am un x sau y propriu si mai am mutari?
    fscanf( fin, "%d%d", &l, &c );
    lv[0] = lv[1] = lv[2] = lv[3] = l;
    cv[0] = cv[1] = cv[2] = cv[3] = c;
    pas = puse = 0;
    // mutarea
    if ( tab[l][c] == 0 ) // putem pune initial?
      do {
        // putem pune piesele
        pas++;
        ok = 1;
        for ( j = 0; j < 4; j++ ) {
          if ( tab[lv[j]][cv[j]] == 0 ) { // piesa nou pusa pe tabla
            tab[lv[j]][cv[j]] = rind+1;
            puse++;
          }
          lv[j] += dl[rind][j]; // avansam ramurile piesei
          cv[j] += dc[rind][j];
          if ( tab[lv[j]][cv[j]] != 0 && tab[lv[j]][cv[j]] != rind+1 )
            ok = 0; // testam daca putem pune piesa unde am ajuns cu ramura
        }
      } while ( ok );

    if ( puse > maxpuse ) // punctul a) actualizam nr. de piese plasate maxim
      maxpuse = puse;
    totpuse += puse;      // punctul b) numarul de piese puse
    rind = 1 - rind;      // rindul celuilalt copil la mutare
    i++;
  }
  fclose( fin );

  // punctul c) dreptunghiul ocupat de arie maxima
  // bordam latura de sus cu 0, ne va folosi la calcule
  for ( c = 1; c <= m; c++ )
    tab[0][c] = 0;

  // transformam matricea astfel incit tab[l][c] = nr. casute ocupate deasupra
  // lui tab[l][c] (inclusiv el insusi)
  for ( l = 1; l <= n; l++ )
    for ( c = 1; c <= m; c++ )
      if ( tab[l][c] > 0 ) // trebuie sa avem ceva in punctul curent
        tab[l][c] = tab[l-1][c] + 1;
        
  // pentru fiecare punct tab[l][c] ne extindem stinga-dreapta cit putem
  maxaria = 0;
  for ( l = 1; l <= n; l++ )
    for ( c = 1; c <= m; c++ )
      if ( tab[l][c] > 0 ) {
        st = c - 1;
        while ( tab[l][st] >= tab[l][c] )
          st--;
        dr = c + 1;
        while ( tab[l][dr] >= tab[l][c] )
          dr++;
        if ( (dr - st - 1) * tab[l][c] > maxaria )
          maxaria = (dr - st - 1) * tab[l][c];
      }

  fout = fopen( "xy.out", "w" );
  fprintf( fout, "%d %d %d\n", maxpuse, n* m - totpuse, maxaria );
  fclose( fout );

  return 0;
}

Ce complexitate totală are această soluție? Știm deja că dreptunghiul maximal necesită O(n3). Dar simularea?

Bucla exterioară se execută de maxim k ori. Presupunînd că vom putea plasa de fiecare dată piese X și Y maximale, vom pune de fiecare dată O(n) piese. Rezultă o complexitate a simulării de O(k·n).

Complexitatea totală va fi O(k·n + n3). Făcînd înlocuirile cu valorile maximale vom obține circa 2 milioane, care se vor încadra ușor în timpul de 0.1s.

Memoria folosită este în mod destul de evident O(n2).

Rezolvări aici [1]

Lecție

Problema creioane

Pentru a vedea la ce ne folosește lecția de astăzi, rezolvați problema creioane, dată la ONI 2008 clasa a 6a. Nu vă faceți griji, nu este un test și nu contează la absolut nimic. Aveți la dispoziție o oră.

Memoizare

Memoizarea este o metodă de a face un program mai rapid fără a-i schimba modul în care el funcționează. Ideea ei este ca atunci cînd efectuăm un calcul scump să păstrăm valoarea calculată într-un tablou pentru a economisi timp în cazul cînd în viitor vom avea din nou nevoie de acea valoare. Să o învățăm prin exemple.

Exemplul 1

Să presupunem că ni se dau n numere a0, a1, ..., an-1 și ni se cere să afișăm factorialele acelor numere modulo k. O soluție naivă ar putea fi următoarea:

for ( i = 0; i < n; i++ ) {
  p = 1;
  for ( j = 2; j <= a[i]; j++ )
    p = (p * j) % k;
  printf( "%d ", p );
}

Să calculăm complexitatea tipului de execuție: pentru fiecare număr ai vom face O(ai) înmulțiri, drept pentru care complexitatea soluției este O(suma(ai)). Desigur că putem face un program mai eficient care calculează un vector fact[i] unde fact[i] este i! (i factorial). Acest vector se poate calcula în O(max(ai)), după care printr-o parcurgere a numerelor ai vom putea calcula rezultatul ceea ce duce la o complexitate optimă de O(n + max(ai)).

Însă în unele cazuri nu este ușor să schimbăm radical programul pentru a scrie o soluție mai eficientă decît soluția naivă. Cum putem folosi tehnica memoizării pentru a modifica foarte puțin soluția brută și a o aduce la complexitate optimă? Am putea ca de fiecare dată cînd calculăm ai! să păstrăm rezultatul într-un vector la poziția ai. Vom păstra, de asemenea și toate factorialele intermediare calculate pe parcurs. Atunci cînd vom avea nevoie de calculul unui factorial vom merge în jos pînă la primul factorial calculat. Iată implementarea:

fact[1] = 1; // pentru a ne opri la final
for ( i = 0; i < n; i++ ) {
  j = a[i];
  while ( fact[j] == 0 )      // cautam in jos primul factorial calculat
    j--;
  for ( j++; j <= a[i]; j++ ) // calculam toate valorile pina la a[i]
    fact[j] = (fact[j-1] * j) % k;
  printf( "%d ", fact[a[i]] );
}

Ce complexitate în timp are această soluție? Deoarece ea nu repetă calcule în vectorul fact rezultă că fiecare element al vectorului va fi calculat cel mult odată, în timp O(1), deci soluția va fi optimă, O(n+max(ai)). Observați că am obținut aceeași complexitate optimă dar fără a schimba structura algoritmului nostru naiv, ci doar memorînd rezultate parțiale într-un vector. Aceasta este exact ideea memoizării.

Exemplul 2

Se dau n numere x0, x1, ..., xn-1 și ni se cere ca pentru fiecare xi să afișăm al ilea număr din șirul lui Fibonacci, modulo k. Din nou, o soluție naivă ar putea fi următoarea:

for ( i = 0; i < n; i++ ) {
  f1 = f2 = 1;
  for ( j = 3; j <= x[i]; j++ ) {
    f = (f1 + f2) % k;
    f1 = f2;
    f2 = f;
  }
  printf( "%d ", f2 );
}

Să calculăm complexitatea tipului de execuție: pentru fiecare număr xi vom face O(xi) adunări, drept pentru care complexitatea soluției este O(suma(xi)). Cum putem folosi tehnica memoizării pentru a modifica foarte puțin soluția brută și a o aduce la complexitate optimă? Am putea ca de fiecare dată cînd calculăm termenul Fibonacci numărul xi să păstrăm rezultatul într-un vector la poziția ai. Vom păstra, de asemenea și toate calculele intermediare. Atunci cînd vom avea nevoie de calculul unui termen al șirului vom merge în jos pînă la primul termen calculat. Iată implementarea:

fib[0] = fib[1] = 1; // pentru a ne opri la final
for ( i = 0; i < n; i++ ) {
  j = a[i];
  while ( fib[j] == 0 )      // cautam in jos primul factorial calculat
    j--;
  for ( j++; j <= a[i]; j++ ) // calculam toate valorile pina la a[i]
    fib[j] = (fib[j-1] + fib[j-2]) % k;
  printf( "%d ", fib[a[i]] );
}

Ce complexitate în timp are această soluție? Deoarece ea nu repetă calcule în vectorul fib rezultă că fiecare element al vectorului va fi calculat cel mult odată, în timp O(1), deci soluția va fi optimă, O(n+max(xi)).

Exemplul 3

Un exemplu avansat de folosire a memoizării, de clasa a 7a, pentru cei care știu funcții și recursivitate este o funcție cunoscută care calculează al n-ulea număr din șirul lui Fibonacci. Un mod naiv și direct de a scrie funcția este:

int fib( int n ) {
  if ( n == 1 || n == 2 )
    return 1;
  return fib( n-1 ) + fib( n-2 );
}

Problema cu această implementare este că va chema de multe ori funcția fib cu aceleași valori, refăcînd frecvent aceleași calcule. De exemplu, fib(n-2) se va calcula de două ori, fib(n-3) se va calcula de 3 ori, iar fib(n-4) se va calcula de 5 ori! Faceți desenul și convingeți-vă. Numărul de apeluri crește exponențial.

O soluție ar fi să implementăm funcția nerecursiv, așa cum deja știm. În unele cazuri acest lucru complică foarte mult codul, deoarece implică o schimbare radicală. Putem însă modifica puțin funcția fib pentru a memora valoarea o dată calculată, astfel încît la un următor apel să o returneze direct. Pentru aceasta vom folosi un vector de valori, să-i spunem val, în care vom memora valorile șirului lui Fibonacci gata calculate. Iată modifcarea:

int val[1000] = { 1, 1 };

// exemplu de funcție fibonacci implementată folosind memoizare
int fib( int n ) {
  if ( val[n] == 0 ) // inca necalculat
    val[n] = fib( n-1 ) + fib( n-2 ); // il calculam in tabel
  return val[n]; // returnam valoarea din tabel
}

Exemplul 4

O astfel de problemă este și problema creioane. Rezolvarea forță brută este relativ ușor de scris, dar nu se va încadra în timp pentru teste mari deoarece are complexitate O(n2). O putem însă modifica ca atunci cînd calculăm înălțimea unei grămezi de creioane să calculăm înălțimea fiecărui creion din grămadă. În acest fel vom avea O(1) calcule per element, ceea ce duce la o soluție optimală liniară, O(n).

Temă

Tema 18 clasa a 6a

  • creioane dată la ONI 2008 clasa a 6a
  • bila1 ONI 2010 baraj gimnaziu

Atenție! La aceste probleme se vor adăuga problemele de la concursul pe care îl vom da săptămîna aceasta.

Rezolvări aici [2]