Questo è il primo anno che ho la possibilità di partecipare alle territoriali, giacchè vorrei passare spero possiate rispondere a qualche domanda:
Per quanto riguarda i grafi, i problemi delle territoriali richiedono algoritmi semplici (come quelli per la visita in profondità e in ampiezza) o anche algoritmi un po più sofisticati (come la ricerca del cammino minimo dato un grafo pesato)?
Ah, e gli algoritmi di visita in profondità e in ampiezza permettono di fare le stesse cose o uno dei due è più indicato per certi tipi di problemi?
E’ importante sapere la tabella di codici ASCII per manipolare le stringhe? E’ importante saper usare le stringhe?
Se uso il c++, posso usare tutte le librerie e i containers standard? E i file sorgente che faccio testare al compilatore di questo sito verranno compilati allo stesso modo anche dal compilatore di gara?
Scusate le domande stupide ma ho iniziato a prepararmi circa tre giorni fa
Potrebbe capitare (e nemmeno così raramente) che sia richiesto il cammino minimo, tuttavia se hai compreso bene le due visite (BFS e DFS) puoi arrangiarti senza troppi problemi (Dijkstra non è indispensabile alle territoriali).
Per quanto riguarda le differenze tra BFS (ampiezza) e DFS (profondità) diciamo che la prima è comoda quando il grafo non è pesato (quindi puoi comunque pensarlo come grafo dove ogni arco pesa 1) mentre la seconda per tutto il resto: dipende molto da persona a persona, io personalmente alle territoriali non ho mai usato la BFS e mi sono sempre arrangiato con la DFS, ma saperle entrambe fa solo bene.
Stringhe:
Non hai niente da imparare a memoria per quanto riguarda la ASCII table.
Se ad esempio ti dovesse servire il codice necessario a produrre la ‘a’ ti basterà stampare a video il carattere ‘a’ castato in int.
Insomma puoi comunque (a inizio gara) produrti un file di testo con tutti i simboli ASCII e i rispettivi valori interi!
Librerie/Containers:
Puoi usare tutto ciò che è standard ( <algorithm>, <vector>, <string>, … ).
Per i grafi servono soprattutto DFS e BFS, le quali sono quasi equivalenti qui alle territoriali. La BFS è indicata per percorsi minimi su grafi non pesati, mentre la DFS per quelli massimi (sempre senza peso). Comunque potresti incontrare problemi di cammini minimi (o massimi) su grafi pesati, per i quali ti conviene usare l’algoritmo di Dijkstra.
Sapere il codice ASCII a memoria non ti servirà a nulla e non viene richiesta nessuna abilità particolare nella manipolazione delle stringhe.
Con il C++ hai a disposizione l’intera STL (con tutti algoritmi e contenitori annessi).
Il compilatore dovrebbe essere lo stesso, ma se volevi chiedere se verranno valutati così come su questa piattaforma (mostrando il punteggio in pratica) onestamente non ti so dire. Sapevo che forse tra qualche anno sarà così, ma fino all’anno scorso non si aveva modo di verificare il codice.
Qualche altra info sulle territoriali:
Di solito c’è un problema semplice da risolvere senza l’utilizzo di nessun algoritmo e due più complicati. Questi due vertono solitamente sui grafi o su qualche algoritmo Greedy (negli ultimi 2 anni anche Programmazione Dinamica).
EDIT: riguardo la DFS sono d’accordo con Vash, io usavo solo quella alle territoriali.
Ora come ora, se esce Dijkstra sono fregato perchè non lo so implementare (oggi ho provato e in 2 ore di codificazione ho preso metà dei punti) invece se esce un grafo standard tipo “torero” delle territoriali 2007 prendo tutti i punti con facilità.
Per quando riguarda la programmazione dinamica, riesco a risolvere problemi del livello di sommelier dell’anno scorso, per quelli più difficili non saprei.
Lunedì non andrò a scuola per prepararmi alla gara ahahah, quindi ho due giorni e due notti di tempo, quale dei due argomenti (grafi o dinamica) mi conviene fare meglio?
L'anno scorso si passava solo con 50/50 (tutti e tre i problemi giusti) Ma erano particolarmente semplici. In teoria se ne fai 2 su 3 è un buon risultato, ma dipende comunque con chi gareggi. Se nella tua sede fanno tutti il massimo del punteggio e tu fai anche solo un punto in meno, non passi. In genere a Roma i punteggi sono alti.
Se riesci a risolvere problemi tipo Sommelier in dinamica allora questa la puoi anche lasciare da parte per ora. Concentrati più sulla ricorsione (è forse uno degli strumenti più potenti) e sulle visite dei grafi.
Si, sono di Roma, quest’anno temevo principalmente due persone della provincia, ora che so che anche tu sei di Roma e sei iscritto al forum sono diventate 3 ahahah
Comunque c’è anche un ripescaggio nazionale, o sbaglio? Perchè a 50 punti l’anno scorso non ci arrivavo, ma a 44/46 si (mojito mi ha tagliato il punteggio).
Faccio grafi e ricorsione (che è la tecnica che so usare di meno) allora.
Si, sono di Roma, quest'anno temevo principalmente due persone della provincia, ora che so che anche tu sei di Roma e sei iscritto al forum sono diventate 3 ahahah
Comunque c'è anche un ripescaggio nazionale, o sbaglio? Perchè a 50 punti l'anno scorso non ci arrivavo, ma a 44/46 si (mojito mi ha tagliato il punteggio).
Faccio grafi e ricorsione (che è la tecnica che so usare di meno) allora.
Livex
Che io sappia non cè mai stato un ripescaggio di nessun tipo, o passi o ciccia. Chi sarebbero le altre due persone che temi? ahah
PS: comunque se non le hai già fatte io ti consiglio caldamente di fare le GATOR che termineranno stasera
La Gator l’ho fatta, ne ho risolti 3 e mezzo (non so implementare algoritmi complicati sui grafi).
Pensavo qualcosa del tipo: Viene preso il primo di ogni sede, e poi vengono presi i migliori N a livello nazionale, in modo che alla fine passano circa 80 persone in tutta Italia.
Temo un oro alle OII dell’anno scorso (in realtà non è che lo temo, diciamo che ho riconosciuto la sua superiorità ahah) e poi un altro molto forte alle olimpiadi di Matematica che farà la gara anche di informatica.
Altre domande che mi sono venute risolvendo alcuni problemi:
Avete mai provato ad usare il goto in gara? Ci siete riusciti o ve l’ha rifiutato?
Prima della gara c’è del tempo (mezz’ora?) per provare l’ambiente di sviluppo giusto?
La Gator l'ho fatta, ne ho risolti 3 e mezzo (non so implementare algoritmi complicati sui grafi).
Pensavo qualcosa del tipo: Viene preso il primo di ogni sede, e poi vengono presi i migliori N a livello nazionale, in modo che alla fine passano circa 80 persone in tutta Italia.
Temo un oro alle OII dell'anno scorso (in realtà non è che lo temo, diciamo che ho riconosciuto la sua superiorità ahah) e poi un altro molto forte alle olimpiadi di Matematica che farà la gara anche di informatica.
Altre domande che mi sono venute risolvendo alcuni problemi:
Avete mai provato ad usare il goto in gara? Ci siete riusciti o ve l'ha rifiutato?
Prima della gara c'è del tempo (mezz'ora?) per provare l'ambiente di sviluppo giusto?
Livex
Da ogni sede vengono presi i primi 3-4 poi però dipende da quanti atleti ci sono nella sede e soprattutto dalla regione di appartenenza. Comunque per la cronaca sono anche io un medagliato delle OII ahah
Per quanto riguarda il goto....perchè?? Che necessità hai di usarlo?? In genere è definita una "Cattiva Pratica" l'utilizzo del goto in linguaggi di alto livello dato che hai decine di altri modi per fare la stessa cosa. Io te lo sconsiglio ma comunque dovrebbe essere accettato senza problemi. Si in genere puoi presentarti una mezzoretta prima per provare che la tua postazione funzioni. Per quanto riguarda l'ambiente quest'anno dovrebbe esserci una distro di linux che puoi provare in macchina virtuale già da subito.
La Gator l'ho fatta, ne ho risolti 3 e mezzo (non so implementare algoritmi complicati sui grafi).
Pensavo qualcosa del tipo: Viene preso il primo di ogni sede, e poi vengono presi i migliori N a livello nazionale, in modo che alla fine passano circa 80 persone in tutta Italia.
Temo un oro alle OII dell'anno scorso (in realtà non è che lo temo, diciamo che ho riconosciuto la sua superiorità ahah) e poi un altro molto forte alle olimpiadi di Matematica che farà la gara anche di informatica.
Altre domande che mi sono venute risolvendo alcuni problemi:
Avete mai provato ad usare il goto in gara? Ci siete riusciti o ve l'ha rifiutato?
Prima della gara c'è del tempo (mezz'ora?) per provare l'ambiente di sviluppo giusto?
Livex
I P.O. (quindi anche il tuo oro) non fanno le territoriali, hai una persona in meno da temere
