Difference between revisions of "Clasa a VII-a lecția 22 - 13 feb 2020"

From Algopedia
Jump to navigationJump to search
(Created page with "= Tema - rezolvări = == ZParcurgere == Problema [http://varena.ro/problema/z zparcurgere] a fost dată la concursul Grigore Moisil by net 2006. === Soluție === Cum o rezolv...")
 
 
Line 594: Line 594:
  
 
= Lecţie =
 
= Lecţie =
 +
<html5media height="720" width="1280">http://algopedia.ro/video/2019-2020/2020-02-13-clasa-7-lectie-info-22-720p.mp4</html5media>
 
== Citire/scriere rapidă ==
 
== Citire/scriere rapidă ==
 
Știm că atunci cînd avem de citit numere la intrare <code>fscanf()</code> este foarte lentă. Știm că putem citi mai rapid folosind <code>fgetc()</code> și calculînd numerele. Am prezentat, în trecut, o funcție de citire a întregilor bazată pe <code>fgetc()</code>. 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.
 
Știm că atunci cînd avem de citit numere la intrare <code>fscanf()</code> este foarte lentă. Știm că putem citi mai rapid folosind <code>fgetc()</code> și calculînd numerele. Am prezentat, în trecut, o funcție de citire a întregilor bazată pe <code>fgetc()</code>. 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.

Latest revision as of 14:56, 14 February 2020

Tema - rezolvări

ZParcurgere

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

Soluție

Cum o rezolvăm?

În problemele pe care încercăm să le rezolvăm cu tehnica divide et impera vom încerca să definim problema de rezolvat. Astfel, în acest caz, definim:

E(N, L, C) = elementul din matricea de latură 2N aflat la poziția (L, C)

Observăm că putem descompune problema în patru subprobleme, în care matricele sînt un sfert din matricea originală. Dar există o diferență: valorile din matrice nu pornesc de la 1. De aceea trebuie să introducem un nou parametru, elementul de start:

E(N, L, C, S) = elementul din matricea de latură 2N aflat la poziția (L, C) cu elemente care încep cu S

Ce observăm?

  • Putem împărți problema în patru subprobleme, cele patru pătrate de latură 2N-1.
  • Trebuie să ajustăm linia și coloana pentru a apela corect elementul din subproblema mai mică.
  • Trebuie să ajustăm elementul de start pentru subproblema mai mică.

Mai exact:

  • Dacă linia L ≤ 2N-1, ea rămîne neschimbată - vorbim de cele două sferturi de sus.
  • Altfel, vorbim de cele două sferturi de jos, linia L se ajustează scăzînd 2N-1, iar elementul de start crește cu jumate din elementele matricei, adică 2N-1·2N.
  • Similar, dacă coloana C ≤ 2N-1, ea rămîne neschimbată - vorbim de cele două sferturi din stînga.
  • Altfel, vorbim de cele două sferturi din dreapta, coloana C se ajustează scăzînd 2N-1, iar elementul de start crește cu un sfert din elementele matricei, adică 2N-1·2N-1.

Astfel:





În aceste condiții avem relația:

E(N, L, C, S) = E(N-1, L', C', S'')

