Jak zrobiliście zadanie?

NIE MÓWIĆ!! Pasek na górze mówi, że runda została przedłużona o 4 godziny!!
Nie wiem, na ile ten pasek mówi prawdę, bo nigdzie indziej nie ma o tym żadnej wiadomości, ale przezorny zawsze ubezpieczony.

Pasek na górze chyba mówi o zadaniu MAK2, ponieważ zadań z 4 rundy już się nie da submitować.

randomowo :)

zasadnicza idea:
trzymam w hasmapie zapytania o pary z zadania.
dla każdego delikwenta szukam w jedną i drugą stronę najbliższego sąsiada.
Zapisuję te informacje kompresując długie ścieżki np:
od 1 do 2 5 kroków do 4 7 kroków
od 2 do 1 5 kroków do 6 2 kroki
itd
każdy node dostaje określone podzapytania do policzenia zbieram to do kupy w jednym z nich a ten na końcu kwadratowo dla każdej pary szuka rozwiązania (200*200) powinno się mieścić

jedno ale
należy się obronić przed złośliwymi testami dlatego na początku dodaję randomowo tak do 2000 nodow trzeba sobie z nimi potem poradzić w postprocesingu

test przykładowy :

0a OK 0.14s/1.00s 10 0/0
0b OK 0.80s/5.00s 20

A przydałoby się przełużyć, chociażby ze względu na to jak muliła sprawdzarka przez ostatnie pare godzin ^^

Rzeczywiście, trafna uwaga :). W takim razie - random :P. Losujemy początkowe pozycje i z nich się rozchodzimy do sąsiadów zbierając po drodze napotkanych gości, którzy należą do różnych zapytań. To daje złożoność O(max przerwa pomiędzy pozycjami startowymi), co jak nie mamy ogromnego pecha, to powinno być rzędu niewiele większego od n/100 (choć możliwe, że to jest bardziej jakieś n log 100 / 100, ale w zasadzie to nie wnikałem, to tylko niesprawdzone podejrzenia, możliwe że to bzdura). Ale aby niepotrzebne nie nabijać złożoności, to trzeba mieć szybki lookup, tzn. stwierdzić, czy gość o numerze x należy do naszego zbioru pozycji startowych i czy jest gościem z zapytania. W tym celu trzeba było użyć jakichś hash_table'ów. Trzeba było znać unordered_cosie i wiedzieć, że należą do STLa (spełniałem to pierwsze, ale po lekturze ustaleń technicznych moja niewiedza doprowadziła mnie do wniosku, że nie można ich używać, podczas kiedy można) albo naklepać ręcznie chociażby prowizoryczne ich wersje.
Moje rozwiązanie tutaj: http://pastebin.com/f0YPWVd0
Moim (i nie tylko moim), na pewno trudniejsze od SEK :P. Dla mnie i do rozkminy (choć to mi na szczęście poszło bardzo szybko, ale jednak pomysł nietrywialny, a w SEK bardzo łatwy) i do naklepania.

Ja na początku używałem unordered_mapy/seta, ale na jednym z ostatnich próbnych uruchomień odkryłem że na zwykłej mapie/secie działa prawie 2,5x szybciej O.o

Ja robiłem deterministycznie. Pierwsza maszyna rozdziela po równej długości łuki koła. Następnie każda maszyna sprawdza czy nie istnieje któraś z wartości (b-s), dla każdego punktu łuku. O(nlog m / B).

Po równej długości łuku koła? Niby jak, przecież nie masz zielonego pojęcia, gdzie na kółku są ludzie o danych indeksach, na tym polega cała trudność zadania.

