Aproximación de la secuencia creciente

Question

Se trata de una pregunta sobre los deberes con la que realmente estamos luchando:

Definiremos el distancia entre secuencias $(a_i)_{i=1}^n,(b_i)_{i=1}^n$ por: $$\text{dist}\left((a_i)_{i=1}^n,(b_i)_{i=1}^n\right)=\sum _{i=1}^n \left|a_i-b_i\right|$$

Dejemos que $(a_i)_{i=1}^n$ una secuencia de enteros positivos $a_i\in\{1,\dots,n^5\}$ . Tenemos que encontrar un estrictamente creciente secuencia de enteros $(b_i)_{i=1}^n$ tal que $\text{dist}\left((a_i)_{i=1}^n,(b_i)_{i=1}^n\right)$ es mínimo ( $b_i$ puede ser negativo).

Es decir, una secuencia aproximada para la secuencia $(8,2,4)$ es $(2,3,4)$ y la distancia es $7$ .

Pensamos en encontrar esta secuencia de forma iterativa: Primero, tomando la media $A$ (redondeado) y colocándolo en el centro de $ \ b_n$ y completarlo así: $$b_n=A-\left\lfloor\frac{n}{2}\right\rfloor,A-\left\lfloor\frac{n}{2}\right\rfloor+1,\dots,A-1,A,A+1\dots,A+\left\lfloor\frac{n}{2}\right\rfloor$$

A continuación, tratando de mejorar la aproximación de $ \ b_n$ manteniendo la propiedad de monotonicidad hasta llegar a nuestro destino. Necesitamos dar un algoritmo de tiempo polinómico, así que cualquier cosa que no sea exponencial está bien. Hay un $\mathcal{O}(n\lg n)$ algoritmo para este problema.

Sin embargo, nos pareció complicado frasear el paso iterativo de la mejora (¡y mucho menos computarlo!).

Además, dado que $(a_i)_{i=1}^n$ se aproxima, efectivamente, a $(b_i)_{i=1}^n$ No sé cómo demostrarlo formalmente (que no existe otra secuencia cuya distancia a $a_n$ es menor).

Creo que es una pregunta interesante (sin embargo, la encontramos desafiante) y agradeceré cualquier ayuda al respecto.

ADICIÓN: Después de pensar más en ello, no creo que haya necesidad de calcular la media porque a partir de, por ejemplo, esta secuencia: $$a_1, a_1+1, a_1+2, \dots, a_1+n-1$$ es esencialmente la misma, ya que la dirección que estoy tratando de pensar es iterar una y otra vez sobre el resultado.

Qué tal si empezamos con la subsecuencia creciente más larga, supongamos que encontramos dicha subsecuencia de longitud $k$ . Ahora tenemos que "cuidar" de $n-k$ agujeros. Puedo hacerlo con lápiz y papel utilizando una heurística intuitiva, pero no se me ocurre un algoritmo para hacerlo.

Answer 1

Los instructores nos presentaron el algoritmo (su propio trabajo BTW) así que pensé en dar aquí las ideas principales de la solución.

---

En primer lugar, existe una reducción de encontrar una secuencia estrictamente creciente a encontrar una secuencia no decreciente de la siguiente manera (anotaré una secuencia de longitud $n$ como una matriz de $n$ números, es decir $X[1,\dots,n]$ ):

1. $X[1,\dots,n]$ se da.
2. Computar $X'[i]=X[i]-i$ .
3. Encontrar una secuencia aproximada no decreciente de $X'[1,\dots,n]$ Llámalo $Y[1,\dots,n]$ .
4. Definir $Y'[i]=Y[i]+i$ .
5. Volver $Y'[1,\dots,n]$ ( $Y$ es claramente creciente).

Así que basta con resolver el caso no decreciente.

---

Toda secuencia no decreciente puede dividirse en bloques constantes máximos, es decir $(3,5,5,7,7,7,7,8,8,9)$ se compone de los bloques $3\big|5\big|7\big|8\big|9$ . Diremos que un número $C$ se aproxima a una secuencia $X[1,\dots,n]$ si la secuencia constante $\left( C,\dots,C \right)$ se aproxima a $X[1,\dots,n]$ .

