Clasa a 7-a lecția 19 - 04 feb 2016

From Algopedia
Jump to navigationJump to search

Tema - rezolvări

Tema 17 clasa a 7a

Rezolvări aici [1]

Problema intervale

Problema intervale este o problemă de precalculare. 

#include <stdio.h>

#define MAX_N 1000000
#define MAX_K 7

char nrp[MAX_N + 1];
int spart[MAX_N + 1][MAX_K];

int main() {
  FILE *fin, *fout;
  int p, d, a, b, k;

  // ciurul lui Eratostene modificat sa calculeze numarul de divizori primi
  for ( p = 2; p <= MAX_N; p++ )
    if ( nrp[p] == 0 )
      for ( d = p; d <= MAX_N; d += p )
        nrp[d]++;

  // calcul sume partiale pentru fiecare K posibil (1..7)
  for ( d = 1; d <= MAX_N; d++ ) {
    for ( k = 1; k <= MAX_K; k++ )
      spart[d][k-1] = spart[d-1][k-1];
    spart[d][nrp[d]-1]++;
  }

  // raspundem la interbari
  fin = fopen( "intervale.in", "r" );
  fout = fopen( "intervale.out", "w" );
  while ( fscanf( fin, "%d%d%d", &a, &b, &k ) == 3 ) {
    if ( k == 0 )
      fprintf( fout, "%d\n", a == 1 ? 1 : 0 );
    else if ( k > 7 )
      fprintf( fout, "0\n" );
    else
      fprintf( fout, "%d\n", spart[b][k-1] - spart[a-1][k-1] );
  }
  fclose( fin );
  fclose( fout );

  return 0;
}

Problema Reginald

Problema Reginald este exact problema intervale, cu mai puţină memorie disponibilă. Mai exact, nu mai putem stoca matricea de 7 x numărul maxim. 

#include <stdio.h>

#define MAX_N 4000000
#define MAX_K 7
#define MAX_QUERY 1000000
#define NIL -1

char nrp[MAX_N + 1];
int spart[MAX_N + 1];
int ind[MAX_K] = { NIL, NIL, NIL, NIL, NIL, NIL, NIL };
struct query { int a; int b; int r; int next; } q[MAX_QUERY];

int main() {
  FILE *fin, *fout;
  int p, d, n, k, maxb;

  fin = fopen( "reginald.in", "r" );
  maxb = 0;
  fscanf( fin, "%d", &n );
  for ( p = 0; p < n; p++ ) {
    fscanf( fin, "%d%d%d", &q[p].a, &q[p].b, &k );
    if ( q[p].b > maxb )
      maxb = q[p].b;
    if ( k == 0 )             // cind K este 0 raspunsul este
      q[p].r = (q[p].a == 1); // 1 doar daca [a,b] include pe 1
    else if ( k < 8 ) {
      q[p].next = ind[k-1];   // intrebarile standard le depunem in coada 
      ind[k-1] = p;           // la indexul potrivit
    }
  }
  fclose( fin );

  // ciurul lui Eratostene modificat sa calculeze numarul de divizori primi
  for ( p = 2; p <= maxb; p++ )
    if ( nrp[p] == 0 )
      for ( d = p; d <= maxb; d += p )
        nrp[d]++;
  
  for ( k = 1; k <= MAX_K; k++ ) {   // raspundem la intrebari (k = [1..7])
    for ( d = 1; d <= MAX_N; d++ )   // calcul sume partiale pentru K
      spart[d] = spart[d-1] + (nrp[d] == k);
    // pentru fiecare intrebare de K, putem raspunde pe baza sumelor partiale
    for ( p = ind[k-1]; p != NIL; p = q[p].next )
      q[p].r = spart[q[p].b] - spart[q[p].a-1];
  }

  fout = fopen( "reginald.out", "w" );
  for ( p = 0; p < n; p++ )
    fprintf( fout, "%d\n", q[p].r );
  fclose( fout );

  return 0;
}

Lecţie

Sume de intervale

Se dă un vector cu n elemente, iniţial zero. O operaţiune pe acest vector constă în incrementarea fiecărui element între indicii i şi j. Se dau, de asemenea, m operaţiuni de executat. Să se afişeze valorile finale ale vectorului.

Soluţia forţă brută implică execuţia celor m operaţiuni. O operaţiune constă în incrementarea a maxim n elemente din vector, deci avem n x m operaţii, plus afişarea elementelor finale. Complexitatea totală este O(mn).

