Tema - rezolvări

ZParcurgere

Problema zparcurgere a fost dată la concursul Grigore Moisil by net 2006.

Tabela

Problema tabela este preluată de la infoarena.

Puzzle2

Problema puzzle2 a fost dată la infogim 2019, runda 1.

Antitir

Problema antitir a fost dată la barajul pentru concursul de la Shumen 2012, juniori.

Comentarii generale

Unii din voi ați calculat media coordonatelor. Este incorect. Trebuia medianul.
Mulți nu v-ați prins de faptul că ținta trebuie plasată în medianul coordonatelor.
Mulți nu știți numere negative. Nu mi-e clar dacă doar la info, sau și la mate, probabil ambele. Foarte grav: Cojocariu, Iordache, Petcu, Teodorescu.
Unii din voi nu au ați făcut parsing, deși textul problemei spune că este necesară o implementare eficientă: Benescu, Burac, Cadîr, Chivu, Cojocariu, Hossu, Ipate, Petrescu, Rughiniș.
Unii din voi ați folosit funcția abs(). Este lentă, ca orice apel de funcție. Este și inutilă, se implementează simplu ca x < 0 ? -x : x.
Mulți ați ratat testul 7 din cauza depășirilor. Ați adunat la un număr long long (corect pînă aici) două diferențe în valoare absolută. Problema este că suma acelor diferențe poate depăși întregul.
Parsingul intrării era eficient dacă foloseați isspace() pentru a vă opri pe primul caracter diferit de spațiu sau \n. Voi ați preferat să testați dacă e cifră sau '-', mai puțin eficient.

Comentarii individuale

Prima grupă

Aizic: Algoritm incorect, calculează media coordonatelor.
Badea: Algoritm bun, bravo! Pici un test din cauza depășirilor, suma valorilor absolute poate depăși un întreg, atunci cînd o aduni la suma totală.
Benescu: algoritm incorect, bazat pe media aritmetică. Trebuia medianul. Nu faci parsing, deși enunțul cere o implementare eficientă.
Burac: Algoritm bun, dar nu faci parsing, deși era evident că trebuia.
Calotă: Algoritm bun, bravo! Pierzi un test din cauza depășirilor: cele două valori absolute, adunate, pot depăși întregul. Nu e bine să folosești funcția abs(), nu poate fi mai rapidă ca o instrucțiune.
Chivu: Algoritm incorect, bazat pe media coordonatelor. Corect era medianul. Nu faci parsing deși enunțul cere o implementare eficientă.
Cojocariu: Algoritm corect. Ai lăsat printf-uri de debug! Pentru a negativa un număr nu scrii dif*=-1;. Scrii dif=-dif;. Pierzi teste deoarece scazi unu din poziția mediană, în mod incorect (la selecție). Nu faci parsing, drept care algoritmul este lent și obții TLE.
Dobre: Algoritm foarte bun, bravo. Parsingul tău nu este robust, două spații la rînd și nu mai functionează. Folosești o variabilă globală steg. Era mult mai elegant să returnezi direct valoarea negativă. Pare că nu te simți confortabil să lucrezi cu numere negative, ceea ce e foarte grav. Se scrie "parsing", cu 's'.
Hossu: Algoritm incorect și de complexitate mult prea mare.
Iordache: Algoritm incorect bazat pe media coordonatelor. Pentru a negativa un număr nu scrii l*=-1;. Scrii l=-l;.
Mocanu: Algoritm incorect, calculează media coordonatelor.
Mușat: Algoritm foarte bun, bravo. Parsing foarte bun, bravo. Selecția nu e cea mai eficientă, e bazată pe codul de anul trecut. Pici un test din cauza depășirilor. Suma a două valori absolute poate depăși întregul.
Nicola: nimic? Avertisment.
Petcu: Algoritm corect, bravo. Problema e la parsing: tu aduni cifre pozitive la un număr negativ, nu va funcționa.
Ștefănescu: Algoritmul este bun, bazat pe găsirea medianului, bravo! Parsing nerobust, se bazează pe teste perfecte cu un singur spațiu de delimitare. Este și ineficient, cu trei teste în buclă. Iar dacă pun caracterul '-' în mijlocul numărului îl fentez complet. Declară variabilele înainte de a începe instrucțiunile.
Togan: Algoritm bun, bravo! Parsingul nu este robust, dacă ai undeva un spațiu în plus nu va funcționa. Nu e bine să-i trimiți ca parametru fișierul, este mai lent așa. Fă-l variabilă globală.
Voicu T: Algoritm foarte bun, bravo. Parsing drăguț, cu propriul vector de frecvență.

A doua grupă