Mój pomysł był taki: Centralny node wysyła zapytania postaci (A, B, kierunek) do pozostałych. Jeśli któryś da niepustą odpowiedź, tzn. dotarł do kolejnego punktu na ścieżce do A, powtarzamy proces aż dojdziemy i przetwarzamy kolejne query.
Jeśli wszystkie dadzą pustą odpowiedź, każemy jednemu z nich iść od A w ustalonym kierunku, a pozostałym od losowego miejsca w ustalonym kierunku o K kroków (K - duża liczba, proporcjonalna do liczby studentów i odwrotnie proporcjonalna do liczby node'ów).

Pozostałe node'y przechowują listę unordered_map, w których przechowujemy te długie sekwencje kroków w postaci (nr studenta -> który w sekwencji), dodatkowo dla każdej mapy pamiętamy numer pierwszego i ostatniego studenta. Kiedy dostaniemy zapytanie, przeglądamy te mapy i dla każdej jesteśmy w stanie w czasie stałym odpowiedzieć, czy mamy dany numer, odsyłamy wtedy do serwera numer nowego studenta (z dalszym kierunkiem) i przebytą odległość. Ew. jeśli w tej mapie mieliśmy też docelowego studenta, odsyłamy tę informację razem z odległością.

Naklepałem to (zajęło ok. 300 linii) i nawet działało - niestety po testach okazało się (czego wcześniej nie doczytałem (w "o zadaniach rozproszonych"), że jeden node może wysłać do 1000 wiadomości, a u mnie centralny wysyłałby dużo więcej.
Niewykluczone, że i tak by to było niewydajne, już nie sprawdzałem. :P

"Po równej długości łuku koła?" Pierwsza maszyna przechodzi całe kółko:)

@Krzysztof Jamróz - to po co wtedy inne maszyny?

Co do złożoności tej metody, której większość jak widzę użyła (losowego wybrania 100 punktów i kazania wszystkim node'om pójścia w obie strony, aż do napotkania sąsiedniego punktu) - oczekiwana długość najdłuższego fragmentu losowo wybranego jest równa n/N*H_N, gdzie n-ilość ludzi, N-ilość node'ów, natomiast H_N to N-ta liczba harmoniczna, która asymptotycznie jest rzędu logN.
Zatem spodziewana złożoność to O(n/N * logN)
Źródło: http://math.stackexchange.com/questions/14190/average-length-of-the-longest-segment - co prawda, tutaj nie jest kółko, a prosty odcinek, ale myślę że wielkiej różnicy to nie robi ;)

Moje rozwiązanie wyglądało tak:

Losujemy na początek pewien podzbiór uczniów (ja losowałem 30 * ilość nodów czy coś i usuwałem duplikaty) i dla ułatwienia dodajemy jeszcze do niego uczniów, którzy należą do jakiegoś zapytania (robi to maszyna 0 i potem przesyła pozostałym maszynom). Zbiór tych studentów nazwijmy K.

Średnia odległość między kolejnymi z wybranych studentów to n/|K| (n to NumberOfStudents()). Bardzo mała jest szansa, że między jakąś parą będzie znacznie większa (nie liczyłem tego, no ale prawo dużych liczb...).

Teraz rozdzielamy po równo wybranych studentów między nody.

Każdy node dla każdego z własnych studentów s1 idzie sobie w obie strony, aż dotrze do innego studenta s2 ze zbioru |K| (ja to sprawdzałem za pomocą hash_mapy - nie wiem czy to dobrze, dla największego testu przykładowego miałem ciut ponad 2 sekundy). Jeżeli tak jest, to tworzymy krawędź (s1,s2,d), gdzie d to policzona długość.

Wadą tego rozwiązania jest to, że każda krawędź zostanie znaleziona dwa razy (idąc od obu studentów)

Takie krawędzie wysyłamy do node 0. Następnie usuwamy wszystkich studentów w zbiorze K, którzy nie należą do żadnego zapytania - oczywiście będzie polegać to na tym, że łączymy obie krawędzie w takim delikwencie i samego delikwenta kasujemy. (to z powrotem na node 0)


Pozostaje nam graf, który ma nie więcej niż NumberOfQueries()*2 wierzchołków. Można teraz liczyć odległość dfsem - oczywiście można kombinować z ładniejszym rozwiązaniem, ale po co :).

Co do rozwiązania Marcina - też myślałem, żeby powrzucać więcej wierzchołków do tego podzbioru (ty masz 30*N), ale ostatecznie postanowiłem to uszczuplić do po prostu N losowo wybranych, i tych z zapytań. Powodem ku temu była konieczność sprawdzania w każdym kroku algorytmu przynależności ucznia do zbioru, co powiększyłoby stałą w złożoności. Z drugiej strony, zmniejszasz tym samym oczekiwaną maksymalną odległość pomiędzy sąsiadami. Z trzeciej strony, dochodzi zapewne jakiś efekt związany z koniecznością komunikacji pomiędzy node'ami. Ciekawe który efekt ma największy wpływ na szybkość...

Zauważamy, że jeśli droga z A do B wiedzie przez C, to |AB|=|AC|+|BC| :)
Ze wszystkich zapytań spisujemy "points of interest" do vectora, ewentualnie dodajemy jeszcze jeden punkt, ucznia numer 1.
Sortujemy, usuwamy powtórzenia. Deterministycznie, więc każdy slave generuje sobie taki sam vector. I teraz pętla: dopóki tacy istnieją, wybierz któregoś "niezrobionego" ucznia, idź w lewo lub prawo tak długo, aż spotkasz następny point of interest (binary search na vectorze). Wyślij do mastera informację, że te dwa punkty dzieli taka odległość, czekaj na odpowiedź.
Master przyjmuje wiadomości, nanosi w mapie, że ten odcinek jest "zrobiony", odsyła aktualną zawartość mapy.
Gdy slave nie ma już nowych odcinków do zrobienia, powiadamia mastera, że skończył. Gdy wszystkie slave'y skończą, master skleja posiadane odcinki w wielokąt, przechadza się od ucznia nr 1 w dowolną stronę i notuje dla każdego point of interest odległość od 1. Na końcu, dla każdego zapytania, |XY| = ||X1| - |1Y||, bo |1X|+|XY|=|1Y|, przy czym jeśli wyjdzie |XY|*2>n, to zwracamy n-|XY| (bo |11|=0 lub n).