Se poate mai bine? Putem optimiza timpul unei operaţiuni. Ideea este următoarea: în loc să incrementăm pe rînd elementele vectorului, am putea să le grupăm. Pentru aceasta vom întîrzia incrementarea, marcînd doar locurile unde trebuie să adunăm.

Cu alte cuvinte: am putea considera intervalele ca pe nişte paranteze aşezate pe o dreaptă. O paranteză deschisă înseamnă că de acum înainte trebuie să adunăm 1 la toate elementele care urmează. O paranteză închisă înseamnă că ne putem opri din adunat 1. Să presupunem că nu avem capete de interval suprapuse. Atunci am putea memora parantezele într-un vector separat. Vom memora 1 pentru o paranteză deschisă, -1 pentru o paranteză închisă şi 0 în caz că nu avem nici un capăt de interval în acel element.

Ipoteză: vectorul de sume parţiale ale acestui vector constituie chiar rezolvarea problemei. Să observăm ce se întîmplă atunci cînd adunăm s[i] = s[i] + s[i-1]: la început avem elemente zero. Cînd deschidem o paranteză acel element devine 1. Următoarele sume parţiale vor fi şi ele tot 1, pînă dăm de un alt capăt de interval. Să presupunem că mai deschidem o paranteză. Atunci suma va deveni 2 şi ea se va propaga în continuare pe elemente zero. Apoi să presupunem că se închide o paranteză. Adunînd -1 suma devine iarăşi 1, care se va propaga în continuare.

Funcţionează acest algoritm dacă avem capete de interval suprapuse? Da, cu condiţia ca elementul în care se suprapun capete să fie suma acelor capete, adică o sumă de 1 şi -1. Aceasta înseamnă că atunci cînd generăm vectorul de paranteze nu vom scrie s[i] = 1 ci s[i]++ (la fel şi pentru -1, vom decrementa).

Generalizare 1: putem generaliza această metodă pentru problema în care intervalele nu adună 1, ci orice număr, constant pe parcursul intervalului. Cum generalizăm? O paranteză deschisă nu va aduna 1 ci constanta respectivă.

Generalizare 2: dar dacă vectorul iniţial are valori diferite de zero? În acest caz vom calcula un vector separat, iniţializat cu zero, pe care facem calculul sumelor parţiale. Acest vector ne va spune cu cît s-a mărit fiecare element zero. În final vom aduna acest vector de sume parţiale la vectorul iniţial.

Acesta exemplu de precalculare, este cunoscut printre unii din voi drept "șmenul lui Mars", denumire care îmi displace deoarece sugerează că informatica este o colecție de șmenuri.

Cînd nu funcţionează această soluţie? Atunci cînd nu avem vector iniţial (elementele sînt toate zero), iar coordonatele intervalelor sînt prea mari pentru ca vectorul de sume parţiale să încapă în memorie. Să presupunem că ni se cere numărul maxim din vectorul de sume parţiale. În acest caz există o soluţie alternativă, mai generală (în sensul în care rezolvă o clasă mai mare de probleme cu intervale), care nu folosește precalculare: putem memora capetele de intervale, pe care apoi le ordonăm crescător, ţinînd minte de ce tip sînt, închis sau deschis. Apoi le parcurgem în ordine, calculînd sumele parţiale fără să le stocăm. Suma parţială maximă este răspunsul cerut.

Desigur că atunci cînd vectorul încape în memorie, e mai uşoară precalcularea. Acest tip de precalculare se poate extinde în două dimensiuni, pe matrice: se dau m dreptunghiuri care adună 1 la toate elementele respective dintr-o matrice. Această precalculare necesită O(n2) memorie. Ea nu se justifică decît în măsura în care este facil de programat, deoarece avem o soluție de aceeași complexitate care folosește varianta pe vector, folosind doar O(n) memorie.

Sume de arii

Aceasta ideea poate fi extinsa si in doua dimensiuni, construind B astfel incat Ai,j = suma subtabloului din B cu coltul in (0, 0) si (i, j), astfel (pt. ADUNA(x1,y1,x2,y2,v)): 

B[x1][y1] += v;
B[x1][y2 + 1] -= v;
B[x2 + 1][y1] -= v;
B[x2 + 1][y2 + 1] += v;

Pe cazul general, daca vrem sa facem operatii in d dimensiuni vom avea o complexitate O(2d).

Tema

Tema 18 clasa a 7a

Rezolvări aici [2]

Retrieved from "https://www.algopedia.ro/wiki/index.php?title=Clasa_a_7-a_lecția_19_-_04_feb_2016&oldid=13279"