Tema - rezolvări

Onigim

Problema onigim a fost dată la ONI 2013 clasa a 5^a. Ea admite o rezolvare foarte scurtă cu liste, desigur peste nivelul clasei a 5^a.

Comentarii generale

Pare că problema nu v-a pus probleme. Listele au fost cucerite. Ura! :-)
Avertismente: Moroșan, Stancu (surse fără liste).

Macheta

Problema macheta a fost dată la ONI 2011 clasa a 8^a. Ea admite o rezolvare foarte scurtă cu liste, care nu apare printre rezolvările oficiale.

Comentarii generale

Felicitări celor ce au reușit o soluție foarte bună și ordonată: prea mulți să vă enumăr, bravo tuturor!
Pare că majoritatea ați înțeles listele. Felicitări!
Dragilor: 101 ≠ 1001 ≠ 10001. Dimensionați corect vectorii! Vă poate costa enorm la olimpiadă. Dacă foloseați constante poate nu greșeați.
Unii din voi au avut folosit o sortare a cladirilor vizibile. Nu era necesar, puteați folosi un vector de frecvență.
Unii din voi au memorat date nenecesare pentru fiecare clădire, cum ar fi coordonata y și lungimea pe y. Nu rispiți memoria, vă rog.
Folosiți vă rog constante, pentru claritate. Chiar dacă unele din exemplele mele nu le folosesc :-).
Unii din voi s-au complicat la parcurgerea x-ilor unei clădiri. Cele două while se pot combina într-un singur for deoarece trebuie parcurși toți x-ii.
Avertismente: Moroșan (nici o sursă), Stancu (soluție fără liste).

Comentarii individuale

Prima grupă

