Psihologia concursurilor de informatică/6 Probleme de concurs 3

From Algopedia
Revision as of 15:23, 9 March 2018 by Cata (talk | contribs) (Created page with "⇦ înapoi la Psihologia concursurilor de informatică = Capitolul VI: Probleme de concurs (13-18) = == Problema 13 == Probabil că orice elev care are cât de cât ex...")

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

⇦ înapoi la Psihologia concursurilor de informatică

Capitolul VI: Probleme de concurs (13-18)

Problema 13

Probabil că orice elev care are cât de cât experiență în programare a auzit despre problema celui mai lung subșir crescător. Când este prezentată la concurs, problema e „învelită” sub diverse forme. Aici o vom formaliza din punct de vedere matematic.

ENUNȚ: Se dă un vector cu N elemente numere întregi. Se cere să se determine cel mai lung subșir crescător.

Intrarea: Fișierul de tip text INPUT.TXT conține pe prima linie numărul N de elemente din vector (N≤10.000), iar pe fiecare din următoarele N linii se află câte un element al vectorului.

Ieșirea: În fișierul de tip text OUTPUT.TXT se vor lista pe prima linie lungimea L a celui mai lung subșir crescător, iar pe următoarele L linii subșirul în sine. Dacă există mai multe soluții, se va tipări una singură.

Exemplu:

INPUT.TXT OUTPUT.TXT
6
2
5
7
3
4
1
3
2
3
4

Timp de implementare: 45 minute.

Timp de rulare: 5 secunde.

Complexitate cerută: O(N\log N).


REZOLVARE: Începem prin a lămuri diferența dintre noțiunile de „subșir” și „subsecvență”. Fie V[1], V[2], ..., V[N], vectorul citit. Prin subșir de lungime L al vectorului V se înțelege o succesiune nu neapărat continuă de elemente V[K_{1}],V[K_{2}],\dots ,V[K_{L}], unde K_{1}<K_{2}<...<K_{L}. Prin subsecvență de lungime L a vectorului, începând de la poziția K, se înțelege succesiunea continuă de elemente V[K], V[K+1], ..., V[K+L-1].

Rezolvarea prin metoda programării dinamice este în general cunoscută și nu vom insista asupra ei. Probabil că aflarea celui mai lung subșir crescător este punctul de plecare al oricărui elev în învățarea programării dinamice. Totuși, această metodă de rezolvare are complexitatea O(N^{2}). În continuare prezentăm o metodă mai puțin cunoscută și ceva mai dificil de implementat, dar mult mai eficientă. Ea are complexitatea O(N\log N). Vom enunța principiul de rezolvare, urmat de o schiță a demonstrației de corectitudine.

Fie V vectorul citit. Se parcurge vectorul de la stânga la dreapta și se construiesc în paralel doi vectori P și Q, astfel: inițial vectorul Q este vid. Se ia fiecare element din V și se suprascrie peste cel mai mic element din Q care este strict mai mare ca el. Dacă nu există un asemenea element în Q, cu alte cuvinte dacă elementul analizat din V este mai mare ca toate elementele din Q, atunci el este adăugat la sfârșitul vectorului Q. Concomitent, se notează în vectorul P poziția pe care a fost adăugat în vectorul Q elementul din V. Iată cum se construiesc vectorii P și Q pentru exemplul din enunț:

Psycho-fig68.png

Lungimea L la care ajunge vectorul Q la sfârșitul acestei prelucrări este tocmai lungimea celui mai lung subșir crescător al vectorului V. Pentru a afla exact și care sunt elementele subșirului crescător se procedează astfel: se caută ultima apariție în vectorul P a valorii L. Să spunem că ea este găsită pe poziția K_{L}. Se caută apoi ultima apariție în vectorul P a valorii L-1, anterior poziției K_{L}. Ea va fi pe poziția K_{{L-1}}<K_{{L}}. Analog se caută în vectorul P valorile L-2, L-3, ..., 2, 1. Subșirul crescător este S=(V[K_{1}],V[K2],\dots ,V[K_{L}]).

