Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2008-04-14 22:20:50.
Revizia anterioară   Revizia următoare  

 

Fişierul intrare/ieşire:scmax.in, scmax.outSursăad-hoc
AutorArhiva EducationalaAdăugată deFlorianFlorian Marcu Florian
Timp execuţie pe test0.15 secLimită de memorie36864 kbytes
Scorul tăuN/ADificultateN/A

Vezi solutiile trimise | Statistici

Subsir crescator maximal

Fie un vector a cu N elemente. Numim subsir al lui a de lungime K un vector a' = (ai1, ai2, ..., aiK) astfel incat sa avem i1 < i2 < ... < iK.

Cerinta

Sa se determine un subsir al lui a care este ordonat strict crescator si care are lungimea maxima.

Date de intrare

Fisierul de intrare scmax.in contine pe prima linie numarul N reprezentand numarul de elemente ale vectorului a . Pe cea de-a doua linie se afla N numere naturale reprezentand elementele vectorului a.

Date de iesire

In fisierul de iesire scmax.out se va afisa pe prima linie Lmax, lungimea celui mai lung subsir crescator al sirului a. Pe cea de-a doua linie se vor afla Lmax numere naturale reprezentand cel mai lung subsir crescator al vectorului a. Daca exista mai multe solutii se poate afisa oricare.

Restrictii

  • 1 ≤ N ≤ 100 000
  • 1 ≤ ai ≤ 2 000 000 000, pentru orice i de la 1 la N
  • Se acorda 50% din punctaj daca este afisata corect doar lungimea celui mai lung subsir crescator

Exemplu

scmax.inscmax.out
5
24 12 15 15 19
3
12 15 19

Indicatii de rezolvare

O prima rezolvare utilizeaza programarea dinamica. Se noteaza besti - lungimea maxima a unui subsir crescator care se termina pe pozitia i . Obtinem astfel urmatoarea relatie de recurenta: besti = 1 + max(bestj) cu 1j < i si aj < ai . Pentru a reconstrui solutia mai retinem un vector cu semnificatia prei - pozitia valorii care preceda elementul i in subsirul crescator care se termina pe pozitia i. Aceasta solutie are complexitatea O(N2) si obtine 70 de puncte. O astfel de solutie gasiti aici.
Complexitatea optima este O(N*log2N). La fiecare pas i trebuie determinata lungimea cea mai mare bestj unde 1 ≤ j < i astfel incat ajai. Pentru a afla aceasta informatie in timp optim O(log2N) se poate folosi un arbore de intervale sau un arbore indexat binar. O astfel de abordare obtine 100 de puncte si se gaseste aici. O alta idee de rezolvare ce obtine punctajul maxim, dar mai simplu de implementat si mai rapida, se gaseste aici. Ideea de rezolvare din spatele acestei solutii se gaseste in cartea lui Catalin Francu, "Psihologia concursurilor de informatica", editura L&S.

Trebuie sa te autentifici pentru a trimite solutii. Click aici

Cum se trimit solutii?

remote content