Observații:

  • La fiecare pas N scade cu 1.
  • E(1, 1, 1, S) = S.

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

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  int n, k, l, c, lat, start, p2n;

  fin = fopen( "z.in", "r" );
  fout = fopen( "z.out", "w" );

  fscanf( fin, "%d%d", &n, &k ); // matrice de latura 2^n, k intrebari
  // calculam p2n = 2^n, latura matricei originale
  p2n = 1;
  while ( n-- > 0 )
    p2n *= 2;

  // citim cele k intrebari si raspundem la ele
  for ( ; k > 0; k-- ) {
    fscanf( fin, "%d%d", &l, &c ); // linia si coloana elementului de calculat
    lat = p2n; // latura matricei actuale (initial 2^n)
    start = 1; // primul element din matricea de latura 2^n
    // impartim succesiv latura la 2, pina ajungem la 1
    while ( lat > 1 ) {
      if ( l > lat / 2 ) { // daca l este in jumatatea de jos a matricei
        start += lat * lat / 2; // elementul de start creste cu 1/2 din matrice
        l -= lat / 2;           // ajustam linia in noua matrice
      }
      if ( c > lat / 2 ) { // daca c este in jumatatea din dreapta a matricei
        start += lat * lat / 4; // elementul de start creste cu 1/4 din matrice
        c -= lat / 2;           // ajustam coloana in noua matrice
      }
      lat /= 2;            // latura noii matrice este jumate din cea curenta
    }
    fprintf( fout, "%d\n", start );
  }

  fclose( fin );
  fclose( fout );

  return 0;
}

Ce complexitate are acest algoritm?

Timpul este logaritmic în latura matricei, per fiecare întrebare. Avem K întrebări. Timpul este, deci O(K·log 2N) adică O(K·N).

Memoria folosită este, desigur, constantă.

Tabela

Problema tabela este preluată de la infoarena.

Soluție decrease and conquer

Pentru a observa regula completăm matricea pînă la latură 8:

0 1 2 3 4 5 6 7
1 0 3 2 5 4 7 6
2 3 0 1 6 7 4 5
3 2 1 0 7 6 5 4
4 5 6 7 0 1 2 3
5 4 7 6 1 0 3 2
6 7 4 5 2 3 0 1
7 6 5 4 3 2 1 0

Acum este mai ușor să observăm reguli:

  • O matrice de dimensiune 2N va conține elemente între 0 și 2N-1.
  • Dacă împărțim matricea în sferturi, două din sferturi conțin jumate din numere, celelalte două sferturi conțin cea de-a doua jumate din numere.

Să definim problema de rezolvat:

E(N, L, C) = elementul din matricea de latură 2N aflat la poziția (L, C)

Observăm că putem descompune problema în patru subprobleme, în care matricele sînt un sfert din matricea originală. Dar există o diferență: valorile din cele patru matrice nu pornesc mereu de la 0. De aceea trebuie să introducem un nou parametru, elementul de start:

E(N, L, C, S) = elementul din matricea de latură 2N aflat la poziția (L, C) cu elemente care încep cu S

Ce observăm?

  • Putem împărți problema în patru subprobleme, cele patru pătrate de latură 2N-1.
  • Trebuie să ajustăm linia și coloana pentru a apela corect elementul din subproblema mai mică.
  • Trebuie să ajustăm elementul de start pentru subproblema mai mică.

Mai exact:

  • Dacă linia L ≤ 2N-1, ea rămîne neschimbată - vorbim de cele două sferturi de sus.
  • Altfel, vorbim de cele două sferturi de jos, linia L se ajustează scăzînd 2N-1, iar elementul de start crește cu 2N-1.
  • Similar, dacă coloana C ≤ 2N-1, ea rămîne neschimbată - vorbim de cele două sferturi din stînga.
  • Altfel, vorbim de cele două sferturi din dreapta, coloana C se ajustează scăzînd 2N-1, iar elementul de start crește cu 2N-1.
  • Dacă atît linia cît și coloana depășesc 2N-1 elementul de start nu se ajustează.

Astfel:




În aceste condiții avem relația:

