Startowanie w zawodach

10.11.2009

Przyjdzie Wam zapewne nie raz startować w zawodach o formule "ACMowej", np. w Dolnośląskich Zawodach w Programowaniu Zespołowym. W najbliższy weekend, odbywają się na Uniwersytecie Wrocławskim najbardziej prestiżowe zawody w tej części Europy, czyli właśnie ACM ICPC CEPC. Parę osób od nas zostało zaproszonych poza konkursem, aby poczuć ducha tej imprezy.

W zawodach takich drużyny z reguły mają 3 osoby, 1 komputer i 5 godzin czasu. Liczba zadań oscyluje w okolicach 6-12 i z reguły zrobienie wszystkich z nich oznacza zwycięstwo. Format zadania z reguły jest podobny: należy wczytać ze standardowego wejścia liczbę testów a następnie wczytać testy i wypisać odpowiedzi. Limity czasu i pamięci zazwyczaj są podane w treści -- jeśli nie są, to zapewne są podane w wydrukowanych materiałach pomocniczych.
Treści zadań są wydrukowane, najczęściej w trzech kopiach, co jest bardzo istotne, bo czytanie ich z ekranu komputera blokowałoby najcenniejszy zasób.
Każde zadanie warte jest jeden punkt.
W przypadku gdy dwie drużyny mają tyle samo rozwiązanych zadań, ranking ustala się na podstawie tzw. "łącznego czasu".
Dla każdego zadania, które drużyna rozwiąże poprawnie, do łącznego czasu dodaje się liczbę bombek razy 20 minut, plus czas od rozpoczęcia zawodów.
Wniosków z tej reguły jest kilka:
  • jeśli możesz poświęcić 10 minut na napisanie testów z trudnymi przypadkami i sam sobie znaleźć błąd, to zrób to
  • jeśli widzisz które z zadań jest łatwiejsze, to zacznij od niego
  • bombki za nierozwiązane zadania nie mają znaczenia, więc jeśli pod koniec zawodów widzisz, że masz za mało rozwiązanych zadań, to próbuj rozwiązać kolejne aż do skutku