Aizic: Program foarte bun, bravo! Nu aveai nevoie de sortare dacă foloseai un vector de frecvență al vizibilității clădirilor.
Badea: Program foarte bun, bravo! Observație importantă, nu aveai nevoie de vectorii y[] și Ly[]. E bine să te obișnuiești să nu folosești memorie extra, poți să ai probleme la olimpiadă. Plus, risipa nu e bună :)
Benescu: Program foarte bun, bravo! Observație minoră, folosește constante pentru claritatea codului.
Burac: Program foarte bun, bravo! Observație minoră, folosește constante pentru claritatea codului.
Calotă: Program foarte bun, bravo! Observații minore: denumirea last[] nu e deloc corectă căci nu e ultimul element ci primul, trebuia list[], ai folosit constante dar nu și la numărul de clădiri, iar NIL se scrie cu un singur L :-)
Chivu: Program foarte bun, bravo! Observație importantă, nu aveai nevoie de vectorii cy[] și cly[]. În plus, ai declarat vectorul liste[] de 2000 de elemente, sînt doar 1000 de y posibili. E bine să te obișnuiești să nu folosești memorie extra, poți să ai probleme la olimpiadă. Plus, risipa nu e bună :)
Cojocariu: Program bun, bravo! Așa da! Observații: la fscanf() nu citi o valoare necesară în aceeași variabilă cu o valoare inutilă. Este riscant. Inserezi la finalul listelor! Inutil și ineficient. Dacă toate clădirile sînt pe aceeași linie citirea ta este O(n²). Vezi inserția la început de listă. Dacă vrei să inserezi la final de listă în mod eficient trebuie să mai ții un vector de legături la ultima celulă a listelor. Parcurgerea listelor conține cod dublat inutil. Nu ai urmărit cu atenție cum se face parcurgerea, nu e bine.
Dobre: Program bun. Ai înțeles listele, dar ai unele încîlceli în gîndire. Am următoarele observații: Nu trebuia să memorezi coordonatele y, pentru ca abia apoi să creezi vectorul de liste. Puteai să combini totul la citire, mai simplu. Apoi, Inserezi la finalul listelor! Inutil și ineficient. Dacă toate clădirile sînt pe aceeași linie citirea ta este O(n²). Vezi inserția la început de listă. Dacă vrei să inserezi la final de listă în mod eficient trebuie să mai ții un vector de legături la ultima celulă a listelor. Apoi, parcurgerea listelor și prelucrarea clădirilor este încîlcită. De exemplu ai un steg care este totuna cu rez[nr]. Ai două etape, întîi cauți primul punct vizibil, apoi ai o altă buclă care continuă prima buclă pînă la finalul x-ilor. Puteai combina cele două bucle, oricum trebuie să actualizezi înălțimile vizibile. Nu aveai nevoie de sortare dacă foloseai un vector de frecvență al vizibilității clădirilor.
Hossu: Program bun. Observație importantă, nu aveai nevoie de vectorii y[] și Ly[]. E bine să te obișnuiești să nu folosești memorie extra, poți să ai probleme la olimpiadă. Plus, risipa nu e bună :) Ai complicat inutil inserția la început de listă, nu ai caz particular cînd lista e vidă. Atenție la dimensionări, vectorul height[] trebuia să fie de 2000 de elemente. De aceea cred că pici teste.
Iordache: Program foarte bun, bravo! Observație minoră, folosește constante pentru claritatea codului. Denumirile variabilelor lasă de dorit. Nu închizi fișiere! Foarte urît!
Mocanu: Pare că ai înțeles listele. Dar nu cred că ai înțeles rezolvarea povestită la lecție. Tu nu folosești deloc coordonatele y ale clădirilor. Construiești liste pentru x, pe verticală, trebuia să construiești pentru y, pe orizontală.
Mușat: Program bun, folosești corect liste. Observații: de ce faci citirile una cîte una? Folosești 5 fscanf() în loc de unul singur. Atenție la dimensionări! Tu ai dimensionat totul de 1000, dar majoritatea vectorilor sînt de 100, numărul maxim de clădiri! Observație importantă, nu aveai nevoie de vectorii vp[], inceput_l[] și latime[]. E bine să te obișnuiești să nu folosești memorie extra, poți să ai probleme la olimpiadă. Plus, risipa nu e bună :)
Nicola: Program foarte bun, bravo! Neimportant, nu aveai nevoie de vectorul val[]. Ai val[i] = i, deci e inutil.
Petcu: Program foarte bun, bravo! Observație minoră, folosește constante pentru claritatea codului.
Ștefănescu: Program foarte bun, bravo! Atenție la dimensionări! Tu ai dimensionat totul de 1000, dar majoritatea vectorilor sînt de 100, numărul maxim de clădiri! Nu aveai nevoie de sortare dacă foloseai un vector de frecvență al vizibilității clădirilor.
Togan: Programul este bun. Dar! Atenție la dimensionări, vectorul next[] are 101 de elemente, nu 1000. Observație importantă, nu aveai nevoie de vectorii y[] și Ly[]. E bine să te obișnuiești să nu folosești memorie extra, poți să ai probleme la olimpiadă. Plus, risipa nu e bună :) Observație minoră, folosește constante pentru claritatea codului. Din nou încîlceală:

      j=liste[i];///merg pe fiecare linie
      while(j!=0){///merg pe lista
        k=x[j-1];
        out=0;
        while(x[j-1]<(lx[j-1]+k)){///actualizez inalt maximale
          if(inaltime[x[j-1]]<h[j-1]){
            inaltime[x[j-1]]=h[j-1];
            out=1;
          }
          x[j-1]++;
        }
        if(out==1){
          output[j]=1;
        }
        j=next[j-1];
      }

Acel while este de fapt for. Folosești o variabilă de ciclu k, dar ea este doar pentru inducerea în eroare a adversarului (cititorul de cod)! Tu de fapt variezi limita inițială a for-ului! Togan, exercițiu: scrie acest cod normal, vezi dacă poți.

Voicu: Program foarte bun, bravo! Observație minoră, folosește constante pentru claritatea codului.

A doua grupă

