Informatyka MIMUW

Sprowadź dowód do jak najmniejszej liczby przypadków, np. możesz tylko rozważać liczby o niemalejących ciagach czterech cyfr.

Dla każdego nowego niezerowego elementu x, który jest aktualnie na pozycji j-tej, jeśli wstawiamy x na pozycję i-tą, to w tym momencie na pozycji (i-1)-szej jest pewien jego poprzednik y w najdłuższym ciągu malejącym kończącym się na pozycji j-tej. To znaczy w szczególności, że y>x, oraz że y jest na pewnej pozycji mniejszej od j.

W każdym optymalnym pakowaniu można je tak zmienić, że najmniejszy element będzie razem z maksymalnym, z którym się mieści do tego samego pudełka

Relacja mniejszości dla ciągów niech będzie relacją mniejszości leksykograficznej.

Rotacją ciągu \( u=u[1..n] \) jest każdy ciąg postaci \( u^{(k)}\ =\ u[k+1.. n]u[1.. k] \). (W szczególności \( u^{(0)}=u^{(n)}=u) \).

Zdefiniujmy:

\( D(u)=\{k:1\leq k\leq n \) oraz \( u^{(k)}>w^{(j)} \) dla pewnego \( j\} \),
\( D(w)=\{k:1\leq k\leq n \) oraz \( w^{(k)}>u^{(j)} \) dla pewnego \( j\} \).

Skorzystamy z prostego faktu:

Jeśli \( D(u)=[1.. n] \) lub \( D(w)=[1.. n] \), to \( u,w \) nie są równoważne. Poprawność algorytmu wynika teraz z tego, że po każdej głównej iteracji zachodzi niezmiennik:

\( D(w)\supseteq [1.. i] \)\ oraz \ \( D(u)\supseteq [1.. j] \).

Dla ciągów postaci \( 1^*201,\ 1^*20 \) o tej samej długości.