Potyczki Algorytmiczne
Otwarty ogólnopolski konkurs programistyczny 2016
 
Google
partner
Atende
sponsor
Uniwerytet Warszawski
organizator
liczba uczestników
0
Zadania rozproszone

W tegorocznej edycji Potyczek Algorytmicznych ponownie pojawią się zadania rozproszone. Na tej stronie znajdziesz informacje przydatne przy pisaniu rozwiązań do zadań tego typu.

  • Po skompilowaniu Twojego programu, system sprawdzający uruchomi wiele jego instancji, każdą na osobnym komputerze.
  • Instancje Twojego programu będą pobierać dane wejściowe, korzystając z biblioteki dostarczonej wraz z zadaniem. Jej zachowanie będzie takie samo dla każdej instancji. Twój program nie powinien czytać ze standardowego wejścia.
  • Instancje ponumerowane są kolejnymi liczbami naturalnymi (od zera). Za pomocą biblioteki message dostarczonej przez organizatorów program może się dowiedzieć, na ilu komputerach jest uruchomiony, oraz poznać swój numer instancji.
  • Biblioteka message pozwala również na komunikację pomiędzy instancjami programu.
  • Wynik powinien zostać wypisany na standardowe wyjście przez dokładnie jedną (dowolnie przez Ciebie wybraną) instancję. Pozostałe instancje nie powinny nic wypisywać na standardowe wyjście.
  • Podobnie jak w przypadku zadań zwykłych, zawartość standardowego wyjścia diagnostycznego (stderr) jest ignorowana przez system sprawdzający. Jego długość jest jednak limitowana i nie może przekroczyć 1MB.
  • Jeśli którakolwiek instancja programu przekroczy limit czasu lub zakończy się błędem wykonania, test uznawany jest za niezaliczony.

Biblioteka message

Biblioteka message służy do przekazywania wiadomości pomiędzy instancjami programu. W pliku message.h znajdziesz komentarze wyjaśniające, jak należy jej używać.

Każda wiadomość to pewien ciąg wartości. Aby wysłać wiadomość do danej instancji, najpierw budujemy jej zawartość, kolejno dodając jej pola (funkcje PutChar, PutInt i PutLL), a następnie powodujemy wysłanie (funkcja Send). Po odebraniu wiadomości, możemy odczytać jej kolejne pola za pomocą funkcji GetChar, GetInt i GetLL. Wiadomości wysłane pomiędzy ustaloną parą instancji przychodzą w kolejności ich wysyłania.

Testowanie rozwiązań

Aby przetestować swoje rozwiązanie, możesz użyć dostarczonej przez nas biblioteki, która pozwala symulować wykonanie wielu instancji programu na jednym komputerze.

W tym celu ściągnij jedną z wersji dostępnych w załącznikach na dole strony. Oto kilka ostrzeżeń dotyczących naszego narzędzia:

  • Nie gwarantujemy, że będzie działało prawidłowo pod każdym systemem operacyjnym.
  • Tworzy ono oddzielny proces dla każdej z symulowanych instancji. Jeśli określiłeś zbyt duża liczbę instancji lub jeśli Twój program zużywa zbyt dużo CPU/pamięci, użycie tego narzędzia może spowodować zawieszenie systemu.
  • Czas działania podany przez nasze narzędzie może znacznie różnić się od czasu działania w rzeczywistym systemie sprawdzającym.

Podstawowe użycie:

 

alias rpa='{folder_z_rozpakowanym_archiwum}/rpa.sh'
rpa build --source=solution.c
rpa run --executable=./solution --nodes=100 --output=all

 

Możesz również uruchomić "rpa test", aby wykonać operacje "build" oraz "run" jedna po drugiej. Przykładowe wywołanie narzędzia dla programu "dzielniki_rozproszone" opisanego w sekcji Tutorial:

 

rpa test --source=dzielniki_rozproszone.cpp --nodes=10 < dzielniki1.in

 

Dodatkowe instrukcje (w języku angielskim) dostępne są poprzez polecenie:

 

python folder_z_rozpakowanym_archiwum/rpa.py --help

 

W przypadku napotkania problemów lub braku wersji biblioteki odpowiedniej dla Twojej platformy, przeczytaj plik README w archiwum. Znajdziesz tam instrukcje dotyczące własnoręcznej kompilacji narzędzia oraz zmieniania pliku konfiguracyjnego (config.json).

Limity

  • Liczba instancji jest określona osobno dla każdego testu i zawiera się w przedziale od 10 do 100.
  • W treści każdego zadania określone są limity na łączną liczbę oraz łączny rozmiar wiadomości, które każda instancja może przesłać do pozostałych.
  • Limit pamięci (ten sam dla każdej z instancji) jest określony w treści zadania. Limit ten obejmuje całą pamięć wykorzystywaną przez program, w szczególności stos, stertę i sam kod programu. Dodatkowo w limicie tym muszą zmieścić się wiadomości, które zostały już zakolejkowane, ale nie zostały jeszcze wysłane, oraz wiadomości, które zostały już odebrane, ale nie zostały jeszcze w całości przeczytane.
  • Pojedyncza wysłana wiadomość może mieć co najwyżej 256 KB.

Benchmarki

W archiwum benchmarki znajduje się kilka prostych programów wraz z ich czasami wykonania w środowisku, w którym będą testowane Twoje rozwiązania. Zapoznanie się z nimi może Ci dać wyobrażenie o tym, ile trwa przesyłanie wiadomości pomiędzy instancjami.

Załączniki