Asgari: Algoritm bun, bravo! Citirea face toți banii :) funcția abs1() este lentă: folosește inutil long long și nu e declarată static inline. Selecția este ineficientă, se vede că ai luat-o din codul mai vechi predat anul trecut, în loc să adaptezi pivotarea predată recent. Folosește constante (pentru mărimea bufferului).
Cadîr: Algoritm corect, dar lent. Faci sortare, în loc să faci selecție. Nu faci parsing, deși enunțul cere o implementare eficientă.
Dimulescu: Algoritm bun, bravo! Ai pescuit pînă la sînge! De ce ai făcut variabila negativ globală? Nu are sens, e locală funcției. Puteai să returnezi direct valoarea negativă. Parsingul nu e robust, dacă ai undeva două spații nu va funcționa.
Fares: Algoritm bun, ca idee, dar implementarea încîlcită inutil. Ai avertisment de compilare grav. Pierzi un test din cauza depășirilor, suma valorilor absolute poate depăși întregul. Parsingul e ineficient, nu folosești isdigit().
Ghica: Algoritm corect. Parsing ineficient, nu folosești isdigit(). Ai cod duplicat inutil și cazuri particulare inexistente. Dacă totuși voiai să faci un select special cînd n este par atunci trebuia să faci doar acel select. Tu faci două, primul se aruncă la gunoi. Foarte ineficient.
Grecu: algoritm forță brută. Cam cîte puncte te așteptai să iei cu el?
Ilie: soluție suboptimală, complexitate O(n log n). De aceea ești la limită cu timpul. Nu se încadrează în 0.7s. Faci calcule inutile la adunarea de diferențe. Parsing bun, dar neoptim, ai două teste în primul while. Folosești abs(), este lent. Transmiți fișierul ca parametru funcției de citire întreg, pierzi timp, trebuia făcut global.
Ipate: Algoritm corect principial, dar te bazezi pe selectsort. De ce? Tocmai am învățat quicksort, mult mai rapid Oricum, nu era nevoie de sortare, ci de selecție. Nu faci parsing. Toate astea deși enunțul spune că este necesară o implementare eficientă. Ceea ce ai scris tu este orice numai eficient nu.
Marcu: Algoritm bun, bravo. Ai greșit implementarea de parsing: isdigit nu se compară cu 1, el returnează valori zero sau nonzero. Ai scris while ( isdigit( ch = fgetc( fin ) ) == 1 ). Trebuia să testezi pur și simplu while ( isdigit( ch = fgetc( fin ) ) ).
Nicu: Algoritm corect, dar implementare foarte încîlcită inutil. Ai cazuri particulare cînd n este par, de ce? while( !isdigit(ch = fgetc(fin)) && ch != EOF && ch != '-' ) {} este o capodoperă! În primul rînd că cele două acolade sînt inutile. Atunci cînd corpul instrucțiunii while este vid pui punct și virgulă după condiție, nu acolade. În al doilea rînd este ineficient. În al treilea rînd, ce treabă are EOF? Trebuia să scrii while( isspace(ch = fgetc(fin)) );. Faptul că transmiți un parametru funcției de citire întreg o face mai lentă. Trebuia să lași fișierul ca variabilă globală. Funcția abs1() este lentă: folosește inutil long long și nu e declarată static inline. Este, de asemenea, identică cu a lui Armin. Aveți comunicări telepatice?
Petrescu: Algoritm bun, bravo. Punctajul țintei poate fi long long, de aceea pierzi teste. Nu faci parsing, deși enunțul cere o implementare eficientă.
Popescu: Algoritm bun, parsing așa și așa. Pentru a testa dacă un caracter este cifră folosește isdigit(), nu teste.
Rebengiuc: Algoritm bun, bravo! Te bazezi pe faptul că după selecție valorile mai mici ca medianul sînt în prima jumate, iar cele mai mari în a doua jumate. Drăguț! Neevident!
Rughiniș: Algoritmul este posibil să fie corect, dar este foarte lent. Parcurgi toate punctele posibile, chiar și pe cele care nu au . săgeți. Nu faci parsing deși era clar nevoie.
Stancu: nimic? Avertisment.
Tatomir: Algoritm bun, bravo. Cod duplicat. Totul este dublat. Ești copy/paster șef! Parsing ineficient, nu folosești isdigit(). Selecția este ineficientă, se vede că ai copiat-o după un cod vechi, nu ai adaptat pivotarea făcută recent. Ai observat un lucru interesant: nu este nevoie să scădem coordonatele țintei din toate celelalte coordonate, deoarece ele se anulează. De asemenea ai observat că după selecție valorile mai mici decît pivotul vor fi la stînga sa.
Teodorescu: Algoritm corect, bravo. Parsingul ineficient, nu folosești isdigit. Nu știi numere întregi, nu se scrie nr *= -1; ci nr = -nr;.
Voicu M: Algoritmul este corect, dar lent: sortezi în loc să cauți medianul prin selecție. Suma pe care o calculezi poate fi long long, de aceea ai incorect la anumite teste. Nu are sens să scrii corpul unui while ca {;}. Dacă corpul este vid pui pur și simplu punct și virgulă după testul lui while. Funcția de citire întreg va fi lentă deoarece transmiți doi parametri și lucrezi cu pointeri. Era mai simplu, mai rapid și mai normal să returnezi valoarea calculată.

