Niestety lokalny (jedno-procesorowy) pomiar czasu zadań rozproszonych jest bardzo trudny.

Receive() [z tego co widzę u siebie] uprawia spin-polling/busy-looping i tym samym żre 100% jednego procka aż otrzyma dane [pewnie bo nie używa blokujących syscall'i]. Tym samym spowalnia wszystkie pozostałe wątki wykonania.

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ć!

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

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.

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ść...

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

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

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

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? Niby jak, przecież nie masz zielonego pojęcia, gdzie na kółku są ludzie o danych indeksach, na tym polega cała trudność zadania.

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

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

@Michał Włodarczyk "Można też dla każdego samochodu policzyć najbliższego sąsiada w lewo i w prawo, z którym się nie może wyminąć i prawdą jest, że jeśli nowy porządek zachowuje takie trójki to da się go osiągnąć.
Konieczne jest tu drzewo przedziałowe albo set, więc złożoność nlogn."
Ale nie jest prawdą, że jeśli da się go osiągnąć, to zachowuje takie trójki. Przykład - samochody szerokości 2,3,4 dla parkingu o szerokości 5. Można osiągnąć układ 3,2,4, ale wcześniej najbliższy po lewej dla tego szerokości 4 był szerokości 3, a teraz jest 2 (i oba z nim kolidowały).

Można to jednak poprawić. Moje rozwiązanie jest następujące:
Sortuję oba ciągi samochodów po pozycji na parkingu, następnie dla każdego z przejść początkowego i końcowego ciągu do przodu i do tyłu (razem cztery przejścia) buduję sobie malejący stos (np. na tablicy, by dało się szybko wyszukiwać) tych samochodów, które przekraczają połowę szerokości parkingu. Dodając nowy samochód:
- szukam najmniejszego z samochodów na kolejce, który "koliduje" z obecnym i wpisuję go jako "sąsiada" dla tego przejścia (jeśli nie było dotychczas żadnego, który by kolidował, samochód zostaje bez "sąsiada")
- jeśli dany samochód przekracza połowę szerokości parkingu, dodaję go do kolejki, kasując wszystkie nie szersze od niego po drodze
Można przestawić samochody wtedy i tylko wtedy, gdy są identyczne zarówno oba ciągi skonstruowane przy przechodzeniu do przodu, jak i przy przechodzeniu do tyłu.

Pseudo-dowód: Załóżmy, że można przestawić samochody, a my powiedzieliśmy, że nie można, tzn. nasze ciągi sąsiadów się gdzieś różniły, tzn. sąsiad dla pewnego samochodu X wcześniej był A, a potem B. Jednak taka sytuacja jest niemożliwa, bo albo A musiałby się zamienić z X miejscami, co jest niemożliwe, bo ze sobą kolidują, albo A musiałby się zamienić miejscami z B, co jest również niemożliwe, bo oba są szersze od połowy parkingu.
Załóżmy teraz odwrotnie, że przestawiliśmy samochody A i B, które ze sobą kolidowały, a skonstruowane ciągi są identyczne. Możemy przyjąć bez straty ogólności, że A ma szerokość przekraczającą połowę szerokości parkingu. Rozważmy "sąsiada" B od strony A (tzn. przy przejściu do przodu, jeśli A jest po lewej stronie B i przy przejściu do tyłu w przeciwnym przypadku). Tym sąsiadem nie może być A, bo oznaczałoby to, że wcale nie zamieniliśmy miejscami A i B (pamiętajmy, że ciągi sąsiadów były identyczne). Jest to więc inny samochód C o szerokości przekraczającej połowę szerokości parkingu i takiej, że C i B ze sobą kolidują. To jest jednak również niemożliwe - teraz A jest z drugiej strony B, a C było najbliższym przekraczającym połowę szerokości parkingu z tej pierwszej strony, a więc A i C też musiały się minąć, co jest niemożliwe.

To rozwiązanie ma zaletę, że jest proste - wykorzystujemy tylko sortowanie i wyszukiwanie binarne.

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.