Replace the Numbers

Dzisiaj chciałem wam opowiedzieć o tym jak przekombinowałem rozwiązanie zadania Replace the Numbers z treningów codeforce. Zadanie należało do tych prostszych. Mieliśmy tablicę na której mogliśmy wykonywać dwa rodzaje operacji:

1. Wstawienie elementu v na koniec tablicy
2. Zamiana wszystkich wystąpień elementu a na element b (będę oznaczał jako a -> b)

Mając daną listę instrukcji należało wypisać jak tablica będzie wyglądać po wykonaniu wszystkich operacji. Oczekiwana złożoność to coś pomiędzy O(n) a O(n lg n).

Zacznijmy od podejścia brutalnego. Możemy symulować wykonanie każdej z instrukcji. Wstawiać elementy na koniec tablicy oraz przechodzić przez całą tablicę i zamieniać elementy z a na b. Oczywiście takie podejście zajmuje czas kwadratowy w najgorszym przypadku.

Pierwsze o czym pomyślałem to podejście leniwe. Wstawiajmy elementy, tak… ale nie zamieniajmy ich od razu jak przyjdzie instrukcja typu 2, tylko zamieńmy je na końcu jak będziemy wszystko wypisywać. Czyli podczas wypisywania muszę umieć znaleźć instrukcję, która daną wartość zamieniła. Pierwszy mój pomysł to pamiętać znaczniki czasowe: kiedy dany element przyszedł oraz kiedy przyszła dana instrukcja zamiany. Mając te informacje mogę instrukcje a->b posortować najpierw po a a następnie po znacznikach czasowych. To umożliwi mi wyszukiwanie binarne, którą instrukcję muszę zastosować do danego elementu (jeśli już zacząłeś się gubić, to się nie przejmuj i czytaj dalej). Pojawia się jednak problem. Bo po instrukcji a->b mogła przyjść b->c. Więc finalnie nasz element a musi zostać zamieniony na c. Nie możemy powtórzyć wyszukiwania na co zostało zamienione b, bo to prowadzi do rozwiązania kwadratowego. Najlepiej by było — pomyślałem sobie — żebym od razu mógł wiedzieć że a należy zamienić na c. Najprostszym rozwiązaniem byłoby, gdybym gdy tylko przyszła instukcja b->c zamienił wszystkie instrukcje wcześniejsze postaci x->b na x->c. No i tak, tak… to prowadzi do rozwiązania kwadratowego. To na co wpadłem… to utworzyć graf. Połączmy krawędziami skierowanymi wszystkie instrukcje x->b z instrukcją b->c (oczywiście, instrukcja x->b musiała przyjść przed b->c oraz między nimi nie mogło być innej instrukcji postaci b->y). W ten sposób powstanie nam DAG na którym możemy wykonać programowanie dynamiczne (programowanie dynamiczne robi się w ten sposób, że najpierw sortuje się topologicznie graf, a następnie idzie od prawej strony do lewej). Jeśli dany wierzchołek x->y nie ma następnika to jego wynikiem jest y. Jeśli ma następnik to jego wynikiem jest wynik następnika.

Znaczniki czasowe, DAGi, sortowanie topologiczne, programowanie dynamiczne i na końcu wyszukiwanie binarne. Całość działała w czasie O(n lg n). Udało mi się zaimplementować to na treningu i otrzymać ACC.

Jakiś czas później jednak, do głowy wpadło mi inne rozwiązanie (co jest o tyle ciekawe, że nie myślałem o tym zadaniu w sposób świadomy). Popatrzmy na inny, “prostszy” problem: Mamy dwa rodzaje instrukcji:

1. Wstaw element v na początek tablicy
2. Jeśli w przyszłości spotkasz element a to zamień go na ten element, na które zamieniasz element b.

Drugi punkt trochę skomplikowałem, może przykład pomoże. Jeśli przyszła instukcja b->c a później a->b to od teraz wszystkie elementy a jakie przyjdą w przyszłości zamieniamy na c (bo zamieniamy je na elementy na które zamieniamy elementy b, a elementy b zamieniamy na elementy c).

Napisałem, że zadanie jest prostsze, bo teraz przechodzi prosta symulacja. Tworzymy tablice zamien i poczatkowo ustawiamy ją jako:

zamien[i] = i

Gdy przyjdzie instrukcja a->b wykonujemy:

zamien[a] = zamien[b]

A gdy trzeba wstawić element v to po prostu wstawiamy element zamien[v]. Ponieważ autor zadania jest śmieszkiem i kazał nam wstawiać na początek tablicy… możemy po prostu wstawiać elementy na koniec, a następnie tablicę obrócić.

Napisałem, że zadanie jest prostsze w cudzysłowiu… bo to jest to samo zadanie… tylko instrukcje przyszły w odwrotnej kolejności.

Wniosek z historii jest taki, że chociaż nie zmieniłbym nic na zawodach, bo zadanie rozwiązałem, a zastanawianie się nad prostszym rozwiązaniem na zawodach nic nie daje… to warto czasami przemyśleć swoje zadania po zawodach. Albo nawet przeczytać rozwiązania do zadań które i tak się zrobiło. Może w przyszłości na zawodach wpadniecie na prostsze rozwiązania.