scmax

Scmax

== include(page="template/taskheader" task_id="scmax") ==

h2. astronomy: ai o mica scapare in eval, while(!feof(fout)) { fscanf(fout,"%d",&a[++pp]); }, daca el are afisate mai multe numere in fisierul de iesire poate sa dea SIGKILL la eval, fiindca "a" are dimensiune doar 1004.
 
Fie un vector $a$ cu $N$ elemente. Numim subir al lui $a$ de lungime $K$, un vector $a'$ =  ( $a{~i1~}$, $a{~i2~}$ , ... , $a{~iK~}$ ) cu $i{~1~}$ < {$i{~2~}$} < ... < {$i{~K~}$} .

Fie un vector $a$ cu $N$ elemente. Numim subsir al lui $a$ de lungime $K$ un vector $a'$ =  ({$a{~i{~1~}~}$}, $a{~i{~2~}~}$, ..., {$a{~i{~K~}~}$}) astfel incat sa avem $i{~1~}$ < {$i{~2~}$} < ... < {$i{~K~}$}.

h2. Cerinta

h2. 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$.

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

h2. Date de iesire

In fisierul de iesire $scmax.out$ se va afisa pe prima linie $Lmax$, avand semnificatia ca cel mai lung subsir crescator al sirului $a$ are lungimea $Lmax$. Pe cea de-a doua linie se vor afla $Lmax$ numere naturale reprezentand cel mai lung subsir crescator al vectorului $a$.

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.

h2. Restrictii

* $1 ≤ $N$ ≤ 1000.$
* $1 ≤ $a{~i~}$ ≤ 50000 , pentru orice $i$ = 1, $N$ .$
* $Daca exista mai multe solutii se poate afisa oricare.$
* $Se acorda 50% din punctaj daca este afisata corect doar lungimea celui mai lung subsir crescator.$

* $1 ≤ N ≤ 100 000$
* {$1 ≤ a{~i~} ≤ 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

h2. Exemplu

  12 15 19
|

h3. Explicatie

h2. Indicatii de rezolvare
 
O prima rezolvare utilizeaza programarea dinamica. Se noteaza $best{~i~}$ - lungimea maxima a unui subsir crescator care se termina pe pozitia $i$ . Obtinem astfel urmatoarea relatie de recurenta: $best{~i~}$ = 1 + {$max(best{~j~})$} cu $1$ &le; $j$ < $i$ si $a{~j~}$ < $a{~i~}$ . Pentru a reconstrui solutia mai retinem un vector cu semnificatia $pre{~i~}$ - pozitia valorii care preceda elementul $i$ in subsirul crescator care se termina pe pozitia $i$. Aceasta solutie are complexitatea $O(N^2^)$ si obtine 70 de puncte. O astfel de solutie gasiti 'aici':job_detail/146353?action=view-source.
Complexitatea optima este {$O(N*log{~2~}N)$}. La fiecare pas $i$ trebuie determinata lungimea cea mai mare $best{~j~}$ unde {$1 &le; j < i$} astfel incat {$a{~j~}$} &le; {$a{~i~}$}. Pentru a afla aceasta informatie in timp optim {$O(log{~2~}N)$} se poate folosi un arbore de intervale sau un arbore indexat binar. O astfel de abordare obtine 100 de puncte si se gaseste 'aici':job_detail/146356?action=view-source. O alta idee de rezolvare ce obtine punctajul maxim, dar mai simplu de implementat si mai rapida, se gaseste 'aici':job_detail/146355?action=view-source. Ideea de rezolvare din spatele acestei solutii se gaseste in cartea lui Catalin Francu, "Psihologia concursurilor de informatica", editura L&S.
 
Printre problemele care folosesc ideile de mai sus se numara:
 
* 'Euro 2':problema/euro2
* 'Interclasare':problema/interclasare
* 'Cuburi3':problema/cuburi3
* 'Subsiruri':problema/subsiruri
* 'Subsir2':problema/subsir2

*Feedback(Cosmin):* Nu punem si solutia in O(n log n)?
*Raspuns(Florian):* Din pacate nu stiu solutia in NlogN. Dar daca imi spui ideea cred ca ma prind. Si vedem ce putem face.

== include(page="template/taskfooter" task_id="scmax") ==

2985