English
Forum jest zablokowane. Podczas blokady nie można dodawać ani edytować wiadomości.
Ostatnie posty
Zajefajne zadania, szczególnie 3A (OGR) i cała ostatnia runda poza BST może, który było tylko spoko. Ostatnia runda była bardzo trudna. Nie miałem innych zajęć, a i tak zupełnie się nie wyrobiłem z zadaniami. Dobrze jest mieć raz na rok taki konkurs :)
Potwierdzam kozaczność zadanek :)
Bardzo się cieszymy, że się podobały :)
Imo zadanka kozak były
Dzięki Waszym testom mam 10 ;) udało mi się znaleźć błąd 10 min przed północą.
Zgadza się. Oczywiście nadal mogą zachodzić problemy probabilistyczne wynikające z liczby wylosowanych bitów, ale taki jest zamysł.
Nice - miałem ten sam podział na przypadki, ale nie scalałem krawędzi, i również zaciąłem się na podprzypadku 4.1 :-) Jakoś nawet w niektórych przypadkach czasem odejmowałem coś co policzyłem za dużo w innych, że w końcu liczyło to każdą konfigurację raz, no ale 4.1 wciąż miałem kwadratowo.
To rozumiem że z waszego rozwiązania wynika, że jeśli weźmiemy zbiór hashy dla krawędzi w grafie to liczba trójek xorujących się do 0 jest liniowa? Nie widzę czemu miałaby to być prawda dla dowolnego zbioru hashy, więc rozumiem że jest to własność wynikająca z tego jak ten zbiór powstał?
To rozumiem że z waszego rozwiązania wynika, że jeśli weźmiemy zbiór hashy dla krawędzi w grafie to liczba trójek xorujących się do 0 jest liniowa? Nie widzę czemu miałaby to być prawda dla dowolnego zbioru hashy, więc rozumiem że jest to własność wynikająca z tego jak ten zbiór powstał?
Ehhhhhhhhh. Dzięki Marek
Modulo? :P
Komuś też pykały testy i był przekonany o poprawności rozwiązania, a nie dostał 10 pkt? xd
Potwierdzam, że układa się to alfabetycznie i kolejność podczas wszystkich rund była czystym zbiegiem okoliczności. Postaramy się w przyszłym roku to poprawić.
Niezbyt szczegółowy opis naszego rozwiązania, mamy nadzieję, że jak chcesz zrozumieć to zrozumiesz.
Po pierwsze dla każdego cyklu bazowego losujemy 60-bitową wartość i dla każdej krawędzi spamiętujemy xora wartości cykli bazowych, które przez nią przechodzą. Dla krawędzi taką liczbę możemy nazywać jej haszem. Zbiór krawędzi rozspójnia graf, jeśli hasze jakiegoś jego niepustego podzbioru xorują się do zera. Mamy kilka prostych przypadków: krawędź o wartości 0 (most); dwie krawędzie o tej samej wartości. Możemy łatwo w czasie liniowym policzyć wszystkie trójki krawędzi, które zawierają jeden z tych przypadków. Następnie dla każdego mostu możemy scalić oba jego końce. To samo, gdy mamy wiele krawędzi o tej samej wartości: dla wszystkich nich oprócz jednej (dowolnej) scalamy ich końce. Pozbywamy się też również powstałych pętli, nie są one w niczym przydatne. W ten sposób otrzymujemy trzyspójny graf nie zmieniając zbioru trójek haszy xorujących się do zera. Nie musimy się teraz skupiać na dokładnym policzeniu wyniku, ale na znalezieniu wszystkich trójek haszy, które xorują się do zera. Być może niektóre z nich znajdziemy wiele razy, nie szkodzi, na koniec wyciągniemy z tego wynik.
Mając trzyspójny graf znajdźmy dowolne jego drzewo dfs i rozważmy możliwe przypadki trójek krawędzi: 3 niedrzewowe, 2 niedrzewowe i 1 drzewowa, 1 niedrzewowa i 2 drzewowe, 3 drzewowe.
Pierwszy przypadek jest niemożliwy, gdyż usuwając jedynie niedrzewowe krawędzie nie rozspójnimy grafu.
Drugi jest prosty: niezależnie od tego jak wyznaczaliśmy cykle bazowe, to dla dowolnego drzewa rozpinającego możemy myśleć, że to jego krawędzie niedrzewowe wyznaczały owe cykle. Przez szukaną krawędź drzewową muszą zatem przechodzić dokładnie dwie krawędzie niedrzewowe. Możemy się przeiterować po krawędzi drzewowej i jeśli ona bierze udział w tym przypadku, to inną krawędzią w takiej trójce musi być dowolna krawędź niedrzewowa przechodząca nad nią.
Trzeci przypadek jest nieco trudniejszy, ale nadal możliwy do rozwiązania. Dwie krawędzie drzewowe muszą leżeć jedna nad drugą i zbiór krawędzi niedrzewowych przechodzących przez nie musi różnić się dokładnie jedną krawędzią. Mamy tu dwa podprzypadki: większy zbiór jest niżej lub wyżej. W obu przypadkach istnieje jeden kandydat na krawędź niedrzewową, która nie przechodzi nad tą drugą krawędzią drzewową. Możemy to rozwiązać standardowymi drzewowymi operacjami, np. zamiatając krawędzie niedrzewowe w odpowiedniej kolejności (zależnie od podprzypadku) i używając find&union. Można to też zrobić liniowo, ale jest to trochę trudniejsze.
Czwarty przypadek jest najtrudniejszy i ma dwa podprzypadki. Albo trzy krawędzie leżą po kolei jedna pod drugą, albo istnieje wierzchołek, który w dwóch poddrzewach ma dwie krawędzie, a nad sobą jedną. Ten drugi podprzypadek nadal da się rozwiązać, jednak pierwszego nie umiemy, dlatego nie rozwiążemy żadnego z nich.
Znaleźliśmy zatem wszystkie trójki haszy takie, że chociaż jedna krawędź w takiej trójce jest niedrzewowa. Przypomnijmy sobie zatem, że nasz graf był trzyspójny. Na pewno zachodzi zatem m>=1.5n (stopnie muszą wynosić co najmniej 3). Dla każdej krawędzi niedrzewowej scalmy zatem oba jej końce, otrzymując w ten sposób nowy graf (znowu pozbywając się pętli). Pozbędziemy się w tej sposób co najmniej m-(n-1) krawędzi, zatem co najmniej 1/3 z nich. Nowy graf nadal musi być trzyspójny, czyli nadal musi spełniać wspomnianą nierówność. Czy jeśli istniała trójka krawędzi drzewowych, których wartości xorowały się do zera, to czy mogła ona w ten sposób zniknąć? Nie, jeśli była ona poprawnym cięciem grafu, to na pewno dla żadnej z tych krawędzi nie scaliliśmy obu jej końców. Możemy zatem ponownie przejrzeć wszystkie przypadki i znowu redukować nasz graf. Całość powtarzamy, aż w grafie zostanie jeden wierzchołek.
Możemy zatem szybko (w czasie O(mlog(m)), O(mlog*(m)) lub nawet O(m)) znaleźć wszystkie trójki, które nas interesują, a następnie zredukować nasz graf, którego rozmiar maleje geometrycznie. Sumaryczna złożoność będzie zatem taka, jak złożoność jednej fazy.
Na koniec, mając wszystkie pożądane trójki i dla każdego hasza wiedząc, ile krawędzi w pierwotnym grafie go miało, możemy łatwo policzyć wynik.
Po pierwsze dla każdego cyklu bazowego losujemy 60-bitową wartość i dla każdej krawędzi spamiętujemy xora wartości cykli bazowych, które przez nią przechodzą. Dla krawędzi taką liczbę możemy nazywać jej haszem. Zbiór krawędzi rozspójnia graf, jeśli hasze jakiegoś jego niepustego podzbioru xorują się do zera. Mamy kilka prostych przypadków: krawędź o wartości 0 (most); dwie krawędzie o tej samej wartości. Możemy łatwo w czasie liniowym policzyć wszystkie trójki krawędzi, które zawierają jeden z tych przypadków. Następnie dla każdego mostu możemy scalić oba jego końce. To samo, gdy mamy wiele krawędzi o tej samej wartości: dla wszystkich nich oprócz jednej (dowolnej) scalamy ich końce. Pozbywamy się też również powstałych pętli, nie są one w niczym przydatne. W ten sposób otrzymujemy trzyspójny graf nie zmieniając zbioru trójek haszy xorujących się do zera. Nie musimy się teraz skupiać na dokładnym policzeniu wyniku, ale na znalezieniu wszystkich trójek haszy, które xorują się do zera. Być może niektóre z nich znajdziemy wiele razy, nie szkodzi, na koniec wyciągniemy z tego wynik.
Mając trzyspójny graf znajdźmy dowolne jego drzewo dfs i rozważmy możliwe przypadki trójek krawędzi: 3 niedrzewowe, 2 niedrzewowe i 1 drzewowa, 1 niedrzewowa i 2 drzewowe, 3 drzewowe.
Pierwszy przypadek jest niemożliwy, gdyż usuwając jedynie niedrzewowe krawędzie nie rozspójnimy grafu.
Drugi jest prosty: niezależnie od tego jak wyznaczaliśmy cykle bazowe, to dla dowolnego drzewa rozpinającego możemy myśleć, że to jego krawędzie niedrzewowe wyznaczały owe cykle. Przez szukaną krawędź drzewową muszą zatem przechodzić dokładnie dwie krawędzie niedrzewowe. Możemy się przeiterować po krawędzi drzewowej i jeśli ona bierze udział w tym przypadku, to inną krawędzią w takiej trójce musi być dowolna krawędź niedrzewowa przechodząca nad nią.
Trzeci przypadek jest nieco trudniejszy, ale nadal możliwy do rozwiązania. Dwie krawędzie drzewowe muszą leżeć jedna nad drugą i zbiór krawędzi niedrzewowych przechodzących przez nie musi różnić się dokładnie jedną krawędzią. Mamy tu dwa podprzypadki: większy zbiór jest niżej lub wyżej. W obu przypadkach istnieje jeden kandydat na krawędź niedrzewową, która nie przechodzi nad tą drugą krawędzią drzewową. Możemy to rozwiązać standardowymi drzewowymi operacjami, np. zamiatając krawędzie niedrzewowe w odpowiedniej kolejności (zależnie od podprzypadku) i używając find&union. Można to też zrobić liniowo, ale jest to trochę trudniejsze.
Czwarty przypadek jest najtrudniejszy i ma dwa podprzypadki. Albo trzy krawędzie leżą po kolei jedna pod drugą, albo istnieje wierzchołek, który w dwóch poddrzewach ma dwie krawędzie, a nad sobą jedną. Ten drugi podprzypadek nadal da się rozwiązać, jednak pierwszego nie umiemy, dlatego nie rozwiążemy żadnego z nich.
Znaleźliśmy zatem wszystkie trójki haszy takie, że chociaż jedna krawędź w takiej trójce jest niedrzewowa. Przypomnijmy sobie zatem, że nasz graf był trzyspójny. Na pewno zachodzi zatem m>=1.5n (stopnie muszą wynosić co najmniej 3). Dla każdej krawędzi niedrzewowej scalmy zatem oba jej końce, otrzymując w ten sposób nowy graf (znowu pozbywając się pętli). Pozbędziemy się w tej sposób co najmniej m-(n-1) krawędzi, zatem co najmniej 1/3 z nich. Nowy graf nadal musi być trzyspójny, czyli nadal musi spełniać wspomnianą nierówność. Czy jeśli istniała trójka krawędzi drzewowych, których wartości xorowały się do zera, to czy mogła ona w ten sposób zniknąć? Nie, jeśli była ona poprawnym cięciem grafu, to na pewno dla żadnej z tych krawędzi nie scaliliśmy obu jej końców. Możemy zatem ponownie przejrzeć wszystkie przypadki i znowu redukować nasz graf. Całość powtarzamy, aż w grafie zostanie jeden wierzchołek.
Możemy zatem szybko (w czasie O(mlog(m)), O(mlog*(m)) lub nawet O(m)) znaleźć wszystkie trójki, które nas interesują, a następnie zredukować nasz graf, którego rozmiar maleje geometrycznie. Sumaryczna złożoność będzie zatem taka, jak złożoność jednej fazy.
Na koniec, mając wszystkie pożądane trójki i dla każdego hasza wiedząc, ile krawędzi w pierwotnym grafie go miało, możemy łatwo policzyć wynik.
No to jest alfabetycznie po kodzie zadania, ale też mnie to skonfundowało. Lepiej byłoby chyba A-B-C.
Zauważyłem że w rundach 1-4 zadania wyświetlały się w kolejności B, A, C, za to w 5. rundzie w kolejności B, C, A. Czy utrzymywanie tej kolejności, a później taka zmiana były zamierzone?
Ktoś podpowie jak zrobić TRZ szybciej niż O(n^2)?