Cześć,
wysłał ktoś może rozwiązanie typu "binsearchem po wyniku"?
tj O((n/M + m/M) * lg n + M)? (lub M^2 na końcu)

Ja zdobyłem za coś takiego 5/10 i zastanawiam się ile straciłem za logarytm, a ile za nieoptymalną komunikację (broadcast jako chain, zamiast dwustopniowego drzewka).

Nie robiłem takiego rozwiązania, ale zauważ że logarytm dwójkowy z maksymalnego n to coś koło 30 - czyli faktyczne przyspieszenie względem rozwiązania nierozproszonego to w najgorszym wypadku jakieś 3 razy (100/30) zamiast zakładanych 100.