Radix Sort e stabil: la fiecare pas cifra pe acea poziție e nedescrescătoare de-a lungul permutării, iar la egalitate se păstrează ordinea pasului precedent. Deci cifra crește strict exact unde ordinea s-a inversat; reconstruim cifrele, iar dacă vreuna atinge B, răspundem -1.
Vezi enunțul oficialÎncearcă întâi singur! Indiciile elimină din satisfacția rezolvării.
Nu ni se dau cifrele șirului, ci doar ordinea elementelor după fiecare pas al sortării. Cheia e că Radix Sort (LSD) e o sortare stabilă: la pasul rearanjează elementele după cifra de pe poziția , iar când două elemente au aceeași cifră le lasă în ordinea pe care o aveau înainte. Privind cum se schimbă ordinea de la un pas la altul, putem „citi” cifrele înapoi.
Conectează-te ca să marchezi problemele rezolvate.