Tema opțională - rezolvări

Supersuma

Problema supersuma a fost dată la barajul pentru concursul de la Shumen 2014, juniori.

Rezolvări aici [1]

Lecţie

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

Citire/scriere rapidă

Știm că atunci cînd avem de citit numere la intrare fscanf() este foarte lentă. Știm că putem citi mai rapid folosind fgetc() și calculînd numerele. Am prezentat, în trecut, o funcție de citire a întregilor bazată pe fgetc(). Am spus că, printre elevi, circulă denumirea de parsing. Vom folosi și noi această denumire, deși ea nu este tocmai corectă, parsingul fiind un capitol al informaticii care se ocupă cu mult mai mult decît citirea întregilor.

Nu am prezentat niciodată o funcție de scriere eficientă a întregilor, care să nu folosească fprintf().

Citire/scriere rapidă cu fgetc/fputc

Iată, mai jos, atît funcția de citire cu care sîntem obișnuiți, cît și o funcție de scriere, ambele bazate pe fgetc() și fputc():

#define MAXLOG10 10

FILE *fin, *fout;
int p10[MAXLOG10 + 1] = { 0, 1, 10, 100, 1000, 10000, 100000, 1000000,
  10000000, 100000000, 1000000000 }; // santinela pe prima pozitie

// citire intreg cu semn
int readInt() {
  int ch, res = 0, semn = 1;

  while ( isspace( ch = fgetc( fin ) ) );
  if ( ch == '-' ) {
    semn = -1;
    ch = fgetc( fin );
  }
  do
    res = 10 * res + ch - '0';
  while ( isdigit( ch = fgetc( fin ) ) );

  return semn * res;
}

// scriere intreg cu semn
void writeInt( int x ) {
  int i, cf;

  if ( x < 0 ) {
    fputc( '-', fout );
    x = -x;
  }
  i = MAXLOG10;
  while ( p10[i] > x )
    i--;
  if ( i == 0 )
    fputc( '0', fout );
  else
    do {
      cf = '0';
      while ( p10[i] <= x ) {
        x -= p10[i];
        cf++;
      }
      fputc( cf, fout );
    } while ( --i > 0 );

  fputc( ' ', fout ); // separatorul, poate sa difere ('\n'?)
}

Cum procedează funcția de scriere rapidă? Ea evită împărțirile. Pentru a afișa numărul x:

Stochează puterile lui 10 într-un vector preinițializat.
Caută p10[i], cea mai mare putere a lui 10 care încape în numărul x.
Pentru fiecare putere p10[i] mai mică sau egală cu cea inițială, va tipări cifra corespunzătoare acelei puteri.
Pentru a afla acea cifră vom scădea în mod repetat puterea lui 10 din numărul x.
Cifra astfel calculată va fi tipărită cu fputc().

Cîte scăderi va face acest algoritm? Pe medie va efectua 4.5 scăderi per cifră, ceea ce înseamnă, pentru un întreg de 10 cifre, 45 de scăderi.

Se poate mai bine?

Citire/scriere cu buffer folosind fgetc/fputc

Putem face o mică optimizare: să setăm un buffer mai mare pentru operațiunile cu fișiere. Funcție prin care setăm un buffer se numește setvbuf() și se apelează astfel:

#define BUFSIZE (128 * 1024)

char rbuf[BUFSIZE], wbuf[BUFSIZE];

  ...

  fin = fopen( "rw.in", "r" );
  setvbuf( fin, rbuf, _IOFBF, BUFSIZE);
  fout = fopen( "rw.out", "w" );
  setvbuf( fout, wbuf, _IOFBF, BUFSIZE);

Se poate mai bine?

Citire/scriere rapidă cu fread/fwrite

Funcțiile fread() și fwrite() se află la baza funcțiilor fscanf()/fprintf() și fgetc()/fputc(). Ele sînt cele mai de jos funcții de citire/scriere care folosesc bufferele sistemului de operare.

Cum le vom folosi? Citirea de pe disc, sau alt mediu extern, este foarte lentă. Ceea ce ia cel mai mult este citirea primului octet. Octeții care urmează se citesc mult mai rapid. De aceea este foarte ineficient să citim cîte un octet o dată folosind fread().

Vom citi, în schimb, cîte un bloc de date mai mare în memorie, din care vom returna cîte un octet (caractere) la cerere. Acest bloc se numește buffer și este folosit și în funcțiile sistem, fgetc() și fscanf().

Iată cum arată un parsing scris cu fread() și fwrite():

#define MAXLOG10 10
#define BUFSIZE (128 * 1024)

FILE *fin, *fout;
int p10[MAXLOG10 + 1] = { 0, 1, 10, 100, 1000, 10000, 100000, 1000000,
  10000000, 100000000, 1000000000 }; // santinela pe prima pozitie
