InfoAs Atlas

<- Go back View preview

Problema Subsir crescator de lungime maxima 2

Identification properties

🔒 The following are read-only properties. If you wish to change them, please create a new problem.

Name

Content ID

Hash Note: The hash is stored in the filesystem.

Content properties

Task

Un subșir al unui șir reprezintă o colecție de elemente ale șirului, nu neapărat consecutive, dar aflate în aceeași ordine ca în șirul inițial. Spre exemplu, subșiruri valide pentru `(1, 2, 5, 3, 4)` sunt `(1, 2, 3), (2, 4), (5), (5, 3, 4)`, dar subșiruri invalide sunt `(3, 2), (5, 2, 1)`, deoarece am schimbat ordinea elementelor din șirul inițial.

## Cerință

Se dă un șir cu `n` numere naturale distincte. Să se determine cel mai lung subșir de elemente din șir, cu proprietatea că elementele subșirului se află în ordine crescătoare: un _SCLM_ al șirului dat.
## Date de intrare

Programul citește de la tastatură, de pe prima linie, numărul natural `n`, iar de pe următoarea linie, `n` valori naturale separate prin câte un spațiu, reprezentând elementele șirului.
## Date de ieșire

Programul afișează pe ecran, pe prima linie, lungimea celui mai lung subșir crescător, iar pe a doua linie, indicii elementelor din șir, ordonați crescător, care formează subșirul crescător de lungime maximă.
## Restricții și precizări

* `1 ≤ n ≤ 100.000`
  * `1 ≤ elementele șirului ≤ 2.000.000.000`
  * Elementele șirului sunt indexate de la `1`
  * Orice șir de indici care formează un subșir crescător maximal este corect

Examples

Default code

Summary

Editorial

Problema subșirului crescător de lungime maximă este una clasică pentru programarea dinamică. Această soluție este una eficientă, având complexitatea de timp `O(n * log<sub>2</sub>n)`. O soluție rezonabilă și mai lizibilă se găsește pentru problema _Subsir crescator de lungime maxima_ , care este mai ușoară: https://infoas.ro/problema/subsir-crescator-de-lungime-maxima .

**Soluție.** Notăm cu `a` șirul nostru. Avem un vector `dp`, cu o semnificație mai greu de înțeles, însă care se dovedește foarte utilă în rezolvarea problemei: în subșirul crescător de lungime maximă, indicele celui de al `i`-lea element este `dp(i)`. Dacă există mai multe variante pentru al `i`-lea element (de pildă, șirul `(6, 8, 7, 9)` are soluțiile maximale `(6, 8, 9)` și `(6, 7, 9)`, unde al doilea element poate să fie `8` sau `7`), atunci se ia elementul cu valoare mai mică.

Soluția aceasta este foarte practică, deoarece atunci când găsim o valoare pentru `dp(i)`, elementul de dinainte este cu siguranță `dp(i - 1)`. Totodată, deoarece elementele ale căror indici se află în `dp` sunt crescătoare, atunci putem să optimiză programul nostru cu o căutare binară (să vedem acum cum).

Nu în ultimul rând, creăm un vector `t(i)`, care ne zice care este indicele elementului anterior lui `i` din SCLM.

Creăm o valoare `lung`, care reprezintă lungimea subșirului crescător de lungime maximă curent. Pentru început, considerăm doar primul element, cel cu indicele `1`. Așadar, `lung = 1`, iar `dp(1) = 1`.

Pentru elementele următoare (`i` începând cu `2` până la `n`), avem două cazuri:

* `a(dp(lung)) ≤ a(i)`: deoarece cel mai mare element din SCLM este mai mic decât elementul curent, înseamnă că putem să lungim SCLM cu `1`. Așadar, lungimea crește cu `1`, `dp(lung nou) = i`, iar `t(i) = dp(lung vechi)`;
  * `a(i) < a(dp(lung))`: înseamnă că elementul curent trebuie să se afle undeva în subșirul nostru crescător curent de lungime `lung`. Pentru a crește șansele de a găsi un subșir mai lung, căutăm binar cea mai mică poziție din `dp` între `1` și `lung`, pentru care `a(dp(poz)) ≥ a(i)`. Făcând acest lucru, scădem practic valoarea din subșir, crescând astfel șansele de a găsi pe viitor un subșir mai lung. Actualizăm `t(i) = dp(poz - 1)` și `dp(poz) = i`.

