#Cos’è una gara di informaticaIn una gara di informatica si risolvono problemi scrivendo programmi. A ogni problema corrisponde un compito preciso: dato un certo input, il programma deve produrre l’output richiesto.
Per partecipare alle gare di informatica non è necessario saper usare un programma già pronto1, non si deve costruire un computer, tanto meno programmare dei robot. Una gara di informatica consiste nel trovare un algoritmo, cioè una sequenza finita di istruzioni che risolva correttamente tutti i casi di input previsti dal problema.
Le gare di informatica hanno quindi due aspetti distinti:
•trovare un algoritmo corretto (non è richiesto di dimostrarne la correttezza);•implementarlo in un linguaggio di programmazione in modo abbastanza efficiente.
#Le Olimpiadi Italiane di InformaticaLe OII sono una competizione rivolta agli studenti delle scuole secondarie superiori. Il percorso di selezione comprende diverse fasi: dalla selezione scolastica alla selezione territoriale, fino alla gara nazionale. Le regole precise, le date e i criteri di selezione possono cambiare di anno in anno: per informazioni aggiornate consultare il sito ufficiale delle OII: https://olimpiadi-informatica.it/.
Dalla fase territoriale in poi, l’obiettivo è lo stesso: leggere i dati forniti, elaborare una risposta e stamparla nel formato richiesto. La teoria richiesta per cominciare a partecipare alle olimpiadi di informatica è molto ridotta: basta saper scrivere codice in un linguaggio di programmazione a scelta (preferibilmente C++, ne parleremo nei capitoli futuri). La teoria spiegata in questo libro comprende principalmente strumenti e tecniche che possono essere applicate in molti problemi diversi, e che rendono la soluzione più efficiente o più facile da tradurre in codice.

#Com’è fatto un problemaUn problema contiene le seguenti sezioni:
•Descrizione: spiega la situazione e che cosa bisogna calcolare.•Input: descrive i dati che il programma riceverà.•Output: descrive esattamente che cosa il programma deve stampare.•Vincoli: indicano quanto possono essere grandi i dati e sono fondamentali per scegliere l’algoritmo.•Subtask (opzionale): sono sottoproblemi più semplici, che permettono di ottenere punteggio parziale.•Esempi: mostrano alcuni input e il corrispondente output.Vediamo un esempio di problema molto semplice:
Descrizione
Dati due interi 𝑎 e 𝑏, stampa il maggiore dei due.
Input
L’unica riga contiene due interi 𝑎 e 𝑏, separati da uno spazio.
Output
Stampa il maggiore tra 𝑎 e 𝑏.
Vincoli
−109≤𝑎,𝑏≤109.
Esempi
inputoutput

7 4
7


6 10
10


Gli esempi mostrano solo alcuni casi semplici, mentre una soluzione deve funzionare per tutti i valori ammessi dai vincoli.

#Il programma e il giudiceDurante una gara il programma non conversa con una persona. Un sistema automatico, chiamato giudice, avvia il tuo programma, gli fornisce l’input e controlla l’output.
La comunicazione tra il programma e il giudice avviene solitamente tramite l’input standard e l’output standard. In C++ questi due canali sono normalmente gestiti da std::cin e std::cout, come vedremo più avanti. Il programma deve terminare da solo: non deve chiedere conferma all’utente e non deve stampare messaggi aggiuntivi come Inserisci un numero.
Per il problema precedente, un output come questo non sarebbe corretto:
Il risultato è: 7
Il giudice si aspetta il formato indicato nella sezione Output, quindi bisogna stampare soltanto:
7
Gli esempi servono a capire il formato dell’output richiesto e a testare la tua soluzione, ma il giudice testerà la tua soluzione con molti altri input nascosti.
Nota che questo non è l’unico formato di problemi possibile: esistono anche i problemi output only e i problemi interattivi:
•output only: Sono problemi in cui l’utente scarica tutti i file di test di input, anche quelli segreti, e li elabora sulla propria macchina. Gli input possono essere statici o dinamici: nel primo caso sono uguali per tutti gli utenti e non cambiano nel tempo, nell’altro sono diversi per ogni utente e vengono rigenerati dopo un intervallo di tempo oppure se viene inviata una soluzione.
Nella fase territoriale delle OII il formato dei problemi è output only dinamico.
•interattivi: Un problema interattivo prevede che la soluzione dell’utente comunichi con un’altra soluzione (o con se stessa) tramite specifiche funzioni. Questa classe di problemi è abbastanza rara: compare a volte tra i problemi della fase finale delle OII, oppure in gare internazionali.

#Vincoli di tempo e di memoriaOltre a dover risolvere il problema correttamente, la tua soluzione dovrà rispettare degli ulteriori vincoli sul tempo di esecuzione e sulla memoria. Andiamo con ordine e consideriamo il seguente problema:
“Dato un intero positivo 𝑁, calcolare la somma di tutti i numeri da 1 a 𝑁.”
•Soluzione 1: Eseguiamo la somma 1+2+…+𝑁 e stampiamo in output il risultato. Questa soluzione è assolutamente corretta, ma calcola la somma eseguendo 𝑁−1 somme diverse.•Soluzione 2: Usiamo la formula chiusa 𝑁(𝑁+1)2 e stampiamo questo valore. Anche questa soluzione è corretta, ma esegue solo 3 operazioni, indipendentemente dal valore di 𝑁.Se proviamo effettivamente a scrivere queste due soluzioni in C++ e misuriamo quanto tempo impiegano a essere eseguite per valori diversi di 𝑁, otteniamo questa tabella:2
N
Soluzione 1
Soluzione 2

