865. Bombardier Jaś [PZPI06_2]

Zadanie:
https://pl.spoj.com/problems/PZPI06_2

Skrócony opis problemu:

Obliczenie stałej prędkości obrotowej działa, które wykonuje m strzałów pod różnymi kątami. Kąty te mają wspólny mianownik n. Działo obraca się przeciwnie do ruchu wskazówek zegara. Żadne 2 strzały nie zostały oddane w tym samym kierunku.

Uproszczony opis problemu:

Na początku zajmijmy się kątami - o co chodzi z tym mianownikiem? Otóż dla $n=15$ możliwe kąty są postaci $360^\circ \cdot \frac{k}{15}$, a więc: $0^\circ , 24^\circ , 48^\circ , 72^\circ , 96^\circ , 120^\circ , \ldots$.

A teraz: o co naprawdę chodzi w zadaniu? Weźmy sobie 3 test z zadania. Tak wyglądają strzały działa z tego przykładu (wykonane w programie GeoGebra):

Widzimy, że najpierw wykonaliśmy strzał w kierunku B (0/15), potem F (4/15), E (7/15), D (8/15), a na końcu C (11/15). Wynik to 4 dla tego testu (a więc $96^\circ$). Dlaczego?

Chodzi o to, żeby podać najmniejszy możliwy taki kąt, że jak wystartujemy z jakiegoś punktu to damy radę trafić we wszystkie te cele. Spróbujmy zatem wystartować z B. Przemieszczać możemy się jedynie właśnie o ten kąt, który zwracamy na wyjściu. Z B idziemy o $96^\circ$ w lewo, a więc do F, następnie pomijamy E i idziemy do D (bo to on jest oddalony o $96^\circ$ od F), a następnie... no właśnie - nigdzie. Żeby ruszyć się dalej potrzebowalibyśmy celu w odległości $24^\circ$ od C. Nie ma go tam jednak.

Czy to oznacza, że 4 jest złym wynikiem? Nie. Gdybyśmy zaczęli bowiem od E, przeszlibyśmy kolejno przez E, C, B, F, D. Po D nie mielibyśmy co prawda gdzie iść, ale wszystkie strzały zostałyby pokryte.

Rozwiązanie naiwne:

Możemy sprawdzać dla kolejnych kątów (zaczynając od najmniejszego - jednostkowego) czy da się pokryć nim wszystkie cele działa. Zaczynamy zatem z dowolnego punktu i przechodzimy przez wszystkie $m-1$ pozostałych. Jeśli dojdziemy do ostatniego oznacza to, że dany kąt jest naszym wynikiem. Jeśli nie - zaczynamy od kolejnego punktu.

Złożoność: $O(n \cdot m^2)$, jako że dla każdego z $n$ kątów pesymistycznie sprawdzamy $m$ celi, a dla każdego z tych celi musimy przejść pozostałe $m-1$ celi.

Optymalizacja:

Możemy nie zaczynać od kąta równego 1, ale od największego kąta między kolejnymi celami. Patrząc na powyższy rysunek widzimy, że nie damy rady przejść wszystkich celi z kątem mniejszym od 4 (czyli $96^\circ$), gdyż nie bylibyśmy w stanie przejść choćby od B do F. Nie zmienia to złożoności, ale przyspiesza program w niektórych przypadkach.

Rozwiązanie sprytniejsze:

Zastanówmy się jak możemy przyspieszyć poprzedni algorytm. Na pewno dla jakiegoś celu musimy sprawdzić pozostałe $m-1$ celi. Pozostało nam zatem albo sprawdzić stałą liczbę kątów, albo dla każdego kąta sprawdzić stałą liczbę celi (a nie wszystkie jak to robiliśmy poprzednio). Którą zmienną wyeliminujemy zatem ze złożoności? Możemy wyczuć, że ciężko by było sprawdzić stałą liczbę kątów, jako że przecież to ów kąt mamy znaleźć. Musielibyśmy więc zgadywać jakoś kilka kątów. Skupmy się więc na wyeliminowaniu jednego $m$ ze złożoności.

