Qualcuno ha risolto wheel? Avevo pensato di usare una coda statica circolare, ma avrei molta difficoltà nell’implentarla, quindi ero in cerca di una soluzione più semplice
Io conosco due soluzioni: una con range minimum query, l’altra precalcola i massimi e minimi facendo scorrere l’intervallo un elemento alla volta. Però entrambe richiedono una struttura dati.
Entrambi sono fattibili. In particolare, nella seconda bisogna fare pruning della ricerca quando l’elemento shiftato non è un massimo né un minimo, e l’elemento nuovo a sinistra non è un candidato. In tal caso si può accelerare la ricerca.
L’RMQ è fattibile nel caso si implementi un vettore di 3N-1 elementi, per gestire tutte le rotazioni
Dai un’occhiata ai Segment Tree 
EDIT: O alle min-queue/max-queue, così @davideraga2 è contento xD
Si può risolvere in modo elegante usando le strutture deque e multiset assieme
1 Mi Piace
C’è una soluzione che non usa strutture dati, se dividi a metà l’array e consideri il minimo/massimo dalle estremità e dal centro
1 Mi Piace
Si, non hai torto! Ma andrebbe fuori tempo per gli ultimi 4 tasks secondo me
Non penso, non l’ho provata ma dovrebbe essere O(N + Q)
Ciao, io sono riuscito a risolverlo però è andato fuori tempo con gli ultimi 2 subtask (quello che ha impiegato di più era attorno a 0.8 s). Essendo C++ più simile all’arabo che ad un linguaggio di programmazione per me, ho semplicemente diviso e confrontato il minimo/massimo (non ricordo benissmo, se vuoi lunedì recupero la soluzione.