Clasele 9-10 lecția 7 - 29 oct 2014

From Algopedia
Jump to: navigation, search

Algoritmi pe vectori și matrice (încheiere)

Din lecția trecută ne-au rămas de discutat trei probleme:

  • Dreptunghiul maxim de sub histogramă
  • Dreptunghiul gol de arie maximă
  • Range Minimum Query

Probleme de la OJI din anii trecuți

Iată și o arhivă cu enunțurile și soluțiile comisiei.

OJI 2014, clasa a 9-a: Cool

Infoarena: Cool

Cerința 1

Trebuie să decidem dacă un vector de K numere conține valori K consecutive distincte (nu neapărat sortate). Putem face aceasta cu un vector caracteristic, întrucât valorile elementelor sunt mici:

  • bifăm toate elementele într-un vector caracteristic;
  • dacă, la orice moment, bifăm un element care era deja bifat, răspunsul este „nu”;
  • reținem minimul și maximul întâlnit;
  • la final, răspunsul este „da” dacă și numai dacă max - min = K - 1.

Cerința 2

Trebuie să aflăm lungimea maximă a unei subsecvențe cool și numărul de subsecvențe cool.

Observăm că limitele permit o abordare în O(n^{2}). Pe de altă parte, vectorul are O(n^{2}) subsecvențe. Putem să testăm fiecare subsecvență în O(1)? Putem, dacă aplicăm un truc des întâlnit în cazul subsecvențelor: deducem răspunsul pentru subsecvența (i...j) extinzând în O(1) răspunsul pentru subsecvența (i...j-1). Așadar:

  • Fixăm i (el va itera de la 1 la n);
  • Subsecvența (i...i) este evident cool, de lungime 1.
  • Pentru a trece de la o subsecvență (i...j-1) la (i...j),
    • Bifăm v[j] în vectorul de subsecvențe.
    • Dacă v[j] era deja bifat, putem trece la următorul i, întrucât orice secvență pentru j-uri mai mari va conține duplicate.
    • Menținem minimul și maximul văzute de la i încoace.
    • Ori de câte ori max - min = j - i, subsecvența (i...j) este cool.

Tema de astăzi vă cere să rezolvați ambele cerințe pentru numere arbitrar de mari.

OJI 2014, clasa a 9-a: Pseudobil

Matricea originală
Matricea rotită. Sursa: soluția originală a comisiei

Campion: Pseudobil

Cerința 1

Cerința 1 aproape că nu merită menționată. Trebuie doar să calculăm suma

1+3+5+...+(D-3)+(D-1)+(D-3)+...+5+3+1={\frac  {D^{2}}{2}}-D+1

Cerința 2

Cerința 2 este să răspundem în timp rapid la m întrebări de forma: dându-se un romb cu latura K, amplasat la x y, câte bile conține el?

Într-o formă sau alta, va trebui să precalculăm niște informații, ca să putem răspunde la fiecare interogare în O(1). Noi știm să precalculăm date referitoare la dreptunghiuri, dar nu și la romburi. Soluția comisiei prezintă două variante interesante. Insistăm pe una dintre ele: rotirea cu 45° a matricei (vezi imaginile alăturate). Dacă facem această rotire, transformăm interogările de formă romboidală în întrebări de formă dreptunghiulară.

Cum facem rotirea cât mai ușor? Avem nevoie de două operații:

  • pentru rotire, să convertim coordonatele din matricea originală în coordonate din matricea rotită, ca să știm unde transcriem diversele valori;
  • pentru interogări, să convertim colțurile rombului în coordonate din matricea rotită.

