Booklet soluzioni 2015
- 9 marzo: inizio lavori.
- 12 aprile: prima bozza di soluzione per tutti i problemi.
Questa è la parte "difficile", non si può decidere facilmente se una certa spiegazione di una soluzione può andar bene per essere inserita in un booklet, la bellezza di una spiegazione è soggettiva. Una cosa importante è che ci sia chiarezza nei vari passaggi: punti bonus per illustrazioni e figure in generale.
La consuetudine che si segue quando si prepara un booklet è quella di (se opportuno) andare per gradi di difficoltà, partendo quindi da una soluzione più semplice e arrivando per raffinamenti successivi fino alla soluzione ottima. Ciò è anche consistente con l'esistenza dei subtask, ad esempio si potrebbe dire "con l'algoritmo che abbiamo appena trovato riusciamo a risolvere in tempo ragionevole i primi 3 subtask".
A spanne, crediamo che questa sia una buona metrica:
- La soluzione più efficiente, va (ovviamente) spiegata nei dettagli, e va aggiunto anche il codice.
- Le soluzioni più lente possono essere lasciate all'immaginazione del lettore (ad esempio una frase che dice "Alla luce di quanto osservato è possibile implementare un algoritmo quadratico, in grado di totalizzare la metà dei punto.", senza spiegare i dettagli).
- In alcuni casi, tuttavia, le soluzioni più lente sono interessanti/istruttive, e quindi può valere la pena spendere del tempo per descriverle più nei dettagli. Ad esempio, date un'occhiata al problema Taglialegna delle ultime OII (trovate sotto il link al booklet che abbiamo prodotto per quell'occasione).
Un'altra consuetudine che abbiamo seguito fin ora è quella di fornire uno o più (se ad esempio ci sono due approcci fondamentalmente diversi alla risoluzione del problema) codici funzionanti. Questo punto diciamo che più che una consuetudine è oramai un requisito 😄. Il linguaggio ufficiale (e unico) che abbiamo deciso, per tanti motivi, di adottare per scrivere il codice sorgente "modello" presente nel booklet è il C++11 (se necessario si veda la sezione Non conosco il C++11, cosa posso fare?).
- Gara online pre OII 2014.
- OII 2014 (sessione di pratica).
- OII 2014.
- Una selezione locale, svolta a Cesena, per andare alle regionali ACM-ICPC.
- IOI 2005 (inglese).
- IOI 2008 (inglese).
Per chi capisce l'inglese, altre "ispirazioni" si possono trovare negli editorial pubblicati su Codeforces (ad esempio questo).
- Non si richiede uno stile di scrittura particolarmente aulico, ma è bene che sia un po' distaccato.
- Preferire quando possibile la forma impersonale ("è possibile, è facile, è immediato"); tuttavia, va anche bene la prima persona plurale qualora non se ne abusi.
- Evitare di usare troppo la retorica e la ricerca del dialogo con chi legge.
Il codice deve essere tenuto in una sezione a parte rispetto alla descrizione (si veda Come faccio a inserire una nuova sezione?).
Inoltre, per uniformità e per rimanere coerenti con quanto fatto negli anni passati, è bene che:
- Commenti e variabili siano in italiano.
- Le parentesi graffe vengano aperte sulla stessa riga.
- Non ci sia un blocco senza graffe che contiene un blocco con le graffe. Tuttavia, il contrario è consentito.
- Le keyword
if,for,while, ... siano seguite da uno spazio. - Non ci sia nessuno spazio prima delle parentesi dopo i nomi di funzione.
- Venga evitato il camel case, noi abbiamo sempre usato i nomi tutti minuscoli con underscore.
- Vengano messi spazi attorno agli operatori aritmetici.
- (Nel caso abbiate bisogno di costanti) Definizioni come
#define MAXN 100010siano sostituite daconst int MAXN = 100010; - (In caso dobbiate allocare vettori statici), questi siano dimensionati correttamente. Allocare vettori sovradimensionati è un trucco sporco e poco elegante.
- Gli
#includee imainnon vanno scritti. Implementate solo la funzione indicate nel testo.
Chi non è ancora iscritto a github (questo sito), deve farlo per poter lavorare al progetto. Quando vi siete iscritti e loggati, tornare alla pagina del progetto e cliccate su "Watch", in modo da essere notificati di ogni discussione/cambiamento/pull request e così via.
Iscrivetevi a ShareLatex (è gratis ovviamente). Potete farlo da qui. Una volta iscritti loggatevi e passate al passo 1.
Nota: Se siete più esperti, potete invece usare un vostro compilatore LaTeX (ma comunque ShareLatex è gratis e funziona bene, quindi perché no?).
Cliccate su questo link. Si dovrebbe aprire una pagina di SL in cui potete "clonare" il template.
Questo è il contenuto della cartella del template:
-
locale/italian.texnon toccate -
cms-contest.clsquesto file nuoce alla salute, non volete davvero leggerlo, fidatevi -
main.texquesto è il file principale che dovrete compilare -
testo.texquesto è un file "finto". Dovrete cancellarlo e sostituirlo col file del testo (più dettagli dopo) -
soluzione.texquesto è il file che dovrete riempire
Questo è uno screen di quello che vedo io quando clono il template:
Vi consigliamo di rinominare il progetto, che di default si chiama "problema_OIS". Potete farlo cliccando sulla matitina che compare quando portate il mouse sul nome del progetto.
Cliccate su "Condividi", e poi "Rendi pubblico":
A questo punto, impostate che volete che chiunque abbia il link possa solo leggere, ma non modificare. Applicate e aprite una issue qui su github con il titolo "Link SL problema <qui il nome del problema>", in cui scrivete il link al progetto SL per quel problema. Ad esempio, il link per il progetto dell'immagine sopra era https://www.sharelatex.com/project/54fa0caf590736ca3075240b (lo trovate nella barra della URL).
La prima cosa da fare è eliminare il file testo.tex. Potete farlo dalla freccina rossa che compare quando selezionate il file:
A questo punto scaricate da github il file italian.tex del problema su cui state lavorando e caricatelo su SL. Rinominatelo infine in testo.tex.
In alternativa (invece di cancellare, caricare un nuovo file, rinominarlo) è sufficiente modificare il testo.tex esistente sostituendo il suo contenuto con il contenuto dell'italian.tex desiderato.
Aprite soluzione.tex e scrivete lì la soluzione. Mentre scriverete la soluzione probabilmente vi verranno in mente dei dubbi, oppure vi mancheranno le figure, oppure vorrete includere il codice formattato ma non saprete come fare. Leggete la prossima sezione e dovreste trovare delle risposte.
Concetto generale: per qualunque cosa, potete scrivere a noi. Il modo più utile di scrivere a noi in modo che anche gli altri possano imparare dalle domande degli altri è probabilmente quello di aprire delle issue sulla pagina di questo progetto github. // TODO
Prima di tutto, niente panico. A noi serve solo un piccolo subset di funzioni di LaTeX. In generale se non riuscite a trovare come fare in una googlata, sentitevi liberissimi di chiedere qui, aprendo una issue.
Per un tuffo di 5 minuti nella sintassi, potete guardare questo.
Creare immagini vettoriali di qualità è un'operazione abbastanza lunga e faticosa. Noi di solito usiamo asymptote. La soluzione migliore al problema delle immagini probabilmente è:
- le immagini le facciamo noi (ma può essere che ci metteremo qualche giorno)
- voi scrivete la soluzione, facendo riferimento anche alle immagini (che non ci saranno ancora), poi mano a mano che ne avete bisogno aprite una issue su questo progetto, in cui descrivete che cosa vorreste (magari fate upload di uno schizzo a penna se vi sentite artistici), e noi ve la produciamo.
Di nuovo, don't panic. Queste cose succedono e non dovete vergognarvene. Conviene che apriate una issue (in cui indicate chiaramente il nome del problema, quindi con un titolo chiaro del tipo "Chiarimenti soluzione lineare di trampolino").
Come per le immagini, creare il codice colorato non è facilissimo. Gabriele ha scritto un beautyfier apposta per questo compito. Una volta che avete il codice definitivo della soluzione, aprite una issue apposta e Gabriele vi manda il codice da inserire in soluzione.tex per avere il codice colorato giusto.
Puoi creare una nuova sezione (per organizzare meglio la tua soluzione o per crearne una per il codice) in due passaggi: prima definisci un comando (per es. \NlogNVeloce) scrivendo una cosa simile a:
\createsection{\NlogNVeloce}{{\small{$\blacksquare$}} \normalsize Una soluzione $O(N \log N)$ efficiente}
E poi al momento giusto usi il comando (che crea una sezione), semplicemente scrivendo \NlogNVeloce.
Se conosci il C++, il problema quasi non si pone. Scrivi il codice in C++ e ci mettiamo un attimo a renderlo più "C++undicioso".
Se non conosci il C++ ma solo C o Pascal, la faccenda si complica. Probabilmente la cosa migliore è aspettare fino all'ultimo a scrivere il codice (te lo scriviamo noi).
// TODO