int rpos; char rbuf[BUFSIZE];
int wpos; char wbuf[BUFSIZE];

// initializare citire
static inline void initRead() {
  rpos = BUFSIZE - 1;
}

// citire caracter
static inline char readChar() {
  if ( !(rpos = (rpos + 1) & (BUFSIZE - 1)) )
    fread( rbuf, 1, BUFSIZE, fin );
  return rbuf[rpos];
}
 
// citire intreg cu semn
int readInt() { // citeste un intreg
  int ch, res = 0, semn = 1;

  while ( isspace( ch = readChar() ) );
  if ( ch == '-' ) {
    semn = -1;
    ch = readChar();
  }
  do
    res = 10 * res + ch - '0';
  while ( isdigit( ch = readChar() ) );

  return semn * res;
}

// initializare scriere
static inline void initWrite() {
  wpos = 0;
}

// scriere caracter
static inline void writeChar( char ch ) {
  wbuf[wpos] = ch;
  if ( !(wpos = (wpos + 1) & (BUFSIZE - 1)) )
    fwrite( wbuf, 1, BUFSIZE, fout );
}
 
// scriere intreg cu semn
void writeInt( int x ) {
  int i, cf;

  if ( x < 0 ) {
    writeChar( '-' );
    x = -x;
  }
  i = MAXLOG10;
  while ( p10[i] > x )
    i--;
  if ( i == 0 )
    writeChar( '0' );
  else
    do {
      cf = '0';
      while ( p10[i] <= x ) {
        x -= p10[i];
        cf++;
      }
      writeChar( cf );
    } while ( --i > 0 );

  writeChar( ' ' ); // separatorul, poate sa difere ('\n'?)
}

// scrie caracterele ramase in buffer
static inline void flushBuf() {
  fwrite( wbuf, 1, wpos, fout );
}

Cum folosim aceste funcții? Astfel:

  fin = fopen( "input.in", "r" );
  initRead();
  n = readInt();
  // ... alte citiri
  fclose( fin );

  fout = fopen( "input.out", "w" );
  initWrite();
  writeInt( n );
  // ... alte scrieri
  flushBuf();
  fclose( fout );

Comparații moduri de citire/scriere

Ce funcții ar trebui să folosim atunci cînd facem parsing? Care este diferența de viteză între ele?

Comparația între diverse funcții nu este ușoară, deoarece sistemul de operare va încărca în memorie fișierele des folosite, așa numitul caching. Aceasta face ca citirile să se efectueze din memorie, și nu de pe disc, ceea ce le va face să apară în mod artificial mai rapide decît sînt în realitate. Pentru o testare reală ar trebui să ne asigurăm că fișierele nu se află în cache.

Iată o comparație între diversele tipuri de citire/scriere. Ea măsoară un milion de citiri și un milion de scrieri de întregi folosind cele patru metode: fscanf(), fgetc(), fgetc() cu buffer și fread(). Ca metodologie folosită, am executat fiecare metodă de zece ori și am luat cel mai mic timp obținut. Aceasta înseamnă, probabil, că fișierul de intrare se află în cache. Pe de altă parte același lucru este foarte probabil să se întîmple și pe evaluatorul de la olimpiadă.

Experiment	1 milion citiri + 1 milion scrieri numere întregi cu semn la varena.ro
fscanf/fprintf	793ms
fgetc/fputc	658ms
fgetc/fputc + buffer	657ms
fread/fwrite	341ms

Desigur că lucrurile pot sta diferit între Windows și Linux.

Programare dinamică

Introducere

Wikipedia definește programarea dinamică drept o metodă pentru rezolvarea unor probleme complexe prin descompunerea lor în subprobleme mai simple. Se poate aplica problemelor care prezintă proprietățile de suprapunere a subproblemelor și de substructură optimală. Atunci cînd se poate aplica, metoda ia mult mai puțin timp decît alte soluții naive.

Substructura optimală înseamnă că soluția unei problemei de optimizare date poate fi obținută prin combinarea unor soluții optimale ale subproblemelor. Ca atare, primul pas către găsirea unei rezolvări prin această metodă este verificarea dacă problema are proprietatea substructurii optimale. Astfel de substructuri optimale sînt în mod uzual descrise prin recurență. De exemplu, date niște orașe și distanțele între ele, drumul cel mai scurt de la orașul u la orașul v are proprietatea de substructură optimală: să luăm orice oraș intermediar w pe drumul cel mai scurt, d. Dacă d este cu adevărat drumul cel mai scurt, atunci drumul d1 de la u la w și d2 de la w la v sînt cu adevărat cele mai scurte drumuri între orașele corespunzătoare. Dacă drumul de la u la w nu ar fi cel mai scurt posibil ar însemna că am avea un alt drum mai scurt, ceea ce ar duce la un drum total d, de la u la v, mai scurt decît cel original. Așadar, putem formula soluția problemei găsirii celui mai scurt drum într-o manieră recursivă, ceea ce fac algoritmii Bellman-Ford și Floyd-Warshall.