Asgari: Program foarte bun, bravo!
Cadîr: Construiești corect listele de clădiri, mai puțin faptul că ai dimensionat pe greșit vectorii liste[] și next[], dimensiunile lor sînt invers. Parcurgerea listelor este greșită. Straniu, căci ai făcut-o bine la onigim. Vezi soluția mai jos.
Dimulescu: Atenție la indentare! Nu pot urmări programul tău și nici tu. Dacă continui așa nu poți continua la IQ Academy. Indentarea e ceva ce înveți la începuturile programării, este ridicol să îți tot fac observație pentru ea. Programul pare bun, motivul pentru care pici teste este dimensionarea lui h[], el are 2000 de elemente căci o clădirea poate să înceapă la x=1000 și să aibă L_x=1000. Elementele c[i][1] și c[i][3] sînt inutile, puteai să nu le stochezi degeaba. În acest caz matricea c[][] complică mult înțelegerea programului tău. Corect era să folosești cinci vectori cu denumiri diferite, altfel cum pot eu să-mi dau ușor seama ce reprezintă c[i][1]?
Fares: Program bun, bravo! Din categoria 'lenea gîndirii', toți vectorii sînt dimensionați la 1001, să nu ne batem capul, chit că mulți din ei au nevoie doar de 101 elemente.
Ghica: Nu înțeleg cum creezi listele. Aloci celule cînd la indicele i, cînd la indicele k. Denumirile de variabile nu ajută deloc la înțelegere. Pare că inserezi un element nou la finalul listelor, cînd inserarea la început e ușoară. Atenție la dimensionările de vectori! next[] și cel[] sînt prea mari, 2100 în loc de 101 și 2001, în vreme ce v[], lun[], și f[] sînt de 100 în loc de 101. Astea sînt greșeli de începători! Calculează cu atenție dimensiunea. Pentru viitor atenție mai mare la enunț, la dimensiuni, la calcule, la denumirile variabilelor.
Grecu: Program foarte bun, bravo! Mulțumesc pentru comentarii. Atenție, key[] este folosit pentru valoarea dintr-o celulă de listă. Tu îl folosești ca vector de liste. E confuzant. Atenție la dimensionările de vectori! cldH[1001], lx[1001], coordx[1001] sînt în realitate de 101 elemente. Folosește constante pentru claritatea codului, poate nu te mai încurci la dimensionări.
Ilie: Program foarte bun, bravo! Observație minoră, te-ai complicat la parcurgerea x-ilor unei clădiri. Cele două while se pot combina într-un singur for deoarece trebuie parcurși toți x-ii. Observație importantă, nu aveai nevoie de vectorii y[] și Ly[]. E bine să te obișnuiești să nu folosești memorie extra, poți să ai probleme la olimpiadă. Plus, risipa nu e bună :)
Ipate: Program foarte bun, bravo! Atenție la dimensionări, ai făcut un artificiu să lucrezi cu NIL = 0 drept care ai folosit vectorul next[] de la 1, ceea ce înseamnă că trebuia să îl dimensionezi de 101, nu 100. Artificiile de genul acesta nu sînt bune. Însă îmi place lejeritatea cu care jonglezi cu indici de la zero sau de la unu, arată că ai control și nu ți-e teamă să calculezi. Atenție, key[] este folosit pentru valoarea dintr-o celulă de listă. Tu îl folosești ca vector de liste. E confuzant.
Marcu: Program foarte bun, bravo! Observație minoră, folosește constante pentru claritatea codului.
Moroșan: Nimic? Este a doua temă la care nu trimiți nimic la una din probleme.
Nicu: Programul tău ar fi putut fi foarte bun. Dar are prea multe bube. Ce este asta: int num_y[10001], next[10001], h[10001], vx[10001], vlx[10001], h1[10001], poz[10001];? o glumă? În primul rînd numărul de clădiri este 100, iar coordonatele sînt maxim 1000. În al doilea rînd tu ai pus un zero în plus la toate. Asta nu e nici măcar programare aproximativă, este o grosolănie! Nu înțeleg de ce apelezi num_y[y - 1]; atunci cînd y poate fi zero. Observație minoră, te-ai complicat la parcurgerea x-ilor unei clădiri. Cele două while se pot combina într-un singur for deoarece trebuie parcurși toți x-ii.
Petrescu: Program foarte bun, bravo! În continuare le încîlcești :) În dorința de a folosi NIL=0 și a nu folosi vectori de la 1 te-ai complicat la parcurgerea listelor. Stegulețe degeaba, aux este, de fapt, o legătură la celula curentă și nu o variabilă auxiliară, iar while-l interior este de fapt un for. Dar, una peste alta, văd o îmbunătățire.
Popescu: Program foarte bun. Atenție la dimensionări! Tu ai dimensionat totul de 1000, dar majoritatea vectorilor sînt de 100, numărul maxim de clădiri! E bine să te obișnuiești să nu folosești memorie extra, poți să ai probleme la olimpiadă. Plus, risipa nu e bună :) Dacă foloseai constante poate nu greșeai.
Rebengiuc: Program foarte bun, bravo! Atenție mare la define-uri: #define MAX_POZ MAX_XY + MAX_LX, poți avea probleme dacă undeva în cod ai MAX_POZ * 10, deoarece doar MAX_LX se va înmulti cu 10. Corect era #define MAX_POZ (MAX_XY + MAX_LX)
Rughiniș: Nu ai înțeles rezolvarea din clasă. Degeaba scriu lecția, degeaba ai video. Ai făcut liste pe coordonata x. Soluție ineficientă, ce folosește și mult mai multă memorie. Partea bună este că pare că ai înțeles bine inserările în liste.
Stancu: Program fără liste. E clar că nu ai înțeles deloc listele, ceea ce mi-ai scris și în comentariile programului. Ce nu înțeleg este de ce stai cumințel. Ai lecția scrisă, ai filmul lecției. Dacă totuși nu înțelegi, ai clubul curioșilor, mai ai și emailul meu personal. Nu este OK să spui "nu înțeleg" și atît. Vreau să văd că nu ai înțeles după ce ai făcut efortul. Părerea mea e că nu l-ai făcut.
Tatomir: Program foarte bun, bravo!
Teodorescu: Program foarte bun, bravo! Atenție mare la dimensionări! Majoritatea vectorilor erau de 100 de elemente, tu i-ai declarat pe toți de 1000.
Voicu: Program bun, bravo! Nu aveai nevoie de sortare dacă foloseai un vector de frecvență al vizibilității clădirilor.