E(N, L, C, S) = E(N-1, L', C', S')

Observații:

  • La fiecare pas N scade cu 1.
  • E(1, 1, 1, S) = S.

Iată o soluție posibilă (30 linii de cod efectiv):

#include <stdio.h>

int main() {
  FILE *fin, *fout;
  unsigned n, l, c, start, dif;

  fin = fopen( "tabela.in", "r" );
  fscanf( fin, "%d%d", &l, &c );
  fclose( fin );

  start = l < c ? c : l; // coordonata maxima
  // calculam cea mai mica putere a lui 2 in care incape coordonata maxima
  n = 1;
  while ( n < start )
    n *= 2;;

  start = 0; // elementul de start in matricea originala (stinga-sus)
  while ( n > 1 ) { // cita vreme matricea are latura mai mare ca 1
    dif = 0;        // sfertul in care ne aflam, initial stinga-sus
    if ( l > n / 2 ) { // ne aflam in jumatatea de jos?
      l -= n / 2;      // ajustam linia
      dif = 1 - dif;   // 0 = jumatea de sus, 1 = jumatea de jos
    }
    if ( c > n / 2 ) { // ne aflam in jumatea din dreapta?
      c -= n / 2;      // ajustam coloana
      dif = 1 - dif;   // 0 = jumatea din stinga, 1 = jumatea din dreapta
    }
    start += dif * n / 2; // ajustam elementul de start, daca e cazul
    n /= 2;               // trecem la matricea de latura n / 2
  }
  
  fout = fopen( "tabela.out", "w" );
  fprintf( fout, "%d\n", start );
  fclose( fout );

  return 0;
}

Ce complexitate are acest algoritm?

El este logaritmic în maximul dintre linie și coloană, cu alte cuvinte O(log max(L, C)).

Memoria este constantă.

Soluție matematică

Mi-a fost atrasă atenția că există formulă pentru elementele matricei:

Ml,c = l xor c

La prima vedere pare surprinzător, nu-i așa?

În fapt, dacă urmărim programul de mai sus observăm că el calculează variabila start (rezultatul) astfel:

  • La fiecare pas se calculează o putere a lui 2 care se adună sau nu la start.
  • Puterea lui 2 se adună numai atunci cînd ea apare doar în linie sau doar în coloană.
  • Dacă puterea lui 2 apare în linie sau în coloană ea va fi scăzută din acea linie sau coloană.
  • Astfel, ele nu mai influențează calculul în iteratia următoare.

Ce calculează, deci, programul? Un xor bit cu bit al liniei și coloanei de la intrare (numerotate de la zero).

Cu această soluție timpul se reduce de la logaritmic la O(1).

Interesant, nu? :-)

Puzzle2

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

Soluție

Cea mai simplă soluție, în opinia mea, este să punem "la grămadă" ambele șiruri de numere, cel total și cele rămase pe masă. Apoi le sortăm. În final căutăm numere care apar o singură dată.

Pentru aceasta avem mai multe soluții. Cea mai simplă, cred, este să ne uităm la fiecare număr în stînga și în dreapta sa. Dacă numărul este diferit de ambii vecini ai săi el va fi afișat.

Trebuie să avem grijă la următoarele lucruri:

  • Timpul este scurt, 0.11s.
  • Deci sortarea trebuie să fie eficientă - implementarea de quicksort făcută la lecție este foarte bună.
  • Pentru o mai bună aleatorizare putem adăuga o alegere aleatoare a pivotului cu funcția rand().
  • Vom citi circa 200000 de numere de circa 9 cifre si un separator, aproximativ 2 milioane de octeți. Merită să facem parsing, dat fiind timpul foarte scurt.
  • Vom scrie circa 50000 de numere, posibil 100000, aproximativ 1 milion de octeți. Merită să facem parsing la scriere.

Iată o soluție care ține cont de aceste observații (64 linii de cod cu tot cu parsing intrare/ieșire):

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

#define MAXN 100000

FILE *fin, *fout;
char cf[12] = "0000000000 "; // pentru parsing output
int v[2 * MAXN + 1];         // + doua santinele, una la inceput, una la final

int readInt() { // citeste un intreg
  int ch, res = 0;

  while ( !isdigit( ch = fgetc( fin ) ) );
  do
    res = 10 * res + ch - '0';
  while ( isdigit( ch = fgetc( fin ) ) );

  return res;
}

