Numărul minim de tije

Ce trebuie reținut despre o tijă

Regula de plasare privește numai ultimul disc de pe fiecare tijă: o tijă ocupată este adecvată dacă discul din vârful ei are diametrul mai mare sau egal cu al discului nou. Discurile de dedesubt nu mai contează niciodată, fiindcă nu vor mai fi atinse.

Prin urmare, întreaga stare a depozitului se reține printr-un singur șir: diametrele discurilor aflate în vârful fiecărei tije, în ordinea tijelor. Pentru exemplul din enunț, cele trei tije ocupate — 14, 5, 3 pe prima, 7 pe a doua, 9 pe a treia — se reduc la șirul de vârfuri 3, 7, 9.

Observația care face algoritmul rapid

Șirul vârfurilor este strict crescător în orice moment. Se poate arăta ușor de ce se păstrează așa:

• La început șirul este vid, deci proprietatea este îndeplinită.
• Când un disc nou de diametru x se plasează pe tija i, aceasta este prima tijă adecvată, deci prima al cărei vârf este mai mare sau egal cu x. Fiind prima, vârful tijei dinaintea ei este strict mai mic decât x. După plasare, noul vârf al tijei i este chiar x, iar el rămâne mai mare decât vârful dinaintea lui și mai mic sau egal decât cel dinainte de plasare, deci mai mic decât vârful tijei următoare. Ordinea se păstrează.
• Când discul deschide o tijă nouă, înseamnă că niciun vârf existent nu este mai mare sau egal cu x, deci toate sunt strict mai mici. Adăugat la coadă, x păstrează creșterea strictă.

Fiind un șir crescător, prima tijă adecvată — adică primul vârf mai mare sau egal cu x — se găsește prin căutare binară, nu prin parcurgerea tijelor una câte una. Aici se află diferența dintre o soluție de ordinul n² și una de ordinul n·log n.

Explicarea metodei de rezolvare

Se folosește un singur tablou, t, în care t[i] reține diametrul discului aflat în vârful tijei i, și o variabilă m, numărul tijelor ocupate până în acel moment. La început m este 0.

Diametrele se citesc din fișier unul câte unul. Pentru fiecare diametru x se caută binar, în primele m poziții ale tabloului t, cea mai mică poziție i pentru care t[i] ≥ x. Căutarea reduce la jumătate, la fiecare pas, intervalul în care poate sta răspunsul: se compară x cu valoarea din mijlocul intervalului și, dacă aceasta este mai mare sau egală, răspunsul se reține și căutarea continuă în jumătatea stângă, altfel în cea dreaptă.

Dacă s-a găsit o astfel de poziție, discul se așază pe tija respectivă, iar t[i] primește valoarea x. Dacă nu s-a găsit niciuna, înseamnă că toate tijele ocupate au vârfuri mai mici decât x, deci niciuna nu este adecvată: se deschide o tijă nouă, m crește cu 1, iar t[m] primește valoarea x.

La sfârșitul citirii, m este chiar numărul de tije ocupate, adică rezultatul cerut. El nu trebuie calculat separat: numărul de tije crește exact atunci când se deschide una nouă.

Justificarea eficienței

Din punctul de vedere al timpului. Pentru fiecare dintre cele n diametre se face o căutare binară într-un tablou cu cel mult n poziții, adică cel mult log₂n comparații, urmată de o singură atribuire. Timpul total este deci de ordinul n·log n. Pentru n = 10⁵, aceasta înseamnă aproximativ 1,7 milioane de operații, care se execută instantaneu.

Soluția directă — parcurgerea tijelor una câte una, până la găsirea celei adecvate — ar face, în cazul cel mai defavorabil, până la m comparații pentru fiecare disc, deci un total de ordinul n². Pentru n = 10⁵ ar însemna de ordinul a 10¹⁰ operații, adică minute de așteptare în loc de o fracțiune de secundă. Baremul acordă cele 2 puncte pentru eficiență la o complexitate de cel mult O(n·log n), deci varianta cu parcurgere le pierde, deși dă rezultatul corect.