Concurs - rezolvări

Criptic

Problema criptic a fost dată la cercul de informatică din liceul Tudor Vianu în 2013 la clasa a 7^a.

Rezolvări aici [1]

Lecție

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

Precalculare

Precalcularea este un termen general pentru folosirea unor structuri auxiliare de date, uneori fără o legătură directă cu problema de rezolvat, care ne ajută în rezolvarea problemei. Aceste structuri de date sînt calculate la început, înainte de calculul propriu zis, ceea ce duce la denumire: precalculare. De obicei precalcularea reduce complexitatea anumitor pași din algoritm, prețul ei fiind un calcul mic la început, astfel încît, per total, algoritmul va fi mai rapid.

În continuare vom vorbi despre cîteva exemple clasice de precalculare.

Santinela în căutarea liniară

Precum știm, codul clasic de căutare a elementului e în vectorul v[] de n elemente este:

i = 0;
while ( i < n && v[i] != e )
  i++;
if ( i < n ) // ... testul daca am gasit elementul

Am discutat cum putem elimina unul din testele din while folosind o santinelă. Vom așeza e pe prima poziție în afara vectorului. Astfel, ne asigurăm că vom găsi elementul în vector. Putem, deci, să nu mai testăm condiția i < n. Noul cod va fi:

v[n] = e;
i = 0;
while ( v[i] != e )
  i++;
