Omówienie zadania Dwa pionki (III etap XXV OI)

W zadaniu mamy nieskończoną kratkę i na jednym z jej punktów stoją dwa pionki. Mamy podany zestaw ruchów, który te pionki mogą wykonywać. Dla każdego pionka ten zestaw ruchów jest taki sam i każdy pionek może wykonać jakiś podzbiór ruchów ze swojego zestawu. Chcemy teraz tak wykonać ruchy pionkami, aby znalazły się one możliwie jak najdalej od siebie.

Analiza zadania

W teście przykładowym oba zestawy składają się z trzech ruchów i każdy ruch możemy reprezentować graficznie jako wektor na płaszczyźnie. Aby pionki znalazły się jak najdalej od siebie, jeden z nich możemy przesunąć wektorem \([-1,-2]\), a drugi z nich najpierw wektorem \([4,0]\), a potem wektorem \([-1,3]\). Wtedy odległość między nimi będzie równa \(\sqrt{41}\).

Widać, że na rozwiązanie składa się pewien podzbiór wektorów, dzięki któremu przesuwamy pierwszy pionek z punktu początkowego do jakiegoś punktu \(P_1\) oraz drugi podzbiór wektorów, dzięki któremu przesuwamy drugi pionek z punktu początkowego do punktu \(P_2\).

Popatrzmy sobie teraz na drogę z punktu \(P_1\) do punktu \(P_2\). Tę drogę możemy również pokonać, korzystając z wektorów, przy czym najpierw wykorzystujemy wszystkie wektory z pierwszego podzbioru, tylko że z przeciwnym zwrotem (czyli używamy wektora \([-a,-b]\) zamiast wektora \([a,b]\)), a następnie wykorzystujemy wszystkie wektory z drugiego podzbioru. Jeżeli nasz zestaw wektorów oznaczymy przez \(S\), to możemy symbolicznie zapisać, że ścieżka z \(P_1\) do \(P_2\) składa się z wektorów ze zbioru \(S\) oraz ze zbioru \(-S\) zawierającego wszystkie wektory ze zbioru \(S\), z tym że o przeciwnym zwrocie.

Co więcej, jeżeli zaczniemy od jakiegoś punktu \(Q_1\) i stworzymy dowolną ścieżkę, która składa się z wektorów ze zbioru \(S\) i \(-S\) i prowadzi do jakiegoś punktu \(Q_2\), to istnieje rozwiązanie naszego zadania, w którym pionki przemieszczamy na odległość równą odległości pomiędzy punktami \(Q_1\) i \(Q_2\). Zauważmy bowiem, że kolejność wykonywania ruchów nie ma znaczenia (ponieważ dodawanie wektorów jest przemienne), więc wystarczy wybrać wszystkie wektory ze ścieżki, które pochodziły ze zbioru \(S\) i zbudować z nich ścieżkę dla pionka drugiego, a wszystkie wektory pochodzące ze zbioru \(-S\) będą budowały ścieżkę dla pionka pierwszego.

Sprowadzenie do znanego problemu

Tak więc maksymalizacja odległości pomiędzy punktami \(P_1\) i \(P_2\) w rozwiązaniu to jest to samo, co maksymalizacja odległości pomiędzy pionkami \(Q_1\) i \(Q_2\), pomiędzy którymi tworzymy ścieżkę z wektorów ze zbioru \(S\) i \(-S\). Możemy o tym myśleć również w ten sposób, że mamy jeden pionek stojący w punkcie \(Q_1\) i chcemy go za pomocą wektorów ze zbioru \(S\) i \(-S\) przesunąć jak najdalej od tego punktu. A to już jest dokładnie treść zadania Pionek, które pojawiło się na pierwszym etapie XXV Olimpiady Informatycznej.

Jego rozwiązanie działające w czasie \(O(n \log n)\) zostało dokładnie opisane w książce Przygody Bajtazara, więc nie będziemy go tutaj przytaczać. Aby rozwiązać zadanie Dwa pionki, należy wobec tego wykonać bardzo proste sprowadzenie do zadania, którego rozwiązanie już znamy. Do zestawu wektorów z wejścia dodajemy wszystkie te wektory z przeciwnym zwrotem i na takim nowym zestawie, który zawiera dwa razy więcej wektorów, uruchamiamy rozwiązanie zadania Pionek. Wynika z tego, że rozwiązanie zadania Dwa pionki również będzie działać w czasie \(O(n \log n)\).