Ho provato a fare il problema “multiples of 3” con risultato un 40/100. non avendo idea di come renderlo più efficiente sono venuto a cercare nel forum topic sul problema e quelli che ho trovato parlano di argomenti (che sono, mi sembra di aver capito, indispensabili da sapere per fare questo e altri problemi) quali segment tree e la square root decomposition ecc La domanda è dove posso trovare il materiale per studiarli?
In questo topic se ne è parlato un po’:
(sì, assumiamo che range tree e segment tree siano la stessa cosa )
Nel topic sopra trovi anche la sqrt decomposition, che è diciamo uno “step” arrivare alla soluzione logaritmica…
In che senso “nel topic sopra”? e la sqrt decomposition sarebbe lo step successivo del segment tree o precedente?
Nel topic “Range trees”, linkato nel mio messaggio.
Precedente (anche se in realtà a essere pignoli la sqrt decomposition è un’idea più generale e si può usare in più situazioni diverse dove il segment tree non sarebbe utilizzabile)
Un libro in cui reperire la maggior parte degli algoritmi / strutture dati utili nelle gare è il Competitive Programming 3, che puoi scaricare in pdf comprare tranquillamente online
Altrimenti, puoi utilizzare alcuni dei numerosi tutorial online
Segment Tree
- Video-tutorial del magico Tushar (hello friends)
- Una “guida” su GeeksForGeeks
- “Blog post” su codeforces
Sqrt Decomposition
- Video-tutorial su youtube