Clasa a 7-a lecția 21 - 03 mar 2016

From Algopedia
Jump to navigationJump to search

Temă

Rezolvări aici [1]

Tema - rezolvări

Problema char

Problema char a fost dată la ONI 2010 clasa a 7a. Ea ne cere să rezolvăm o problemă clasică și anume numărul maxim de intervale neintersectante. Ideea de rezolvare este greedy: pornim de la stînga la dreapta și închidem intervalul care se termină primul (în sensul de intervalul care are cel mai mic capăt dreapta) şi care nu intersectează ultimul interval selectat.

Ca implementare, pentru a nu face o sortare, putem păstra la coordonatele capetelor dreapta coordonata capătului din stînga. În caz că avem mai multe intervale care se termină în același punct vom păstra cel mai scurt interval, deoarece este cel mai avantajos. Această implementare este O(n), unde n este numărul de caractere din text. 

#include <stdio.h>

#define NMAX 10000
#define PMAX 100

char text[NMAX];
int cap[NMAX + 2 * PMAX + 1], f[26];

int main() {
  FILE *fin, *fout;
  int n, m, h, i, j, max, nmax;

  fin = fopen( "char.in", "r" );
  fscanf( fin, "%d ", &n );
  for ( i = 0; i < n; i++ )
    f[text[i] = fgetc( fin ) - 'a'] = 1;
  fscanf( fin, "%d", &h );
  for ( i = j = 0; i < h; i++ ) {
    while ( f[j] == 0 ) // avansam pe prima litera care apare in text
      j++;
    fscanf( fin, "%d", &f[j++] ); // stocam puterea in vectorul de frecventa
  }
  fclose( fin );

  max = 0;
  for ( i = 0; i < n; i++ ) {
    // nr. de litere cu putere maxima
    if ( f[text[i]] > max ) {
      max = f[text[i]];
      nmax = 1;
    } else if ( f[text[i]] == max )
      nmax++;
    // generare capete dreapta - pastram capatul din stinga cel mai mare
    if ( cap[j = i + PMAX + 1 + f[text[i]]] < (m = i + PMAX + 1 - f[text[i]]) )
      cap[j] = m;
  }
  // parcurgere greedy a capetelor dreapta
  j = m = 0;
  for ( i = PMAX + 1; i < n + 2 * PMAX + 1; i++ )
    if ( cap[i] > j ) {
      m++;
      j = i;
    }

  fout = fopen( "char.out", "w" );
  fprintf( fout, "%d\n%d\n", nmax, m );
  fclose( fout );

  return 0;
}

Problema baloane

