628. Półki [SHELVES]

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

Skrócony opis problemu:

Mając półki ustawione ukośnie w $n$ ($n \le 1000$) kolumnach oraz $k$ ($k \le 250000$) piłek, które są kolejno spuszczane w różnych kolumnach z górnych półek określ gdzie spadnie ostatnia piłka, jeśli po każdym stoczeniu się piłki po półce odwraca się jej ustawienie (jeśli nie jest ona półką skrajną). A więc półki \ zamieniają się na / i odwrotnie.

Przykładowo, jeśli mamy jedną piłkę i taki zestaw półek:

o    
\ \ /
 / / 
\ \ /

To po sturlaniu się piłki po wszystkich 3 półkach, ich rozkład będzie wyglądał następująco:

\ \ /
 \ / 
\ \ /
o  

Jak widać, półki po bokach nie zmieniają nachylenia, gdyż wtedy piłka wypadłaby poza planszę. Zmianie uległa więc tylko nachylenie czerwonej półki.

W zadaniu półki \ są podane jako 1, a / jako -1.

Rozwiązanie naiwne:

Możemy po prostu dla każdej piłki przechodzić wszystkie półki i zamieniać ich nachylenie i dla ostatniej piłki wypisać jej położenie.

Złożoność: $O(n \cdot k)$. Bo jest $k$ piłek i dla każdej przechodzimy drogę o długości $n$.

Rozwiązanie sprytne:

Możemy aktualizować wszystkie piłki na raz.

Pomyślmy - kolejność ma znaczenie. Nie możemy najpierw puścić drugiej piłki, a potem pierwszej. Dalej, nie możemy anulować piłek - jeśli puścimy 2 piłki z tego samego miejsca, to nie wrócimy do ustawienia pierwotnego, gdyż druga piłka pójdzie inną drogą. Potrzebujemy jednak tylko miejsca, w którym wypadnie ostatnia piłka, a nie np. i-ta. Tak więc możemy sobie nie po kolei odwracać te półki. Największym spostrzeżeniem jest to, że możemy aktualizować wiele piłek na raz - idąc od góry. Tak więc zliczamy dla każdego miejsca, ile piłek z niego wystartuje. No i jeśli z danego miejsca startuje $x$ piłek, to $\left\lfloor\frac{x}{2}\right\rfloor$ poleci na lewo i $\left\lfloor\frac{n}{2}\right\rfloor$ na prawo. Jeśli $x$ jest nieparzyste to jedna piłka więcej poleci tam, gdzie wskazywał pierwotny kierunek. Tak więc robimy sobie tablicę z ilością piłek w każdej z $2n$ kolumn na poziomie, który rozpatrujemy. $2n$, bo jak widać na powyższych "ilustracjach" półki na 2 kolejnych poziomach są między sobą, a nie dokładnie pod sobą. Tak więc dla każdego miejsca przesuwając się o 2 połowę piłek dodajemy do komórki po lewej i połowę do tej po prawej i jeśli ilość piłek jest nieparzysta do inkrementujemy pomórkę po lewej dla półki / i po prawej dla półki \. Jeśli rozpatrywana półka jest półką skrajną to nie dzielimy na pół, jako że wszystkie piłki idą w jednym kierunku.

Na końcu przechodzimy w czasie $O(n)$ przez planszę dla ostatniej piłki i zapamiętujemy jej ostatnią pozycję. Możemy też na bieżąco modyfikować pozycję ostatniej piłki pamiętając ją osobno. Czyli jeśli dojdziemy do miejsca, na którym jest ostatnia piłka to dodatkowo modyfikujemy osobną zmienną pokazującą jej położenie.

Złożoność: $O(n^2)$. Bo przechodzimy $n$ poziomów, a na każdym jest $2n$ możliwych położeń. $n^2$ jest mniejsze od $n \cdot k$ biorąc pod uwagę rozmiary danych z zadania. Tak więc zwracajcie na nie uwagę!

Ostateczny algorytm:

int main()
{
    int n, k, y, x; // dane; y to komórki planszy wczytywane na bieżąco pojedynczo; x to pozycja ostatniej piłki
    int tab[2n]; // tablica ilości piłek w danych miejscach; na początku wyzerowana
    int i, j;
    
    get(n, k);
    for(i = 1; i < k; ++i)
        get(x),
        ++tab[x-1]; // pozycje piłek są liczone od 1 wg specyfikacji, a my będziemy numerowali od 0
    get(x); --x; // tu też numeracja od 0
    for(j = 0; j < n; ++j) // dla każdego poziomu
        for(i = j&1; i < n+n-1; i += 2) // dla rzędów nieparzystych jest 1 komórka mniej - ignorujemy tą początkową; idziemy co 2, ale przez 2n pól
        {
            get(y);
            if(!i) // jeśli półka jest na skraju po lewej stronie
                tab[1] += tab[0]; // dodaj wszystko do komórki o 1 na prawo
            else if(i == n+n-2) // jeśli po prawej stronie na skraju
                tab[i-1] += tab[i]; // dodaj wszystko do komórki o 1 na lewo
            else
            {
                tab[i+1] += tab[i]/2; // połowa na prawo; dzielenie na intach to automatycznie floor
                tab[i-1] += tab[i]/2; // połowa na lewo
                if(tab[i]&1) // dla nieparzystej liczby dodatkowe 1 w odpowiednim kierunku + odwrócenie kierunku
                    ++tab[i+y],
                    y = -y;
            }
            if(x == i) // jeśli jesteśmy w miejscu, przez które przechodzi ostatnia piłka to zmodyfikujmy kierunek ostatniej piłki
                x += y;
            tab[i] = 0; // wszystkie piłki poszły w odpowiednim kierunku, więc wyzerujmy komórkę
        }
    print(x+1);
}