szukanie zaawansowane
 [ Posty: 3 ] 
Autor Wiadomość
Mężczyzna Offline
PostNapisane: 25 wrz 2015, o 17:58 
Użytkownik

Posty: 1936
Lokalizacja: Warszawa
Mamy permutację liczb 1...n. Konstruujemy graf wierzchołków 1...n w ten sposób, że dwa wierzchołki są połączone (krawędź nieskierowana) wtw gdy są one w inwersji ze sobą.

Naszym zadaniem jest wymyślić algorytm, który dla danej permutacji policzy ile graf ma spójnych składowych:

Ja zaproponuję coś takiego: (proszę o sprawdzenie, ale także pokazanie alternatywnych rozwiązań).
To rozwiązanie działa w czasie O(n\log^*)
Używamy Union find, na początku 1...n to osobne zbiory.

1. Policzmy tablicę sufixową dla minimów. Tzn dla każdego sufixu znamy minimum.
2. Sprawdzamy jakie jest minimum na przedziale [1..n]. Okazuje się, że to p[i]. Wówczas lecimy
od 1 do i-1 i wszystkie scalamy z p[i] - dostajemy jeden zbiór. Potem powtarzamy to samo, w konsekwencji jesteśmy w sytuacji takiej:



I teraz:
Bierzemy maximum - niebieska kropka - z grupki pierwszej. Porównujemy go z minimum grupki drugiej:
Jeśli niebieska kropka (max) jest większa niż czerwona (min) to mamy inwersję i scalamy (UNION) obie grupki. Jedną (mniejszą) z niebieskich kropek eliminujemy i kontynuujemy.

Jeśli niebieska kropka (max) jest mniejsza niż czerwona (min) to żaden element z pierwszej grupki nie jest w inwersji z żadną inną grupką. Dlatego zapominamy o pierwszej grupce. I postępujemy tak samo dalej.

Co teraz ? Teraz zliczamy ilość zbiorów.

Czy to jest ok ? Ma ktoś pomysł na szybszą implementację ?
Uniwersytet Wrocławski Instytut Matematyczny - rekrutacja 2018
Góra
Mężczyzna Offline
PostNapisane: 25 wrz 2015, o 19:36 
Użytkownik

Posty: 59
Lokalizacja: Polska
Find union to overkill w tym przypadku, bo masz znaleźć tylko ilość składowych. Wyrzuć z twojego algorytmu operacje union oraz przerzuć szukanie maksimów i "scalanie składowych" (nie scalaj, tylko zliczaj je według twojego pomysłu z minimami i maksimami) do drugiej części kroku 2.
Góra
Mężczyzna Offline
PostNapisane: 25 wrz 2015, o 20:16 
Użytkownik

Posty: 1936
Lokalizacja: Warszawa
0. Powiedz coś więcej proszę.
1. Ogólna idea ok ?
2. To działa ?

-- 28 wrz 2015, o 10:22 --

Ok, przedstawię coś takiego:
1. Policzmy tablicę sufixową dla minimów. Tzn. dla każdego sufixu znamy minimum.
2. Sprawdzamy jakie jest minimum na przedziale . Okazuje się, że to . Wówczas lecimy 1…i i wszystkim elementom nadajemy id = 1. Potem powtarzamy to samo (nadając coraz to większe id), w konsekwencji jesteśmy w sytuacji takiej:
Obrazek
Zauważmy, że minima są posortowane rosnąco od lewej do prawej. Stąd jeśli maximum (kropka niebieska) ze zbioru o id = k jest mniejsze niż minimum (czerwona kropka) zbioru k+1, to tym bardziej jest mniejsze niż minima zbiorów o większych id, a więc zbiór k-ty nie może zostać z niczym scalony scalony. Wtedy przechodzimy do kolejnej grupki.
Jeśli jednak niebieska kropka zbioru k-tego jest większa niż czerwona kropka k+1-go to wszystkim elementom zbioru k+1-go nadajemy id = k – scaliliśmy dwa zbiory. Następnie eliminujemy jednego z kandydatów na maximum i kontynuujemy algorytm.

(znalezienie maximum dla każdej grupki może zostać zrealizowane w czasie liniowym)
Góra
Utwórz nowy temat Odpowiedz w temacie  [ Posty: 3 ] 


 Zobacz podobne tematy
 Tytuł tematu   Autor   Odpowiedzi 
 5 zadania z permutacji  johny_wav  3
 liczba cykli długości 4 w grafie G  JakubCh  0
 Wyznacz liczbę naturalną n (poziom R)  damian18833  1
 typ permutacji oraz ich ilosc  Instru  1
 drzewa, część wspólna spójnych podgrafów  anilahcim  4
 
Atom [Regulamin Forum] [Instrukcja LaTeX-a] [Poradnik] [F.A.Q.] [Reklama] [Kontakt]
Copyright (C) Karpatka.pl