Problema [2] a fost dată la olimpiada pe şcoală 2012 clasele 11-12 (dar este, în fapt, o problemă de nivel ONI clasa a 7 a. Este exact problema clasică: numărul minim de puncte pe axă care "ating" toate intervalele este totuna cu numărul maxim de intervale neintersectante (deşi acest lucru merita o schiţă de demonstraţie din partea voastră).

Deoarece dispunem de suficientă memorie problema se poate rezolva clasic, uşor: pentru fiecare punct pe axa Ox - dacă avem un interval care se termină în acel punct - vom reţine coordonata de început a acelui punct. Dacă avem mai multe intervale care se termină în acelaşi punct îl vom reţine pe cel mai dezavantajos, adică pe cel mai mic. Apoi parcurgem axa Ox şi, de fiecare dată cînd dăm peste o închidere de interval, ne întrebăm dacă acel interval a fost "atins" de ultima săgeată, caz în care îl ignorăm. În caz contrar va trebui sa "tragem" o săgeată în acel punct şi să actualizăm ultima săgeată.

Complexitatea acestei soluţii este O(N + XMAX + RMAX), unde N este maxim 100 000, XMAX este maxim un milion şi RMAX este 100. Această soluţie este mult sub timpul acordat, de 0.5s. Complexitatea spaţială este O(XMAX + RMAX). Dacă am memora întregi am avea nevoie de aproximativ 4MB de memorie, în vreme ce problema ne dă doar 2MB. Cum facem să ne încadrăm?

Observăm că razele intervalelor sînt mici, maxim 100. Drept pentru care putem să stocăm raza în punctele de final de interval. Ea este suficientă pentru a calcula capătul de început. Astfel memoria se reduce la 1MB.

Iată o soluţie care implementează aceste idei: 

#include <stdio.h>

#define MAXX 1000000
#define MAXR 100

char pct[MAXX+MAXR+1]; // 1MB

int main() {
  FILE *fin, *fout;
  int n, i, ult, sag, x, r;

  fin = fopen( "baloane.in", "r" );
  fscanf( fin, "%d", &n );
  for ( i = 0; i < n; i++ ) {            // citim cele n baloane
    fscanf( fin, "%d%d", &x, &r );       // centru x, raza r
                                         // la punctul x+r nu avem balon
    if ( pct[x+r] == 0 || pct[x+r] > r ) // sau e un balon mai mare?
      pct[x+r] = r;                      // memoram raza balonului la final
  }
  fclose( fin );

  ult = -200; // ultimul final de balon vizitat este unul imposibil
  sag = 0;    // numarul de sageti trase este zero
  for ( x = 1; x <= MAXX+MAXR; x++ ) { // pentru fiecare punct pe axa numerelor
    if ( (r = pct[x]) > 0 )     // daca la i se termina un balon
      if ( (x - 2*r) >= ult ) { // capatul stinga nu e atins de ultima sageata?
        sag++;   // marim numarul de sageti necesare
        ult = x; // ult este locul unde am tras ultima sageata
      }
  }

  fout = fopen( "baloane.out", "w" );
  fprintf( fout, "%d\n", sag );
  fclose( fout );

  return 0;
}

Problema macheta

Problema macheta a fost dată la ONI 2011 clasa a 8a. Ea cere să calculăm vizibilitatea unor dreptunghiuri proiectate în plan. Există multe soluţii la această problemă (comisia de olimpiadă a dat trei!). Voi prezenta mai jos o soluţie care nu are complexitate optimă, dar care este relativ uşor de implementat şi, datorită valorilor mici ale variabilelor, se încadrează lejer în timpul cerut.

Ce avem, în fapt, de calculat? Ce se vede la final cînd ne uităm la clădiri dinspre sud? Ne-am mai întîlnit cu genul acesta de vedere, el se numeşte skyline. Cum putem descrie un skyline? Un mod facil, în acest caz, este să memorăm pentru fiecare punct pe axa Ox (pe pămînt) o înălţime a clădirii vizibile pe acea coloană. Vom avea astfel un vector de coordonata maximă, adică de 2000 de elemente. Cum putem construi acest vector? Putem, de exemplu, să "aşezăm" fiecare clădire în el. Putem considera o clădire ca un interval pe axa Ox care are o valoare înscrisă pe el, respectiv înălţimea acelui interval. Cînd aşezăm clădirea înscriem în vector înălţimea ei la toate punctele acoperite.

Acum, dacă aşezăm toate clădirile, unele elemente ale vectorului vor fi suprascrise. Deci trebuie să avem grijă, ordinea contează. Cum nu avem prea multe ordini de aşezare, observăm repede că cea dinspre în faţă către spate ne dă o soluţie. Cînd aşezăm o clădire care vine în spatele altor clădiri, un punct al ei va fi vizibil numai dacă este strict mai înalt decît înălţimea vizibilă în skyline în acel punct.

Recapitulăm algoritmul:

  1. Iniţializăm vectorul de înălţimi, h[], cu zero (acel skyline).
  2. Ordonăm clădirile după y. În cadrul aceluiaşi y, coordonata x nu contează.
  3. Parcurgem clădirile în această ordine. Pentru fiecare clădire C de înălţime H:
    1. Parcurgem fiecare punct al intervalului pe axa Ox. Pentru fiecare punct x al clădirii, pe axă:
      1. Dacă h[x] este strict mai mic decît H, atunci clădirea este vizibilă şi:
        1. h[x] devine H
        2. memorăm numărul clădirii într-un vector de frecvenţă al clădirilor
  4. În final parcurgem vectorul de frecvenţă al clădirilor şi afişăm toate clădirile memorate

Deoarece coordonatele sînt mici putem să evităm ordonarea după axa y. Vom memora pentru fiecare coordonată y o listă de clădiri care încep la acea coordonată.

Acest algoritm are complexitate O(N · LMAX), unde N este numărul clădirilor, iar LMAX este coordonata maximă. Mulţumită valorilor mici soluţia duce la un timp de rulare aproape de zero. Memoria necesară este O(N + LMAX). Dacă folosim timpurile corecte de date vom ajunge la circa 5KB, adică şi ea este aproape de zero.

Iată o soluţie bazată pe acest algoritm: 

#include <stdio.h>

#define NIL 0
#define MAXCLAD 100
#define MAXCOORD 1000

char clad[MAXCLAD+1];      // clad[j]=1 daca cladirea j este vizibila la final
short vizibil[2*MAXCOORD]; // vizibil[x] = inaltimea vizibila in punctul x
char lista[MAXCOORD + 1];  // capetele liste cladiri care incep la coordonata y
short x1[MAXCLAD+1], x2[MAXCLAD+1]; // x-ul de inceput si final al cladirilor
short h[MAXCLAD+1];   // inaltimile cladirilor
char next[MAXCLAD+1]; // urmatorul in lista

int main() {
  FILE *fin, *fout;
  int n, i, x, y, lx, ly, H, viz;

  fin = fopen( "macheta.in", "r" );
  fscanf( fin, "%d", &n );
  for ( i = 1; i <= n; i++ ) {
    fscanf( fin, "%d%d%d%d%d", &x, &y, &lx, &ly, &H ); // citim cladirea
    // cream celula de lista cu valorile x1, x2, h si next
    x1[i] = x;          // inceputul cladirii pe axa Ox
    x2[i] = x + lx;     // sfirsitul cladirii pe axa Ox
    h[i] = H;           // inaltimea cladirii
    next[i] = lista[y]; // inseram celula la inceputul listei y
    lista[y] = i;
  }
  fclose( fin );

  // asezam cladirile in vectorul de vizibilitate, din fata in spate
  for ( y = 0; y <= MAXCOORD; y++ ) {
    i = lista[y];
    while ( i != NIL ) { // parcurgem cladirile care incep la coordonata y
      viz = 0;           // initial cladirea i nu e vizibila
      for ( x = x1[i]; x < x2[i]; x++ )
        if ( vizibil[x] < h[i] ) { // este vizibila?
          viz = 1;
          vizibil[x] = h[i]; // marcam noua inaltime
        }
      clad[i] = viz; // marcam cladirea i ca vizibila sau nu, depinzind de viz
      i = next[i];   // trecem la urmatoarea cladire de pe linia y
    }
  }

  fout = fopen( "macheta.out", "w" );
  for ( i = 1; i <= n; i++ ) // afisam cladirile vizibile
    if ( clad[i] == 1 )
      fprintf( fout, "%d ", i );
  fprintf( fout, "\n" );
  fclose( fout );

  return 0;
}

Există soluţii mai bune? Desigur. Putem sorta intervalele şi apoi parcurge într-o ordine de la stînga la dreapta, ţinînd cont de cele vizibile la un moment dat în parcurgere. Această soluţie va fi O(N log N) ca timp şi O(N) ca memorie, dar ea va fi ceva mai laborios de implementat.

Lecție

Am discutat despre problemele Neuroni si Raze.

Tema

Retrieved from "https://www.algopedia.ro/wiki/index.php?title=Clasa_a_7-a_lecția_21_-_03_mar_2016&oldid=13323"