Liczba*

He said his solution was wrong so he removed the testcases.

Maciek - miałem podobne rozkminy i być może jest to za wolne, bo przesłanie O(NODES^2) wiadomości jedna po drugiej jest dosyć wolne. Też robię tak, że prawie wszystkie wierzchołki nasłuchują i coś się dzieje. Też wyznaczam jakiś korzeń i potem identycznie robię trzecią część. Problem w tym, że nic tu się nie dzieje jednocześnie (algorytm właściwie nie jest rozproszony :D ) i pewnie dlatego mam dobre czasy na kompie i TLE na dużych testach na sio. Ale nie wiem, może jedynym moim problemem były za duże wiadomości, bo zapomniałem je dzielić na mniejsze w tym zadaniu (w ostatniej części).

Weird, I can not open this link on my computer..
https://www.dropbox.com/s/wznmedsym0gfkw6/car-male.zip?dl=0&m=
Is it correct?

Moje rozwiązanie (choć nie jestem pewien implementacji):

Większość życia węzły spędzają w pętli Receive(-1) nasłuchując wiadomości wszystkich typów. Każdy wierzchołek wie, ile zawirusowanych wiadomości dostał od każdego innego. Każda kolejna będzie mieć inne znaczenie, więc typ wiadomości da się ustalić bez względu na to, czy wiadomość jest zawirusowana czy nie.

Każdy wierzchołek zna wszystkie krawędzie wchodzące, i wysyła w drugą stronę pierwszą Potencjalnie Zawirusowaną wiadomość: "jestem Twoją krawędzią wychodzącą". Zakładamy, że wszystkie wierzchołki odbiorą taką wiadomość w odpowiednim momencie, choć mi to sprawiło trochę problemów implementacyjnych.

Próbujemy zbudować drzewo wchodzące do pewnego korzenia. Potencjalny korzeń zawsze trzyma token, zawierający informację o tym, które z wierzchołków są osiągalne krawędziami wchodzącymi. W tym celu robi po nich DFSa - wywołanie DFSa następuje drugą Potencjalnie Zawirusowaną wiadomością. Każdy wierzchołek odpowiada tylko na pierwsze wywołanie DFSa, a wywołujący wierzchołek zostaje jego rodzicem. Pozostałe wywołania dostają pustą odpowiedź.

Teraz korzeń wie, które wierzchołki są osiągalne z niego wchodzącymi krawędziami. Jeśli wszystkie, to w podobny sposób rozsyła trzecią Potencjalnie Zawirusowaną wiadomość: "wyślijcie dane". Po zebraniu danych węzły kończą pracę.

Jeśli nie, to chce znaleźć nowy korzeń - wierzchołek, który nie znajduje się w jego drzewie. Więc rozsyła zapytanie o to, czy ktoś ma krawędź wychodzącą do takiego wierzchołka. Wierzchołek w drzewie, który może wysyłać do wierzchołka poza drzewem, zwraca odpowiedź na zapytanie krawędziami drzewowymi. Wewnątrz odpowiedzi znajduje się ścieżka, którą powinien być przekazywany token (ta sama, którą szło zapytanie).

Mój pierwszy pomysł na wyznaczenie ludzi, do których mogę przesyłać informacje był taki (nawet zaimplementowałem i działał, ale potem miałem dużo hardszy i szybszy algos do tego):

Chcę wiedzieć czy A może wysyłać do B. To robię tak: A wysyła liczbę 1 do B. B otrzymuje tę wiadomość i wie, czy była to jedynka (czyli czy A może mu wysyłać). Teraz musi przekazać tę informację wierzchołkowi A. Zrobimy to samymi pustymi wiadomościami. Jest sobie jakiś inny wierzchołek pomocniczy C (np. C = B + 1, chyba że B + 1 = A). Jeśli B otrzymało 1, to wysyły pustą wiadomość do A, który przez "int from = Receive(-1)" dowiaduje się, żę dostał od B (pustą) wiadomość - wnioskuje z tego, że B otrzymał jedynkę. Jeśli natomiast B otrzymało 0, to wysyła pustą wiadomość do C, który wie, że ma wysłać pustą wiadomość do A. A otrzymuje pustą wiadomość od C (a nie od B) i to mu mówi, że B otrzymało nie-jedynkę. Jeszcze w pierwszym przypadku po zakończeniu tego A powinno wysłać pustą wiadomość do C, by odmrozić C, który inaczej by nasłuchiwał w nieskonczoność.

Łatwo to napisać w O(NODES^2), ale da się zrównoleglić do O(NODES) - po prostu trzeba jednocześnie przetwarzać NODES/3 rozłącznych trójek A,B,C i to synchronizować. Miałem to napisane w jakiejś tam wersji, ale potem i tak okazało się niepotrzebne.