if ( i < n ) // ... testul daca am gasit elementul

Așezarea santinelei în vector poate fi un exemplu foarte simplu de precalculare. Ea va folosi un element al vectorului, ce va trebui dimensionat cu unu în plus.

Avantaje: cod mai rapid și mai scurt.
Schimbă complexitatea algoritmului: nu.
Timp precalculare: O(1).
Memorie extra folosită: O(1) (un element în plus).

Bordarea

Bordarea, tehnica prin care "înconjurăm" matricea cu elemente distincte, ar putea fi și ea considerată o precalculare. În loc de o santinelă avem acum multiple santinele. Codul de testare al depășirii matricei se simplifică și devine mai eficient.

Avantaje: cod mai rapid și mai scurt.
Schimbă complexitatea algoritmului: nu.
Memorie extra folosită: O(n) (unde n este dimensiunea matricei).

Precalculare tip caracter

Dacă avem nevoie să aflăm dacă un caracter dat este cifră, testul clasic este:

if ( ch >= '0' && ch <= '9' )
  // ...

Putem elimina un test dacă precalculăm un vector de stegulețe, pentru toate caracterele, care să aibă 1 pe pozițiile caracterelor cifre și 0 în rest. Astfel:

char ecifra[128];

// precalculare: initializare ecifra[]
for ( ch = '0'; ch <= '9'; ch++ )
  ecifra[ch] = 1;

// test cifra
if ( ecifra[ch] )
  // ...

Vom calcula la început cîte o valoare per cifră. Apoi, în algoritm vom scuti unul din teste.

Din fericire nu trebuie să facem explicit acest lucru. Biblioteca <ctype.h> ne oferă funcția:

int isdigit( int ch )

care face exact ce ne dorim. Există și alte funcții, cum ar fi isalpha() (testare literă) și isalnum() (testare cifra sau litera).

Avantaje: cod mai rapid și mai scurt.
Schimbă complexitatea algoritmului: nu.
Timp precalculare: O(Σ) (unde Σ este numărul de caractere).
Memorie extra folosită: O(Σ) (unde Σ este numărul de caractere).

Precalculare valori cifre în baze de numerație

Să luăm ca exemplu problema criptic. La intrare se aflau numere în baza 62, ce trebuiau citite ca întregi în memorie. Pentru aceasta trebuia să calculăm valoarea unei cifre. Codul simplu și direct va fi:

char ch;
// ...
ch = fgetc( fin );
if ( ch >= '0' && ch <= '9' )
  v = ch - '0';
else if ( ch >= 'a' && ch <= 'z' )
  v = ch - 'a' + 10;
else
  v = ch - 'A' + 36;

El va face 2 sau 4 teste de inegalitate. Pentru a nu avea nici un test putem precalcula într-un vector valorile cifrelor în baza 62:

  int val[128];
  // ...
  for ( ch = '0'; ch <= '9'; ch++ ) // valorile cifrelor
    val[ch] = ch - '0';
  for ( ch = 'a'; ch <= 'z'; ch++ )
    val[ch] = ch - 'a' + 10;
  for ( ch = 'A'; ch <= 'Z'; ch++ )
    val[ch] = ch - 'A' + 36;

Apoi, la folosire:

char ch;
// ...
ch = fgetc( fin );
v = val[ch];

Avantaje: cod mai rapid și mai scurt.
Schimbă complexitatea algoritmului: nu.
Timp precalculare: O(Σ) (unde Σ este numărul de caractere).
Memorie extra folosită: O(Σ) (unde Σ este numărul de caractere).

Ciurul lui Eratostene

V-aţi gîndit vreodată că ciurul lui Eratostene este de fapt o precalculare a unui vector de frecvenţă ciur[], care, pentru fiecare număr p, calculează ciur[p] care ne spune dacă p este prim?

Cum am calcula primalitatea tuturor numerelor pînă la n în absența ciurului? Am verifica de primalitate fiecare din numere, în O(p). Complexitatea algoritmului ar fi:

