Zadania, z którymi zmierzą się uczestnicy naszych zawodów wymagają zastosowania metod informatycznych do problemów analizy danych. Na tej stronie można się dowiedzieć, w jaki sposób rozwiązania są zgłaszane i oceniane.
Rozwiązywanie zadań
Zadania zgłaszane są w formie programu rozwiązującego postawiony typ problemów. Następnie automatyczny sędzia, czyli specjalny program działający na naszych serwerach wykonuje sprawdzenia czy zadanie zostało zrobione prawidłowo. Dane powinny być przekazywane przez standardowe wejście/wyjście.
Każde zadanie opatrzone jest przykładowymi danymi jakie może otrzymać i prawidłowymi odpowiedziami dla tych przykładowych danych, zawodnicy nie wiedzą jednak na ilu i na jakich testach zadanie będzie ostatecznie sprawdzone. Dla dobrego wytłumaczenia jak ten proces przebiega, podajemy poniżej zadanie zbyt proste by mogło się pojawić na zawodach, pozwalające jednak na demonstrację podstawowych elementów programu, jaki należy napisać. Problem ten nie jest statystyczny ani związany z analizą danych (osoby biorące udział w zawodach serii ACM ICPC mogą rozpoznać pewne podobieństwa, ale uwaga, większość zadań na naszych zawodach to zadania niedeterministyczne, ale o tym potem).
Przykładowe zadanie
Przygotowujesz prosty system zabezpieczenia logowania na stronę internetową. Masz już program, który wyświetla w postaci zabezpieczonego obrazka tekst. Postanowiłeś, że aby zadanie było łatwiejsze dla człowieka, zapiszesz je w formie równania, które jest zawsze prawdziwe, na przykład „1+2=3”. W ten sposób jeśli człowiek będzie miał trudności z odczytaniem którejś z cyfr i tak poradzi sobie z równaniem. Bo przecież CAPTCHA ma utrudniać życie robotom, nie ludziom. Dla ułatwienia postanowiłeś, że dodawanie dwóch liczb całkowitych jest w zupełności wystarczające. Przygotowałeś program, który wylosował za ciebie pary liczb, i
. Napisz program, który zwróci równania. Każde równanie powinno zajmować jedną linię, w ten sposób Twój program generujący obrazki bez problemu sobie z tym poradzi.
dane wejściowe:
1 2 3 5
dane wyjściowe:
1 + 2 = 3 3 + 5 = 8
Przykładowe rozwiązania
Rozwiązanie tego zadania jest proste, nie wymaga właściwie żadnego programowania z naszej strony, ale pozwala zademonstrować ważną koncepcję. Pamiętajmy, że dane wejściowe pochodzą ze standardowego wejścia, znaczy to, że musimy je z niego odczytać i wygenerować odpowiedź na standardowe wyjście. Poniżej demonstrujemy przykładowe rozwiązania tego zadania we wszystkich dostępnych językach programowania (w kolejności alfabetycznej).
Język/Pakiet C
#include <stdio.h>
int main() {
long a, b;
while (scanf("%ld %ld", &a, &b)!=EOF) {
printf("%ld + %ld = %ld\n", a, b, a+b);
}
return 0;
}
Programy w języku C kompilujemy przy użyciu kompilatora GCC w wersji 4.8.0.
W systemie dostępna jest również biblioteka GSL w wersji 1.15, której możemy użyć dodając do programu linię #include <gsl/gsl_math.h>. Dostępna jest też biblioteka Alglib w wersji 3.7. Do kompilacji programów używamy opcji:
gcc -Wall -O2 -pipe -o nazwa kod.c -lgsl -lgslcblas -lm -I/usr/include/libalglib -lalglib
co generuje program gotowy do użycia. System sędziowski automatycznie rozpoznaje język po rozszerzeniu pliku, w przypadku języka C jest to „.c”.
Język/Pakiet C++
#include <iostream>
using namespace std;
int main() {
long a, b;
while (cin >> a >> b) {
cout << a << " + " << b << " = " << a+b << endl;
}
}
Programy w języku C++ kompilujemy przy użyciu kompilatora GCC w wersji 4.8.0. W systemie dostępna jest również biblioteka GSL w wersji 1.15, której możemy użyć dodając do programu linię #include <gsl/gsl_math.h>. Dostępna jest też biblioteka Alglib w wersji 3.7. Do kompilacji programów używamy opcji:
g++ -Wall -O2 -pipe -o nazwa kod.c -lgsl -lgslcblas -lm -I/usr/include/libalglib -lalglib
co generuje program gotowy do użycia. System sędziowski automatycznie rozpoznaje język po rozszerzeniu pliku, w przypadku języka C++ jest to „.cpp”.
Język/Pakiet Octave
line = fgetl(stdin);
while line!= -1
w=str2num(line);
printf("%i + %i = %i\n", w(1), w(2), w(1)+w(2));
line = fgetl(stdin);
endwhile
Programy w pakiecie Octave są zgodne z programami w pakiecie Matlab opracowanym przez firmę MathWorks. Programy są interpretowane i nie występuje tu etap kompilacji, programy są bezpośrednio uruchamiane w środowisku Octave w wersji 3.6.4 przy użyciu:
octave --quiet kod.moc
System sędziowski automatycznie rozpoznaje język po rozszerzeniu pliku, w przypadku języka Octave jest to „.moc”.
Język/Pakiet Pascal
program Test; var a, b : integer; begin while not eof do begin readln(a, b); writeln(a,' + ',b,' = ',a+b); end end.
Programy w języku Pascal kompilowane są przy użyciu kompilatora FreePascal w wersji 2.6.2 zgodnego z kompilatorem Turbo Pascal 7.0. W systemie dostępna jest również biblioteka AlgLib w wersji 2.6.0. Do kompilacji programów używamy:
fpc -viwn -O2 -Sg -XS -onazwa kod.pas
co generuje program gotowy do użycia. System sędziowski automatycznie rozpoznaje język po rozszerzeniu pliku, w przypadku języka Pascal jest to „.pas”.
Język/Pakiet Python
from sys import stdin line = stdin.readline() while line!="": xy=map(int,line.split()) print xy[0],"+",xy[1],"=",xy[0]+xy[1] line = stdin.readline()
Programy w języku Python są interpretowane i nie występuje tu etap kompilacji, są bezpośrednio uruchamiane w interpreterze Python w wersji 2.7.5. Dostępne są również biblioteki NumPy w wersji 1.7.1 i SciPy w wersji 0.12.0, których możemy użyć przykładowo pisząc from numpy import * lub from scipy import *. Program jest uruchamiany przy użyciu komendy:
python kod.py
System sędziowski automatycznie rozpoznaje język po rozszerzeniu pliku, w przypadku języka Python jest to „.py”.
Język/Pakiet R
con <- file("stdin", open="r")
while (length(line <- readLines(con, 1))) {
w <- sapply(strsplit(line, " ")[[1]], as.numeric)
cat(w[1]," + ",w[2]," = ",w[1]+w[2],"\n",sep="")
}
close(con)
Programy w pakiecie R są kompatybilne z językiem S-Plus obecnie rozwijanym przez Tibco Software. Programy są interpretowane i nie występuje tu etap kompilacji, są bezpośrednio uruchamiane w interpreterze pakietu R w wersji 3.0.0 przy użyciu:
Rscript --vanilla kod.r
System sędziowski automatycznie rozpoznaje język po rozszerzeniu pliku, w przypadku języka R jest to „.r”.
Język/Pakiet SAS
data _null_; infile stdin; input x y; file stdout; sum=x+y; put x "+ " y "= " sum; run;
Programy w pakiecie SAS są interpretowane i nie występuje tu etap kompilacji. Na systemie sędziowskim zagwarantowana jest instalacja odpowiadająca pakietowi SAS Analytics Pro. Programy są bezpośrednio uruchamiane w interpreterze pakietu SAS w wersji 9.3 przy użyciu:
sas -log /dev/null kod.sas
System sędziowski automatycznie rozpoznaje język po rozszerzeniu pliku, w przypadku pakietu SAS jest to „.sas”.
Podczas eliminacji uczestnicy mogą korzystać z rozwiązania SAS OnDemand for Academics. Jeśli szkoła lub uczelnia bierze będzie będzie chciała wziąć udział w tym programie, poproście swojego opiekuna o utworzenie kursu przygotowawczego do zawodów, dzięki czemu uzyskacie dostęp do pakietu SAS Enterprise Guide. Dla osób, które nie zdążą uzyskać dostępu do pakietu, przygotowaliśmy specjalny „kurs” przy Politechnice Wrocławskiej. Proszę postępować zgodnie z instrukcjami dla studentów wybierając jako uczelnię na której znajduje się kurs „Wroclaw University of Technology – Wroclaw„, natomiast jako kurs „Nomad 2013 – Sec. 1: Zawody Nomad, III edycja, Wroclaw 2013„.
Typy zadań
Podczas zawodów zawodnicy zmagać się będą z kilkoma typami zadań.
Zadania deterministyczne
Najprostszy typ zadań. Na każde pytanie jest tylko jedna dobra odpowiedź ponieważ nie występuje tu czynnik losowy. Aby zadanie zostało uznane za poprawnie rozwiązane, musi zwrócić oczekiwany wynik dla każdego przykładu. Jeśli zadanie wymaga porównywanie liczb zmiennoprzecinkowych, rozwiązanie zaproponowane przez uczestnika musi spełniać minimalne wymogi dokładności, tzn. przynajmniej dokładności względnej lub bezwzględnej. Zadanie opisane powyżej jest właśnie zadaniem deterministycznym. Również przykładowe zadanie dla pierwszej kategorii wiekowej należy do tej grupy. Wzorcowy plik wyjścia zawiera dokładne wartości.
Zadania prowadzące do problemu testowania hipotez
Drugim typem zadań są zadania sprowadzające się do problemu testowania hipotez. Tutaj na każde z zadań oczekujemy odpowiedzi postaci „1”, co zgodnie z kodowaniem w wielu językach programowania oznacza „prawda” lub „0”, co rozumiemy jako „fałsz”. Są to wszystkie zadania, w których należy coś sprawdzić. Wykonany test powinien być na poziomie istotności 0.05 i mieć niezerową moc, czyli spośród przykładów prawdziwych poprawnie zakwalifikować średnio przynajmniej 95% i poprawnie zakwalifikować przynajmniej jeden przypadek fałszywy. To, czy zadanie jest prawidłowo rozwiązane sprawdzamy wykonując test na poziomie istotności 0.01. Przykładowe zadanie dla drugiej kategorii wiekowej jest zadaniem testowania. Wzorcowy plik wyjścia zawiera prawdziwe wartości.
Zadania prowadzące do problemu estymacji
Trzecim typem zadań są zadania prowadzące do problemu estymacji. W tym problemie szacujemy pewne wartości. Elementem prawidłowego rozwiązania jest trafienie oszacowaniami do pewnych przedziałów. Przedziały są wyznaczone tak, by zawierały prawidłowe wartości oraz pozwalały na błędy numeryczne i losowe. Aby zadanie zostało zaakceptowane, należy prawidłowo oszacować przynajmniej 95% wartości. Sprawdzane jest to przy użyciu testu na poziomie istotności 0.01. Wzorcowy plik wyjścia zawiera przedziały dopuszczalnych wartości.
Instrukcja obsługi panelu drużyny
Do zgłaszania rozwiązań zadań służyć będzie specjalny panel internetowy. Każda z drużyn dostanie indywidualny login oraz hasło, za pomocą których uzyska dostęp do interfejsu systemu sędziowskiego. Po zalogowaniu do panelu możliwe będzie wysyłanie rozwiązań kolejnych zadań, odczytanie odpowiedzi systemu, a także zadawanie pytań oraz sprawdzenie aktualnej punktacji drużyny.
Zgłaszanie rozwiązań
Wysyłanie rozwiązań zadań do systemu sędziowskiego jest niezwykle proste. Po zalogowaniu się do panelu wystarczy wejść do zakładki submit, tam wybrać problem na jaki wysyłamy odpowiedź, a następnie wskazać plik z rozwiązaniem. Po czasie zależnym od złożoności obliczeniowej programu system sędziowski wygeneruje odpowiedź, którą zobaczyć można klikając na zakładkę submissions.
Komunikaty sędziego
System sędziowski wydać może jeden z następujących 9 komunikatów:
CORRECT
Wysłane rozwiązanie jest prawidłowe.
COMPILER-ERROR
Wystąpił błąd podczas kompilacji programu (interpretacji skryptu). Dokładny opis błędu również można znaleźć na stronie submissions.
TIMELIMIT
Program przekroczył dopuszczalny limit czasowy. Prawdopodobnie pojawiła się w nim nieskończona pętla, możliwe jest też to, że wybrane rozwiązanie jest po prostu mało efektywne obliczeniowo.
RUN-ERROR
Podczas uruchamiania programu wystąpił błąd. Prawdopodobnie jest to dzielenie przez zero, próba wykorzystania zbyt dużej ilości pamięci, czy też inna tego typu pomyłka.
NO-OTPUT
Program nie zwrócił informacji na wyjściu. Należy sprawdzić, czy wysłane rozwiązanie zadania rzeczywiście generuje odpowiedź na standardowym wyjściu.
WRONG-ANSWER
Program zwrócił nieprawidłowy wynik. Może to być spowodowane merytorycznym błędem w rozwiązaniu. Warto też zwrócić uwagę, czy program rzeczywiście podaje te informacje, o które chodzi w treści zadania.
PRESENTATION-ERROR
Format informacji zwracanej na wyjściu nie jest zgodna z wymaganiami określonymi w treści zadania.
TOO-LATE
Niestety rozwiązanie zostało wysłane zbyt późno.
Pytania
Do zadawania pytań w trakcie trwania mistrzostw służy strona clarifications. W miejscu tym znajduje się przekierowanie do formularza [Request Clarification], za pomocą którego zadać można pytania natury ogólnej, bądź odnoszące się do konkretnych zadań.
Punktacja
Informacje odnośnie liczby punktów przydzielonych drużynie za poszczególne zadania dostępne są na stronie scoreboard. W miejscu tym można też sprawdzić ile rozwiązań zostało wysłane, a także ile z nich było poprawnych oraz ile czasu zajęło najlepsze rozwiązanie.
Instrukcja obsługi panelu publicznego
Panel publiczny umożliwia sprawdzenie aktualnego stanu rywalizacji we wszystkich kategoriach. Oprócz liczby punktów przydzielonych za kolejne zadania widoczne są informacje dotyczące liczby zgłoszonych rozwiązań, a także czasu działania najlepszego programu (dla każdej z drużyn osobno).
Krótka instrukcja obsługi systemów na stanowiskach podczas finału
Podczas finału stanowiska komputerowe pracują pod kontrolą systemu operacyjnego Linux zainstalowanego w wirtualnych maszynach (podczas 3 edycji jest to Arch Linux). Szczegóły dotyczące logowania do systemu zostaną podane przez opiekunów sal tuż przed zawodami. Skróty do wszystkich potrzebnych narzędzi znajdują się na pulpicie. Jest wśród nich:
- przeglądarka internetowa ze stroną startową ustawioną na stronę logowania do automatycznego sędziego (podczas 2 edycji jest to Firefox 21.0)
- kilka edytorów tekstu do wyboru (podczas 2 edycji dostępne są następujące edytory graficzne: gVim 7.3.917, XEmacs 21.5.33, gedit 3.8.2, Geany 1.23.1 oraz SciTe 3.3.1, dostępne są też różne edytory pracujące z poziomu linii komend)
- terminal (podczas 2 edycji dostępny jest LXTerminal 0.1.11)
- pakiety statystyczne i matematyczne
Na pulpicie znajduje się również link do katalogu domowego użytkownika, w którym można przechowywać swoje pliki. Zarządzać systemem można również z poziomu linii komend. Oto kilka przydatnych komend dla osób, które nie miały styczności z pracą z poziomu terminala:
- cd katalog – przejście do katalogu
- cd ~ – przejście do katalogu domowego
- ls – wyświetlenie zawartości katalogu
- touch plik – utworzenie pliku
- cp plik1 plik2 – skopiowanie pliku
- mv plik1 plik2 – przeniesienie pliku
- rm plik – skasowanie pliku
- mkdir katalog – utworzenie katalogu
- cp -r katalog1 katalog2 – skopiowanie katalogu
- mv katalog1 katalog2 – przeniesienie katalogu
- rm -r katalog – skasowanie katalogu
- man 1 komenda – pomoc dotycząca komendy (jeśli dostępna)
- man 3 funkcja – pomoc dotycząca funkcji standardowej biblioteki języka C (jeśli dostępna)
- komenda ––help – standardowy sposób uzyskania pomocy dotyczący komendy (jeśli dostępna, niekiedy pisane z jednym, niekiedy z dwoma minusami przed opcją „help”)
- gcc – kompilator języka C
- g++ – kompilator języka C++
- fpc – kompilator języka Pascal
- python2 – standardowy interpreter języka Python
- ipython2 – interaktywny interpreter języka Python
- octave – pakiet matematyczny Octave
- R – pakiet statystyczny R
- sas – pakiet statystyczny SAS
Opis sposobów wywoływania pakietów lub kompilacji na serwerze opisany jest w poszczególnych sekcjach poświęconych językom bądź pakietom.