Este elegant să ne scriem o funcție care primește două coordonate lin și col și le modifică. Presupunem că liniile și coloanele sunt numerotate de la zero (indiferent ce spune enunțul problemei, nu irosim memorie!). Observăm că:

  • în matricea rotită, elementele de pe aceeași linie au suma coordonatelor constantă;
  • în matricea rotită, elementele de pe aceeași coloană au diferența coordonatelor constantă.
  void converteste(int lin1, int col1, int *lin2, int *col2) {
    *lin2 = lin1 + col1;
    *col2 = col1 - lin1 + (n - 1);
  }

  // Rotește matricea a și scrie rezultatul în matricea b.
  // Presupune că matricea b este deja inițializată cu zerouri.
  void roteste() {
    int l, c;
    for (int i = 0; i < n; i++) {
      for (int j = 0; j < n; j++) {
        converteste(i, j, &l, &c);
        b[l][c] = a[i][j];
      }
  }

OJI 2014, clasa a 10-a: Ferma

Cerința 1

Ni se cere să căutăm parcela conexă de arie maximă. Desigur, este suficient să rulăm un algoritm flood fill din fiecare celulă (încă netraversată) a matricei. Limita stivei este maxim 10 MB, iar numărul de niveluri este maxim 160.000, deci memoria permisă pe fiecare nivel este de 60 de octeți (arhisuficientă).

Cerința 2

Pe măsură ce rulăm algoritmul de flood fill, putem calcula, pentru fiecare celulă, aria zonei din care face parte. Apoi, pentru fiecare celulă, calculăm aria maximă pe care o putem obține dacă îi schimbăm culoarea într-una din culorile vecinilor ei.

Atenție la cazuri speciale:

  • O celulă poate uni nu doar 2 parcele, ci și 3 sau 4.
  • O celulă poate „uni” și o singură parcelă, dacă are un singur vecin de acea culoare. Astfel tratăm cazul când aria maximă se obține nu prin unirea mai multor parcele, ci prin alipirea unei celule la o parcelă existentă.

OJI 2014, clasa a 10-a: Triunghi

Cerința 1

Ni se cere să generăm un șir de k numere anti-triunghi, pornind de la un minim dat. Observăm că, dacă considerăm elementele sortate nedescrescător, atunci v[k + 2] ≥ v[k + 1] + v[k], deoarece altfel cele trei numere pot forma un triunghi.

Șirul care crește cel mai încet se obține la limită, când înlocuim inegalitatea cu egalitate și obținem exact șirul lui Fibonacci, amplificat cu min.

Problema este un pic nedreaptă deoarece pune limitele n < k ≤ 46 și valorile șirului ≤ 2.000.000.000. Ea lasă în seama voastră să observați că al 46-lea termen Fibonacci este și ultimul mai mic decât 2.000.000.000. Această observație este importantă, deoarece alte șiruri (de exemplu 1 2 4 8 16 ...) vor crește prea repede și vor depăși limita de 2.000.000.000.

Cerința 2

Și această cerință este nedreaptă, deoarece vă cere să vă bazați pe intuiție și să acceptați niște proprietăți neevidente ale numerelor.

Ni se cere să extindem șirul dat, de n numere anti-triunghi, până la k numere anti-triunghi. Din nou, vom căuta un șir care crește cât mai lent, pentru a ne încadra în 2.000.000.000.

Dorim să pornim cu valorile 1 1. Face excepție cazul în care există numere repetate în șirul inițial, deoarece (1 x x) poate forma un triunghi. De fapt, dacă există numere repetate, există o singură pereche, care sunt și valorile minime din șir (demonstrați de ce e așa!).

Apoi generăm un șir „aproape Fibonacci”, încorporând și elementele impuse printr-un fel de interclasare. Mai exact, dacă ultimii doi termeni generați au fost x și y și dacă am încorporat până acum primele p numere impuse, atunci:

  • dacă y, x + y și a[p] formează un triunghi, atunci următorul termen generat este a[p];
  • altfel următorul termen generat este x + y.

De ce este așa? Dorim să înghesuim cât mai multe numere anti-triunghi înainte de a[p]. Dacă x + y ar crea un triunghi, l-ar crea cu y (cel mai mare dintre numerele deja generate) și cu a[p] (cel mai mic dintre numerele încă neîncorporate). Dacă x + y nu creează un triunghi, adică y + (x + y)a[p], atunci cu atât mai mult relația se va menține dacă îl micșorăm pe y sau îl mărim pe a[p].

Temă