Ciao.
Il problema è https://cms.di.unipi.it/#/task/combinazione/statement
Durante la risoluzione del problema ho trovato una soluzione semplice, min(m(i+1) - m(i))+1
Ritengo che questa soluzione sia valida ma si verifica solo in pochi casi (alcuni timeout)
Dato che la media di due numeri è m(i) = s(i)+s(i+1)/2 sono arrivato alla conclusione che s(i) e s(i-1) sono specchiati intorno a m(i), cioè che s(i+1)-m(i) == m(i)-s(i)
Quindi sono arrivato alla conclusione che il risultato sia il minimo dei delta tra le medie perché se il risultato non fosse cosi da qualche parte c’è qualche superamento di s(i) > m(i) e quindi il risultato è il minimo perché è il massimo numero di soluzioni valide (si varia s(0) = m(0)…m(0)-r)
Ho fatto un ragionamento del tipo se le medie sono {2, 5, 9} i risultati sono {2-1, 2+1, 5-(2+1)+5, 9+9-(5-(2+1)+5) } che sono infatti {1, 3, 7, 11}, stesso ragionamento con {0, 4, 6, 12} e {−1, 5, 5, 13}
Sono arrivato a questo ragionamento osservando che escluso s(0) che è “libero” nel sue range (m(0)-r…m(0)), gli altri sono s(i) = m(i-1) + m(i-1)-s(i-1) (seguendo la regola dello specchio.
Quindi perchè questa soluzione funziona solo con pochissimi input?