Pracuje się często w środowisku linux, co nie dla każdego jest wygodne.
Z reguły dostępne jest jakieś środowisko graficzne, w miarę przyjazne użytkownikowi, nie mniej pewne rzeczy należy umieć zrobić w konsoli.
Do edytowania plików polecam (jeśli będzie dostępny) gedit, bo przypomina w obsłudze najbardziej notatnik z tego co widziałem.
Z konsolowych edytorów mcedit najbardziej przypomina Nortona Commandera, jeśli w ogóle wiecie co to było:)
Jeśli ktoś wymiata w vimie, czy emacsie to z reguły też są dostępne, ale warto używać, czegoś co potrafi obsłużyć każdy członek drużyny.
Edytory tekstu potrzebne są do napisania programu, a także do napisania testów.
Absolutne minimum, to przepisać test przykładowy z treści.
Bardziej skomplikowane testy można wygenerować własnoręcznie napisanym programem, chociaż najwygodniej byłoby do tego znać jakiś język skryptowy.
Jak uruchomić środowisko graficzne i jak potem odpalić w środowisku graficznym konsolę.
Przykładowa sesja pod konsolą mogłaby wyglądać jakoś tak:
mkdir zadanieD
cd zadanieD
gedit d.cpp &
#klepu klepu klepu
g++ -O3 -o d d.cpp
gedit test &
#klepu klepu klepu
time ./d < test
gedit trudny_test.cpp &
#klepu klepu klep
g++ -O3 -o trudny_test trudny_test.cpp
./trudny_test > trudny_test.txt
time ./d < trudny_test.txt
Przed zawodami zawsze jest dzień próbny, podczas którego można się zapoznać ze środowiskiem i gorąco radzę to zrobić.
Jak widać powyżej, kompilowanie odbywa się z wiersza poleceń. Organizatorzy zazwyczaj podają polecenie jakim kompilowany będzie wasz program i warto robić dokładnie tak samo. Warto też dodać opcje -Wall, aby wyłapać parę częstych błędów.
Często zamiast pisać g++ -O3 -o d d.cpp sratata, wystarczy napisać:
make d
Zaznajomcie się też z tym jak kopiuje się i wkleja dane do schowka -- pod linuxem może to być nieco inaczej niż dajmy na to w cmd.exe.
Pierwsze 10 minut zawodów jest zazwyczaj bardzo nerwowe. Z racji tego, że "łączny czas" liczony jest tak a nie inaczej, bardzo ważne jest, aby pierwsze zadanie rozwiązać jak najszybciej -- każda stracona minuta, liczy się przecież tylukrotnie ile zadań planuje się rozwiązać.
Niezmiernie ważne jest zatem, aby znaleźć zadanie, które jest najprostsze.
W tym celu najlepiej jest podzielić zadania (w miarę po równo i losowo) pomiędzy siebie i przeczytać je wszystkie.
Bardziej doświadczeni zawodnicy mogą sobie pozwolić na nie przeczytanie wszystkich zdań jeśli czytając jakieś dojdą do wniosku, że jest trywialne.
Wam serdecznie to odradzam.
Najpierw przeczytajcie wszystkie zadania.
Dopiero potem ustalcie, które z nich jest najprostsze.
Będzie to zapewne wymagało opowiedzenia reszcie drużyny o czym jest najprostsze zadanie z tych, które przeczytaliście.
Jeśli nie jesteście w stanie tego opowiedzieć w 20 sekund, to zapewne nie jest to najprostsze zadanie:)
Jako, że głupio już przy pierwszym zadaniu mieć bombkę, warto, aby gdy jedna osoba pisze, druga gapiła jej się na ekran, a trzecia myślała nad trudnymi testami.
Bardziej doświadczeni zawodnicy mogą sobie pozwolić na zostawienie piszącego bez nadzoru, Wam jednak gorąco to odradzam.
Raz jeszcze podkreślę -- przeczytajcie wszystkie zadania. Organizatorzy często musząc wykazać się w raportach mają niejako obowiązek dać chociaż jedno proste zadanie -- przeoczenie go to wstyd:)
Kolejna sprawa to obserwowanie rankingu, który uaktualniany jest na żywo. Zdaję sobie sprawę, że możecie nie dać rady rozwiązać żadnego zadania w ciągu pierwszych 5 minut, ale wierzcie mi, że są drużyny, które po 5 minutach już będą miały ACC. Jest to bardzo wyraźna wskazówka, od którego zadania należy zacząć.
Jeśli więc po 5 minutach nadal jesteście w powijakach, zerknijcie na ranking.
Zerkajcie tam w ogóle w miarę regularnie. 
Jeśli nie chcecie odrywać nosa od programowania, obserwujcie kolory baloników na sali -- za każde poprawne rozwiązanie, drużyny dostają baloniki o kolorach odpowiadających poszczególnym zadaniom. Balonik zazwyczaj jest przynoszony drużynie z pewnym opóźnieniem, więc lepiej patrzeć na ranking.
Podczas programowania, kompilujcie swój program jak najczęsciej.
Nie ma nic gorszego niż dowiedzieć się na sam koniec pisania, że macie 40 ekranów błędów, bo zapomnieliście jednej spacji przy deklaracji jakiegoś STLowego typu.
Wyróbcie sobie pewien szablon, np.:
#include<iostream>
#include<vector>
#include<algorithm>
#Include<set>
#include<map>
#include<queue>
using namespace std;
void solve(){
}
int main(){
  int t;
  ios::sync_with_stdio(false);
  cin >> t;
  while(t--){
    solve();
  }
}
i zapiszcie go w jakimś pliku, np. jako szablon.cpp, a potem
cp szablon.cpp zadanieD/d.cpp
Po pierwsze zaoszczędzi to (bardzo mało) czasu, po drugie (ważniejsze) odbieże Waszej głowie poczucie, że "robi coś porzytecznego".
To bardzo ważne, żeby wyzbyć się tego natrętnego uczucia, które każe siąść do klawiatury i zacząć klepać, chociaż jeszcze nie ma się pomysłu co.
Warto sobie uświadomić, że wczytanie danych wejściowych to nie jest praca intelektualna, a pisanie tego kawałka kodu blokuje najcenniejszy resource.
Dopóki więc nie macie pomysłu jak rozwiązać zadanie, nie piszcie nic na komputerze, a czas spędzony przy nim ograniczajcie do minimum.
Piszcie na kartkach.
Rysujcie dużo przykładów/kontrprzykładów.
Jeśli trzeba rozmawiajcie ze sobą, ale nie kłóćcie się i nie drzyjcie na całą salę, bo inne drużyny mogą podsłuchać.
Debugowanie, to coś co pewnie zajmie dużo czasu i będzie irytować resztę drużyny.
Nauczcie się zatem korzystać z drukarki. Gdy nie macie pomysłu dlaczego program nie działa, kliknijcie Drukuj i oddajcie klawiaturę innej osobie z drużyny.
Poczekajcie grzecznie na wydruk, i przeanalizujcie wydruk.
Dopiero gdy znajdziecie na wydruku coś co jest podejrzane, postarajcie się delikatnie oderwać kolegę od monitora.
Do debugu można używać cerr zamiast cout, co ma tę zaletę, że jest to osobny strumień, który powinien być ignorowany przez sprawdzaczkę.
Z resztą przez Was też może być ignorowany, bodaj tak:
./d 2> /dev/null
Przekierowywanie plików do programu, programu do pliku i programu do programu, powinniście mieć w miarę opanowane.
Program sędziowski z reguły ma kilka różnych rodzajów komunikatów.
ACC -- super
P.E. -- zadanie zaliczone, chociaż format outputu jest zły -- to się raczej nie zdarza jeśli oceniają maszyny a nie ludzie
WA -- zła odpowiedź dla jednego z testów
TLE -- zbyt długi czas wykonywania
RTE -- z reguły jakiś "crash" -- coś nahahmęcone ze wskaźnikami, z zakresem tablic, ze stosem, generalnie coś robicie źle i program wybuchł
W przypadku TLE, raczej nie chodzi o to, że gdzieś używacie wektora a powinny to być tablice -- zazwyczaj macie po prostu złą złożoność.
Nie mniej jeśli nie macie już pomysłów jak zrobić coś lepiej, warto pomyśleć nad jakąś heurystyką, czy drobną optymalizacją.
Trochę można by o tym opowiadać, ale na pewno warto się zastanowić, czy nie da rady czegoś ztablicować (policzyć raz a dobrze i zapamiętać wyniki), usunąć gdzieś rekursję na rzecz iteracji, pozbyć się set/map, na rzecz posortowanych vectorów i binarysearcha.
Bardzo częstym powodem koszmarnie wolnego działania programu, jest nadużywanie dzielenia i modulo. Starajcie się wykonywać te operacje jak najrzadziej, preferując raczej if'y, czy gromadzenie wyniku w long longu i liczenie modulo tylko raz na jakiś czas.
Powtórzę jeszcze raz : przeczytajcie wszystkie zadania. Nie dajcie się złapać w płapkę, jaką jest siedzenie 5 godzin nad jednym zadaniem, bo przecież "to napewno zaraz zacznie działać, tylko muszę znaleźć jednego małego buga". Jeśli nie udało się programu doprowadzić do ACC w pół godziny, a innym drużynom zajęło ono 10 minut, to najpewniej oznacza, że albo w ogóle nie zrobicie tego zadania i zajmijcie się innym (przeczytajcie pozostałe). Albo należy zacząć zupełnie od nowa -- niech inna osoba siądzie i napisze zupełnie od zera, nie sugerując się tym, co było już napisane. Jeśli zadanie faktycznie da się zrobić w 10 minut, to stracicie na tym 10 minut. Z drugiej strony lepiej stracić 10 minut, niż debugować program przez kolejne pół godziny.
Używajcie papieru. Róbcie wydruki. Piszcie rozwiązania na kartce. Serio. Jak spróbujecie to odkryjecie, że pisanie w C++ na papierze wcale nie jest trudne, a odkrywa się całą masę błędów w swoim rozumowaniu. Doceńcie, ile czasu dla drużyny oszczędza Wam każdy błąd znaleziony w rozumowaniu jeszcze zanim siądziecie do komputera! Rzecz jasna program napisany w C++ na papierze, raczej nie będzie działał.
Taka już specyfika tego języka, że ciężko napisać coś bez błędów.
Mówię o błędach w rozumowaniu -- o nie uwzględnieniu w ogóle jakiegoś przypadku, czy nie zwróceniu uwagi na limity podane w treści.
Pomijając pierwsze zadanie, wszystkie następne radzę pisać najpierw na kartce.
Przygodę z pojedynczym zadaniem ACMowym, warto zacząć od bardzo pobieżnej analizy:
  • ile tekstu jest w treści
  • jakie limity (liczby) pojawiają się w treści
  • jak wygląda przykładowy plik wynikowy -- czy trzeba dużo wypisać, czy wystarczy tak/nie ?
  • czasem zadanie ma streszczenie -- warto je przeczytać
Z tych danych często da się wywnioskować o jaką mniej więcej złożoność chodzi.
Niepisana reguła jest mniej więcej taka, że podstawiając limity do wzoru na złożoność powinno wyjść coś w okolicach 1-10 milionów.
Przykładowo widząc, że:
  • tekstu jest mało
  • limit to 100 000
  • a należy wypisać całkiem sporo danych
Należy się domyślać, że w zadaniu być może chodzi o zrobienie czegoś o złożoności O(n lg n), być może sortowania.
Albo np. binarysearcha n razy. Albo może trzeba mieć kolejkę priorytetową i wsadzić do niej n elementów.
Mówiłem, że na olimpiadzie warto zacząć od napisania czegokolwiek czego jesteście pewni -- programu wzorcowego.
Na ACM nie polecam tego, bo tu jednak liczy się czas, a do przetestowania programu służy system sędziowski -- na Olimpiadzie nie wiecie na żywo czy program jest czy nie jest poprawny, więc musicie go bardzo rzetelnie sami przetestować.
Nie mniej jeśli macie uczucie, że nie dacie rady zrobić więcej jak jedno zadanie, to możecie użyć wszystkich zasobów jakie macie, aby je rozwiązać.
A więc ułożyć ciekawe testy, napisać wzorcówkę, gapić się w pare osób na ekran itd.
Jest to jednak dość rozpaczliwe podejście do sprawy, chociaż nie wątpliwie bardzo drużynowe.
Niestety jednak (z mojego doświadczenia) zawody w programowaniu drużynowym, są drużynowe raczej z nazwy. Każdy pracuje raczej indywidualnie i wręcz konkuruje o klawiaturę z resztą drużyny. O sile drużyny decyduje jej skład i to na ile ich wiedza się uzupełnia i czy umieją ze sobą kulturalnie porozmawiać na temat oddania klawiatury. Rzecz jasna trzeba umieć przekonać drugą osobę, że wie się o co chodzi w zadaniu i jego rozwiązaniu i tutaj nieocenione są osoby, które potrafią w mig zrozumieć siebie nawzajem.
Na koniec ostrzeżenie. Nie nastawiajcie się, że za pierwszym razem uda Wam się zrobić chociaż jedno zadanie.
To nie jest realistyczny cel. Realistyczny cel to: zrobić wszystkie zadania, które umiałoby się zrobić mając 3 komputery i 5h czasu.
Być może ta liczba to zero i nie należy sobie z tego powodu czynić wyrzutów.
Jeśli jednak, po powrocie do domu uświadomicie sobie, że jednak nie przeczytaliście jednego z zadań, albo, że to co kolega próbował napisać przez 5h było bez sensu i wystarczyło na to spojrzeć, to ... bardzo źle.
Ja osobiście trzymam kciuki i przeczuwam, że rozwiążecie jakieś zadanie. Nie będę miał jednak żadnych pretensji, jeśli niczego nie zrobicie.
Ważne, abyście Wy także nie mieli do siebie pretensji, a zwłaszcza do siebie nawzajem.
Nie ma nic bardziej żałosnego, niż drużyna, która obrzuca się nawzajem oskarżeniami.
Pretensje można mieć zawsze tylko do samego siebie -- bug w kodzie Twojego kolegi, jest także efektem Twojej nieuwagi i braku komunikacji.
Należy też wiedzieć, że byłoby naprawdę podejrzane, gdyby startujący pierwszy raz rozwiązali dwa zadania.
Świadczyłoby to zapewne marnie o testach i/lub zadaniach.
Nastawcie się raczej na to, że dopiero po 10 startach, dojdziecie do jako-takiej wprawy.
Tym bardziej istotne jest, abyście zaczęli startować w takich zawodach jak najwcześniej i wynajdywali sobie różnego rodzaju sparingi, na których moglibyście trenować.
Jeśli nie możecie znaleźć sparingów (chociaż oferta UWr jest tutaj całkiem całkiem), zorganizujcie je sobie sami -- w sieci jest pełno zadań z zawodów ACMu z ubiegłych lat i innych rejonów świata.
Możecie odnieść wrażenie, że dzieli Was przepaść od drużyn na podium.
To najlepsze co możecie wynieść z takich zawodów -- świadomość, że jest jeszcze coś czego możecie się nauczyć.
Prawdziwy dramat, to gdy już jesteście na tym podium, lub tuż pod nim i nie macie do końca pojęcia dlaczego -- po paru latach startowania okazuje się, że o ile top10 jest w miarę ustalone, to top3 zmienia się co chwila i nie bardzo wiadomo kto od kogo i czego powinien się uczyć, loteryjka.
Świetną sytuacją jest więc taka, w której jesteście pewni, że skaszaniliście, wiecie co skaszaniliście, wiecie jak to poprawić i wiecie kogo gonić.
Myślę, że przed Wami jakieś rok-dwa takiego gonienia.

Copyright © 2008-2010 Wrocławski Portal Informatyczny

design: rafalpolito.com