Ciao a tutti, più o meno a inizio estate ho trovato questo portale tramite il sito delle OII, alle quali ho intenzione di partecipare nell’imminente anno scolastico (dovrei fare il quarto anno… Avrei voluto partecipare già lo scorso anno ma purtroppo alle terze classi non è stato concesso ). Non mi è servito molto tempo per rendermi conto che per potersi classificare bene sia alla fase territoriale che a quella nazionale, non sono sufficienti le conoscenze derivanti dallo studio a scuola, per cui mi sono subito cimentato nella risoluzione di alcuni problemi partendo da quelli che mi sembravano abbastanza “semplici”. Nel frattempo, ho letto la guida del prof. Alessandro Bugatti, che mi è stata di aiuto per risolvere problemi leggermente più articolati, e sto anche seguendo dei video su youtube che ho trovato navigando su questo forum. Tuttavia, penso di non avere ancora molta praticità con i problemi che richiedono un approccio ricorsivo, o di programmazione dinamica, per cui vorrei chiedervi quali sono i problemi di queste 2 categorie dai quali mi conviene iniziare per migliorare. Grazie in ogni caso a chiunque potrà rispondermi!
P.S.
Dimenticavo, anche qualche problema per avvicinarmi ad algoritmi più complessi sui grafi non mi dispiacerebbe
Se non li hai già fatti fai easy1, easy2 e easy3. Poi passerei ai problemi delle territoriali (prendi i problemi per evento), fatti quelli ois e nazionali.
la ricorsione cerca di evitarla quanto più possibile perché molto spesso una soluzione ricorsiva è anche esponenziale, tuttavia in certi casi può risultare anche molto utile soprattutto quando si utilizzano alberi o strutture più complesse. Ricorda che un problema che può essere risolto con la ricorsione, può essere risolto anche senza, quindi è difficile definire una categoria. Un esercizio che mi viene in mente è Treno di container
la programmazione dinamica è fondamentale saperla, nella guida del prof. Bugatti è detto ben poco, se vuoi approfondire puoi guardare qui nel capitolo 7. Qui sul correttore li puoi trovarli sotto il tag dp. Alcuni esercizi possono essere: Ma chi è quel mona?, Rescaling Sequence o Pranzo dalla nonna
per i grafi alle territoriali ti basta sapere dijkstra, bfs e dfs, alle nazionali potrai troverare algoritmi più complessi come LCA, ordinamento topologico o componenti fortemente connessi. Se vuoi allenarti puoi trovare sempre sul correttore sotto il tag graph. Alcuni esempi: Viaggio, Barbablu, Ponti e isole
Ma la cosa più importare è fare tanta pratica e esercizi e non aver paura di chiedere consigli sul forum
Ciao,
io un paio di anni fa mi trovavo nella tua identica situazione solo senza la fortuna di avere altra gente a cui chiedere, così la prima cosa che feci per prepararmi a dovere fu cercare dei buoni libri sul C e sul C++ (dato che a scuola non avevo fatto molto di programmazione e il mio libro è più utile come carbonella che per imparare un linguaggio), cosa che tu puoi evitare di fare se conosci già a sufficienza le basi dei linguaggi (e qualcosa di OOP che non fa mai male) e dando un’occhiata a questi due siti: http://www.cplusplus.com http://it.cppreference.com/w/ (c’è anche in inglese se preferisci)
In particolare ti consiglio di dare un’occhiata a e oltre che a per via di priority_queue che per qualche algoritmo è utilissimo.
Per i problemi con cui allenarti quasi tutti quelli sotto il tag greedy sono fattibili:
Studio amico (suggerimento: counting sort), DreamTeam Selection (dai un’occhiata a std::sort e std::nth_element), Vortex Improved Motors (non so che ci faccia sotto i tag dp e greedy ma con un po’ di matematica fatta alla buona si fa), Server Farm (è impressionante vedere quanto sia utile std::sort), Impila la pila (greedy per eccellenza), Truffa contabile (permette tanti approcci diversi), Rispetta i versi (è uno dei problemi delle vecchie selezioni territoriali, non troppo difficile ma una delle cose che è utile nelle gare a tempo è in quanto tempo si butta giù una soluzione), Canottaggio (i problemi delle GATOR sono simili per difficoltà [nei casi fortunati] a quelli delle territoriali), Trampolino elastico e Assenza di gravità.
I problemi dp invece sono quelli secondo me i più difficili la maggior parte delle volte:
il problema dp per eccellenza credo sia Entscheidungsproblem (se hai mai sentito parlare di “stati” dovresti capire il perché), poi c’è anche Somme di sequenze che non è male (quanti stati ci sono e in quanto vengono computati?) e qualche altro problemino come Poldo, Sommelier, Torri e Permutazione genetica (potresti trovarlo “bizzarro come problema”) giusto per fare un po’ di pratica.
Non ti preoccupare se non riesci a farli né tutti né subito, l’importante è fare pratica e avrai tempo fino a aprile per farla.
Per i problemi sui grafi tanti auguri , per me sono stati i più difficili quantomeno all’inizio, dai un’occhiata a questi per imparare qualche algoritmo:
dijkstra (algoritmo di Dijkstra o equivalente), Sentieri bollenti (territoriali 2016), Depurazione dell’acqua (forse l’hai visto nella guida di Bugatti, è originale), barbablù (io l’ho risolto con un algoritmo chiamato Floyd Warshall e un po’ di magia ), Minimum spanning tree (MST), Slalom tra le telecamere (tosto), Ponti e isole (BFS o DFS), Mappa antica (BFS su matrice) e Rete idrica (DFS su albero).
DFS: depth-first search/ricerca in profondità (ricorsiva per eccellenza).
BFS: ricerca in ampiezza/breadth-first search (iterativa per eccellenza).
Vi ringrazio tutti per le risposte, mi metterò a lavoro quanto prima! Alcuni dei problemi che mi avete consigliato effettivamente li ho già risolti, tipo easy1, 2 e 3, barbablu, vortex, studio amico, rispetta i versi, trampolino elastico e somme di sequenza. Nei prossimi giorni proverò a risolvere gli altri che mi avete consigliato e poi ovviamente me ne cercherò di nuovi . @Tredici hai ragione, anche i miei libri (scolastici) di informatica ci starebbero meglio come carbonella… Fortunatamente ho iniziato già 3 anni fa ad imparare il C/C++ equalcosa di C#, quindi non credo di avere problemi sotto questo punto di vista, anzi. Anche la OOP la conosco abbastanza bene, ciò che sto studiando in questo periodo sono i container della STL e la libreria “algorithm” che ho visto essere molto utili per risolvere molti problemi (ad esempio la priority_queue che hai già nominato mi ha permesso di raggiungere 100/100 in somme costose, mentre con un comune array non ci riuscivo, oppure le funzioni di sorting e ricerca permettono di risparmiare moltissimo tempo nella stesura del codice). @bortoz si ho visto che spesso gli algoritmi ricorsivi hanno anche un costo esponenziale, ma da quel che ho capito applicando anche la memoizzazione è possibile ridurre drasticamente il costo (ad esempio nel calcolo dei numeri di fibonacci)!
Concordo ma finora non ho visto nessuno calcolarsi fibonacci in modo ricorsivo. Generalmente si tende a preferire l’approccio bottom-up rispetto a quello top-down anche se citando Bugatti: “scegliere l’uno o l’altro può dipendere dal problema in sé, che a volte sembra suggerire un modo piuttosto che l’altro, e anche, ma è una mia opinione, dal modo con cui il cervello del risolutore funziona, nel senso se trova più naturale usare un approccio piuttosto che l’altro”
P.S. solo a me non funziona l’anteprima?
Anche io infatti sono solito calcolare fibonacci con approccio bottom-up, l’ho preso come esempio per dire che applicando la memoizzazione la complessità si riduce da esponenziale a lineare!
Comunque anche a me l’anteprima non funziona…
Per l’anteprima dovete abilitare l’esecuzione degli script del forum sul vostro browser, se avete Chrome dovreste vedere una sorta di scudo con una crocetta rossa nella barra di ricerca sulla quale clickare, altrimenti dovrete fugare tra le impostazioni.
). Non mi è servito molto tempo per rendermi conto che per potersi classificare bene sia alla fase territoriale che a quella nazionale, non sono sufficienti le conoscenze derivanti dallo studio a scuola, per cui mi sono subito cimentato nella risoluzione di alcuni problemi partendo da quelli che mi sembravano abbastanza “semplici”. Nel frattempo, ho letto la guida del prof. Alessandro Bugatti, che mi è stata di aiuto per risolvere problemi leggermente più articolati, e sto anche seguendo dei video su youtube che ho trovato navigando su questo forum. Tuttavia, penso di non avere ancora molta praticità con i problemi che richiedono un approccio ricorsivo, o di programmazione dinamica, per cui vorrei chiedervi quali sono i problemi di queste 2 categorie dai quali mi conviene iniziare per migliorare. Grazie in ogni caso a chiunque potrà rispondermi!
, per me sono stati i più difficili quantomeno all’inizio, dai un’occhiata a questi per imparare qualche algoritmo:
), Minimum spanning tree (MST), Slalom tra le telecamere (tosto), Ponti e isole (BFS o DFS), Mappa antica (BFS su matrice) e Rete idrica (DFS su albero).
