Ho visto che alcuni problemi, anche delle Nazionali, usano il cosiddetto Grader che implementa in genere la funzione
int solve(variabili di input)
Volevo capire se le variabili che vengono passate alla funzione, che ovviamente occupano memoria, sono calcolate nel totale della memoria usata, o vengono inteligentemente levate.
Chiedo questo perchè ad esempio nel problema “maree” alla funzione solve vengono passati 2 vettori int da 3 000 000 elementi che sono un quantitativo di memoria non indifferente ((43000000)/(10241024)) = circa 11 Mega a vettore??)
Ok che ad esempio in quel problema il limite di memoria è di 256 MB quindi non è un problema per 20 mega
Ma se il problem avesse dato in input una matrice di 10 000 * 10 000 ?? alla funzione “solve” verrebbe passata una matrice da 400 Mega? .-.
Saluti,
Simone
Volevo capire se le variabili che vengono passate alla funzione, che ovviamente occupano memoria, sono calcolate nel totale della memoria usata, o vengono inteligentemente levate.simone.pri
Vengono calcolate, per un semplice motivo: il file che scrivi (contenente la funzione implementata) viene compilato e linkato assieme al grader (che gestisce letture e scritture, chiamando la tua funzione quando necessario). Quindi alla fine si ottiene un unico eseguibile a partire da due file sorgente. Questo eseguibile viene poi utilizzato per la valutazione come fosse un normale programma che legge/scrive su input.txt/output.txt.
Ma se il problem avesse dato in input una matrice di 10 000 * 10 000 ?? alla funzione "solve" verrebbe passata una matrice da 400 Mega? .-.In un caso simile, penso che la memoria a disposizione per quel task verrebbe impostata ad 1 GiB, se non di più :)simone.pri
Vengono calcolate, per un semplice motivo: il file che scrivi (contenente la funzione implementata) viene compilato e linkato assieme al grader (che gestisce letture e scritture, chiamando la tua funzione quando necessario). Quindi alla fine si ottiene un unico eseguibile a partire da due file sorgente. Questo eseguibile viene poi utilizzato per la valutazione come fosse un normale programma che legge/scrive su input.txt/output.txt.Si immaginavo, ma allora perchè non lasciare all'atleta la possibilità di leggere il file come gli pare?
Nella maggioranza dei casi si risolve il problema leggendo l'input carattere per carattere, o numero per numero senza salvarsi in memoria nulla, elaborando direttamente l'input in lettura.
Il passaggio ai grader è iniziato “dall’alto”, per così dire… dalle IOI di qualche anno fa. Personalmente penso ci siano diversi vantaggi:
L’atleta ha meno codice da scrivere
Every new line of code you willingly bring into the world is code that has to be debugged, code that has to be read and understood, code that has to be supported. Every time you write new code, you should do so reluctantly, under duress, because you completely exhausted all your other options.
La lettura è uguale per tutti
Purtroppo non è sempre ovvio stabilire se due file sono ugualmente validi come input per un certo programma (ci sono diverse codifiche, ma anche semplicemente diversi tipi di Newline). Diciamo che in un input.txt ci sono delle righe di testo senza spazi, e diciamo che due atleti leggono rispettivamente con scanf(“%s”, riga); e con do { riga[i++] = getchar(); } while (riga[i] != ‘\n’); Diciamo che entrambi i programmi funzionano.
Ma se da oggi a domani decidiamo di utilizzare dei file con line endings diversi? Per esempio si potrebbe rieseguire la generazione degli input.txt su un sistema operativo diverso… Se l’atleta è fortunato non cambia nulla… ma potrebbe essere sfortunato. Tanto vale allora fare un solo tipo di lettura, di sicuro funzionante. Eventualmente si può sempre cambiare la modalità di lettura in un solo punto e tutti i codici degli atleti si adatteranno.
Il tempo di lettura è ininfluente
Dato che la lettura è uguale sia per la soluzione ufficiale che per le soluzioni degli atleti, è facile “tarare” i casi di prova in modo da dare esattamente X punti ad una soluzione quadratica, Y ad una soluzione lineare, e così via. Quando il tempo di lettura influisce, si rischia di vedere delle soluzioni che prendono meno punti del dovuto (perché usano letture lente) e analogamente soluzioni che prendono più punti del dovuto (perché usano tecniche di fast i/o).
Si impara il concetto di API
Utilizzando sempre la lettura da file non si impara una cosa molto importante nella programmazione: utilizzare e scrivere API. La “funzione solve” infatti, non è altro che una API che il grader usa per interfacciarsi con il programma scritto dall’atleta. Inoltre un problema potrebbe essere interattivo (vedi “aliens”), in tal caso i file non sono proprio sufficienti: l’unico modo per dare un task simile è con le API.
È più facile
Perché preoccuparsi di come funzionano freopen, scanf, gets, getchar, cin, cout, e così via, quando si può farne a meno? (Non del tutto vero, vedi sscanf e stringstream).
La valutazione spesso è più veloce
“La giuria” può decidere di usare tecniche di fast i/o in modo da rendere più veloce la valutazione per tutti.