void writeInt( int x ) { // scrie un intreg
  int n = 10; // pozitia spatiului in cf[]  - '\0'

  while( x > 0 ) {
    cf[--n] = '0' + x % 10;
    x /= 10;
  }
  fputs( &cf[n], fout );
}

void myqsort( int begin, int end ) {
  int aux, b = begin, e = end,
    pivot = v[(begin + end) / 2]; // poate fi orice pozitie intre begin si end - 1

  while (v[b] < pivot) // cauta primul element mai mare sau egal cu pivotul
    b++;

  while (v[e] > pivot) // cauta primul element mai mic sau egal cu pivotul
    e--;

  while( b < e ) { // daca indicii nu s-au atins
    aux = v[b];    // interschimba elementele la pozitiile b si e
    v[b] = v[e];
    v[e] = aux;
    
    do // cauta primul element mai mare sau egal cu pivotul
      b++;
    while (v[b] < pivot);

    do // cauta primul element mai mic sau egal cu pivotul
      e--;
    while (v[e] > pivot);
  }

  // acum [begin..e] sint mai mici sau egale cu pivotul
  if ( begin < e )
    myqsort(begin, e);
  // si [e+1..end] sint mai mari sau egale cu pivotul
  if ( e + 1 < end )
    myqsort(e + 1, end);
}

int main() {
  int m, n, i;

  fin = fopen( "puzzle2.in", "r" );
  n = readInt();
  for ( i = 1; i <= n; i++ )
    v[i] = readInt();
  m = readInt();
  for ( i = 1; i <= m; i++ )
    v[n + i] = readInt();
  fclose( fin );

  myqsort( 1, m + n );
  
  fout = fopen( "puzzle2.out", "w" );
  for ( i = 1; i <= n + m; i++ ) // cautam elemente nepereche
    if ( v[i] != v[i - 1] && v[i] != v[i + 1] )
      writeInt( v[i] );
  fputc( '\n', fout );
  fclose( fout );

  return 0;
}

Ce complexitate are această soluție?

Timpul este evident dominat de sortare, el fiind O(N log N).

Memoria este O(N), mai exact circa 800KB.

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ă.

Soluție

Dacă luăm cîteva exemple vom observa imediat că:

  • Punctajul este compus din două sume separate, pe x și pe y.
  • Dacă fixăm centrul țintei la coordonatele (xt, yt) atunci:
    • Punctajul pe x, Px, este suma modulelor diferențelor între coordonatele xi ale punctelor și xt: |xi - xt|
    • Punctajul pe y, Py, este suma modulelor diferențelor între coordonatele yi ale punctelor și yt: |yi - yt|
    • Punctajul țintei va fi P = Px + Py.

Ce rezultă de aici? Că problema noastră plană este de fapt o problemă liniară. Coordonata x a țintei este independentă de coordonata y. Noua noastră problemă este, deci, să se găsească xt astfel încît suma diferențelor modulelor să fie minimă. Putem, apoi repeta același lucru pentru y.

Cum rezolvăm problema cea nouă?

  • Să presupunem că centrul țintei nu este suprapus cu nici o coordonată x.
  • Ce se întîmplă dacă mutăm coordonata țintei xt la dreapta cu o unitate?
  • Săgețile din stînga centrului vor adăuga cîte o unitate, iar cele din dreapta vor scădea cîte o unitate.
  • Deci, P' = P - Nstînga + Ndreapta

Cu aceste observații, dacă pornim cu centru țintei din cea mai mică coordonată xi și o deplasăm spre dreapta cîte o unitate, punctajul va scădea. Pe măsură ce săgețile din dreapta trec în stînga punctajul va scădea din ce în ce mai puțin. Atunci cînd numărul săgeților din stînga depășește numărul săgeților din dreapta punctajul va începe să crească.

Precum am spus:

P' = P - Nstînga + Ndreapta

Punctajul va fi minim atunci cînd

Nstînga = Ndreapta = N/2

