Zadanie Odwracane Sortowanie

Question

Mam problem z takim zadaniem:

Poza brutem, nie wiem jak je zrobić. Prosiłbym o hinta.

Z góry dziękuję za pomoc i poświęcony czas.

Comments

Ciekawe zadanie, będę się przyglądał wątkowi.

Answer 1

Zadanie polega na wypisaniu na jakiej pozycji jest jedynka, w ciągu wejściowym, a następnie wydajnie odwrócić liczby, i wypisać pozycję dwójki, znowu odwrócić i napisać pozycję trójki itd...

Trudnością zadania jest znalezienie sposobu na wydajne odwracanie. Gdyby to wprost symulować byłaby złożoność O(n^2) czyli za dużo.

Mam pomysł, ale nie wiem czy nie za wolny - byłby O(n^(3/2)). Pomysł polega na tym zrobić lazy odwracanie. Przechodzimy od lewej do prawej i zapisujemy sobie w jakieś liście przedziały do odwrócenia, dla każdej liczby przetwarzamy każdy przedział który nachodzi na tę liczbę i dodajemy nowy przedział do listy. Jeżeli w liście nazbiera się więcej niż n^(1/2) przedziałów to wykonujemy te odwracania. Pojedyncze odwrócenie zajmie O(n), a wykonamy ich co najwyżej n^(1/2) razy, więc zajmie to razem O(n^(3/2)). Natomiast samo przetwarzanie wykona się n razy i maksymalnie lista ma rozmiar n^(1/2) więc to też zajmie O(n^(3/2)). Mamy więc O(n^(3/2) + n^(3/2)) = O(n^(3/2))

Comments

a nie da się tego przyśpieszyć jakoś numerując elementy od 1 do N i potem zamiast trzymać elementy 1,2,3,...N to trzymać tak jakby przedziały w sensie [1,N] i potem jak dzielimy to na kilka mniejszych przedziałów itd.?

---

@jankustosz1, to jest chyba wzorcówka, jak patrzę to zadanie ma tag sqrt