English
Forum jest zablokowane. Podczas blokady nie można dodawać ani edytować wiadomości.
Ostatnie posty
Składam wniosek formalny o usunięcie Juliusza Phama
Potwierdzam
Potwierdzam
Potwierdzam
Kilka małych i średnich testów, wszystkie losowe, smacznego!
https://drive.google.com/file/d/1l-lYXhk6L6e0IwMrfr7ni9RCh8-99o1p/view?usp=sharing
https://drive.google.com/file/d/1l-lYXhk6L6e0IwMrfr7ni9RCh8-99o1p/view?usp=sharing
Dziękuję bardzo :)
76 zróżnicowanych maxtestów
https://easyupload.io/5oge7x
https://easyupload.io/5oge7x
u mnie działa
🥴👍
Ktoś pójdzie k-tego dnia jeśli należy do podzbioru wielkości k, który nie dzieli wspólnego zaklęcia. Żeby znaleźć minimalny taki zbiór dla każdego zaklęcia musimy wybrać co najmniej jedną (z dwóch) osób nie znających tego zaklęcia. Chcemy zatem rozwiązać problem minimalnego pokrycia wierzchołkowego z małym ograniczeniem na wielkość zbioru.
Tutaj jest bardzo proste rozwiązanie w O(2^k*m): https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/10ExtendingTractability-2x2.pdf
Możemy lekko zmodyfikować to rozwiązanie wybierając krawędz która łączy dwa wierzchołki ze stopniem wyjścia co najmniej 2 i rozpatrując 3 przypadki: nie bierzemy jednego końca, nie bierzemy drugiego końca, bierzemy oba. Jeśli nie bierzemy jakiegoś wierzchołka to musimy wziąć wszystkie wierzchołki sąsiadujące z nim, więc każdy z tych przypadków zmniejsza k o co najmniej 2 dając nam maksymalnie O(3^(k/2)) przypadków.
Jeśli nie jesteśmy w stanie wybrać takiej krawędzi to wszystkie spójne będą gwiazdami więc możemy dokończyć pokrycie w O(m).
Tutaj jest bardzo proste rozwiązanie w O(2^k*m): https://www.cs.princeton.edu/~wayne/kleinberg-tardos/pearson/10ExtendingTractability-2x2.pdf
Możemy lekko zmodyfikować to rozwiązanie wybierając krawędz która łączy dwa wierzchołki ze stopniem wyjścia co najmniej 2 i rozpatrując 3 przypadki: nie bierzemy jednego końca, nie bierzemy drugiego końca, bierzemy oba. Jeśli nie bierzemy jakiegoś wierzchołka to musimy wziąć wszystkie wierzchołki sąsiadujące z nim, więc każdy z tych przypadków zmniejsza k o co najmniej 2 dając nam maksymalnie O(3^(k/2)) przypadków.
Jeśli nie jesteśmy w stanie wybrać takiej krawędzi to wszystkie spójne będą gwiazdami więc możemy dokończyć pokrycie w O(m).
Jak się dobrze zastanowić to twój wykładniczy dynamik liczy tak naprawde dla każdego mędrca "jaka jest najmniejsza grup mędrców, taka, że x do niej należy, oraz dla każdego zaklęcia istnieje mędrzec z tej grupy który go nie zna".
Ponieważ każde zaklęcie jest "nieznane" przez dokładnie dwóch mędrców (a,b) to oznacza, że albo a musi się znaleźć w tym zbiorze albo b. Czyli jeżeli narysujemy krawdzie miedzy (a,b) to szukamy tak naprawde Min Vertex Cover, oraz takich wierzchołków, które znajdują się w co najmniej jednym Min VC. Ten problem w ogólności jest NP, ale nas interesuje tylko minimalny VC który ma rozmiar mniejszy niż k. To już da się łatwo zrobić w O(n2^k), ale okazuje się, że można zbić podstawe wykładnika z 2 do czegoś mniejszego (już 1.5 powinno być OK), jest kilka algorytmów, ja klepałem 2.2 z https://www.mimuw.edu.pl/~malcin/dydaktyka/2012-13/fpt/fpt_01_branching.pdf
Ponieważ każde zaklęcie jest "nieznane" przez dokładnie dwóch mędrców (a,b) to oznacza, że albo a musi się znaleźć w tym zbiorze albo b. Czyli jeżeli narysujemy krawdzie miedzy (a,b) to szukamy tak naprawde Min Vertex Cover, oraz takich wierzchołków, które znajdują się w co najmniej jednym Min VC. Ten problem w ogólności jest NP, ale nas interesuje tylko minimalny VC który ma rozmiar mniejszy niż k. To już da się łatwo zrobić w O(n2^k), ale okazuje się, że można zbić podstawe wykładnika z 2 do czegoś mniejszego (już 1.5 powinno być OK), jest kilka algorytmów, ja klepałem 2.2 z https://www.mimuw.edu.pl/~malcin/dydaktyka/2012-13/fpt/fpt_01_branching.pdf
Chciałby ktoś się podzielić ideą rozwiązania do Mędrców?
Ja jedyne na co wpadłem to programowanie dynamiczne na maskach bitowych o złożoności wykładniczej.
Dla każdego mędrca liczę którego dnia pójdzie na wieczny spoczynek (o ile będzie on pierwszym takim mędrcem). W tym celu początkowo zakładam, że zaklęcia które on zna to jedyny zaklęcia jakie są (usuwam pozostałe) i liczę dla wszystkich pozostałych mędrców kiedy oni udają się na wieczny spoczynek (rekurencja!). Z policzonych wartości liczę minimum. Minimum + 1 to dzień w którym owy mędrzec pójdzie na wieczny spoczynek. Dlaczego? Bo jeśli do tego czasu nikt nie pójdzie na wieczny spoczynek, to znaczy, że mędrzec zorientuje się, że jego wiedza na temat wszystkich mędrców nie jest pełna - zatem musi istnieć zaklęcie którego on nie zna.
Niestety nie udało mi się algorytmu przyśpieszyć.
Ktoś chciałbym przedstawić swoje rozwiązanie?
Ja jedyne na co wpadłem to programowanie dynamiczne na maskach bitowych o złożoności wykładniczej.
Dla każdego mędrca liczę którego dnia pójdzie na wieczny spoczynek (o ile będzie on pierwszym takim mędrcem). W tym celu początkowo zakładam, że zaklęcia które on zna to jedyny zaklęcia jakie są (usuwam pozostałe) i liczę dla wszystkich pozostałych mędrców kiedy oni udają się na wieczny spoczynek (rekurencja!). Z policzonych wartości liczę minimum. Minimum + 1 to dzień w którym owy mędrzec pójdzie na wieczny spoczynek. Dlaczego? Bo jeśli do tego czasu nikt nie pójdzie na wieczny spoczynek, to znaczy, że mędrzec zorientuje się, że jego wiedza na temat wszystkich mędrców nie jest pełna - zatem musi istnieć zaklęcie którego on nie zna.
Niestety nie udało mi się algorytmu przyśpieszyć.
Ktoś chciałbym przedstawić swoje rozwiązanie?
Potwierdzam ;(
Potwierdzam
Potwierdzam