Valoarea căutată pentru centrul țintei este, deci, medianul valorilor xi . Cu alte cuvinte, valoarea care s-ar afla pe poziția din mijloc dacă valorile xi ar fi sortate.

Dar aceasta este o clasică problemă de selecție. Vom selecta din cele N coordonate pe cea aflată la poziția N / 2.

Algoritmul este următorul:

  • Citește perechile de coordonate (x, y).
  • xt = selecție(xi, N/2)
  • yt = selecție(yi, N/2)
  • Calculează punctajul ca fiind P = suma(|xi - xt|) + suma(|yi - yt|)
  • Afișează punctajul P

Implementare:

  • Vom citi la intrare două milioane de numere a cîte 10 cifre plus un separator. Cu totul avem circa 22 milioane octeți. Este clar că trebuie să facem parsing.
  • Pentru o aleatorizare bună vom folosi o alegere aleatoare a pivotului, folosind funcția rand()

Iată un program posibil (73 linii de cod efectiv):

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

#define MAXP 1000000

int x[MAXP], y[MAXP];
FILE *fin, *fout;

int readInt() { // citeste un intreg
  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;
}

inline static int modul( int x ) {
  return x >= 0 ? x : -x;
}

int median( int n, int c[] ) { // c = 0 pentru x,   c = 1 pentru y
  int aux, med = n / 2, start = 0, end = n - 1, pivot, ipiv, i, j;

  while ( start < end ) {
    ipiv = start + rand() % (end - start); // alege un pivot aleator in [start..end)
    pivot = c[ipiv];

    i = start; j = end;
    while ( c[i] < pivot )
      i++;
    while ( c[j] > pivot )
      j--;
    while ( i < j ) {
      aux = c[i];
      c[i] = c[j];
      c[j] = aux;
      do
        i++;
      while ( c[i] < pivot );
      do
        j--;
      while ( c[j] > pivot );
    }
    // avem acum impartirea [start j] si [j+1 end]
    if ( med <= j )
      end = j;
    else
      start = j + 1;
  }
  return c[start];
}

int main() {
  int n, i, xmed, ymed;
  long long sum;

  srand( time( NULL ) );
  fin = fopen( "antitir.in", "r" );
  n = readInt();
  for ( i = 0; i < n; i++ ) {
    x[i] = readInt();
    y[i] = readInt();
  }
  fclose(fin);

  xmed = median( n, x );
  ymed = median( n, y );

  sum = 0;
  for ( i = 0; i < n; i++ )
    sum += modul( x[i] - xmed );
  for ( i = 0; i < n; i++ )
    sum += modul( y[i] - ymed );

  fout = fopen( "antitir.out", "w" );
  fprintf( fout, "%lld\n", sum );
  fclose( fout );

  return 0;
}

Ce complexitate are acest algoritm?

Pe cazul mediu el va fi O(N), datorită citirii și selecției.

Memoria ocupată este tot O(N), mai exact circa 8MB.

Tema opțională - rezolvări

Supersuma

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

Soluție

Genul acesta de probleme se rezolvă rareori găsind o formulă inversă pentru supersumă. Mai curînd calculăm rapid supersuma unui număr, iar apoi, deoarece supersuma este o funcție crescătoare, putem aplica metoda înjumătățirii intervalului, care este o formă de căutare binară.

Rămîne să calculăm rapid supersuma unui număr. Să observăm că:

  • Numărul de divizori ai unui număr N este log N.
  • Supersuma unui număr N va avea, deci, log 1 + log 2 + log 3 + ... + log N divizori, adică O(log N!) = O(N log N) divizori de adunat.
  • Vom calcula log N super sume, datorită căutării binare.
  • Complexitatea ar ajunge, deci, la O(N log2N)
  • Putem calcula aproximativ N astfel încît supersuma lui N să fie K maxim (14 cifre de 9). Rezultă N maxim circa 11 milioane.
  • Înlocuind vom avea circa 11 milioane·23·23 operații, adică circa 4 miliarde, mult prea multe.
  • Chiar și presupunînd că reducem calculul supersumei la O(N), tot vom avea prea multe operații, circa 250 milioane.

