Alle Olimpiadi di Informatica, il sistema di gara utilizzato maggiormente è CMS, viene utilizzato per la finale nazionale, per tutti i round delle Olimpiadi a Squadre e per le gare di selezione per le Olimpiadi Internazionali.
CMS supporta diversi formati con cui sviluppare i problemi, il formato utilizzato alle Olimpiadi Italiane è Italian YAML.
Per coloro che volessero cimentarsi nella preparazione di un problema, ecco una descrizione del formato Italian YAML.
La struttura di problema per le OII è la seguente:
mytask
├── att
│ ├── grader.cpp
│ ├── mytask.cpp
│ ├── input0.txt
│ └── output0.txt
├── cor
│ └── correttore.cpp
├── gen
│ ├── GEN
│ ├── generatore.py
│ ├── valida.py
│ └── limiti.py
├── sol
│ ├── grader.cpp
│ ├── soluzione.cpp
│ └── template.cpp
├── testo
│ ├── italian.tex
│ ├── english.tex
│ ├── mytask.output0.txt
│ ├── mytask.output1.txt
│ ├── logo.pdf
│ └── testo.pdf
└── task.yaml
Notiamo che alle OII vengono utilizzati i grader e che l'unico linguaggio consentito è il C++. Alle OIS, invece, la struttura del problema è leggermente diversa, ma non entreremo nei dettagli.
attLa directory att contiene i file allegati che i partecipanti possono scaricare durante la gara nella pagina del problema. Solitamente questa directory contiene:
grader.cpp: un grader di esempio che può essere utilizzato per testare le soluzioni in locale.mytask.cpp: il template della soluzione.input0.txt/output0.txt: i file di input e output d'esempio.Gli allegati possono contenere anche più esempi di input/output: input1.txt/output1.txt, ecc.
Gli esempi di input/output devono essere preferibilmente dei symlink che puntano ai file nella directory testo, ad esempio testo/mytask.input0.txt.
Qualora il grader ufficiare non sia troppo complesso, il file grader.cpp può essere un symlink a sol/grader.cpp.
Il template mytask.cpp non deve essere un symlink.
corQuesta directory è opzionale e può contenere il correttore del problema (ed eventualmente altri file in casi particolari).
Il correttore è un file chiamato correttore.cpp che stabilisce se l'output prodotto dal partecipante è corretto o meno:
Al correttore vengono passati tre parametri da riga di comando in questo ordine:
Il correttore deve stampare su standard output il punteggio del testcase, un numero reale tra 0 e 1.
Il correttore può stampare su standard error un messaggio che verrà mostrato al partecipante. Alcuni messaggi speciali sono:
translate:success: output corretto;translate:partial: output parzialmente corretto;translate:wrong: output errato.Questi messaggi verranno tradotti nella lingua del partecipante.
Il correttore non deve crashare, altrimenti CMS esplode. Perciò è importante non usare funzioni come assert e non assumere che l'output del partecipante sia nel formato corretto.
genLa directory gen contiene i file necessari per generare i testcase del problema:
GEN: un file di testo contenente i parametri di generazione di ciascun testcase con il seguente formato:
#ST: rappresentano l'inizio di un subtask con il relativo punteggio, ad esempio #ST: 30 rappresenta un subtask con 30 punti;#STNAME: indicato il nome del subtask, ad esempio #STNAME: N_piccolo;#COPY: indicato che l'input del testcase deve essere copiato da un file, ad esempio #COPY: testo/mytask.input0.txt;# rappresentano commenti;100 42 69, il generatore verrà eseguito con i parametri 100 42 69. Tipicamente l'ultimo parametro rappresenta il seed del testcase.#ST: 0
#STNAME: esempi
#COPY: testo/mytask.input0.txt
#ST: 30
#STNAME: N_piccolo
10 1000 1
20 1000 2
30 1000 3
#ST: 70
#STNAME: N_grande
1000 10000 4
2000 10000 5
3000 10000 6
Qualora questo formato non fosse abbastanza flessibile, è possibile utilizzare il file cases.gen.
generatore.py: il generatore di testcase:
GEN, il generatore viene eseguito con i parametri come argomenti da riga di comando;valida.py: il validatore di testcase:
GEN;limiti.py: un file Python contenente i limiti del problema e i limiti dei subtask:
subtask.MAX_N = 10_000
subtask = [
dict(), # Subtask 0: esempi negli allegati
dict(), # Subtask 1: esempi
dict(MAX_N=100), # Subtask 2: N_piccolo
dict(), # Subtask 3: N_grande
]
Ad eccezione del file limiti.py, i restanti file possono essere scritti in qualsiasi linguaggio (supportato da task-maker).
solLa directory sol contiene le soluzioni complete e parziali del problema:
soluzione.cpp rappresenta la soluzione ufficiale da 100 punti del problema e viene usato per generare gli output dei testcase.grader.cpp rappresenta il grader che viene usato dalle soluzioni.template.cpp deve essere preferibilmente un symlink che punta al template dentro att, ad esempio att/mytask.cpp.Le soluzioni devono avere una o più direttive @check che specificano quali subtask sono risolti o meno dalla soluzione:
@check-accepted: la soluzione risolve tutti i casi del subtask.@check-partial-score: la soluzione prende punteggio parziale nel subtask.@check-wrong-answer: la soluzione sbaglia uno o più casi del subtask.@check-time-limit-exceeded: la soluzione viola il tempo limite del subtask.@check-memory-limit-exceeded: la soluzione viola i limiti di memoria del subtask.@check-runtime-error: la soluzione genera runtime error nel subtask.@check-zero: la soluzione prende genericamente zero punti nel subtask.Le direttive @check devono essere inserite all'inizio del file all'interno di commenti a singola linea e devono contenere i nomi dei subtask specificati nel file gen/GEN da #STNAME, ad esempio:
// @check-accepted: esempi N_piccolo
// @check-zero: N_grande
testoLa directory testo contiene i file necessari per generare il testo del problema:
italian.tex: il file sorgente del testo in italiano.english.tex: il file sorgente del testo in inglese.logo.pdf: il logo della gara, solitamente un symlink.mytask.input0.txt/mytask.output0.txt: i file di input/output da mostrare come esempi.Il testo deve essere formato dalle seguenti sezioni:
Implementation: descrizione delle funzioni da implementare.Grader: descrizione del formato di input/output usato dal grader di esempio.Constraints: descrizione dei vincoli sulle variabili.Scoring: descrizione dei subtask e del punteggio assegnato a ciascuno di essi.Examples: esempi di input/output.Explanation: spiegazione degli esempi.Nel testo sono disponibili alcuni comandi speciali:
\Implementation, \Grader, \Constraints, \Scoring, \Examples, \Explanation: vengono sostituiti con i titoli delle rispettive sezioni tradotti nella lingua del file.\limiti: viene sostituito con i limiti del problema presi da limiti.py:\Constraints
\begin{itemize}
\item $1 \le N \le \limiti{MAX_N}$.
\end{itemize}
\subtask: viene sostituito con il numero di punti del subtask presi da GEN,\limitist: viene sostituito con i limiti del subtaks presi da limiti.py:\Scoring
\begin{itemize}
\item \subtask Casi d'esempio.
\item \subtask $N \le \limitist{MAXX}$.
\item \subtask Nessuna limitazione aggiuntiva.
\end{itemize}
signatures environment: può essere utilizzato per mostrare le funzioni da implementare:\begin{signatures}
C++ & \mintinline[breaklines]{c++}{int annota(int N, vector<int> A);}
\end{signatures}
example environment: può essere utilizzato per mostrare gli esempi di input/output:\begin{example}
\exmpfile{mytask.input0.txt}{mytask.output0.txt}%
\end{example}
task.yamlIl file task.yaml contiene alcuni metadati del problema:
name: il nome corto del problema.title: il nome lungo del problema.memory_limit: il limite di memoria in megabyte.time_limit: il limite di tempo in secondi.name: mytask
title: Task super bello
memory_limit: 256
time_limit: 1.0
infile: ""
outfile: ""
score_mode: max_subtask
token_mode: disabled
public_testcases: all
feedback_level: full
Per testare i problemi in locale puoi usare task-maker.
Per Arch è presente il pacchetto della AUR task-maker-rust.
Per Ubuntu è presente il PPA ppa:dariop1/task-maker-rust:
sudo add-apt-repository ppa:dariop1/task-maker-rust
sudo apt update
sudo apt install task-maker-rust
Per macOS è presente il pacchetto brew bortoz/bortoz/task-maker-rust:
brew install bortoz/bortoz/task-maker-rust
Consulta il repository di task-maker.
task-maker-rust.