A zatem co chcemy osiągnąć? Chcemy nadal pesymistycznie każdego z $n$ kątów sprawdzić czy da się pokryć nim wszystkie cele zaczynając tylko od jednego celu. Mamy zatem 1 szansę, żeby trafić w początkowy cel. Dosyć marne prawdopodobieństwo, że się nam to uda ($\frac{1}{m}$). Co z tym zrobimy? Ano wystarczy, że przestaniemy zakładać, że jest to początkowy cel! Jako że jest to środkowy cel, najpierw idziemy sobie w lewo i zliczamy ile celi pokryjemy, a następnie cofamy się do owego celu i sprawdzamy z którego najdalszego celu jesteśmy w stanie do niego dojść. Tyle. Jeśli suma owych dwóch wartości jest równa (lub przekracza) $m$, to dany kąt jest naszym wynikiem.

Złożoność: $O(n \cdot m)$, jako że dla każdego z $n$ kątów możemy sprawdzić tylko 1 cel, a z niego przejść $m-1$ pozostałych celi. Tutaj również można zastosować wspomnianą optymalizację, jednak i tu nie zmienia ona złożoności.

Algorytm bez optymalizacji:

int main()
{
        int n, k, i, j, x, y, czy[2*5000], tab[2*5000];

        get(n, k);
        for(i = 1;i <= n; ++i)
                get(tab[i]),
                czy[tab[i]] = i; // czy dla danego kąta istnieje cel
        for(i = 1; i < k; ++i) // tutaj zamienić 1 na odpowiednią wartość w celu optymalizacji
        {
                for(x = 2, j = 1; x < n; ) // x to ilość celi, które pokryjemy; j to cel, od którego zaczynamy
                {
                        y = tab[j]+i;
                        if(y >= k) // przejście progu 359 stopni - 0 stopni
                                y -= k;
                        if(czy[y])
                                ++x,
                                j = czy[y];
                        else
                                break;
                }
                for(j = 1; x < n; )
                {
                        y = tab[j]-i;
                        if(y < 0) // przejście progu 0 stopni - 359 stopni
                                y += k;
                        if(czy[y])
                                ++x,
                                j = czy[y];
                        else
                                break;
                }
                if(x >= n)
                        print(i),
                        break;
        }
}

Uproszczenie:

Możemy również trochę uprościć nasz algorytm i przejść działem tylko w jednym kierunku od danego celu. Jeśli napotkamy miejsce, w którym powinien być cel, a go nie ma, idziemy po prostu dalej. Jeśli napotkamy drugi taki cel przed przejściem $m-1$ celi to znaczy, że owym kątem nie da się pokryć wszystkich. Jeśli będzie co najwyżej jedno takie miejsce to po prostu znaczy, że początkowym celem będzie ten cel, który był po takim miejscu bez celu (a więc to miejsce bez celu znajdować się będzie tuż przed celem początkowym). Idea jest ciągle taka sama - będziemy mieli po prostu jedną pętlę wewnątrz mniej.

Rozwiązanie sprytniejsze nr 2:

Autorem tego rozwiązania jest Lupus Nocawy.

Można też do zadania podejść z innej strony. Zliczmy kąty między każdą parą celi. Następnie wystarczy znaleźć najmniejszy kąt, który wystąpił co najmniej $m-1$ razy.

Złożoność: $O(m^2 + n)$, jako że na początku obliczamy kąt między każdą parą celi (a jest ich $\frac{m \cdot (m-1)}{2}$), a następnie sprawdzamy pesymistycznie każdy z $n$ kątów. Jako że wg zadania $m < n$, to ten algorytm powinien być szybszy od poprzedniego. Okazuje się jednak, że daje gorszy czas od tamtego. Być może przez testy - w poprzednim algorytmie mamy przyspieszenie w postaci breaka - możemy mieć szczęście i szybko trafić na odpowiedni kąt i pominąć wiele operacji. W tym algorytmie musimy wykonać wszystkie $m^2$ obliczeń, a breaka możemy zastosować dopiero podczas przeglądania $n$ kątów. Zyskujemy tutaj jedynie liniową oszczędność na breaku w porównaniu do kwadratowej w poprzednim algorytmie.

Algorytm:

int main()
{
        int m, n, M[5009], cnt[5009], min = 0;
        get(m, n);
        for(i = 0; i < m; ++i)
                get(M+i);
        for(i = 0; i < m; ++i)
                for(j = i+1; j < m; ++j)
                        ++cnt[(M[j]-M[i]+n)%n],
                        ++cnt[(M[i]-M[j]+n)%n];
        for(i = 1; i < n; ++i)
                if(cnt[i] >= m-1)
                {
                        min = i;
                        break;
                }
        print(min);
}