Va trebui să grupăm cumva divizorii. Să ne folosim de faptul că ei sînt în mod natural grupați, orice divizor d al lui N avînd perechea sa N/d. Să încercăm să grupăm divizorii astfel încît să nu depășim radicalul.

Astfel, vom aduna perechi (d, N/d):

  • Pentru d=1 vom aduna la supersumă 1, apoi 1+2, 1+3, 1+4, ..., 1+N/1
  • Pentru d=2 vom aduna la supersumă 2, apoi 2+3, 2+4, 2+5, ..., 2+N/2
  • Pentru d=3 vom aduna la supersumă 3, apoi 3+4, 3+5, 3+6, ..., 2+N/3

...

  • Pentru d=k vom aduna la supersumă k, apoi k+(k+1), k+(k+2), ..., k+N/k

Ne vom opri atunci cînd k depășește radical din N.

Rezultă că pentru d=k vom aduna:

  • k
  • k + k + k + ... + k de (N/k - k) ori, adică k(N/k - k)
  • k+1 + k+2 + k+3 + ... + N/k adică Gauss(N/k) - Gauss(k)

Ce complexitate are algoritmul rezultat?

El efectuează un număr constant de operații pentru fiecare k. Dar k variază de la 1 la radical din N. Rezultă că algoritmul este O(sqrt(N) log N). Înlocuind obținem circa 3000·23 = 69000 operații, ce vor intra lejer în timp.

Un program posibil este următorul (35 de linii de cod efectiv):

#include <stdio.h>

#define MAXN 11026578

long long supersuma( int n ) {
  int k = 1;
  long long ss = 0L;

  while ( k * k <= n ) {
    ss += k;
    if ( n / k >= k + 1 )
      ss = ss + (n / k - k)* k + ((long long)(n / k)) * (n / k + 1) / 2
        - k * (k + 1) / 2;
    k++;
  }

  return ss;
}

int main() {
  FILE *fin, *fout;
  int st, dr, med;
  long long k;

  fin = fopen( "supersuma.in", "r" );
  fscanf( fin, "%lld", &k );
  fclose( fin );

  // (st .. dr]
  st = 0;
  dr = MAXN;
  while ( dr - st > 1 ) {
    med = (st + dr) / 2;
    if ( supersuma( med ) < k )
      st = med;
    else
      dr = med;
  }
  
  fout = fopen( "supersuma.out", "w" );
  fprintf( fout, "%d\n", dr );
  fclose( fout );

  return 0;
}

Rezolvări aici [1]

Lecţie

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, î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.

Drumul cel mai scurt între două orașe poate fi rezolvat cu programare dinamică

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

i1, i2, i3, …, ik

Astfel

L[i1] = k

Este secvența i2, ..., ik optimală? Cu alte cuvinte lungimea secvenței optime care începe la i2 este k-1? Răspunsul este da, secvența care începe la i2, anume i2, ..., ik este o secvență maximă, deoarece altfel am putea-o înlocui cu o secvență mai lungă, ceea ce ar duce la o subsecvență L[i1] 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(n2), 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ță:


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 (ik, jk), strict crescătoare, cu proprietatea că X[ik] = Y[jk]:

Si,j = (i1, j1) (i2, j2) ... (ik, jk)

cu proprietatea că:

Xi1Xi2... Xik-1Xik = Yj1Yj2... Yjk-1Yjk

Atunci este lungimea M[ik-1][jk-1] la rîndul ei optimală? Cu alte cuvinte subsecvența mai scurtă cu unu, care se termină la poziția ik-1 în X, respectiv poziția jk-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ță:

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

Rezolvări aici [2]