În figura de mai sus au fost hașurate elementele respective găsite în vectorul P. Vectorul Q are la sfârșit lungimea L=3, deci cel mai lung subșir crescător are trei elemente. Se caută în vectorul P cifrele 3, 2 și 1 și se găsesc pe pozițiile K_{1}=1, K_{2}=4 și K_{3}=5, ceea ce înseamnă că cel mai lung subșir crescător este (2, 3, 4).

Demonstrația (care, fără a pierde din corectitudine, face apel la intuiție...) folosește aceleași notații de mai sus și are următoarele etape:

1. Vectorul Q este în permanență sortat crescător.

Demonstrația acestei afirmații se face prin inducție. După primul pas (inserarea elementului V[1]), vectorul Q are un singur element și este bineînțeles ordonat. Trebuie acum arătat că dacă vectorul Q este sortat după inserarea elementului V[i-1], el rămâne sortat și după inserarea lui V[i]. Într-adevăr, pentru elementul V[i] există două variante:

  • V[i] este mai mare decât toate elementele lui Q, caz în care este adăugat la sfârșitul lui Q, care rămâne sortat;
  • Există t>1 astfel încât Q[t-1]≤V[i]<Q[t], caz în care V[i] se suprascrie peste Q[t]. Dar Q[t]≤ Q[t+1] ⇒ Q[t-1]≤V[i]<Q[t+1] și vectorul Q rămâne sortat.

Această deducție ne va fi utilă în calculul complexității algoritmului.

2. Odată ce au fost scrise pentru prima oară, elementele vectorului Q nu mai pot decât să scadă sau să rămână constante. Ele nu pot crește niciodată.

Afirmația este evidentă, decurgând din modul de construcție a lui Q.

3. Elementele din vectorul V de la poziția K_{{i-1}}+1 la poziția K_{{i}}-1 sunt fie mai mici decât V[K_{{i-1}}], fie mai mari decât V[K_{i}].

Acest lucru este natural, deoarece dacă ar exista K_{{i-1}}<X<K_{i} astfel încât V[K_{{i-1}}]\leq V[X]\leq V[K_{i}], atunci șirul S ar putea fi extins cu elementul V[X], deci nu ar fi subșir maximal, contradicție.

4. Toate elementele care urmează în V după V[K_{L}] sunt mai mici decât V[K_{L}].

Dacă ar exista X>K_{L} astfel încât V[X]\geq V[K_{L}], atunci S ar putea fi extins la dreapta cu V[X], contradicție.

5. Elementul V[K_{1}] este suprascris peste poziția Q[1].

Demonstrația este imediată: Dacă elementul V[K_{1}] este inserat în Q pe o poziție t>1, rezultă că, în momentul tratării lui V[K_{1}], pe poziția t-1 în vectorul Q exista deja un număr X<V[K_{1}]. Aceasta înseamnă că S poate fi prelungit la stânga cu X, deci S nu este un subșir crescător maxim, contradicție.

6. Orice element V[K_{i}] va fi suprascris în Q pe poziția următoare celei pe care a fost scris V[K_{{i-1}}]

Demonstrație: Să presupunem că V[K_{{i-1}}] a fost scris peste Q[t]. Înainte de a ajunge să tratăm elementul V[K_{i}], a trebuit să tratăm elementele V[K_{{i-1}}+1],V[K_{{i-1}}+2],\dots ,V[K_{{i}}-1], care, după cum s-a stabilit la punctul (3), pot fi:

  • mai mici decât V[K_{{i-1}}], caz în care ele vor fi scrise în vector pe poziții mai mici sau egale cu t, iar Q[t] va scădea, deci Q[t]\leq V[K_{{i-1}}] (conform punctului 2);
  • mai mari decât V[K_{i}], caz în care vor fi scrise în Q pe poziții mai mari decât t, așadar Q[t+1]>V[K_{i}].