Suprapunerea subproblemelor înseamnă că ele nu sînt independente, adică subproblemele au în comun alte subprobleme. Nu vom insista pe această proprietate decît atît cît să menționăm că dacă subproblemele nu se suprapun dar prezintă substructură optimală atunci putem aplica tehnica de programare divide et impera (divide and conquer). De aceea quicksort și mergesort nu sînt clasificate ca probleme de programare dinamică.

Metodă

Cînd încercăm să rezolvăm o problemă de programare dinamică întrebarea crucială la care trebuie să răspundem este putem calcula soluția finală pe baza unor subprobleme care sînt la rîndul lor optimale? Pentru a răspunde la întrebare trebuie mai întîi să formulăm subproblemele. Dar pentru a formula subproblemele trebuie să avem în minte principiul substructurii optimale. Altfel s-ar putea să împărțim problema în subprobleme care nu au substructură optimală.

Să recapitulăm: pentru a putea răspunde la întrebarea dacă o problemă admite o soluție prin programare dinamică trebuie să aflăm dacă are substructură optimală. Dar pentru a afla dacă are substructură optimală trebuie să găsim subproblemele. Pe care încercăm să le găsim folosind programarea dinamică.

Nu cumva ne învîrtim în cerc? Așa pare și așa și este, într-o oarecare măsură. Experiența este cea care ne învață cum să căutăm împarțirea în subprobleme astfel încît să obținem proprietatea de optimalitate. Tot experiența este cea care ne ajută să ne dăm seama rapid dacă împărțirea găsită are această proprietate sau nu.

Odată ce demonstrăm că o împărțire în subprobleme se bazează doar pe subprobleme optimale, restul decurge, de obicei, destul de simplu: găsim o formulă de recurență, apoi o implementăm de jos în sus (sau bottom-up), pornind de la cele mai mici probleme, către cele mai mari, pînă la soluția cerută.

Să luăm cîteva exemple.

Subsecvența crescătoare de lungime maximă

Această problemă cere să găsim o subsecvență a unei secvențe de numere în care elementele sînt în ordine crescătoare, iar subsecvența este de lungime maximă. Subsecvența nu este neapărat contiguă, nici unică.

Exemplu

În secvența

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

o secvență crescătoare de lungime maximă este

0, 2, 6, 9, 13, 15

Această secvență are lungime șase. Nu există nici o secvență crescătoare de lungime șapte. Cea mai lungă subsecvență crescătoare nu este unică. De exemplu

0, 4, 6, 9, 11, 15

este o altă subsecvență crescătoare de aceeași lungime, în secvența de intrare.

Soluție

Cum împărțim problema în subprobleme? Să încercăm astfel:

L[i] = lungimea celei mai lungi subsecvențe care începe la poziția i

Are această împărțire proprietatea de optimalitate? Să presupunem că avem o subsecvență optimală crescătoare care trece prin indicii

i₁, i₂, i₃, …, i_k

Astfel

L[i₁] = k

Este secvența i₂, ..., i_k optimală? Cu alte cuvinte lungimea secvenței optime care începe la i₂ este k-1? Răspunsul este da, secvența care începe la i₂, anume i₂, ..., i_k este o secvență maximă, deoarece altfel am putea-o înlocui cu o secvență mai lungă, ceea ce ar duce la o subsecvență L[i₁] mai lungă decît cea inițială, care era optimală. Obținem o contradicție.

Următorul pas este să găsim relația de recurență:

L[i] = max(L[j]+1), j > i și V[j] ≥ V[i]

Următorul pas este să construim subproblemele bottom-up, de la problemele mai mici la cele mai mari. Pentru aceasta vom calcula vectorul L de la coadă la cap, căutînd pentru fiecare element L[i] cel mai mare element L[j] de după el (j > i) astfel încît V[j] ≥ V[i].

Soluția problemei este maximul din vectorul L.

Exemplu

Să calculăm cea mai lungă secvență crescătoare în secvența:

0, 8, 4, 12, 2, 10, 6, 14, 1, 9, 5, 13, 3, 11, 7, 15

Vom calcula lungimile secvențelor maximale de la coadă la cap: L[15], apoi L[14] și așa mai departe. Cînd ajungem la calculul lui L[6] avem următoarea situație:

Exemplu de calcul pentru elementul *L[6]* - cea mai lungă secvență crescătoare care începe la poziția 6.

Pentru a calcula lungimea secvenței maximale care începe la poziția 6 vom căuta toate pozițiile mai mari (7, 8, 9, ...). Le vom lua în considerare doar pe acelea în care V[i] >= V[6]. Dintre ele vom alege poziția unde L[i] este maximă. Astfel vom găsi că V[9] = 9 și L[9] = 3. Vom avea, deci, o secvență de lungime 4. Ea este:

6, 9, 11, 15

Analiză

Acest algoritm are complexitate O(n²), unde n este lungimea secvenței. Memoria folosită este O(n).

Există și un algoritm mai rapid, de complexitate O(n log n), bazat pe căutare binară a valorilor de început.

Reconstrucția soluției

Putem reconstrui o subsecvență maximală folosind încă un vector, N[]. El memorează pentru fiecare indice i un alt indice j care urmează în secevnță după j. Atunci cînd calculăm elementul curent, vom nota nu doar maximul găsit (plus unu) ci și poziția lui în vector, el fiind elementul următor în secvență.

Subșirul de sumă maximală

Această problemă cere să găsim un subșir de sumă maximă într-un șir de numere. Un subșir este contiguu.

Exemplu

Să considerăm șirul:

12, 14, 0, -4, 61, -39

subșirul de sumă maximală este:

12, 14, 0, -4, 61

și are sumă 83.

Soluție

Cum împărțim problema în subprobleme? Să încercăm astfel:

S[i] este suma maximală a unui șir care se termină la poziția i

Are această împărțire proprietatea de optimalitate?

Să presupunem că avem un subșir de sumă maximă și că el se află între indicii i și j. Cu alte cuvine suma maximală este

S[j] = V[i] + V[i+1] + ... + V[j-1] + V[j]

Are șirul care se termină în j-1, sumă maximală? Cu alte cuvinte este suma

S[j-1] = V[i] + V[i+1] + ... + V[j-1]

maximală?

Răspunsul este da, deoarece altfel am putea-o înlocui cu o sumă mai mare, ceea ce ar duce la o sumă mai mare decît cea inițială, care era optimală. Obținem o contradicție.

Următorul pas este să găsim relația de recurență. Observăm că pentru o poziție i avem două variante: fie continuăm secvența anterioară, care se termină în i-1, fie începem una nouă, care pornește în i. Vom continua secvența anterioară dacă adunînd numărul curent obținem o sumă mai mare strict decît numărul curent. Altfel vom porni o sumă nouă. Relația de recurență este:

S[i] = max(V[i], S[i-1] + V[i])

Următorul pas este să construim subproblemele bottom-up, de la problemele mai mici la cele mai mari. Pentru aceasta vom calcula vectorul S calculînd pentru fiecare element S[i] maximul dintre S[i-1] + V[i] și V[i]. Observăm că, în realitate, vom compara S[i-1] cu zero.

Soluția problemei este maximul din vectorul S.

Exemplu

Fie secvența anterioară:

12, 14, 0, -4, 61, -39

Vom calcula de la stînga la dreapta sumele maximale ce se termină la pozițiile respective:

V	12	14	0	-4	61	-39
S	12	26 = max(14, 12 + 14)	26 = max(0, 0 + 26)	22 = max(-4, -4 + 26)	83 = max(61, 61 + 22)	44 = max(-39, -39 + 83)

Analiză

Acest algoritm are complexitate O(n), unde n este lungimea șirului. Memoria folosită este O(1), deoarece nu avem nevoie să stocăm elementele, ci doar ultima sumă calculată.

Reconstrucția soluției

Putem ține minte șirul maximal ținînd minte începutul și sfîrșitul subșirului maximal atunci cînd îl găsim.

Subșirul comun maximal al două șiruri

Această problemă cere să găsim lungimea unui subșir de lungime maximă inclus în două șiruri..

Exemplu

Date șirurile

ABABC

și

CBABA

un subșir maximal are lungime 3 și este

BAB

Soluție

Cum împărțim problema în subprobleme? Să observăm că deoarece subșirul maximal face parte din ambele șiruri el se va termina la o poziție i în șirul X și la o poziție j în șirul Y. Și atunci să încercăm astfel:

M[i][j] = lungimea celui mai lung subșir care se termină la poziția i în X și la poziția j în Y.

Are această împărțire proprietatea de optimalitate?

Să presupunem că avem un subșir optimal care se termină la pozițiile i, respectiv j. Atunci este subșirul M[i-1][j-1] la rîndul lui optimal? Cu alte cuvinte subșirul mai scurt cu unu, care se termină la pozițiile anterioare în X, respectiv Y, este optimal? Da, el este optimal, caci altfel l-am putea înlocui cu un șir mai lung, care ar duce la o soluție mai bună, ceea ce ar însemna că soluția originală nu a fost optimă.

Următorul pas este să găsim relația de recurență:

M[i][j]={\begin{cases}M[i-1][j-1]+1,&{\mbox{dacă }}X[i]=Y[j]\\0,&{\mbox{în caz contrar }}.\end{cases}}

Următorul pas este să construim subproblemele bottom-up, de la problemele mai mici la cele mai mari. Pentru aceasta vom calcula matricea M pe linii, folosind formula de recurență.

Soluția problemei este maximul din matrice.

