573. Marsze na orientację [PZPI1]

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

Skrócony opis problemu:

Mamy $n$ punktów numerowanych od 1 do $n$ oraz $k$ ($k < n$) zapytań. Zapytanie składa się z dwóch liczb: $a$ i $b$. Dla każdego zapytania należy podać dowolną ścieżkę z punktu $a$ do punktu $b$ (przechodząc przez inne punktu po drodze lub nie), jednak żadne dwie trasy (będące odpowiedzią na zapytania) nie mogą mieć wspólnego fragmentu (bezpośredniego połączenia między tą samą parą punktów). Czyli po prostu musimy wypisywać dowolne ścieżki, ale bez wspólnych krawędzi. Jeżeli dla danego testu nie da się utworzyć ścieżek, które by spełniały kryteria z zadania, to należy wypisać NIE.

Rozwiązanie:

Zastanówmy się na początku jak generować kolejne ścieżki by nie miały wspólnej krawędzi. Ano wystarczy każdą z $\frac{n \cdot (n-1)}{2}$ możliwych krawędzi przydzielać tylko do jednej ścieżki. Tak więc bierzemy kolejne zapytania i budujemy z pozostałych krawędzi ścieżkę zaczynającą się w punkcie $a$ i kończącą w $b$, a następnie usuwamy z dostępnych krawędzi te, które wykorzystaliśmy.

Teraz zastanówmy się które z krawędzi wybierać. Skoro mamy do ograniczoną ilość krawędzi do wykorzystania, to rozsądnie byłoby je oszczędzać. A więc dla każdego zapytania, które pojawiło się po raz pierwszy wypisujemy po prostu je. Czyli nie dodajemy dodatkowych punktów pośrednich, bo są zbędne.

Pozostaje nam już tylko znaleźć ścieżki dla zapytań, które pojawiły się więcej niż raz (np. mamy 2 zapytania "7 4" - na pierwsze wypisujemy "7 4" i po zostało nam jeszcze wypisać dla drugiego "7 ... 4"). Tutaj znów chcemy zużyć jak najmniej krawędzi, więc postaramy się najpierw dodać 1 punkt pośredni (co da nam ścieżkę z dwoma krawędziami). No i teraz pytanie - jak wybierać ten punkt? Mamy około $n$ możliwości. Powiedzmy, że wybierzemy dowolny punkt $x$, dla którego krawędzie $x-a$ oraz $x-b$ nie zostały jeszcze przez nas wykorzystane. Czy jest to optymalne rozwiązanie? Okazuje się, że tak! Nie będziemy przecież potrzebować żadnej z obu tych krawędzi. Gdybyśmy potrzebowali, to by znaczyło, że mielibyśmy zapytanie $x a$ lub $x b$ (lub $a x$, lub $b x$), a wtedy byśmy już wykorzystali tę krawędź. A zatem jeśli mamy dostępną daną krawędź, to znaczy, że nie musimy się bać, że będzie nam ona niezbędna gdzie indziej.

No ale jeszcze pozostało pytanie, kiedy wypisujemy NIE. By na nie odpowiedzieć trzeba przypomnieć sobie, że $k < n$. Oznacza to, że mamy mniej zapytań, niż punktów. No a kiedy będzie nam najtrudniej dobrać krawędzie? Wtedy, kiedy wszystkie zapytania będą takie same. Gdyby wszystkie zapytania były różne, to odpowiedzią dla każdego zapytania byłoby ono same. Powiedzmy więc, że $n = 5$ i $k = 4$, a wszystkie zapytania są postaci "1 2". No więc na pierwsze zapytanie odpowiedzią będzie "1 2". Zobaczmy, jakie krawędzie nam zostały:

1 2

1 3

1 4

1 5

2 3

2 4

2 5

3 4

3 5

4 5

Pozostały nam jeszcze 3 zapytania. Widzimy, że mamy też dokładnie 3 krawędzie z 1 oraz 3 z 2. Możemy zatem bez problemu połączyć ze sobą owe krawędzie w pary. Jeśli mielibyśmy 3 zapytania "1 2" i jedno np. "2 3", no odpowiedziami na zapytania byłoby: "1 2", "2 3", "1 4 2", "1 5 2". Jak więc widać, zawsze da się znaleźć ścieżki, które nie będą miały wspólnej krawędzi. Wszystko dzięki ograniczeniu $k < n$. Jest bowiem $n-1$ jedynek, dwójek, itd. we wszystkich możliwych krawędziach (jak widać powyżej). Gdyby było $k \le n$, to nie byłoby już tak łatwo.