Se obține lanțul de inegalități Q[t]\leq V[K_{{i-1}}]\leq V[K_{i}]\leq Q[t+1], de unde rezultă conform modului de construcție că V[K_{i}] va fi scris peste Q[t+1]. Cu aceasta, folosind și punctul (5), am demonstrat că V[K_{i}] este scris pe poziția Q[i], ∀i=1, 2, ..., L. După tratarea primelor K_{L} elemente din V, vectorul Q are lungimea L. Mai rămâne de văzut ce se întâmplă cu elementele V[K_{L}+1],\dots ,V[N].

7. Elementele care îi urmează lui V[K_{L}] se scriu în Q pe poziții mai mici sau egale cu L.

Acest fapt este intuitiv dacă se ține cont de punctul (4). Deducem că la final vectorul Q are lungime L, adică aceeași cu a lui S. Modul de reconstituire a lui S din vectorul P este corect. Trebuie să avem grijă ca, atunci când căutăm în vectorul P o apariție a valorii X, să o alegem pe ultima disponibilă, altfel pot apărea erori. Spre exemplu, pentru vectorii dați în exemplu, V=(2, 5, 7, 3, 4, 1) și P=(1, 2, 3, 2, 3, 1), dacă se alege prima apariție a lui 2 (pe poziția a doua), avem subșirul S=(2, 5, 4) care nu este crescător. Dacă însă alegem ultima apariție a lui 2 (pe poziția a patra), avem subșirul crescător maximal S=(2, 3, 4).

Calculul complexității este ușor de făcut:

  • Pentru construcția vectorilor P și Q sunt necesare N inserții în vectorul Q, care este sortat; o inserție binară cere O(\log N), așadar complexitatea primei părți este O(N\log N).
  • Pentru reconstituirea lui S se face o singură parcurgere a vectorului P, deci O(N).

Complexitatea totală a algoritmului este O(N\log N).

#include <stdio.h>
#include <stdlib.h>
#define Infinity 30000
typedef int Vector[10001];

Vector V,P,Q,*S;
int N,Len; /* Len = Lungimea vectorului Q */

void ReadData(void)
{ FILE *F=fopen("input.txt","rt");
  int i;

  fscanf(F,"%d",&N);
  for(i=1;i<=N;i++) fscanf(F,"%d",&V[i]);
  fclose(F);
}

int Insert(int K,int Lo,int Hi)
{ int Mid=(Lo+Hi)/2;

  if (Lo==Hi)
    { if (Hi>Len) Q[++Len+1]=Infinity;
      Q[Lo]=K;
      return Lo;
    }
    else if (K<Q[Mid]) return Insert(K,Lo,Mid);
                     else return Insert(K,Mid+1,Hi);
}

void BuildPQ(void)
{ int i,Place;

  Len=0;Q[1]=Infinity;
  for (i=1;i<=N;i++)
    P[i]=Insert(V[i],1,Len+1);
}

void BuildS(void)
{ int i,K=N;

  S=malloc(sizeof(*S));
  for (i=Len;i;i--)
    { while (P[K]!=i) K--;
      (*S)[i]=V[K];
    }
}

void WriteSolution(void)
{ FILE *F=fopen("output.txt","wt");
  int i;

  fprintf(F,"%d\n",Len);
  for(i=1;i<=Len;i++) fprintf(F,"%d\n",(*S)[i]);

  fclose(F);
}

void main(void)
{
  ReadData();
  BuildPQ();
  BuildS();
  WriteSolution();
}

Menționăm că în sursa de mai sus se putea construi vectorul S peste vectorul Q, deoarece pentru construirea lui S nu avem nevoie decât de elementele vectorului P. În acest fel, programul ar fi avut nevoie numai de trei vectori, iar volumul total de date nu ar fi depășit un segment. Am preferat totuși varianta în care vectorul S este alocat dinamic pentru a evita confuziile.