Exemplu

Pentru cele două șiruri de mai sus,

ABABC

și

CBABA

Vom calcula o matrice M[5][5] care arată astfel:

	C	B	A	B	A
A	0	0	1	0	1
B	0	1	0	2	0
A	0	0	2	0	3
B	0	1	0	3	0
C	1	0	0	0	0

Observăm că avem două subșiruri comune de lungime 3: ABA și BAB.

Analiză

Acest algoritm are complexitate O(m·n), unde m și n sînt lungimile șirurilor. Memoria folosită este, la prima vedere, O(m·n). În realitate, parcurgînd matricea pe linii, nu avem nevoie să memorăm decît o linie din matrice pentru a calcula toate valorile. De aceea memoria necesară este O(min(m, n)).

Există și algoritmi mai eficienți bazați pe arbori sufix, despre care nu vom discuta aici.

Reconstrucția soluției

Cum facem să aflăm nu doar lungimea ci și care este șirul comun maximal și unde apare el în cele două șiruri?

Vom face calculul matricei noastre printr-o parcurgere pe linii. La fiecare pas ne vom întreba dacă elementul calculat (lungimea) este mai mare decît maximul curent. Dacă da, vom memora acel maxim împreună cu indicii i și j la care s-a obținut el.

La final vom avea poziția de start în primul șir ca fiind i - max + 1 și în al doilea șir ca fiind j - max + 1.

Subsecvența comună maximală a două șiruri

Această problemă cere să găsim lungimea unei subsecvențe de lungime maximă inclusă în două secvențe. Prin secvență înțelegem caractere în ordinea originală, nu neapărat consecutive ca poziție.

Exemplu

Date secvențele

X: ACDEGIKMPR

Y: CMEFPGHRK

o secvență maximală are lungime 4 și este

CEGK

o altă secvență maximală este

CMPR

Soluție

Cum împărțim problema în subprobleme? Să încercăm să o împărțim în mod similar cu subșirul comun maximal:

M[i][j] = lungimea celei mai lungi subsecvențe incluse în șirurile X[1..i] și Y[1..j]

Are această împărțire proprietatea de optimalitate?

Să presupunem că avem o secvență optimală a prefixelor care se termină la pozițiile i, respectiv j. Ea va trece prin anumite perechi (i_k, j_k), strict crescătoare, cu proprietatea că X[i_k] = Y[j_k]:

S_i,j = (i₁, j₁) (i₂, j₂) ... (i_k, j_k)

cu proprietatea că:

X_i₁X_i₂... X_{i_k-1}X_{i_k} = Y_j₁Y_j₂... Y_{j_k-1}Y_{j_k}

Atunci este lungimea M[i_k-1][j_k-1] la rîndul ei optimală? Cu alte cuvinte subsecvența mai scurtă cu unu, care se termină la poziția i_k-1 în X, respectiv poziția j_k-1 în Y, este optimală? Da, ea este optimală, căci altfel am putea-o înlocui cu o secvență mai lungă, care ar duce la o soluție mai bună, ceea ce ar însemna că soluția originală nu a fost optimă.

Următorul pas este să găsim relația de recurență:

M[i][j]={\begin{cases}0,&{\mbox{dacă }}i=0{\mbox{ sau }}j=0\\M[i-1][j-1]+1,&{\mbox{dacă }}X[i]=Y[j]\\max(M[i-1][j],M[i][j-1])&{\mbox{dacă }}X[i]\neq Y[j].\end{cases}}

Cum demonstrăm această relație de recurență? Avem două cazuri de demonstrat:

Egalitate

Prefixele X[1..i] și Y[1..j] se termină în același caracter. În acest caz o subsecvență maximală a celor două prefixe se poate obține selectînd acel ultim caracter. Putem, deci exclude acel caracter și calcula subsecvența maximală în prefixele X[1..i-1] și Y[1..j-1]. La lungimea ei vom aduna unu.

Diferență

Prefixele X[1..i] și Y[1..j] se termină în caractere diferite. Să luăm cazul anterior, avem secvențele:

X: ACDEGIKMPR

Y: CMEFPGHRK

Avem iarăși două cazuri:

Cazul 1: subsecvența optimă se termină în R. În acest caz ea nu se poate termina și în K. Deci putem elimina ultimul caracter din Y și calcula M[i][j-1].
Cazul 2: subsecvența optimă nu se termină în R. În acest caz putem elimina acest R și calcula M[i-1][j].

Următorul pas este să construim subproblemele bottom-up, de la problemele mai mici la cele mai mari. Pentru aceasta vom calcula matricea M pe linii, folosind formula de recurență.

Soluția problemei este M[n][m].

Exemplu

Pentru cele două șiruri de mai sus,

ACDEGIKMPR

și

CMEFPGHRK

Vom calcula o matrice M[10][9] care arată astfel:

	C	M	E	F	P	G	H	R	K
