Algobadge

Usa un vettore di vettori.

Vogliamo tenerci per ogni id il numero di libri con quell'id.

Usa una map.

Vogliamo tenerci valori diversi tra loro e ci interessa vedere l'elemento più vicino ad un certo valore. Se solo ci fosse una struttura dati con una funzione simile....

Usa un set con lower_bound (attento a come usare lower_bound).

Intuitivamente come mettiamo i modellini sugli scaffali? Spoiler: in ordine crescente di C[i] (o decrescente).

Se non ci fossero scaffali D sarebbe la somma delle differenze tra elementi consecutivi (se sono sortati).

Aggiungendo uno scaffale come diminuisce la somma dei D[j]?

Sorta le differenze tra elementi consecutivi.

Il criterio greedy dovrebbe essere chiaro, semplicemente sorto V.

Se la complessità non torna, evita ad esempio di ricalcolare la somma o risortare ogni volta.

Calcolare B direttamente non è così facile. Però il fatto che ci chieda il B massimale e il fatto che i B che funzionano sono distribuiti in un modo ben preciso potrebbe darci un'idea.

Binary search su B

Come facciamo a controllare che un certo B funzioni? Spoiler: sliding window

Le lunghezze delle stringhe sono tutte molto piccole, e abbiamo tanto tempo perché è un problema terry quindi possiamo sostanzialmente fare qualsiasi cosa.

Potrebbe essere utile usare sapere che esiste stringa.substr(inizio, lunghezza) che ritorna una sottostringa e stringa.find(sottostringa) che trova l'indice in cui si trova una sottostringa all'interno di una stringa (se non c'è ritorna -1).

Prova a fare casi piccoli e trovare una formula.

https://en.wikipedia.org/wiki/Josephus_problem

N è molto piccolo.

Posso semplicemente controllare tutti i numeri dell cabala e trovare quello con il massimo resto modulo M.

Per farlo usiamo il backtracking tenendoci il numero che abbiamo fino ad adesso e procedere per ricorsione aggiungendo 3, 6 o 9 controllando che sia diversa dalla scorsa cifra.

La risposta è semplicemente l'mcm dei V[i].

Si può calcolare l'mcm sapendo che mcm(a, b)*mcd(a, b) = a*b. Per calcolare l'mcd si può scrivere l'algoritmo di euclide o usare gcd(a, b).

Il problema chiede sostanzialmente di calcolare velocemente delle potenze, e questo si può fare con fastexp

Fai conti o fai casi piccoli e viene una formula chiusa. Se non sai come leggi i prossimi hint.

Se ci sono $k$ scrigni tra cui scegliere qual'è la probabilità di beccare subito quello giusto?

In media quante scosse prendo per indovinare il prossimo scrigno se ne ho già indovinati $n-k$?

Se non sei riuscito a fare il calcolo dell'hint prima, prova a sommare per ogni $0\le i\le k-1$ la probabilità di ricevere $i$ scosse per $i$.

Dovrebbe venire qualcosa del genere: $\frac{1}{k}\cdot 0+\frac{k-1}{k}\frac{1}{k-1}\cdot 1+\frac{k-1}{k}\frac{k-2}{k-1}\frac{1}{k-2}\cdot 2\cdots =\frac{0}{k}+\frac{1}{k}+\frac{2}{k}\dots$

Adesso se chiamiamo $f_k$ il numero medio di scosse avendo indovinato $n-k$ scrigni la risposta al problema sarà: $f_n+f_{n-1}+\cdots +f_1$

Se non ti è chiaro come trasformare tutto questo in un'unica formula chiusa ricordati che la somma dei numeri da 1 a $n$ è $\frac{n(n+1)}{2}$.

Per riuscire a spegnere tutte le lampadine è necessario arrivare a un interruttore di tipo 1, quindi...

...quindi vogliamo trovare il nodo che massimizza il minimo delle distanze da un interruttore di tipo 1.

Visto che il grafo non è pesato basta fare una BFS a più sorgenti partendo dalle lampadine spente dagli interruttori di tipo 1 e vedere la lampadina con distanza maggiore. (per fare una bfs a più sorgenti basta aggiungere alla queue tutti i nodi da cui vogliamo partire e eseguire il classico algoritmo)

Implementa una dsu

Implementa dijkstra

Posso provare tutti i possibili campi da calcio.

ISe solo potessi generalizzare la prefix sum a più dimensioni...

Usa una prefix sum 2d.

Implementa un segment tree.

Come faccio a controllare se posso sortare una data lista?

Forse la parità degli indici si comporta in modo interessante...

Come faccio a contare il numero di passaggi richiesti?

Il problema si riconduce a contare il numero di inversioni in un array. Posso farlo con un segment tree?