Problem z "wszyscy już skończyli, tylko jeden slave biegnie po łuku 270 stopni" można rozwiązać poprzez odjęcie od n sumy pozostałych odcinków. Problem robienia odcinka "z dwóch stron naraz" można naprawić tak, że po milionie kroków slave robi przerwę, stawia tam nowy point of interest, raportuje go do mastera i bierze sobie inny odcinek do zrobienia.

Komputer 0 robi za huba i rozdaje pytania.
Każdy komputer ma zestaw wierzchołków specjalnych.
Wierzchołkiem specjalnym są wierzchołki z zapytań testowych (każdy komp czyta wszystkie m<=200) oraz 900-m wierzchołków wygenerowanych regeneratorem pseudolosowym (seed jest na twardo wpisany w program, każda instancja dostanie ten sam zestaw).
Pytaniem zadawanym przez hub jest numer wierzchołka specjalnego. Odpowiedzią, numery najbliższych (w obu kierunkach) wierzchołków specjalnych oraz odległości od nich.
Hub rozsyła pierwsze NumberOfNodes()-1 pytań do robotników i czeka na odpowiedź od kogokolwiek. Gdy jakąś otrzyma i ma jeszcze do zadania pytania, wysyła je, jeśli pytania się skończyły, wysyła "pytanie" "-1" każące zakończyć proces.
Jak widać, liczymy nadmiarowo, każdy student jest pytany o sąsiadów przez dwie różne instancje. Da się to poprawić (lecz nie do x1) ale kosztem skomplikowania i większych transferów.

Odpowiedzi zamieniane są w krawędzie i trzymane w mapie (mapa numer wierzchołka wyjściowego -> para(krawędź)) a krawędź to cel i odległość, może przekombinowałem;).
Po zebraniu wszystkiego hub wybiera jeden z wierzchołków, traktuje go jakby był na pozycji 0 i przechodzi nasz graf (składający się z <=900 wierzchołków i będący kołem). Każdy wierzchołek i odległość od pierwszego wrzucane są do kolejnej mapy int->int. Teraz z mapy odczytujemy dla każdego zapytania testowego pozycje pierwszego i drugiego studenta, odpowiedz to oczywiście abs różnicy lub n-abs rożnycy.

Rozkład długości nieprzerwanych przedziałów z grubsza można przybliżyć rozkładem wykładniczym z parametrem n/liczba_podziałów.
Bardzo zgrubnie licząc przy 700 losowych wierzchołkach odcinek o długości >2*10^7 pojawia się z prawdopodobieństwem 6*10^-4, odcinek o długości 3*10^7 z p = 5*10^-7.

Trochę mało elegancko napisane,a le jest;)
http://pastebin.com/DmQyta3S

Gdy każdy komputer startuje z jednego wierzchołka, to tak jak mówi Adam dostajemy oczekiwaną liczbę kroków Θ(n/N log N) na najwolniejszym komputerze. Natomiast jeśli każdy komputer startuje z Ω(log N) wierzchołków, to dostaniemy oczekiwaną liczbę kroków Θ(n/N).

Ja mam 100N wierzchołków startowych. Przynależność do zbioru sprawdzam w czasie stałym, w dwóch odwołaniach do pamięci, przy pomocy perfekcyjnego haszowania. Wreszcie nadarzyła się okazja, żeby tego użyć!

No nie mogę, nie mogę, nie mogę, ale jestem zły! Dostałem 1 pkt, bo mój generator liczb losowych, który przekleiłem z zadania Kryształ sprzed roku generował bardzo nielosowe liczby (generator co prawda "Potyczkowy", ale jego parametry wpisane bez większego myślenia (błąd!) z palca przeze mnie).
Ja już wiem, czemu w tej postaci jest on bardzo kiepskim generatorem i polecam wam, abyście też chwilę nad tym pomyśleli:
http://pastebin.com/8B4Vhgy1

