Allenamento Nazionale

Salve, ho superato la fase territoriale della Basilicata e mi vorrei preparare al meglio per le nazionali. Potreste consigliarmi qualcosa da studiare per migliorare le mie tecniche anche perché a scuola non insegnano niente di tutto ció. Ho dovuto studiare tutto da solo per le territoriali e mi ha aiutato molto la guida del Prof A. Bugatti.

Prima di tutto devi avere bene in mente i concetti di base come:

  • Ricorsione
  • Grafi e loro rappresentazione tramite matrice/liste di adiacenze (soprattutto liste)
  • Visite classiche di un grafo (BFS,DFS)
  • Complessità asintotica (ti sarà di aiuto per prevedere i tempi che necessiterà il tuo algoritmo)

Poi devi avere bene in testa le tecniche principali per risolvere i problemi:

  • Programmazione Dinamica
  • Greedy
  • Divide & Conquer
  • Binary Search
  • Riduzione di un problema ad un grafo
  • Backtracking

Avendo queste basi non ti resta che studiare alcune strutture dati come:

  • Array (statico e dinamico)
  • Lista (single/double linked)
  • Coda/Pila
  • Coda di priorità
  • forse altre che non mi vengono in mente

Poi, se usi il C/C++, dovresti studiarti la STL per trovare implementazioni di algoritmi/strutture dati utili come:

  • Vector (array dinamico)
  • List (double linked list)
  • Queue/Stack (coda e pila)
  • Priority_queue (coda di priorità)
  • Sort (quick-sort)
  • Lower_bound/Upper_bound/Binary_search (ricerche binarie)
  • altro che ora non mi viene in mente

Poi dovresti dare un occhio agli algoritmi classici:

  • Algoritmo di Dijkstra per i cammini minimi (indispensabile)
  • Range minimum query (mooolto utile)
  • Lowest Common Ancestor (raro che ti serva ma è sempre bene conoscerne il concetto)
  • altri che ora ho il buio più totale hahaha

E anche algoritmi/tecniche/strutture dati utili per abbassare la complessità tipo:

  • Segment/Range/Interval tree (non ho mai capito la differenza hahaha)
  • Fenwick tree (lo trovi anche sotto il nome di Binary Indexed Tree)
  • altri…

Infine la cosa più importante forse: fai tanti problemi, fai tanta pratica:

  • Allenati a scrivere velocemente che è il tempo è una risorsa importante
  • “Allenati” a leggere bene i testi dei problemi che spesso ci sono dei casi particolari rognosi o, ancora peggio, i casi particolari te li inventi tu quando il testo ti conferma che non ci sono
  • Scrivi/disegna/schematizza su un foglio di carta per farti venire in mente qualcosa, spesso disegnare aiuta ad osservare qualcosa di non banale
  • Fai i problemi qui sul cms (soprattutto quelli delle OII degli anni scorsi) ma sfrutta anche SPOJ/Codeforces/COCI

Credo sia una bella lista, ma con un po’ di impegno si fa tutto.
Ovviamente facendo problemi le cose le impari un po’ alla volta!

Testi utili potrebbero essere Competitive Programming e Introduction to Algorithms.
Link utile: https://www.topcoder.com/community/data-science/data-science-tutorials/
Video che mi sono serviti: https://www.youtube.com/watch?v=OQ5jsbhAv_M (più parte 2/3/4) e in genere tutti i video di questo prof °L°

Buona fortuna!

10 Mi Piace

Grazie mille, cercheró di imparare tutto ció che hai detto. Comunque mi stavo già leggendo il libro Competive programmer. Ti ringrazio tantissimo.

1 Mi Piace