Suponga que tiene una secuencia S de una longitud inferior a 40. Sea n = el número mínimo de elementos de S que tendría que cambiar para hacer de S una secuencia aritmética. ¿Cómo calcularías n?

Answer 1

Solo hazlo por la fuerza bruta.

Sea [math] s_i [/ ​​math] el elemento [math] i ^ {th} [/ math] de S. Para cada [math] i, j [/ math], hay una secuencia aritmética única [math] A_ {ij} [/ math] tal que el elemento [math] i ^ {th} [/ math] de [math] A_ {ij} [/ math] es [math] s_i [/ ​​math] y el [math] j ^ {th} [/ math] elemento de [math] A_ {ij} [/ math] es [math] s_j [/ math]. Deje que [math] x_ {ij} [/ math] sea igual a la cantidad de lugares donde S y [math] A_ {ij} [/ math] coinciden, y deje que [math] X [/ math] sea el máximo [math] x_ { ij} [/ math] para todos los pares [math] (i, j) [/ math]. La respuesta que desea es la longitud de S menos [matemáticas] X [/ matemáticas].

Dado que solo hay O (n ^ 2) pares, y solo se necesita tiempo lineal para calcular cada [matemática] x_ {ij} [/ matemática], la fuerza bruta como esta requiere O (n ^ 3) tiempo. Desde n <40, eso no es gran cosa