Mistrzowie świata opowiadają o programowaniu zespołowym

Mistrzowie świata opowiadają o programowaniu zespołowym
DataArt od lat przyjaźni się z drużyną Uniwersytetu ITMO w Petersburgu w programowaniu zespołowym. W tym roku Ilya Zban, Ivan Belonogov i Vladimir Smykalov odwiedzili nasze centrum rozwoju oprogramowania w Petersburgu. Mistrzowie świata 2017 opowiedzieli nam o tym, w jaki sposób programiści mogą ze sobą konkurować, obozach treningowych, ulubionych zadaniach i swoich najsilniejszych przeciwnikach.

Olimpiady programistyczne

Najbardziej podstawową formą rywalizacji programistów jest międzynarodowa Olimpiada studencka pod auspicjami ACM (ACM-ICIPC lub, prościej, ICPC). Jej tradycje sięgają lat 70. ubiegłego wieku. Jednak jej obecna forma ukształtowała się w 1989 roku. Olimpiada skierowana jest do studentów i absolwentów. Reguły nie pozwalają na udział programistów powyżej 24 roku życia, a wyjątki zdarzają się naprawdę rzadko. Dodatkowo, jedna osoba może przetestować swoje umiejętności w finale tylko dwukrotnie, a w eliminacjach regionalnych może wziąć udział zaledwie 5 razy. We wczesnych rundach konkurują tysiące zespołów na całym świecie, około setki dociera do wielkiego finału.

Główne zasady

Drużyny składają się z 3 osób, a każda z nich ma do dyspozycji tylko jeden komputer. Przed rozpoczęciem rozgrywek, wszystkie zespoły otrzymują koperty z zadaniami algorytmicznymi lub matematycznymi (od 8 do 13), które muszą rozwiązać w ciągu 5 godzin. Rozwiązaniem musi być aplikacja, która czyta zapytania tekstowe i odpowiada na nie w tej samej formie. Rozwiązanie jest następnie testowane za pomocą testów przygotowanych przez jury z wyprzedzeniem. Rozwiązanie uznawane jest za poprawne tylko wtedy, kiedy przejdzie wszystkie testy.

Zasady ICPC są dokładnie wyjaśnione w in wideo wydanym na potrzeby Urals Programming Championship, które są jedną z podstawowych rund eliminacyjnych olimpiady. Zasady są identyczne dla wszystkich regionów i nie uległy zmianie od 2013 roku.

Języki i środowisko

Podczas finałów 2017, uczestnicy mogli używać języków: Java, C++ i Python. Okazało się jednak, że Python nie jest najszybszy, jury nie mogło więc zagwarantować, że da satysfakcjonująca ocenę aplikacji napisanej z użyciem Pythona. Dodało jednak, że istnieją testowe rozwiązania stworzone w tym języku, które były w stanie przejść wszystkie testy.

Różne konkurencje miały różne zestawy języków – na przykład platforma Codeforces pozwala na użycie około 20 języków od C++ I Javy aż po Haskell i Perl.

Najwięcej zespołów używa C++, ponieważ jest szybszy, a w finale wszystko sprowadza się do szybkości. Wiele teamów używa VIM (Ivan i Ilya go używali) lub Gina (Vladimir je wybrał) jako środowiska. Ci, którzy decydują się na Javę najczęściej skłaniają się ku środowiskom takim, jak Eclipse ponieważ pisanie w Javie bez autocomplete jest trudniejsze.

W niedalekiej przyszłości możemy spodziewać się zmian, ponieważ sponsorem rozgrywek finałowych będzie teraz JetBrain (przez ostatnie 20 lat, do maja 2017 roku było nim IBM). Oznacza to, że będziemy używać produktów nowego sponsora – IDEA dla Javy, CLion dla C++. Prawdopodobnie, w związku z tą zmianą zespoły zaczną chętniej sięgać po debuggery, ale często można sobie poradzić bez nich.

Ewolucja zadań

We wczesnych latach 2000, zadania skupiały się wokół metod „na siłę” z kilkoma restrykcjami, obecnie często wiążą się ze strukturami danych. Jest kilka odrębnych szkół programowania zespołowego na świecie. W Polsce, na przykład, programiści często preferują problemy matematyczne, a w Chinach – skomplikowane zadania techniczne, które wymagają obszernego kodu (np. związanych z kombinatoryką).