Przemysław: Nie, każda instancja musi się normalnie zakończyć. Inaczej dostaniesz komunikat "all instances have either terminated or are deadlocked". Jak się zdedlokują na serwerach, to po prostu musi to być traktowane jako TLE.

Nie mogą nasłuchiwać w nieskończoność. Radziłem sobie z tym tak, że szef pamietał ile razy do każdej instancji wysłał (pustą) wiadomość. Powiedzmy, że to było zawsze 0 albo 1. To teraz szef wysyła każdej instancji jeszcze puste wiadomości, by liczba wysłań do każdej instancji była równa 2, a każda instancja niech wie, że ma przestać nasłuchiwać po drugim otrzymaniu (pustej) wiadomości od szefa. Możliwy wariant: kończy nasłuchiwać, gdy drugi/trzeci raz dostaje wiadomość od tego samego gościa.

Czy instancje mogą nasłuchiwać w nieskończoność, jeśli dokładnie 1 inna wypisze wynik?

Ja też nie umiem zrobić zadania, ale też się wypowiem. Umiem śmiesznym hakiem wyznaczyć wszystkich ludzi, którzy odbierają moje wiadomości, co wydałoby się z pozoru niemożliwe :P.

Na początku oczywiście wyznaczam ludzi, którzy do mnie umieją wysłać wiadomość. Na chwilę wywalam wierzchołek 0 z grafu, zapominam o jego istnieniu. Następne następuje faza przesyłu wiadomości "Słyszę cię". Każdy wierzchołek wysyła pustą wiadomość do każdego z ludzi, którzy wysłali mi sensowną wiadomość. Następnie każdy wierzchołek w while(1) odbiera Receive(-1) nasłuchując ludzi, którzy mu wysłali ową wiadomość "słyszę cię". Problem jest taki, że nie wiem kiedy przestać i w końcu zawieszę się na Receive(-1) a nikt nie będzie mi chciał już wysłać nowej wiadomości. I tu do gry wkracza wierzchołek 0. Na początku programu każę mu iść spać na sekundę. Po tej sekundzie jak 0 się budzi wysyła wszystkim wiadomość "wybudzam cię ze snu" i po prostu każdy wierzchołek wie, że jak otrzymał wiadomość od 0, to była to wiadomość o wybudzeniu, a przez to, że te wiadomości wyszły dużo później można trzymać kciuki, że przyjdą one później niż wiadomości o słyszeniu.

Jest problem techniczny, że nie wiem kogo słyszy 0 ani kto słyszy 0, więc zapuszczam tego algosa trzykrotnie dla wierzchołków 0, 1, 2.

Ta informacja pozwala łatwo rozwiązać zadanie dla DAGa, każdy wierzchołek wybiera sobie dowolnego gościa, do którego idą jego wiadomości i są one wtedy tak drzewowo przepychane aż do jedynego wierzchołka, który umie zebrać wszystko.

Słyszałem, że da się tę informację także wyznaczyć bez takich haków ze sleepami, które opisałem (w ogóle na SIO sleep nie działa, clock() daje rule violation itd, więc musiałem sobie napisać własnego sleepa, który był jakąś pętlą obracająca się 4*10^8 razy z jakimś dummy obliczeniem i miałem też trochę kłopotów z tym, że kompilator mi ją za wszelką cenę optymalizował i wywalał xd). Taka informacja jest raczej konieczna do zrobienia zadania, ale still jest ono w mojej opinii bardzo trudne.

Główne pomysły miałem takie, że należy najpierw znaleźć wierzchołek w grafie, który jest osiągalny z każdego innego (dalej z górki), oraz że należy mocno korzystać z Receive(-1). Samymi pustymi wiadomościami możemy bardzo duzo osiągnąć. U mnie często wszystkie instancje nasłuchiwały, tzn. czekały za pomocą Receive(-1), a tylko jeden wierzchołek cokolwiek robił. Pamiętajmy, że Receive(-1) zwraca inta z przedziału [0, NODES-1], co bardzo pomaga, bo pozwala jakieś informacje przekazywać.

Mam trochę za wolne rozwiązanie i nie przechodzę ostatniego sampla. Liczę na ~5 punktów, więc lepiej, jeśli ktoś inny opowie rozwa.

Czy ktoś, kto zrobił Skup akcji [A] miałby ochotę podzielić się rozwiązaniem?

skąd wiesz, że już nie ustawisz? bo ja tylko zauważam na bieżąco, gdy kwadraty nachodzą na siebie. puste miejsca muszę na końcu policzyć.

Ja mam to samo rozwiązanie, tylko kończę ustawianie dla danej wysokości od razu jak widzę, że już nie ustawię i mam najgorszy czas 0.05s ;P

Działka jest uruchamiana na 100, a Test na 100 i 40. Niektórzy mogą potrzebować sprawdzenia na mniejszej liczbie instancji.