mínima de suma de valores absolutos

Question

declaración

Problema:

Hay 3 matrices A, B, C todos llenos con números enteros positivos, y todos los tres arrays son del mismo tamaño.

Encuentra min (| ab | + | bc | + | ca |) donde a es en A, b está en B, c se encuentra en C.

---

trabajé en el problema todo el fin de semana . Un amigo me dijo que se puede hacer en tiempo lineal. No veo cómo eso podría ser posible.

¿Cómo lo harías?

Answer 1

Bueno, creo que puedo hacerlo en O (n log n). Solo puedo hacer O (n) si las matrices están inicialmente ordenadas.

En primer lugar, tenga en cuenta que puede permutar a, b, c como quiera sin cambiar el valor de la expresión. Entonces, deje que x sea el más pequeño de a, b, c; deje que y sea el medio de los tres; y deje que z sea el máximo. Luego tenga en cuenta que la expresión simplemente equivale a 2*(z-x). (Edit: Esto es fácil de ver ... Una vez que tenga los tres números en orden, x < y < z, la suma es sólo (y-x) + (z-y) + (z-x) lo que equivale a 2*(z-x))

Por lo tanto, todo lo que realmente estamos tratando de hacer es encontrar tres números tales que los dos exteriores están lo más cerca posible, con el otro número "intercalado" entre ellos.

Comience ordenando las tres matrices en O (n log n). Mantener un índice en cada matriz; llame a estos i, j y k. Inicializa los tres a cero. Cualquiera que sea el índice que apunte al valor más pequeño, incremente ese índice. Es decir, si A[i] es menor que B[j] y C[k], incremente i; si B[j] es el más pequeño, incremente j; si C[k] es el más pequeño, incremente k. Repita, haciendo un seguimiento de |A[i]-B[j]| + |B[j]-C[k]| + |C[k]-A[i]| todo el tiempo. El menor valor que observas durante esta marcha es tu respuesta. (Cuando el más pequeño de los tres está al final de su matriz, deténgalo porque ya lo ha hecho).

En cada paso, agrega uno a exactamente un índice; pero solo puede hacer esto n veces para cada conjunto antes de llegar al final. Así que esto es como máximo 3*n pasos, que es O (n), que es menor que O (n log n), lo que significa que el tiempo total es O (n log n). (. O simplemente O (n) si se puede asumir las matrices están ordenados)

Bosquejo de una prueba de que esto funciona: Supongamos A[I], B[J], C[K] son el a, b, c que forman la respuesta real; es decir, tienen el mínimo |a-b|+|b-c|+|c-a|.Supongamos además que a>b>c; la prueba para los otros casos es simétrica.

Lemma: Durante nuestra marcha, no incrementamos j pasado J hasta después de que incrementamos k pasado K. Prueba: siempre incrementamos el índice del elemento más pequeño, y cuando k <= K, B[J] > C[k]. Entonces cuando j=J y k <= K, B[j] no es el elemento más pequeño, entonces no incrementamos j.

Ahora supongamos que incrementamos k pasado K antes de i llega a I. ¿Qué aspecto tienen las cosas antes de realizar ese incremento? Bueno, C[k] es el más pequeño de los tres en ese momento, porque estamos a punto de aumentar k. A[i] es menor que o igual a A[I], porque i < I y A están ordenados. Finalmente, j <= J porque k <= K (según nuestro Lema), entonces B[j] también es menor que A[I]. Tomados en conjunto, esto significa que nuestra suma de abs-diff en este momento es menos que 2*(c-a), lo cual es una contradicción.

Por lo tanto, no incrementamos k pasado K hasta i llega a I. Por lo tanto, en algún momento durante nuestra marcha i=I y k=K. Según nuestro lema, en este punto j es menor o igual que J. Entonces, en este punto, B[j] es menor que los otros dos y j se incrementará; o B[j] está entre los otros dos y nuestra suma es solo 2*(A[i]-C[k]), que es la respuesta correcta.

Esta prueba es descuidada; en particular, no da cuenta explícitamente del caso en que uno o más de a, b, c son iguales. Pero creo que ese detalle puede resolverse con bastante facilidad.

Answer 2

que iba a escribir un programa muy simple como esto:

#!/usr/bin/python 
import sys, os, random 
A = random.sample(range(100), 10) 
B = random.sample(range(100), 10) 
C = random.sample(range(100), 10) 
minsum = sys.maxint 
for a in A: 
for b in B: 
    for c in C: 
    print 'checking with a=%d b=%d c=%d' % (a, b, c) 
    abcsum = abs(a - b) + abs(b - c) + abs(c - a) 
    if abcsum < minsum: 
    print 'found new low sum %d with a=%d b=%d c=%d' % (abcsum, a, b, c) 
    minsum = abcsum 

Y probar una y otra vez hasta que vi un patrón emerge. El patrón que encontré aquí es lo que se esperaría: los números que están más cerca juntos en cada conjunto, independientemente de si los números son "altos" o "bajos", son los que producen la suma mínima más pequeña. Entonces se convierte en un problema de número más cercano. Por lo que sea que valga, probablemente no mucho.