Celem zawsze jest znalezienie i implementacja rozwiązania, które działa szybko. Każdy problem może być rozwiązany za pomocą programu napisanego w taki sposób, by przewidywał wszystkie możliwe opcje. W ostatnich latach takie ekstremalne rozwiązania prawie zniknęły z zadań.

Istnieją limity dotyczące czasu i pamięci, ale w praktyce bardzo rzadko spotykamy się z problemem, kiedy rozwiązanie zużywa za dużo pamięci. Limit czasowy dla każdego testu to zazwyczaj od 1-3 minut, zależnie od zadania. To również jest ujęte w specyfikacji zadania

Rodzaje zadań

Zadania są różne: grafy, linie, geometria, etc. Trzeba, na przykład, przeliczyć najkrótszą trasę pomiędzy dwoma punktami na mapie. Albo zbudować najdłuższą ścieżkę na wyspie reprezentowanej jako nieregularny kształt. Zadaniem może być także porównanie tekstów, w których trzeba zidentyfikować najdłuższy wspólny ciąg znaków.

Kolejnym formatem są zadania interaktywne, w których zawodnik ma rozegrać grę z systemem stworzonym przez jury. W jednym z półfinałów, zadaniem było stworzenie programu, który miałby złamać proponowany algorytm w kółko i krzyżyk q 90% czasu. Zadania z innych finałów, łącznie z ostatnim można zobaczyć tutaj.

Rozwiązania

Zazwyczaj członkowie drużyn wybierają zadania w zależności od ich osobistych preferencji – niektórzy wolą linie, inny preferują geometrię. W każdym przypadku sprowadza się to jednak do pracy zespołowej i indywidualnej w odpowiednich proporcjach.

Pierwszym krokiem jest zawsze znalezienie algorytmu, za pomocą którego można będzie rozwiązać jedno z zadań. Czasami twórca rozwiązania rozmawia z drużyną, by sprawdzić, czy jest ono prawidłowe z matematycznego punktu widzenia. Następnie, twórca rozwiązania tworzy kod, a pozostali członkowie teamu zastanawiają się nad rozwiązaniami innych zadań. Kiedy kod jest pisany, można testować go za pomocą przypadków testowych, które są zazwyczaj dołączone do zadań, i wysłać je do systemu w celu ewaluacji. Ponieważ komputer ma swój limit czasowy (i mamy jeden komputer dla pojedynczego zespołu), w każdej konkurencji jest także zapewniony dostęp do drukarki. Jeśli coś nie działa, kod jest drukowany, a błędów szuka się na papierze.

Ilość kodu nie wpływa bezpośrednio na ostateczny wynik. Inną rzeczą jest, że trudno stworzyć 1000 linii kodu w przewidzianym na zadanie czasie. Jest jednak możliwe, by zakończyć zadanie w 10-15 minut, tworząc zwięzłe rozwiązanie wysokiej jakości. Warunki zostały zaprojektowane w ten sposób, by kod który pisza uczestnicy był elegancki – zazwyczaj to 100-200 linijek kody, zdarza się, że jest to 300. Generalnie 300 linijek to nie tak dużo, ale kiedy masz tylko 5 godzin na stworzenie rozwiązania musisz napisać je szybko. I jeśli popełnisz choćby 1 błąd w tych 300 liniach, rozwiązanie nie będzie działać i będzie to oznaczać, że straciłeś masę czasu. Ponadto – im dłuższy kod, tym trudniej zidentyfikować błąd w wersji drukowanej!

Cechy kodu

Z jednej strony, ludzie zaangażowani w programowanie zespołowe mogą pisać kod szybko i przejrzyście, nawet w najbardziej stresujących warunkach. Z drugiej – często są krytykowani za to, że taki kod zawiera niezrozumiałe zmienne i trudno się go czyta. W kodzie, który jest pisany w trakcie konkurencji, nie ma długich i zrozumiałych nazw zmiennych, ponieważ rok później nie będzie on już wspierany. Ten problem jest jednak istotny na wysokim poziomie, ponieważ kod musi być przede wszystkim zrozumiały dla wszystkich członków zespołu.

Algorytmy