La idea principal de la prueba será entonces - mostrar que cada bloque puede ser aproximado por una constante, y esta constante es un elemento de $X[1,\dots,n]$ .

Lema:

Dejemos que $C \in \mathbb{Z}$ . 

1. Si $C$ se aproxima a $Y[1,\dots,m]$ tan bueno como $C-1$ entonces $Y[1,\dots,m]\geqslant C$ al menos la mitad de las plazas.

2. Si $C$ se aproxima a $Y[1,\dots,m]$ tan bueno como $C+1$ entonces $Y[1,\dots,m]\leqslant C$ al menos la mitad de las plazas.

3. si $C$ se aproxima a $Y[1,\dots,m]$ tan bueno como $C+1$ y $C-1$ entonces $C \in \text{median}\left(Y[1,\dots,n]\right)$

Además, cada bloque puede ser "empujado" hacia arriba o hacia abajo por $1$ y la secuencia seguirá siendo no decreciente. Por lo tanto, si $Y[1,\dots,n]$ se aproxima a $X[1,\dots,n]$ la calidad de la aproximación no cambia si para cada intervalo constante máximo en $A[1,\dots,n]$ sumamos o restamos $1$ .

Queremos aproximar $X[1,\dots,n]$ . Dejemos que $OPT \in OPT(X[1,\dots,n])$ una solución óptima que consiste en un número mínimo de intervalos constantes máximos. Obsérvese que el intervalo mediano de cada bloque no es congruente (de lo contrario podríamos haber unificado los bloques aumentando el bloque de la izquierda y disminuyendo el de la derecha y la secuencia seguiría siendo aproximada y no decreciente, pero hemos elegido la secuencia con el mínimo número de bloques).

Así que podemos elegir $OPT$ ser todo lo anterior y que cada bloque es: $$OPT[i,\dots ,j]=\min \left\{\text{median}\left(X[i,\dots,j]\right)\right\}$$ $OPT$ es no decreciente, pero lo más importante es que cada elemento de $OPT$ es un elemento de $X[1,\dots,n]$ . Utilizaremos este hecho para nuestro algoritmo de tiempo polinómico -

---

Algoritmo:

Esta solución utiliza la técnica de programación dinámica.

En primer lugar, clasificamos $X[1,\dots,n]$ para conseguir $X'[1,\dots,n]$ tal que $X'[i]\geqslant X'[i-1]$ .

A continuación, definiremos $f:\{0,\dots,n\}^2 \to \mathbb{N}$ donde $f(i,j)$ devuelve el mejor valor de aproximación para la secuencia $X[1,\dots,i]$ tal que el último elemento de la secuencia de aproximación es $X'[j]$ . Construiremos una matriz bidimensional $n \times n$ y llenarlo siguiendo esta relación recursiva:

$$ f(i,j)=\begin{cases} \left|X[1]-X'[j]\right| & i=1\\ f(i-1,1)+ \left|X[i]-X'[1]\right| & j=1\\ \min_{k \leqslant j}\left\{ f(i-1,k) +\left|X[i]-X'[j]\right|\right\} & \text{otherwise} \end{cases} $$ El resultado será entonces el mínimo sobre todos los $j$ 's en el $i=n-1$ fila.

(Para llegar a obtener la propia secuencia aproximada mantendremos para cada paso un puntero a la celda que nos llevó al resultado óptimo hasta el momento. Esto es muy común en DP).

Tenga en cuenta que $f \in \mathcal{O} (n^3)$ . Se puede mejorar inmediatamente para $\mathcal{O} (n^2)$ refinando nuestra recursión a:

$$f(i,j)=\min\left\{f(i,j-1)-\left|X'[j-1]-X[i] \right|,f(i-1,j)\right\}+\left| X'[j]-X[i]\right|$$

(Si tengo algo más de tiempo subiré sus $\mathcal{O}(n\lg n)$ solución)