A	0	0	0	0	0	0	0	0	0
C	1	1	1	1	1	1	1	1	1
D	1	1	1	1	1	1	1	1	1
E	1	1	2	2	2	2	2	2	2
G	1	1	2	2	2	3	3	3	3
I	1	1	2	2	2	3	3	3	3
K	1	1	2	2	2	3	3	3	4
M	1	2	2	2	2	3	3	3	4
P	1	2	2	2	3	3	3	3	4
R	1	2	2	2	3	3	3	4	4

Cea mai lungă secvență este de lungime 4, valoarea maximă ce apare în tabel.

Analiză

Acest algoritm are complexitate O(m · n), unde m și n sînt lungimile șirurilor. Memoria folosită este O(min(m,n)) dacă memorăm doar o linie din matrice. Dacă dorim să aflăm și o secvență maximală, nu doar lungimea ei, vom avea nevoie de memorie O(m · n), precum vom vedea mai jos.

Există un algoritm care reduce necesarul de memorie la O(min(m, n)).

Reconstrucția soluției

Dorim să aflăm nu doar lungimea, ci și o secvență maximală inclusă în ambele șiruri. Cum procedăm?

Observăm că literele ce fac parte din secvențele maximale se obțin acolo unde, în matrice, avem ramura doi de calcul, cînd literele de la pozițiile respective sînt egale.

Pentru a putea reconstrui soluția vom memora în fiecare căsuță, pe lîngă lungimea maximă și direcția din care provine ea, adică din care am calculat acel maxim. Direcția poate fi spre stînga, spre în sus, sau în diagonală stînga-sus. Apoi vom porni din elementul M[m][n] și vom urma aceste direcții pînă ce ieșim din matrice. De fiecare dată cînd urmăm o diagonală reținem litera. Astfel, descoperirea secvenței se face în ordine inversă.

Temă

Tema 22 clasa a 7 -a

read/write ca aplicație la parsing.
dreptunghiuri pentru subsecvența crescătoare maximală. Atenţie: puteți pica teste cu TLE, este în regulă.
subșirul de sumă maximă
subșirul comun maximal
subsecvența comună maximală

Rezolvări aici [2]

	C	M	E	F	P	G	H	R	K
A	0	0	0	0	0	0	0	0	0
C	1	1	1	1	1	1	1	1	1
D	1	1	1	1	1	1	1	1	1
E	1	1	2	2	2	2	2	2	2
G	1	1	2	2	2	3	3	3	3
I	1	1	2	2	2	3	3	3	3
K	1	1	2	2	2	3	3	3	4
M	1	2	2	2	2	3	3	3	4
P	1	2	2	2	3	3	3	3	4
R	1	2	2	2	3	3	3	4	4

	C	M	E	F	P	G	H	R	K
A	0	0	0	0	0	0	0	0	0
C	1	1	1	1	1	1	1	1	1
D	1	1	1	1	1	1	1	1	1
E	1	1	2	2	2	2	2	2	2
G	1	1	2	2	2	3	3	3	3
I	1	1	2	2	2	3	3	3	3
K	1	1	2	2	2	3	3	3	4
M	1	2	2	2	2	3	3	3	4
P	1	2	2	2	3	3	3	3	4
R	1	2	2	2	3	3	3	4	4

Clasa a VII-a lecția 22 - 13 feb 2020

Tema - rezolvări

ZParcurgere

Tabela

Puzzle2

Antitir

Comentarii generale

Comentarii individuale

Prima grupă

A doua grupă

Tema opțională - rezolvări

Supersuma

Lecţie

Citire/scriere rapidă

Citire/scriere rapidă cu fgetc/fputc

Citire/scriere cu buffer folosind fgetc/fputc

Citire/scriere rapidă cu fread/fwrite

Comparații moduri de citire/scriere

Programare dinamică

Introducere

Metodă

Subsecvența crescătoare de lungime maximă

Exemplu

Soluție

Exemplu

Analiză

Reconstrucția soluției

Subșirul de sumă maximală

Exemplu

Soluție

Exemplu

Analiză

Reconstrucția soluției

Subșirul comun maximal al două șiruri

Exemplu

Soluție

Exemplu

Analiză

Reconstrucția soluției

Subsecvența comună maximală a două șiruri

Exemplu

Soluție

Egalitate

Diferență

Exemplu

Analiză

Reconstrucția soluției

Temă

Navigation menu

Search

	C	M	E	F	P	G	H	R	K
A	0	0	0	0	0	0	0	0	0
C	1	1	1	1	1	1	1	1	1
D	1	1	1	1	1	1	1	1	1
E	1	1	2	2	2	2	2	2	2
G	1	1	2	2	2	3	3	3	3
I	1	1	2	2	2	3	3	3	3
K	1	1	2	2	2	3	3	3	4
M	1	2	2	2	2	3	3	3	4
P	1	2	2	2	3	3	3	3	4
R	1	2	2	2	3	3	3	4	4