Zaginanie papieru (omówienie)

02.01.2012

Zadanie można było rozwiązać na wiele sposobów. W niniejszym omówieniu przedstawione będzie bardzo proste rozwiązanie osiągające złożoność czasową $O(n^{3})$ lub $O(n^{4})$ (w zależności od szczegółów implementacyjnych).

Zauważmy, że zagięcie papieru odpowiada "usunięciu" zaginanego fragmentu. Zauważmy też, że warunek o zaginaniu z lewej na prawą stronę jest bez znaczenia.

Nasze rozwiązanie będzie bazowało na obserwacji (korzystającej z powyższych stwierdzeń), że najkrótszy końcowy fragment paska jaki można uzyskać przez zaginanie to pewne podsłowo wejściowego słowa zerojedynkowego.

Zatem dla każdego podsłowa (przechodząc je od najkrótszych do najdłuższych) sprawdzamy, do jak małego podsłowa możemy je zagiąć. Rozwiązaniem będzie wynik dla całego paska. Niech słowo na wejściu to $w = w_{0}w_{1} \cdots w_{n-1}$ . Niech $D(i,j)$ oznacza taką wartość dla $w_{i}w_{i+1} \cdots w_{j}$ . Interesuje nas policzenie $D(0,n-1)$ .

Zauważamy szybko, że $D(i,j)$ to minimum z wartości:

1. $j-i+1$

2. $D(i,k)$ dla takich $k \geq (j-i+1)/2$ , że podsłowo $w_{k+1} \cdots w_{j}$ można nałożyć na słowo $w_{i} \cdots w_{k}$ .

3. $D(k,j)$ dla takich $k \leq (j-i+1)/2$ , że podsłowo $w_{i} \cdots w_{k-1}$ można nałożyć na słowo $w_{k+1} \cdots w_{j}$ .

Aby przejrzeć możliwe wartości $k$ dla wszystkich podsłów potrzebujemy czasu rzędu $O(n^{3})$ . Jeżeli umiemiemy szybko (tj. w sumie w czasie rzędu $O(n^{3})$ ) odpowiadać na pytania o możliwość nałożenia słów na siebie (można to uczynić np. w czasie $O(n)$ algorytmem Manachera albo w czasie $O(n^{3})$ za pomocą KMP) to złożoność całego algorytmu pozostanie $O(n^3)$ . Jeśli zdecydujemy się na brutalne porównania dla każdego podsłowa, okaże się, że złożoność osiągnie $O(n^4)$ .

Wersja do wydruku

Działy

Zaginanie papieru (omówienie)

Nagrody:

Organizatorzy: