Jak zrobiliście zadanie Działka [B]?
Mi się udało zakodować następujące rozwiązanie:
Algorytm z dzi z oi9 zmodyfikowałem pod liczenie wszystkich prostokątów. Dane dzielę pasami poziomymi najpierw rozsyłając w dół głębokości (po 100 bo był limit na 1000 wiadomości), więc każda instancja zna głębokości z ostatniego wiersza poprzedniej. Potem dopiero liczę prostokąty zakończone w danym pasie drugi raz czytając poszczególne pola. Na koniec sumuję rozwiązania w jednej instancji. W sumie bardzo zwięzły i prosty kod wyszedł.
Złożoność O(n^2/i), czas max. 7.5s/12s, 10/10.

Ja zrobiłem analogicznie. Nie wiem czy mamy takie same rozsyłanie w dół. Ja napisałem takie, że mamy log(liczba instancji) rund, w i-tej rundzie, rundy numerowane od 0, instancja id wysyła sumę prefiksową (w górę wliczając siebie) jaką zna do tej pory (na początku zna tylko swoją) do instacji id+2^i. Potem, każda instancja dla każdego z wierszy jej przypisanych, liczy prostokąty mające dolny bok w tym wierszu używając stosu i różnic wysokości pomiędzy prostokątami. Na końcu wszyscy wysyłają swoje wyniki do master instancji, która sumuje i wypisuje.

No to ja mam chyba trochę prościej, aczkolwiek mi się w pierwszym i ostatnim 10000 kolumn średnio połowa instancji nudziła (na końcu może nie od razu, bo liczyły prostokąty, ale wcześniej zaczynały, więc to czekanie się przesuwało na zbieranie wyników).

Też chciałem tak jak Paweł i wydawał mi się to fajny pomysł, ale jak się okazało że takie bezczelne przesłanie łańcuchem też siada to już kompletnie się rozczarowałem zadaniem :(

U mnie każda maszyna przetwarzała 100 wierszy na raz w jednej fazie, faz było max 8. Każda maszyna zapamiętuje sobie stan wysokości i stosów w 100 wierszach, co 750 kolumn przesyła wyliczony fragment do następnej i dalej liczy wiersze od góry na kolejnych 750 kolumnach.

5.20s / 12.00s

Koledzy, dopiero teraz jak spojrzałem na "Ograniczenia" w zadaniu to mnie oświeciło i chyba cały czas źle rozumiałem działanie biblioteki do przesyłania wiadomości. Myślałem, że w jednej wiadomości można przesłać tylko pojedynczą wartość Int/Char/LL. Teraz czytając Wasze rozwiązania domyśliłem się, że można wielokrotnie wywołać PutInt przed wywołaniem Send i to spowoduje wysłanie wielu Intów w jednej paczce?

Z tego powodu zakładałem, że nie jesteśmy w stanie propagować tablicy wysokości (jest długości 75000), bo nie wystarczy nam komunikatów. Dlatego w moim rozwiązaniu każdy węzeł liczył od zera tablicę wysokości, a dopiero właściwy algorytm ze stosem działał na podzbiorze działki. Takie podejście kosztowało mnie niestety stratę 9pkt.

Tak - można dodać wiele liczb do kolejki i następnie wysłać je wszystkie w jednej wiadomości. Również z tym pojawił się problem, gdy na raz wysyłało się zbyt dużą ilość danych (ponad 64 KB). U mnie każda maszyna przesyłała jednorazowo 750 liczb, w sumie przesyłając cały wiersz (w 100 wiadomościach) przez 8 faz, czyli ok 800 wiadomości.

Podzieliłem planszę na 100 x 100 kwadratów. Instancja a wylicza wysokości w kolumnie a, oraz wyniki w wierszu a. Wysokości dla górnego wiersza kwadratu (a, b) są wysyłane od instancji b do instancji a, bezpośrednio. Mam dokładnie 9900 wiadomości, 99 per węzeł, każda wielkości <= 3KB (nie licząc sumowania wyniku). Każdy worker robi dokładnie to samo i chyba najmniej danych jest przesyłane ze wszystkich rozwiązań tutaj, natomiast dość dużo wiadomości. Trwa 7s na najwolniejszym teście.

@Krzysztof: sprytne, aczkolwiek wysokości dla wiersza 0 nie musiałeś wysyłać, miałbyś 99 wiadomości mniej (dla porównania ja miałem 99*750 wiadomości po 400 bajtów, czyli danych tyle samo ale w mniejszych paczkach).

Jakby ktoś chciał _zobaczyć_ jak wyglądały testy to tu są obrazki:
https://ufile.io/8mh9l
(biały pixel - dozwolony, czarny - zabroniony)