La final, afișăm lungimea SCLMului, adică `lung`, după care, pentru a afișa elementele din SCLM, apelăm recursiv `afis(dp(lung))` care are următoarea structură:

* dacă `x` este `0`, nu face nimic;
  * în caz contrar:
  * ->`afis(t(x))`;
  * ->afișează pe ecran `x`;

Facem acest lucru din simplul fapt că pentru fiecare indice `i` avem calculat elementul anterior în `t(i)`, iar noi trebuie să afișăm indicii crescător.

Solution

Contributor ID

Author

Tags

Problem set

Chapter ID

Published At

Admin Approved

Difficulty

License

File name	Description	Updated at	Size	Actions
hash.txt	Special file The hash of all the content of a problem. Autogenerated.	10 January 2025 21:26	64 B	View
manifest.json	Special file Metadata for the problem. Autogenerated.	10 January 2025 21:26	2 KB	View
0-subsir-crescator-de-lungime-maxima-2.in	/ 100	10 January 2025 21:26	11 B	View
0-subsir-crescator-de-lungime-maxima-2.ok	/ 100	10 January 2025 21:26	7 B	View
1-subsir-crescator-de-lungime-maxima-2.in	/ 100	10 January 2025 21:26	3 KB	View
1-subsir-crescator-de-lungime-maxima-2.ok	/ 100	10 January 2025 21:26	231 B	View
2-subsir-crescator-de-lungime-maxima-2.in	/ 100	10 January 2025 21:26	4 KB	View
2-subsir-crescator-de-lungime-maxima-2.ok	/ 100	10 January 2025 21:26	390 B	View
3-subsir-crescator-de-lungime-maxima-2.in	/ 100	10 January 2025 21:26	8 KB	View
3-subsir-crescator-de-lungime-maxima-2.ok	/ 100	10 January 2025 21:26	273 B	View
4-subsir-crescator-de-lungime-maxima-2.in	/ 100	10 January 2025 21:26	47 KB	View
4-subsir-crescator-de-lungime-maxima-2.ok	/ 100	10 January 2025 21:26	36 B	View
5-subsir-crescator-de-lungime-maxima-2.in	/ 100	10 January 2025 21:26	184 KB	View
5-subsir-crescator-de-lungime-maxima-2.ok	/ 100	10 January 2025 21:26	502 B	View
6-subsir-crescator-de-lungime-maxima-2.in	/ 100	10 January 2025 21:26	208 KB	View
6-subsir-crescator-de-lungime-maxima-2.ok	/ 100	10 January 2025 21:26	564 B	View
7-subsir-crescator-de-lungime-maxima-2.in	/ 100	10 January 2025 21:26	396 KB	View
7-subsir-crescator-de-lungime-maxima-2.ok	/ 100	10 January 2025 21:26	290 B	View
8-subsir-crescator-de-lungime-maxima-2.in	/ 100	10 January 2025 21:26	445 KB	View
8-subsir-crescator-de-lungime-maxima-2.ok	/ 100	10 January 2025 21:26	252 B	View
9-subsir-crescator-de-lungime-maxima-2.in	/ 100	10 January 2025 21:26	575 KB	View
9-subsir-crescator-de-lungime-maxima-2.ok	/ 100	10 January 2025 21:26	494 B	View
In total: 22 files 1 MB

View files grouped by their test cases.

Index	Input file	Output file	Score	Visibility

Enzo Judge

Offline

Server is offline.

Fernando Judge

Offline

Server is offline.

Main Instance

Offline

Server is offline.

Judge count: 2 Instance count: 1

Online judges will be synchronised with all the files. The previous version(s) of the problem will be overwritten.

Problema Subsir crescator de lungime maxima 2

Identification properties

Content properties

Technical properties

Delete all files