Ja, żeby na pewno mieć deterministyczne i dobre liczby losowe, wkleiłem sobie 100 losowych liczb do kodu na początku :)

Wojtek Nadara: A dlaczego nie używać zwykłego randa? Nie jest tak rozbudowany jak generatory dostarczone wraz z Cpp11, ale w tym przypadku powinien chyba wystarczyć. Albo można użyć biblioteki random, która jeśli mnie pamięć nie myli, powinna być wspierana podczas zadań rozproszonych.
Ale nie martw się, też zepsułem to zadanie strasznie. Nie mam pojęcia dlaczego nie widziałem tutaj pewnych oczywistości. No nic, mamy jeszcze ostatnią rundę do odkucia się.

Tak jak Dominik, korzystałem z nowości. mt19937 gen(145788); Wartość 147588 jest bez znaczenia:) Nawet się zdziwiłem, bo byłem pewien, że <random> nie działa w pełni w gcc4.7.2.
10/10, choć jeden test zafluktował niebezpiecznie. W ocenianym uruchomieniu: 7 OK 1.92s/2.00s we wcześniejszym: 7 OK 1.25s/2.00s
Podoba mi się sposób Jakuba:)

a ja jako generatorki liczb losowych użyłem sobie zwykłej rekurnecji tab[i]=3*tab[i-1]+2*tab[i-2]+tab[i-3] mod n i działa pięknie :)

Ok, to jeszcze raz pytanie: co jest nie tak ze zwykłym randem?

Jest wszystko ok, tylko mi się pomyliło i myślałem, że on zależy od czasu, a chciałem mieć wygodnie i każdą instancją sobie je wyliczałem w taki sam sposób. W tym zadaniu niewiedza zabolała mnie dwukrotnie - raz te unorderedy, a raz rand() :(.

Hmmmm, mam 8/10 punktów, ale we wcześniejszym zgłoszeniu dostałem 9. A jedyną różnicą było to, że wyifowałem przypadek gdy node'ów jest więcej niż studentów, żeby wtedy nadmiarowe komputery się wyłączyły. Co najlepsze, przypadek, który się zepsuł ma numer 8, czyli raczej z dużą liczbą studentów... Nie wiem, czy może serwer miał jakieś większe obciążenie w tamtym momencie, czy takie jednokrotne sprawdzenie ifa miało taki wpływ :/

Adam Krasuski: Jeden if nie powinien nic zmieniać. Pobranie jakiejś wartości z biblioteki też (raczej) nie. Aczkolwiek zawsze każdą wartość, jeśli się da to pobieram tylko raz (np. liczbę instancji wrzucam sobie do zmiennej na początku programu). Ogólnie dla tak małej liczby uczniów jak sto, czy nawet kilka zer więcej, nie opłaca się rozpraszać i można rozwiązać problem na jednym komputerze.

No właśnie też tak uważam, że to pomijalna różnica. Dodatkowy kod pomiędzy dwoma zgłoszeniami jest następujący:

N=min(N,n);//so that there is not an excess of computers
if(id>=N){return 0;}//there is an excess of computers

i tyle (oczywiście kod nie jest wykonywany w pętli, itp. - tylko jednokrotnie, na samym początku programu). A mimo to pół sekundy, albo i wiecej, różnicy na ósmym teście. Zapewne więc tak jak mówiłem, miałem pecha i trafiłem na moment ze spowolnionymi komputerami.

Zbyt mało kodu aby to można jakoś ocenić, ale jeśli masz jeden komputer poświęcony na synchronizację to czy nie powinna być tam nierówność ostra?
Poza tym, czy to nie jest tak, że obciążenie sprzętu nie powinno wpływać na przyjmowany czas działania programów?

No się zastanawiam. Wiem że na olimpiadzie informatycznej wszystko jest uruchamiane na wirtualnej maszynie, a jako miarę czasu brane są cykle procesora, czy coś podobnego. Nie wiem jak jest tutaj.

Co do nierówności - chyba nie, bo jeśli byłyby np. 3 studenty i 5 komputerów, to N=min(3,5)=3, czyli przechodzą dalej komputery o id<3, czyli 0,1,2. Czyli wszystko się zgadza. A nawet jeśli, to akurat w tym teście nie miało znaczenia, bo i tak n było dużo większe od N, więc wszystkie kompy i tak działały.