(questa pagina non ufficiale è momentaneamente ospitata sul sito che ospita anche le pagine ufficiali sulla selezione locale).
Durante i miei anni di università ho avuto la possibilità di partecipare all'ACM International Collegiate Programming Contest, gara di programmazione organizzata dall'ACM. Più precisamente alla selezione regionale del sud-ovest europeo che comprende Italia, Francia, Svizzera, penisola iberica e (fino al 1998) parte della Germania.
DI COSA SI TRATTA?
Si tratta di gara a squadre di tre persone, tutte della stessa università. Ogni squadra ha a disposizione un computer con compilatori C, C++, Pascal standard e Java, carta e penna e qualsiasi materiale cartaceo. In 5 ore di tempo bisogna scrivere quanti più programmi per computer che risolvano i 6-10 problemi che vengono proposti. Ogni programma deve poter leggere i dati di input da un file, elaborarli e scriverne i risultati sullo schermo. Il formato dei file e qualche esempio sui dati in input sono indicati nel testo stesso del problema.
Un esempio di problema (di così semplici però non ne sono mai capitati) è il seguente:
Nome programma: negativo.c o negativo.p o negativo.cpp o negativo.j
File di input: negativo.inScrivere un programma che legga numeri interi in input e li scriva con segno opposto.
Formato dell'input: un numero su ogni riga. Uno zero (che non deve essere processato) termina l'input.
Formato dell'output: un numero su ogni riga.
Esempio di input:
10
-5
0Output per l'esempio:
-10
5
Un programma in C che risolva il problema (a scanso
di errori di scrittura) è il seguente:
#include <stdio.h>FILE *pf;
int i;main()
{
fopen("negativo.in", "r");
while (1) {
fscanf(pf,"%d\n",&i);
if (i)
prinf("%d\n",-i)
else
break;
}
}
Il corrispettivo in Pascal standard è il seguente:
program negativo(fin,output);var fin:text;
var i:integer;begin
reset(fin,"negativo.in");
readln(fin,i);
while i<>0 do begin
writeln(-i:1);
readln(fin,i)
end
end.
Ogni squadra dopo aver scritto uno di questi programmi
lo prova con i dati forniti ed altri di propria invenzione dopodichè,
se pensa che sia corretto al 100%, ne invia il sorgente con la posta elettronica
alla giuria. Questa lo ricompila e lo esegue con dei dati di prova noti
solo a lei e se il programma genera l'output corretto il problema viene
considerato risolto.
Le possibili risposte della giuria, mandate anche esse
via posta elettronica, sono:
- Program accepted (yuppie!)
- Compile error (il programma non si compila)
- Run time error (il programma genera un errore durante
l'esecuzione)
- Wrong answer (l'output del programma non é corretto:
la risposta più frequente)
- Presentation error (l'output del programma é
corretto ma non nel formato giusto)
- Time limit exceeded (il programma non termina l'esecuzione
nel tempo limite, di solito un minuto)
- Contest rule violation (il programma non rispetta il
regolamento: esso non può leggere o scrivere su file o canali diversi
da quelli consentiti, essere formato da più moduli, se si usano
chiamate al sistema operativo, ecc... . Se tale fatto viene considerato
un tentativo di barare, si rischia la squalifica.)
Vince la gara ovviamente la squadra che risolve più problemi. In caso di parità si confronta il tempo totale di risoluzione dei problemi risolti, che viene calcolato nel seguente modo: si sommano al tempo della sottomissione del sorgente corretto dall'inizio della gara 20 minuti per ogni sottomissione per lo stesso problema che ha prodotto risposta errata. Il tempo totale, che é la somma dei tempi di ogni problema risolto, può quindi superare di gran lunga le 5 ore della gara. (esempio: una squadra effettua quattro sottomissioni: la prima errata del problema A dopo 56 minuti dall'inizio, la seconda corretta dopo 1:42 del problema B, poi un'altra errata del problema C dopo 3:02, ed infine una corretta del A dopo 4:40. Il tempo totale e' 1:42 + 4:40 + 20 minuti di penalità per il problema A = 6 ore e 42 minuti con 2 problemi risolti).
Le prime due squadre passano di diritto alla finale mondiale che si é sempre svolta negli Stati Uniti tranne quest'anno (Aprile 1999) che è stata ad Hannover, Olanda.
Ecco i risultati dell'Università di Genova in tutti
questi anni.
|
|
|
|
PARTECIPANTI |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
In italico il risultato delle squadre di cui facevo
parte.
Se vuoi un dettaglio della mia partecipazione, clicca
qui.
COSA E' NECESSARIO FARE PER POTER PARTECIPARE?
Per poter far parte (o diventare riserva) di una delle squadre che partecipano per l'Università di Genova alla gara di programmazione bisogna superare la selezione locale che si svolge pressapoco alla stessa maniera della gara vera o propria tranne che é individuale e che gli unici linguaggi permessi sono, per il momento, il C ed il Pascal.
La selezione locale é riservata agli iscritti all'Università
di Genova non ancora laureati. Bisognerà inoltre non essere laureati
anche in occasione della gara, ma questo non pregiudica la possibilità
di poter partecipare alla selezione.
Finora é sempre successo che chi ha superato la
selezione locale fosse studente o di Informatica (Scienze dell'Informazione)
o di Ingegneria Informatica, a parte uno iscritto a Ingegneria Elettronica.
La selezione é aperta a tutte le facoltà ma chiaramente quanto
più si frequentano corsi distanti dal mondo scientifico e in particolare
dell'informatica tanto più sarà difficile avere le caratteristiche
necessarie per poter superare la prova. E' infatti richiesta una certa
capacità a programmare in Pascal o C ma soprattutto una buona capacità
di analisi dei problemi e nel trovare l'algoritmo giusto. E' quindi necessario
avere almeno una minima conoscenza della complessità degli algoritmi.
Bisogna poi saper leggere testi in un semplice inglese per la gara vera e propria. La selezione locale finora si é sempre svolta con i testi in italiano.
Inoltre, cosa più importante, chi supera la selezione dovrà impegnarsi per prepararsi alla gara: le squadre dovranno incontrarsi per lo meno 8-10 volte nei mesi di settembre-ottobre, in particolare se si è alla prima esperienza.
Le prossime selezioni locali si svolgeranno a maggio 1999.
Le iscrizioni dovrebbero iniziare fra poco alla pagina
ufficiale di Genova.
COME FARE A SUPERARE LA SELEZIONE LOCALE?
Capita spesso che coloro che superano la selezione locale
siano gli stessi degli anni precedenti.
Bisogna infatti pensare che, oltre alla bravura, hanno
dalla loro parte anche la preparazione pre-gara e l'esperienza della gara
vera e propria. D'altra parte ho notato che la maggior parte dei partecipanti
alla selezione non sanno in cosa consista realmente la prova o come si
debba affrontare.
Per limare almeno in parte questo divario ecco i miei consigli (dall'alto di quattro anni di esperienza) su come prepararsi e su come affrontare la selezione.
2 suggerimenti per prepararsi:
1) prova a leggere alcuni testi dei problemi degli anni
precedenti alla pagina
ufficiale di Genova.
2) se programmi abitualmente, simula una gara. Se invece
sei un pò fuori forma provane anche più di una.
Dieci suggerimenti d'oro durante la prova:
1) Calma e lucidità. Se durante la gara hai qualche
dubbio, anche sui testi, chiedi sempre spiegazioni nei modi che ti verranno
indicati (vedi punto 2).
2) LEGGI le istruzioni per la gara (non riesco a capire
perchè molti non lo facciano).
3) leggi SCRUPOLOSAMENTE TUTTI i testi dei problemi:
molti che possono sembrare complicati poi magari sono semplicissimi o viceversa.
4) Scegli uno o più problemi da risolvere (non
sceglierne troppi per volta!). Se é disponibile una classifica parziale
della gara prendi anche spunto da quali problemi sono stati risolti dagli
altri.
5) Analizza attentamente le difficoltà dei problemi
scelti, in particolare considera i casi particolari che possono esserci.
Eventualmente ritorna al passo 4 o addirittura al 3.
6) Scegli un algoritmo che sia un compromesso tra semplicità
e sicurezza sulla correttezza. Se ti accorgi che il programma rischia di
diventare troppo complesso, considera di ritornare al punto 5 o addirittura
al 4.
7) Una volta scritto il programma, provalo con i dati
di prova e con casi particolari notati al punto 5.
8) Se il programma produce l'output giusto mandalo alla
giuria. Se non lo produce, considera di utilizzare dei debuggers (se disponibili)
o di inserire codice di debugging (che dovrà poi essere tolto) per
trovare l'errore. Trovato l'errore, ritorna al punto 7.
9) Mentre aspetti il responso dalla giuria prenditi un
momento di pausa. Se il responso é favorevole, complimenti e torna
al punto 3, 4 o 5. Se così non fosse, prova a rileggere il testo
del problema e a trovare casi particolari non scovati al punto 5. Prova
il programma con altri dati. Se niente di questo serve, considera seriamente
la possibilità di abbandonare il problema dato che, soprattutto
quando si é da soli, é facile fissarsi su certe idee che
possono essere sbagliate e quindi si rischia di perdere tempo dedicabile
alla risoluzione di altri problemi.
10) Vinci :-)
Comments to otto@dist.unige.it