Złożoność: $O(k \cdot n)$, bo najpierw przydzielamy krawędzie zapytaniom, które wystąpiły po raz pierwszy. Pesymistycznie zostanie nam nadal blisko $k$ zapytań. Dla każdego z nich szukamy takiego punktu $x$, dla którego istnieją krawędzie $x-a$ oraz $x-b$. Musimy niestety sprawdzić pesymistycznie wszystkie punkty, więc wykonujemy około $n$ operacji dla każdego z około $k$ pozostałych zapytań.

Algorytm:

int main()
{
        int t, n, k, in[1009][2], map[1100009];
        vector<int> tab[1009];

        get(t);
        for(int i = 1; i <= t; ++i)
        {
                get(n, k);
                print("zestaw i T\n");
                for(int j = 0; j < k; ++j)
                {
                        get(in[j][0], in[j][1]);
                        // haszujemy parę liczb "a b" jako a*1000+b; jeśli danej pary jeszcze nie było, to odpowiedzią na zapytanie będzie ono samo ("a b")
                        if(map[in[j][0]*1000+in[j][1]] < i)
                        {
                                tab[j].push_back(in[j][0]); // wrzucamy "a" do listy punktów dla danego zapytania
                                tab[j].push_back(in[j][1]); // wrzucamy "b"
                                map[in[j][0]*1000+in[j][1]] = map[in[j][1]*1000+in[j][0]] = i; // ustawiamy, że dane zapytanie już było (zarówno a*1000+b, jak i b*1000+a, bo nie wiemy w jakiej kolejności dostaniemy zapytanie)
                        }
                }
                for(int j = 0; j < k; ++j)
                        if(tab[j].empty()) // jeśli nie mamy jeszcze odpowiedzi na dane zapytanie (lista punktów jest pusta)
                        {
                                tab[j].push_back(in[j][0]); // dodajemy "a"
                                for(int l = 1; l <= n; ++l)
                                        if(l != in[j][0] && l != in[j][1] && map[l*1000+in[j][0]] < i && map[l*1000+in[j][1]] < i) // jeśli dany punkt nie jest równy "a" ani "b" oraz nie zużyliśmy jeszcze krawędzie l-a i l-b
                                        {
                                                tab[j].push_back(l); // dodaj ten punkt do listy danego zapytania
                                                map[l*1000+in[j][0]] = map[l*1000+in[j][1]] = map[in[j][0]*1000+l] = map[in[j][1]*1000+l] = i; // ustaw krawędzi l-a, l-b, a-l, b-l na wykorzystane
                                                break;
                                        }
                                tab[j].push_back(in[j][1]); // dodajemy "b"
                        }
                for(int j = 0; j < k; ++j)
                {
                        print(tab[j].size());
                        for(int l = 0; l < tab[j].size(); ++l)
                                print(tab[j][l]);
                        tab[j].clear(); // czyścimy wektor
                }
        }
}

Optymalizacja:

Jak widać w powyższym kodzie ustawiam komórki tablicy $map$ na $i$. O co tutaj chodzi i po co to? Ano muszę jakoś zaznaczać, że dana krawędź została wykorzystana. Mógłbym więc przyjąć, że 0 oznacza, że jeszcze nie została wykorzystana, a 1, że została. Tyle że wtedy po każdym teście musiałbym czyścić tablicę $map$, a szkoda mi czasu na to. Tak więc dla każdego z kolejnych testów podstawiam zamiast 1 wartość $i$, która oznacza $i$-ty test. Zamiast 0, wykorzystane krawędzie oznaczam wszystkimi liczbami mniejszymi od $i$. Dzięki temu jak przechodzę do nowego testu, to $i$ mi się zwiększa o 1 i tym samym wszystkie komórki tablicy $map$ stają się niewykorzystane.

Optymalizacja nr 2:
Jacek Świergocki zaproponował rozpoczynanie od losowego elementu zamiast od pierwszego w pętli szukającej punktu $x$, dla którego krawędzie $(a, x)$ oraz $(b, x)$ nie zostały jeszcze wykorzystane. Oczywiście wszystko zależy od testów - można by wygenerować takie testy, żeby rozpoczynanie od punktu 1 było szybsze. Ale jednak okazuje się, że dla losowych testów losowe podejście jest lepsze. Nie jest to zatem przypadek. Nie wiem jednak czemu tak się dzieje. Musiałoby to oznaczać, że sporo elementów z początku jest już zajętych, a nie wiem czy tak powinno być przy losowych testach. Jeśli ktoś zna się na prawdopodobieństwie i umie to wytłumaczyć, to śmiało. $\ddot\smile$