Znamy naprawdę wiele algorytmów używających różnych struktur danych, takich jak drzewo segmentów, drzewo Fenwicka, drzewo Kartezjańskie, itd. Czasami zbalansowane drzewo wyszukiwania musi być napisane niezależnie, by później moc zmodyfikować je w zależności od tego, czego wymaga zadanie. Na przykład w C++, jest struktura, która może wspierać wiele liczb i – na przykład – odnaleźć następujące po sobie liczby. Problem może jednak obejmować znalezienie nie kolejnej liczby, ale sumy wszystkich liczb mniejszych lub równych danej liczbie. Standardowe struktury nie mogą tego wykonać/

Nie możesz przynieść ze sobą żadnych fragmentów kodu, ale na Mistrzostwach świata możesz używać tzw. team reference, czyli zestawu algorytmów wydrukowanych na papierze. Nawet jeśli można stworzyć wiele na poczekaniu, w tym roku solidnie przygotowaliśmy się do mistrzostw. Testowaliśmy złożone algorytmy, ale właściwie nam się to nie przydało.

Inne turnieje i trening

Nagroda pieniężna nie jest główna motywacja uczestników turnieju. Na zdjęciu: Ivan Belonogov i Ilya Zban, zwycięzcy VK Cup 2015 (źródło - Ivan Belonogov). W 2017, trzeci członek zespołu ITMO, Vladimir Smykalov, był zwycięzcą VK cup.<

Wciąż występujemy w indywidualnych turniejach, a jest ich naprawdę wiele. Na przykład zawodu na rosyjskiej stronie Codeforce regularnie mają tysiące uczestników, wśród których tylko 20% to Rosjanie. Standardowa konkurencja składa się tam z pięciu zadań algorytmicznych, które muszą być rozwiązane w ciągu 2 godzin. Najważniejszą rzeczą wśród społeczności zbudowanej dookoła zawodów jest punktacja bazująca na systemie Elo, jak w szachach. Sukcesy w turniejach przynoszą programistom punkty. Kiedy osiągną oni określony próg punkowy, kolor ich nicka automatycznie zmienia się. Ci, którzy mają czerwone nazwy użytkowników otrzymują nie tylko prośby o pomoc, ale często także oferty pracy. A najważniejsze jest to, że są poważani, jak wszyscy inni mistrzowie sportów. „Czerwony nick” to często najważniejsza motywacja tych, którzy biorą udział w zawodach.

Jedną z rzeczy ważniejszych niż posiadanie czewonego nicka jest czerwona nazwa użytkownika z pierwszą czarną literą. 13 lipca, top 20 Codeforce obejmowało 8 Rosjan, 2 Ukraińców, Polaków i Chińczyków, jednego przedstawiciela Szwajcarii, Australii, Korei, USA, Tajwanu i Buałorusi.

Największe zawody organizowane są przez Mail.ru, Yandex, Facebook, Google i inne firmy. Na przykład, około 20000 uczestników wzięło udział w ostatnim turnieju Google Code Jam. Najlepszy tysiąc programistów otrzymał koszulki, a 25 z nich będzie brało udział w finale, który w tym roku odbędzie się w Dublinie.

Oprócz Google Code Jam, Google stworzył inny turniej znany pod nazwą “Hash Code”, którego finał odbył się w głównej siedzibie firmy. Wśród innych zadań, uczestnicy dostali plan budynku, który musiał być pokryty jak największą ilością punktów z dostępem do Wi-Fi, z użyciem jak najmniejszej ilości kabli i routerów. Optymalne rozwiązanie tego zadania nie istnieje, ale jest możliwe wykonanie go lepiej niż pozostali uczestnicy.

Jeden z budynków którzy organizatorzy Google Hash Code ujęli w zadaniu z routerami – Paris Grand Opera.

Jeszcze inny typ konkurencji jest przewidziany w ramach AI Cup, w trakcie którego uczestnik musi stworzyć program na bazie AI, który będzie w stanie wziąć udział w rozgrywce przeciwko oryginalnemu programowi dostarczonemu przez organizatorów w formie biblioteki. Gry są tworzone na potrzeby turnieju, nie można zagrać w nie samodzielnie. Ale scenariusze wybierane są tak, by tworzone strategie były interesujące.

W tym roku gra przypominała popularne rozgrywki z gatunku MOBA. Rozwiązanie dotyczyło zarządzania grupą 5 czarodziejów, umożliwiając im wymianę rozkazów za pomocą zakodowanych słów.