105
0.057 ms
< 0.001 ms

106
0.607 ms
< 0.001 ms

107
5.95 ms
< 0.001 ms

108
51.6 ms
< 0.001 ms

109
515 ms
< 0.001 ms



Come possiamo notare, per 𝑁=109 la prima soluzione è più di 500.000 volte più lenta! Questo è dovuto a un semplice fatto: i computer impiegano del tempo a svolgere le operazioni. Questo argomento verrà ripreso in dettaglio nel capitolo sulla complessità computazionale per ora, però, teniamo a mente che esistono soluzioni più o meno veloci che risolvono lo stesso problema.
In modo simile, esistono soluzioni che utilizzano più o meno memoria. La memoria del computer serve a conservare i dati che il programma sta usando: variabili, array, stringhe e strutture dati. Anche la memoria disponibile è limitata e il giudice può interrompere una soluzione che ne utilizza troppa.
Supponiamo di avere un vettore di 𝑁 interi salvati in memoria durante l’esecuzione. Un intero occupa normalmente 4 byte, quindi questo vettore richiede circa 4𝑁 byte: circa 4 MB per 𝑁=106 e circa 4 GB per 𝑁=109.
Per farci un’idea, limiti di tempo e memoria comunemente usati sono 1 secondo e 256 MB di memoria (≈ 60 milioni di interi), ma possono variare da problema a problema.

#I vincoliSupponiamo che un problema chieda di verificare se in una lista compaia un certo valore. Se la lista contiene al massimo cento elementi, anche controllare tutte le posizioni può essere sufficiente. Se invece può contenerne un miliardo, lo stesso approccio potrebbe essere troppo lento o richiedere troppa memoria.
I vincoli aiutano quindi a rispondere a una domanda fondamentale: quanto tempo e quanta memoria posso permettermi di consumare?
I subtask servono proprio a questo. Se si ha una soluzione corretta che tuttavia richiede troppo tempo o troppa memoria, oppure risolve solo casi particolari del problema originale, i subtask permettono comunque di ottenere un punteggio parziale. Facciamo un esempio:
Supponiamo che i limiti per un generico problema siano 𝑁≤1018; dei subtask plausibili possono essere:
•𝑁=1 (10 punti)•𝑁≤100 (40 punti)•𝑁≤106 (50 punti)Se la nostra soluzione sfora il tempo massimo per, ad esempio, 𝑁≥1000, otterremo comunque i punteggi del primo e secondo subtask (10+40=50 punti).

#I risultati della valutazioneQuando inviamo una soluzione, il giudice può restituire risultati diversi:
•Accepted (AC): la soluzione ha prodotto risposte corrette per tutti i test assegnati e ha rispettato i limiti.•Wrong Answer (WA): almeno una risposta è sbagliata oppure l’output non rispetta il formato richiesto.•Compilation Error (CE o CTE): il codice non può essere trasformato in un programma eseguibile, per esempio a causa di un errore di sintassi.•Runtime Error (RTE): il programma si interrompe durante l’esecuzione, per esempio accedendo a una posizione inesistente di un array.•Time Limit Exceeded (TLE): il programma non termina entro il tempo consentito.•Memory Limit Exceeded (MLE): il programma usa più memoria di quella consentita.Un risultato diverso da Accepted non significa sempre che l’algoritmo sia sbagliato. Ad esempio, un TLE indica spesso che serve un algoritmo più veloce.
Nota: su https://training.olinfo.it “Memory Limit Exceeded” e “Runtime Error” sono combinati in un singolo verdetto: Execution Killed.

#Prima di scrivere il codice, pensaHai letto il problema e pensi di saperlo risolvere, ma ti viene il mal di pancia al pensiero delle infinite catene di if ... else if ... else if ... che la tua soluzione prevede. È possibile che qualche osservazione in più semplifichi notevolmente l’implementazione del problema. Vediamo un esempio:
Ci viene data una sequenza di lettere 𝐴 e 𝐵 (ad esempio "ABBAABABA...") che sta a indicare quale dei due giocatori ha segnato ogni punto in una partita di tennis, con la garanzia che la sequenza rappresenti una partita valida. Dopo averci spiegato le regole del punteggio nel tennis, il problema ci chiede chi abbia vinto la partita.
Facile, vero? Basterebbe tenere il conto dei punti, dei set e dei game, considerando i vantaggi in caso di parità sul penultimo punto.
Molti si fermerebbero qui e si cimenterebbero subito nell’implementazione. Fermandosi a riflettere un minuto in più, ci si potrebbe accorgere di un fatto molto interessante: indipendentemente dall’andamento della partita, questa non si può concludere con un punto del giocatore che ha perso. In altre parole, vince il giocatore che segna l’ultimo punto.
Questo ci permette di accorciare il nostro codice da un numero indefinito di righe a una singola riga che controlla l’ultimo carattere della sequenza.

1Per questo esiste https://excel-esports.com2Il tempo di esecuzione dipende dal computer su cui viene eseguito il programma. In questo caso un MacBook Pro M4 Max (16-core CPU) compilato con clang versione 21.0.0, C++17.