${\sqrt {1}}+{\sqrt {2}}+{\sqrt {3}}+...+{\sqrt {n}}$

Această sumă este $O(n{\sqrt {n}})$ (demonstrația depășește nivelul cercului nostru). În realitate lucrurile stau puțin mai bine, în sensul că nu vom ajunge cu divizorii pînă la ${\sqrt {k}}$ decît pentru k prim. O estimare a numerelor prime pînă la n este

${\frac {n}{log{n}}}$

De aceea, o estimare ajustată a complexității ar fi

$O({\frac {n{\sqrt {n}}}{log{n}}})$

Am putea face și o altă optimizare: să împărțim k doar la numerele prime de pînă la el. Aceasta mai reduce complexitatea într-un mod ce ar complica și mai mult formula.

Să nu uităm un lucru important: factorizarea folosește împărțiri. Ceea ce, pentru numerele cu care lucrăm noi, introduce o constantă multiplicativă foarte mare, circa 15 pînă la 30, comparabilă cu optimizări de tipul O(log n).

Prin comparație, ciurul lui Eratostene general are complexitatea O(n log n) și nu folosește împărțiri, iar pentru cazul testului de primalitate el poate fi adus la O(n log log n).

Să ne reamintim unele din aplicațiile ciurului lui Eratostene:

Numărul de divizori primi (unici sau neunici) ai tuturor numerelor pînă la n
Suma divizorilor primi (unici sau neunici) ai tuturor numerelor pînă la n
Numărul de divizori ai tuturor numerelor pînă la n
Suma divizorilor tuturor numerelor pînă la n
Descompunerea în factori primi a tuturor numerelor pînă la n
Numărul de numere prime cu fiecare din numerele pînă la n

Concluzii:

Avantaje: cod mai rapid și mai scurt.
Schimbă complexitatea algoritmului: da.
Timp precalculare: O(n log n) sau O( n log log n).
Memorie extra folosită: O(n).

Suma între i şi j

În multe probleme apare următoarea subproblemă: dat un vector v[] de n elemente întregi, să se răspundă la multe întrebări de forma care este suma elementelor vectorului între poziţiile i şi j?. În acest caz vom precalcula o structură de date auxiliară, şi anume un vector s[], astfel încît s[i] este suma elementelor de la 0 pînă la i (inclusiv). El se mai numeşte şi vectorul sumei prefixelor lui v[]. Construcția acestui vector se poate face liniar deoarece avem relaţia

s[i] = s[i-1] + v[i]

Odată calculat acest vector putem răspunde în timp constant la întrebări. Suma elementelor între i şi j este s[j] - s[i-1]. Complexitatea algoritmului forță brută de calcul al unei sume ar fi O(n), pe medie. Precalcularea o reduce la O(1).

Avantaje: cod mai rapid și mai scurt.
Schimbă complexitatea algoritmului: da.
Timp precalculare: O(n).
Memorie extra folosită: O(n).

Suma între (l1, c1) şi (l2, c2)

Este problema anterioară extinsă la matrice: avem o matrice de numere întregi şi întrebări de forma: care este suma elementelor matricei în dreptunghiul care are drept colţuri opuse (l1, c1) şi (l2, c2)?.

În mod similar vom precalcula o matrice auxiliară cu suma elementelor matricei originale între (0, 0) şi (i, j). Ea poate fi calculată în timp constant per element, astfel:

Calcul matrice sume parțiale în dreptunghiuri care pornesc în origine

s[l][c] = s[l][c-1] + s[l-1][c] - s[l-1][c-1] + m[l][c]

Odată calculată matricea s[][] putem răspunde în timp constant la întrebări. Suma elementelor între (l1, c1) şi (l2, c2) este:

S = s[l2][c2] - s[l2][c1-1] - s[l1-1][c2] + s[l1-1][c1-1]

Calcul suma numerelor în orice dreptunghi

