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

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.

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.

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

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.

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.

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.

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).

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).

Wydaje mi sie, że tam nie ma O(NODES^2).

Dla ustalonego korzenia dwie długie operacje (DFS osiągalności i poszukiwania nowego korzenia) przejdą w czasie liniowym względem wielkości tego drzewa. ALE: po zmianie korzenia na nowy, stare drzewo nie będzie już w nich uczestniczyć:
1. DFSa na starym korzeniu nie wywołujemy drugi raz, bo mamy informację w tokenie o osiągalności z niego
2. zapytanie o ścieżkę do kolejnego korzenia też nie dojdzie do starego drzewa - z definicji nowy korzeń nie jest w stanie do niego dojść krawędziami wychodzącymi.

Ja chyba znalazłem sposób, żeby bez żadnych hacków z czasem przesłać informację o tym, kto do kogo może wysyłać normalnie wiadomości. Załóżmy, że wierzchołek a chce powiedzieć wierzchołkowi b, czy z b istnieje krawędź do a. Będzie potrzebny jeszcze do pomocy jakiś inny wierzchołek c. Wtedy na początku b i c nasłuchują (Receive(-1)), natomiast a wysyła wiadomość do b jeśli ta krawędź istnieje lub do c jeśli nie istnieje. Jeden z wierzchołków b, c odbierze teraz wiadomość i przekaże ją do drugiego z nich. W ten sposób b na pewno dostanie jedną wiadomość i w zależności od nadawcy, może się dowiedzieć, czy ma krawędź do a czy nie.

Da się to uogólnić tak, żeby a mógł każdemu innemu wierzchołkowi (poza wierzchołkiem pomocniczym, ale go da sie łatwo ogarnąć na koniec) wysłać jakąś zero-jedynkową wiadomość w jednym przebiegu (nie będę wchodził w szczegóły, da się to łatwo wykminić). Potem każdy wierzchołek musi wysłać wierzchołkowi a info, że już odebrał to co miał odebrać. Jak wierzchołek a od każdego odbierze taki sygnał to wysyła info kolejnemu wierzchołkowi, że teraz jego kolej na wysyłanie informacji o wchodzących do niego krawędziach itd.

Potem już jest z górki, ja tam robię takiego jakby DFSa po odwróconych krawędziach (każdy pełną informację o firmach przesyła tylko jednemu gościowi - swojemu ojcu w drzewie DFS).

Złożoność to jakieś N * całkowita liczba firm, ale z jakiegoś powodu na sprawdzaczce mam TLE na ostatnim teście, chociaż u mnie na kompie działa w sekundę i wysyłam wiadomości mniejsze niż 64kb. Miał ktoś jeszcze problem ze sprawdzaczką?

EDIT: widzę, że Kamil napisał przede mną prawie to samo :/

Maciek - no jeśli tak to pewnie skminiłeś wzorcówkę i gratki.

Jarek - opisałem to samo z (a, b, c) ;p

Nie uważam, by potem było z górki. Możesz dokładniej opisać co potem robisz?

Też miałem TLE na ostatnim, mimo że na kompie działa szybko. Być może dlatego, że wiadomości się wolniej przesyłają.

EDIT: chwila moment. Maciek, nie próbujesz każdej z NODES^2 krawędzi? DFS-y rzeczywiście odwiedzą O(NODES) wierzchołków, ale problemem jest być może liczba wiadomości, które zgaduję że są wolne. Czyli liczba próbowanych krawędzi. Czy może od razu szybko znajdujesz postać drzewa i tylko O(NODES) krawędzi dotkniesz?

> Maciek, nie próbujesz każdej z NODES^2 krawędzi? DFS-y rzeczywiście odwiedzą O(NODES) wierzchołków, ale problemem jest być może liczba wiadomości, które zgaduję że są wolne. Czyli liczba próbowanych krawędzi. Czy może od razu szybko znajdujesz postać drzewa i tylko O(NODES) krawędzi dotkniesz?

W DFSie na pełnym grafie wszystkie krawędzie będą odwiedzone. Ale jest trochę równoległe :) W pierwszym "takcie" wiadomości rozsyła korzeń, w drugim wierzchołki odległe o 1, itd. Także wszystkie wierzchołki zostaną odwiedzone po co najwyżej N taktach, a ich odpowiedzi wrócą do korzenia po co najwyżej N kolejnych.

No chyba że wiadomości wysyłane z jednego węzła do różnych innych węzłów też się nawzajem istotnie blokują? Mam nadzieję, ze nie, ale i tak nie przychodzi mi do głowy scenariusz, w którym kwadraciło by to czas oczekiwania.

Moja druga część algorytmu wygląda mnie więcej tak:
- jest procedura dfs (v):
dla każdej krawędzi u -> v:
---- wyślij wiadomość z jednym zerem do u
---- poczekaj na dane zwrócone przez u i dopisz je do swoich informacji (te dane to: numery wierzchołków z których pochodzą i wartości akcji firm)
- wszystkie wierzchołki poza 0 (który jest na początku korzeniem) nasłuchują, nasłuchiwanie polega na tym, że jeśli odbierzemy wiadomość od kogoś to:
a) jeśli wiadomość nie pochodzi od kogoś, do kogo mamy krawędź lub pochodzi od kogoś, kto już nam wysyłał takiego requesta, to przełączamy się w tryb korzenia, w przeciwnym wypadku:
b) jesli nie robiliśmy dfsa to robimy
c) jeśli nie wysyłaliśmy nikomu naszych informacji to wysyłamy
jeśli wysyłaliśmy to wysyłamy -1 albo coś w tym stylu
- można zauważyć, że jeśli w grafie jest cykl to może się zrobić deadlock, więc tak naprawdę, kiedy jest ta linijka "poczekaj na dane zwrócone...", to trzeba wtedy nasłuchiwać od wszystkich i jeśli dostaniemy wiadomość "0" to od razu odpowiadamy "-1"
- wierzchołek 0 jest na początku korzeniem, czyli robi następujące rzeczy:
a) odpala dfsa
b) sprawdza, czy posiada informacje od wszystkich. Jeśli tak, to udziela odpowiedzi
c) w przeciwnym wypadku wysyła wiadomość do wierzchołka o kolejnym numerze - teraz on się staje korzeniem

Na koniec trzeba zadbać, żeby wszystkie wierzchołki wyszły ze stanu nasłuchiwania - to już są jakieś szczegóły z wykorzystaniem wierzchołka 0, któremu trzeba zgłosić, że się znalazło odpowiedź, a potem on wysyła wiadomość o zakończeniu do n - 1, ten wysyła do n - 2 itd.

Tak jak ja to napisałem, wysyłanych jest O(liczba krawędzi) wiadomości, jedna po drugiej, co może być trochę słabe (ale raczej nie jest jedynym powodem TLE na SIO, bo w trzecim teście i tak jest tylko 99 krawędzi). Da się jednak zrównoleglić tego dfsa, tak że najpierw wysyłamy wszystkie wiadomości z prośbą o dane, a potem nasłuchujemy na wszystkie odpowiedzi

Jarosław Kwiecień: ja miałem problem ze sprawdzaczką ale w drugą stronę - czekam na prywatne wyniki.