Takie konkurencje są ciągle tworzone na francuskiej stronie CodinGame. To świetne, że w turniejach związanych z AI osiągamy dobre wyniki, zajmując miejsca w pierwszych dwóch czołowych 20, nawet jeśli nie trenowaliśmy wcześniej. W programowaniu zespołowym najważniejszą umiejętnością jest siedzenie, myślenie i pisanie kodu.

Platforma Topcoder przeprowadza czasami maratony, które mogą trwać nawet kilka tygodni. Jest kilka takich turniejów, na przykład Deadline24 albo Challenge24, w których runda finałowa trwa jeden dzień. Uczestnicy są wybierani na podstawie rozwiązanych problemów algorytmicznych, a w finale muszą stworzyć strategię zarządzania rozgrywką. W tym turnieju, najbardziej efektywnym było dla nas pisanie kodu w trakcie pierwszych 12 godzin, poprawienie błędów i przerwa na sen.

Platformy online pomagają sprytnie podchodzić do zadań, w innym przypadku umiejętność szybkiego rozwiązywania problemów może przygasnąć. Ale nie są interesujące tylko ze względu na to, że są sposobem na trening. Konkurencje dają zawodnikom motywację i emocje, za którymi w codziennym życiu tęsknimy.

Trening

Właściwie wszystkie nasze treningi trwają pięć godzin, tak jak najważniejsze turnieje. Zazwyczaj rozwiązujemy zadania z poprzednich zawodów. Nie uczymy się nowych algorytmów na siłę, ponieważ już znamy ich bardzo wiele. Nie jesteśmy przecież od tego, by znać najbardziej skomplikowane struktury danych. To, czego się od nas wymaga, to przede wszystkim zdolność szybkiego wymyślania rozwiązań. Dlatego książki nie pomagają nam wcale – lepiej przeglądać pojedyncze artykuły albo słuchać wykładów na temat konkretnych problemów, a sporo jest ich w Internecie.

Łączenie programowania zespołowego ze studiami było trudne przez pierwsze dwa lata, ale trzeci i czwarty rok były już łatwiejsze, ze względu na to, że mieliśmy mniej zajęć na uniwersytecie. Wielu studentów zaczyna przecież pracę w tym okresie. Nie mamy czasu na pełnoetatową pracę, ale często dostajemy oferty po turniejach.

Przeciwnicy

Najsilniejsze drużyny pochodzą najczęściej z rosyjskich, polskich, koreańskich, chińskich i japońskich uniwersytetów. Czasami dobrze wypadają drużyny z Europy Zachodniej lub USA. Ale generalnie, jest tam mniejsze zainteresowanie programowaniem zespołowym. Europa wschodnia i Azja dominują w turniejach indywidualnych, takich jak te z Codeforces. Wnioskując jedynie na podstawie liczb, najwięcej uczestników pochodzi z Indii, ale nie osiągają oni najlepszych rezultatów.

Drużyna USA w sezonie 17/18

Najbardziej zagadkowymi przeciwnikami są programiści z Korei Północnej, którzy nawet nie mając dostępu do Internetu, intensywnie trenuja I często osiągają dobre wyniki. Ale w tym roku w USA nie dostali się do finału i posiadają złą reputację ściągających na Codeforces. Byli nawet oskarżeni o wspólne pisanie kodu i zamieszczanie go przez jedno konto, co jest zabronione w regulaminie.

W tym roku tylko jeden zespół z Europy Zachodniej, studenci Royal Institute of Technology w Sztokholmie dostali się do pierwszej 10 Olimpiady.

Sukces rosyjskich drużyn jest zrozumiały, ponieważ uczą się oni w bardzo prestiżowych szkołach matematycznych i stworzyli społeczność olimpijską, która prężnie wspiera początkujących. Oprócz ITMO, najsilniejsze drużyny pochodzą z SPbSU, Moscow State University, MIPT I uniwersytetów w Jekaterynburgu i Saratowie.

Na zdjęciu widoczna jest inna drużyna z ITMO -Artem Vasiliev, Boris Minaev, i  Gennady Korotkevich. To mistrzowie świata z 2015 roku. Puchary Międzynarodowej Olimpiady Programistycznej nie są przekazywane pomiędzy kolejnymi zwycięzcami, a ITMO ma ich już 7.