¶ Grader
Oh no! Un altro task con i grader!
~ You, probably.
¶ Introduzione ai grader
Ormai da molti anni le Olimpiadi Italiane di Informatica (OII) sta usando i grader nelle selezioni nazionali (e successive) imitando le Olimpiadi Internazionali di Informatica (IOI). In questa breve guida vedremo come si usano e perché vi possono aiutare in molte occasioni!
¶ Come funzionano e perché esistono
Nei task "tradizionali" senza grader la soluzione di un task consiste in un singolo file sorgente in cui scrivi tutto il codice della soluzione. Quindi, in questo file è presente sia il main che tutte le funzioni che hai scritto per risolvere il task. In un task con i grader invece i file in questione sono due:
- Il file del grader (per esempio
grader.cpp), scritto dagli autori del problema, che contiene ilmain, la dichiarazione delle funzioni da implementare nella soluzione e l'implementazione di alcune funzioni che puoi chiamare dalla soluzione. - Il file con la soluzione al problema (per esempio
soluzione.cpp), scritto da te. Questo contiene l'implementazione delle funzioni richieste dal task, più altre funzioni a piacere che puoi usare per risolvere il problema.
Nota che nel file con la soluzione non deve essere presente il main! Infatti se per qualche ragione ci fosse il main sia dentro grader.cpp che dentro soluzione.cpp otterresti un errore simile a:
/tmp/ccY5iLl3.o: In function `main':
soluzione.cpp:(.text.startup+0x0): multiple definition of `main'
/tmp/ccQULgQx.o:grader.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
Tutto ciò mi sembra solo una complicazione inutile!
~ Chi non ha mai usato i grader prima, o che non ha ancora letto questa guida.
Ci sono molte ragioni per usare i grader, sia dal punto di vista di chi sta facendo la gara, sia da quello di chi la prepara.
- Non devi leggere l'input! Per scrivere la soluzione non devi preoccuparti della lettura dell'input e la scrittura dell'output. Quindi non devi preoccuparti di capire il formato del file di input nei dettagli, né di capire il formato del file di output. Soprattutto non rischi di introdurre dei bug (spesso molto difficili da debuggare) nella lettura dell'input.
- Non devi leggere velocemente l'input: esistono modi per leggere molto velocemente l'input, risparmiando molto tempo di esecuzione ed essenzialmente ottenendo un vantaggio rispetto a chi legge l'input normalmente. Con i grader è possibile garantire che tutti leggano il file di input esattamente allo stesso modo. Questo permette agli autori dei problemi di essere più precisi nel tarare i tempi, evitando che soluzioni subottime riescano a prendere troppi punti.
- È possibile scrivere problemi interattivi: problemi in cui la soluzione non deve semplicemente ricevere tutto l'input all'inizio, ma può interagire con un altro programma (il grader). Questo apre le porte a molti problemi interessanti.
Nota che il grader che trovi tra gli allegati non è detto sia lo stesso che viene usato per la valutazione!
¶ Come si usano
Facciamo un esempio semplice, che illustra tutti gli aspetti principali di un task con i grader che possono capitare. Questo task non esiste veramente, è solo un esempio.
Tizio è un amante degli array (sì, lo so, la miglior metafora della storia), in particolare ama quelli che hanno somma positiva (maggiore di zero)! Aiutalo a trovare tutti i sottoarray con somma positiva, e tra questi quello con somma massima.
Un sottoarray è l'insieme di tutti gli elementi compresi tra due indici.Implementazione
Dovrai sottoporre un unico file, con estensione.co.cpp.
👉 Tra gli allegati a questo task troverai dei templatesoluzione.cesoluzione.cppcon un esempio di implementazione.Dovrai implementare la seguente funzione:
int trova(vector<int> v);
- L'array è lungo e contiene i numeri da analizzare.
- La funzione deve ritornare la somma del sottoarray con somma massima.
Il tuo programma potrà utilizzare le seguenti funzioni, definite nel grader:
void sottoarray(int i, int j);
- Chiama la funzione
sottoarrayquando trovi un sottoarray con somma positiva.- Il sottoarray è , e sono inclusi e il sottoarray deve avere somma positiva. Deve valere .
La prima cosa da fare è andare nella pagina del problema e scaricare grader.cpp. È anche consigliato scaricare il template dell'implementazione, cioè uno scheletro di soluzione in cui è presente tutto il codice necessario per complilare, ma non l'effettiva soluzione.
Per esempio, dal sito possiamo scaricare:
// grader.cpp
#include <iostream>
#include <cassert>
#include <vector>
using namespace std;
int trova(vector<int> v);
void sottoarray(int i, int j) {
assert(i <= j);
cout << i << ' ' << j << '\n';
}
int main() {
int N;
cin >> N;
vector<int> v(N);
for (int i = 0; i < N; i++) {
cin >> v[i];
}
cout << trova(v) << '\n';
}
// soluzione.cpp
#include <vector>
using namespace std;
void sottoarray(int i, int j);
int trova(vector<int> v) {
// TODO: implementa qui la soluzione
sottoarray(0, 1);
sottoarray(2, 5);
return 42;
}
Ora possiamo dimenticarci del contenuto di grader.cpp, non sarà più necessario riaprilo! Dentro soluzione.cpp invece dobbiamo ovviamente scrivere la nostra soluzione!
Come ci dice il testo dobbiamo inserire il nostro codice dentro trova, e possiamo usare la funzione sottoarray. Nota che noi non dobbiamo implementare la funzione sottoarray, questa è definita nel grader!
Riporto qui una semplice soluzione, che probabilmente non è ottimale, ma è utile per capire alcuni trucchi e cose che si possono fare con i grader.
// soluzione.cpp
#include <vector>
using namespace std;
void sottoarray(int i, int j);
int N;
vector<int> v; // copia dell'input
vector<int> prefix; // somme prefisse: prefix[i] = v[0] + ... + v[i]
// calcola la somma di v[i...j] usando le somme prefisse
int somma(int i, int j) {
if (i > 0) return prefix[j] - prefix[i-1];
return prefix[j];
}
int trova(vector<int> v) {
// copia l'input in un array globale
::v = v;
N = v.size();
// calcola le somme prefisse
prefix.resize(v.size());
prefix[0] = v[0];
for (int i = 1; i < N; i++)
prefix[i] = prefix[i-1] + v[i];
// trova la soluzione
int best = -1;
for (int i = 0; i < N; i++) {
for (int j = i; j < N; j++) {
int s = somma(i, j);
if (s > 0) {
sottoarray(i, j);
}
best = max(best, s);
}
}
return best;
}
Analizziamo punto per punto questo codice:
- Alla riga 6 non ho implementato la funzione
sottoarray(è nel grader!). - Alle righe 8-10 ho definito delle variabili globali, anche con i grader è possibile usarle. Nota che ho definito
vche ha lo stesso nome del parametro ditrova. Per poterla assegnare, alla riga 20 ho usato un trucco:::v = v,::prima di qualcosa accede allo scope globale (quindi a sinistra dell'uguale c'è la variable globale), mentre a destra dell'uguale c'è il parametro (perché semplicemente ha più priorità). In alternativa è possibile usare un nome diverso o per il parametro, o per la variabile globale. - Alle righe 13-16 ho definito una funzione, anche con i grader è possible definire a piacere funzioni aggiuntive!
- Dentro
trova, alla riga 35, ho chiamato la funzionesottoarraydefinita dal grader. - La funzione
trovadeve restituire un intero, alla riga 40 restituisco il sottoarray di somma massima.
A questo punto la soluzione è scritta, è sufficiente inviare solo soluzione.cpp, quindi non il grader.
¶ Come si compila
Come prima cosa assicurati che soluzione.cpp e grader.cpp si trovino nella stessa cartella, per esempio puoi tenere una cartella per ogni task.
Dopo aver aperto un file .cpp vai su Genera → Imposta i comandi per la compilazione.
Poi inserisci grader.cpp nella sezione Build. Questo farà in modo che ogni volta che compili un file .cpp (come soluzione.cpp), anche il grader.cpp verrà compilato.
Puoi compilare normalmente premendo F9 con aperto il file con la soluzione.
Su Code::Blocks è necessario creare un progetto per compilare la soluzione con il grader.
Il progetto deve essere di tipo Console application, e va scelto C++ come linguaggio.
Il titolo del progetto non è importante, per esempio il nome del task può essere usato per tenere i file in ordine.
Di default Code::Blocks crea un file main.cpp, a noi questo file non serve e possiamo rimuoverlo dal progetto.
Adesso possiamo aggiungere i due file sorgente al progetto: soluzione.cpp e grader.cpp.
A questo punto possiamo compilare ed eseguire normalemente premendo F9.
Su CodeLite è necessario creare un Workspace e poi un progetto al suo interno per compilare insieme la soluzione e il grader. Il nome del workspace può essere per esempio quello della gara, mentre il nome del progetto quello del task.
Di default CodeLite crea un file main.cpp, a noi questo file non serve e possiamo rimuoverlo dal progetto.
Adesso possiamo aggiungere i due file sorgente al progetto: soluzione.cpp e grader.cpp.
La prima volta che compiliamo è possibile che ci compaia una finestra di questo tipo, è sufficiente selezionare GCC (o una qualunque delle altre opzioni) come compilatore.
g++ grader.cpp soluzione.cpp -o soluzione -Wall -Wextra
È sufficiente mettere anche grader.cpp nello stesso comando che useresti per compilare la soluzione.