Complexitatea algoritmului forță brută de calcul al unei sume ar fi O(n²), pe medie. Precalcularea o reduce la O(1).

Avantaje: cod mai rapid și mai scurt.
Schimbă complexitatea algoritmului: da.
Timp precalculare: O(n²).
Memorie extra folosită: O(n²).

Numărul de biţi 1 într-un întreg

Cum putem calcula numărul de cifre 1 din reprezentarea în baza 2 a unui număr?

Direct: shift and mask. Complexitate O(nr. biţi)
Folosind expresia x & (x - 1). Complexitate O(nr. biţi)
Cu precalculare: ţinem un vector în care elementul v[x] este numărul de biţi 1 din reprezentarea în baza 2 a lui x.

Concluzii precalculare număr de biți 1:

Avantaje: cod mai rapid.
Schimbă complexitatea algoritmului: da.
Timp precalculare: O(xMax log xMax).
Memorie extra folosită: O(2^{nr. biți}), sau O(xMax). Poate fi prohibitiv dacă xMax este mare.

Întrebări:

Se poate mai bine decît O(nr. biţi) fără memorie suplimentară (adică O(1) memorie suplimentară)?
Putem adapta metoda precalculării și la numere xMax mari, gen numere întregi pe int?

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

Exemplu

În următorul exemplu avem un vector inițial zero și se cere să executăm două operațiuni: operațiunea a va incrementa elementele de la pozițiile 2 la 13 și operațiunea b care va incrementa elementele de la pozițiile 6 la 9.

Operațiuni aplicate cu metoda forță brută

Îmbunătățire

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 s[] de sume parţiale ale acestui vector constituie chiar rezolvarea problemei.

Avem, deci:

s[i] = v[0] + v[1] + ... + v[i]

Înseamnă că v[k] se va aduna la toate sumele s[k], s[k+1], ..., s[n]. Ceea ce înseamnă că dacă pe poziția k în vectorul v[] avem valoarea unu, acea valoare se va propaga în toate elementele lui s[] începînd cu poziția k.

Dorim să aplicăm un interval [2, 13], deci vom plasa 1 pe poziția 2. El se va propaga pîna la finalul vectorului s[]. Dar noi vrem ca începînd cu poziția 14 acel 1 să nu se mai propage. Deoarece nu putem acest lucru, vom face altceva: vom plasa valoarea -1 pe poziția 14. Ea se va propaga, și ea, pînă la final de vector s[], adunîndu-se la fiecare element o singură dată. Ea va anula propagarea elementului 1 plasat la poziția 2.

Similar, dacă dorim să aplicăm intervalul [6, 9] vom plasa 1 pe poziția 6 în v[] și -1 pe poziția 10.

După ce am plasat toate intervalele, vom calcula în s[] sumele parțiale ale lui v[]. Vectorul s[] este răspunsul, valorile finale cerute.

În fapt, nu avem nevoie de doi vectori. Putem suprascrie vectorul v[], deoarece nu mai avem nevoie de elementele marker.

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.

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

Avantaje: cod mai rapid.
Schimbă complexitatea algoritmului: da.
Timp precalculare: O(k) - k numărul de intervale.
Memorie extra folosită: O(MAXCOORD). Poate fi prohibitiv dacă MAXCOORD este mare.

Sume de dreptunghiuri

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. De data aceasta vom folosi o matrice de sume parțiale, ce necesită O(n²) memorie.

Nu voi detalia algoritmul, iată partea de plasare a unui dreptunghi (l1, c1) -> (l2, c2). Desenul arată punctele unde se adună/scade 1:

Această metodă 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 1D, pe vector, folosind doar O(n) memorie, ca la problema flori1.

Exemple de probleme cu precalculare

