1078. Kreskowany rysunek [ETI07E2]

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

Skrócony opis problemu:

Dla wielokąta wyznaczonego przez ciąg n znaków [NSWE] oznaczających odpowiednio kierunki: północ, południe, zachód, wschód wyznaczyć ilość linii potrzebnych do jego zakreskowania liniami prostymi pod kątem $45\circ$. Wszystkie boki tego wielokąta są albo równoległe, albo prostopadłe do osi OX.

Rozwiązanie nr 1:
Przyjrzyjmy się rysunkowi z zadania:

Jak możemy zliczyć owe proste? Można pewnie jakoś zapamiętywać, po której stronie danego odcinka mamy wnętrze wielokąta i jakoś sprytnie sprawdzać kiedy dana linia się skończyła a kiedy zaczęła. Byłoby przy tym jednak sporo kłopotu, a da się prościej.

Zauważmy, że każdą prostą wyznacza punkt początkowy, końcowy oraz pośrednie, o które owa prosta się "ociera". Co łączy owe punkty? Ano właśnie to, że leżą na tej samej prostej. No a co nam to daje? Ano suma ich współrzędnych jest taka sama. Weźmy np. punkt $G$ $\ddot\smile$. Suma jego współrzędnych to 6, jako że punktem początkowym $\left(0;0\right)$ jest $A$. Wszystkie punkty leżące na prostej skośnej zaczynającej się od $G$ również mają sumę współrzędnych 6 (punkty $O$, $U$, $Y$). Możemy sobie zatem zliczyć dla każdej sumy ile punktów ją osiąga. Zaczynamy po prostu od punktu (0;0) i przy znaku 'N' zwiększamy współrzędną y, przy 'W' zmniejszamy x, itd.

Dla każdej sumy możemy trzymać ilość punktów w mapie. Zastanówmy się jednak jakie wartości może osiągać ta suma. Mamy n ruchów, więc jeśli zrobimy prostokąt o boku 1, to drugi będzie miał długość $\frac{n-2}{2}$. Dla maksymalnej wartości $10^6$ otrzymamy zatem prawie pół miliona. Może to być zarówno wartość ujemna, jak i dodatnia, więc łącznie mamy prawie milion możliwości. Wystarczy nam zatem tablica zamiast mapy, gdyż milion komórek to dla nas niewiele.

Zliczyliśmy już dla każdej sumy ilość punktów, które ją osiąga. Jak na ich podstawie obliczyć wynik? Ano jeśli mamy 2 punkty dla danej sumy, to wiadomo, że mamy 1 linię. Jeśli dla innej sumy mamy 3 punkty, to również mamy 1 linię z 1 punktem pośrednim. A co jeśli mamy 4 punkty? Mogą to być 2 linie z przerwą w środku lub 1 linia z 2 punktami pośrednimi. Nie sposób stwierdzić który scenariusz jest poprawny, szczególnie jeśli dla większej ilości punktów możemy mieć hybrydę obu opcji. Musimy zatem pozbyć się owych punktów pośrednich. Tylko jak?

Zauważmy, że interesują nas tylko linie w 1 kierunku. A zatem takie punkty pośrednie zawsze będą występowały na połączeniu 2 odcinków formujących └ lub ┐. Pierwszy przypadek otrzymujemy gdy będziemy mieli ruchy "SE" lub "WN", a drugi dla ruchów "ES" i "NW". Wystarczy więc, że po otrzymaniu 'W' sprawdzimy czy poprzednim ruchem nie było 'N', a jeśli tak, to odejmujemy 1 dla sumy z poprzedniej sumy.

Na koniec dla każdej sumy ilość punktów, które ją osiąga dzielimy przez 2 i dodajemy do wyniku.

Złożoność: $O(n)$, gdyż dla każdego ruchu wykonujemy stałą liczbę operacji, dzięki wykorzystaniu tablicy, a następnie rozpatrujemy każdą sumę, a ich może być maksymalnie $\frac{n-2}{2}$. Złożoność pamięciowa: $O(n)$, gdyż mamy 2 tablice rzędu $n$ elementów.

Algorytm:

int main()
{
        int n, x = 0, y = 0, z, z2, count = 0, ans = 0, hash[1000009], sums[500009], check[1000009];
        char curr, last = 0;

        get(n);
        while(n--)
        {
                get(curr);
                if(curr == 'N')
                        ++y;
                else if(curr == 'S')
                        --y;
                else if(curr == 'E')
                        ++x;
                else if(curr == 'W')
                        --x;
                ++hash[500000 + (z = x+y)]; // +500000 by nie było ujemnych indeksów
                if(!check[500000+z]) // każdą nową sumę dodajemy do tablicy
                        sums[count++] = 500000+z,
                        check[500000+z] = 1;
                if(curr+last == 'E'+'S' || curr+last == 'W'+'N') // w przypadku "NW", "WN", "ES", "SE"
                        --hash[500000+z2];
                z2 = z; last = curr;
        }
        for(x = 0; x < count; ++x) // sprawdzamy tylko sumy, które się pojawiły
               ans += hash[sums[x]]>>1;
        print(ans);
}

Rozwiązanie nr 2:

Autorem tego rozwiązania jest Witold Długosz.

Możemy również wykorzystać same punkty graniczne. Każda linia zaczyna się i kończy w jakimś punkcie. Gdybyśmy potrafili jednoznacznie opisać takie punkty, to moglibyśmy łatwo zliczyć same linie.

Jak widać, linia zawsze wychodzi spomiędzy boków "NN", "NE", "EN" lub "EE", a kończy się zawsze pomiędzy parą "WW", "SW", "SS" lub "WS". Wystarczy zatem zliczyć pierwsze pary lub drugie.

Złożoność: $O(n)$, gdyż sprawdzimy pary 2 kolejnych ruchów, a owych par jest $n$ (bierzemy również pod uwagę przejście z ostatniego ruchu na pierwszy). Złożoność pamięciowa: $O(1)$, bo nie potrzebujemy nawet tablicy, jako że wystarczą nam jedynie 2 kolejne ruchy.

Algorytm:

int main()
{
 int n, last, first, curr, ans = 0;

 get(n);
 first = last = get() >= 'S'; // pamiętaj pierwszy stan
 while(--n) // jedna iteracja mniej, bo powyżej pobraliśmy 1 znak osobno
 {
  curr = get() >= 'S';
  ans += curr & last; // jeśli dany ruch oraz poprzedni są 'S' lub 'W' inkrementuj wynik
  last = curr;
 }
 print(ans += curr & first); // dodaj przejście z ostatniego ruchu na pierwszy
}