Preparazione Nazionali OII

Ci sono algoritmi must-to-know, se si, quali?
Mi potreste nel caso condividere qualche risorsa in merito?
Vorrei prepararmi alle nazionali al meglio ma non saprei da dove iniziare.

Di algoritmi da conoscere c’è ne sono pochi e probabilmente già lì conoscerai (dijkstra, knapsack, …).
Qui c’è un elenco con le strutture dati da conoscere.

Grazie mille,
piu’ che altro per esempio non ho minimamente idea di come risolvere certi problemi degli anni scorsi.

Non è un grosso problema, due anni fa sono arrivato secondo senza fare neanche un problema a 100. Ricordati che l’obiettivo non è risolvere tutti i problemi, ma fare il maggior numero possibile di punti.

1 Mi Piace

questo lo so ma per esempio non minimamente idea di come risolvere pangramma (credo che tu possa anche darmi qualche aiuto a comprendere meglio il problema)

Per pangrammi serve un po’ di matematica brutta. Comunque questo problema non è stato risolto da nessuno in gara (io compreso :cry:).

non mi serve risolverlo, ma almeno capire come potrei avere un buon punteggio escludendo soluzioni che saprei che non funzionerebbero ahahha

e avevo sentito che servisse sapere degli inversi modulari, ma alla fine come ci si potrebbe avvicinare ad una soluzione?

I primi 8 subtask si possono fare senza nessuna conoscenza particolare analizzando un po’ i casi. I subtask 9 e 10 si possono risolvere con un segment tree, mentre per gli ultimi due servono gli inversi modulari.

ah oke perche` stavo appena studiando i segment tree, imparo prima ad applicarli a probelmi piu’ semplici e poi provero’ a fare pangramma

per gli inversi modulari avevo visto un video e diceva che se il modulo era primo potevi fare
base*pow( esp, mod-2)%mod

source: https://www.youtube.com/watch?v=-OPohCQqi_E

In genere non ti servono tanti algoritmi/strutture dati per risolvere problemi, ad esempio si poteva prendere oro alle ultime oii usando come unica struttura dati il segment tree.
Pero’ sapere molti algoritmi serve perche’ spesso i problemi hanno soluzioni con un approccio simile a certi algoritmi e quindi ti viene piu facilmente un idea per risolverli.
Di roba “must know”, direi che ci sono cose basi, tipo dp in generale, kruskal, bfs, dfs, dijkstra, binsearch, …

perché stavo imparando i segment tree e ho capito come funziona ma ho difficoltà nella implementazione

dp, dfs, bfs, dijkstra, binsearch li so usare
kruskal dovrei rivederlo (usato solo una volta)

In ogni caso piu che saperli usare cosi come sono, e’ utile capire come funzionano e saperli modificare quando opportuno.
Ad esempio sentieri bollenti che si risolve con una 0-1 bfs, che anche se non hai mai visto puoi derivarla da una bfs normale.
O incendi che si risolve con prim modificato per andare in O(n^2) nei grafi completi (e prim a sua volta lo puoi vedere come dijkstra modificato).
Per allenarti sui segtree, sul cms ci sono tre problemi praticamente fatti apposta.
Comunque dopo che hai provato a implmentarli da solo dalla teoria, ti conviene guardare implementazioni di altri per vedere come implementarli un po piu clean (da risorse decenti tipo il cp3, non roba tipo geeksforgeeks).

1 Mi Piace

infatti geekforgeeks non lo uso mai se non per la teoria (non ha per niente del codice pulito)
se vuoi ti mando la mia implementazione attuale per i segment tree

sto cercando di risolvere rangetree1 e rangetree2 ma a quanto pare serve una lazy propagation, cosa che non so conosco

sto cercando di “risolvere” pangramma con i segment tree, ma non trovo un modo efficiente per combinare i rami e dunque risolvere il problema. Perche’ teoricamente dovrei tenermi per ogni intervallo, la risposta attuale, la grandezza minima del pangramma completo fin’ora trovato e un set con i relativi pangrammi della minima grandezza trovati fino a quel momento. Ma non riesco a trovare un modo efficiente per trovare i pangrammi in una sequenza (cio’ infatti si lega anche al fatto di come costruire il segment tree)

Nota che in genere quando usi un segtree, e’ solo parte di una soluzione, e spesso viene fatto su array costruiti da te. Tu stai cercando di usare forzatamente un segment tree perche’ sai gia che pangramma si puo fare con esso, ma in genere quando risolvi un problema, pensi a una soluzione e magari una certa parte della soluzione che hai pensato capita che si puo fare con un segtree.
Per pangramma puoi ragionare nel seguente modo: come fai a contare il numero di pangrammi che riesci a fare per un determinato range sapendo il numero di volte che compare ogni numero in quel range?

2 Mi Piace

se compare ogni numero in quel determinato range significa che ho trovato un pangramma
piu piccolo e’ il range e piu’ piccolo sara’ il pangramma dunque piu’ vicino ad un pangramma minimo