paisprezece: necesită un vector ce păstrează numere prime, ciurul lui Eratostene.
intervale: ciurului lui Eratostene, sume parţiale.
reginald, o optimizare a problemei anterioare.
puncte1: o rezolvare posibilă folosește precalcularea sumelor parţiale ale unei matrice
extraterestri precalculare vector sume prefixe parțiale (a.k.a. șmenul lui Mars)
extraterestri1 Mars + normalizare coordonate
flori precalculare matrice sume prefixe parţiale (a.k.a. şmenul lui Mars 2D)
flori1 exemplu de problemă nerezolvabilă cu precalculare 2D din lipsă de memorie

Concluzii

Precalcularea foloseşte atunci cînd avem de răspuns la mai multe întrebări costisitoare. Aceste întrebări pot fi explicite, cerute de enunţ, sau implicite, decurgînd din metoda de rezolvare.
Precalcularea poate folosi şi atunci cînd numărul de întrebări este mult mai mare decît numărul de răspunsuri posibile, caz în care putem precalcula toate răspunsurile într-un tabel înainte de a răspunde la întrebări. Această precalculare seamănă cu memoizarea. Diferența constă în faptul că precalcularea este executată explicit înainte de calcul, pe cînd memoizarea ține minte valori calculate în timpul calculului.
Precalcularea foloseşte o structură de date adiţională şi memorie suplimentară. Uneori putem economisi memorie folosindu-ne chiar de structura de date iniţială.

Discuții probleme tema opțională

Următoarele observații s-ar putea să vă ajute:

Cine rezolvă problema reginald automat rezolvă problema intervale (cu schimbarea numelor fișierelor de intrare/ieșire, desigur).
Problema flori1 este foarte grea ca structură de date. Veți avea nevoie de un vector de liste, cîte o listă pentru fiecare linie. Pe o linie veți memora dreptunghiuri care încep pe acea linie, precum și dreptunghiuri care se termină pe linia anterioară. Ce anume aveți nevoie să memorați într-o celulă? Trei valori, coloana de început a segmentului, cea de final, și valoarea de adăugat. Apoi veți "plimba" de sus în jos vectorul de markeri (v[] din varianta 1D a lui Mars). El se va actualiza cu perechile din lista liniei curente. Pe baza lui v[] calculați s[] într-un vector diferit, pentru a nu îl influența pe v[], de care aveți nevoie la linia următoare. În final veți vedea că nici nu aveți nevoie de s[] deoarece vi se cere să calculați un maxim.

Temă

Tema 5 clasa a 7^a

intervale dată pregătire OJI 2013 clasa a 9^a la Vianu
patrate1 dată la cercul de informatică Vianu 2013 clasa a 6^a rezolvată în cel mult O(n³)!
extraterestri dată la OJI 2012 clasa a 8^a

Tema 5 opțională clasa a 7^a

reginald dată la pregătire olimpiadă 2013 clasele 7/8/9/10 la Vianu
flori1 dată la pregătire baraj gimnaziu 2013 la Vianu

Opțional, gîndiți-vă la întrebările din curs - calcul număr biți 1 în reprezentarea binară a unui întreg:

Se poate mai bine decît O(nr. biţi) fără memorie suplimentară (adică O(1) memorie suplimentară)?
Putem adapta metoda precalculării și la numere xMax mari, gen numere întregi pe int?

Rezolvări aici [2]

Clasa a VII-a lecția 5 - 10 oct 2019

Contents

Tema - rezolvări

Onigim

Comentarii generale

Macheta

Comentarii generale

Comentarii individuale

Prima grupă

A doua grupă

Concurs - rezolvări

Criptic

Lecție

Precalculare

Santinela în căutarea liniară

Bordarea

Precalculare tip caracter

Precalculare valori cifre în baze de numerație

Ciurul lui Eratostene

Suma între i şi j

Suma între (l1, c1) şi (l2, c2)

Numărul de biţi 1 într-un întreg

Sume de intervale

Exemplu

Îmbunătățire

Sume de dreptunghiuri

Exemple de probleme cu precalculare

Concluzii

Discuții probleme tema opțională

Temă

Navigation menu

Page actions

Page actions

Personal tools

Navigation

Search

Tools