Contando el número de sumas de subconjuntos contiguos de una matriz

12

Se nos da una matriz con todo a [ i ] > 0 .a[1n]a[i]>0

Ahora necesitamos encontrar cuántas sumas distintas se pueden formar a partir de sus submatrices (donde una submatriz es un rango contiguo de la matriz, es decir, para alguna j , k , la suma es la suma de todas las elementos de la submatriz). Por ejemplo, si a = [ 1 , 2 , 1 ] , entonces la respuesta es 4: podemos formar 1 , 2 , 3 , 4 .a[jk]j,ka=[1,2,1]1,2,3,4

Sé cómo contar el número de sumas distintas en el tiempo .O(n2)

Además, me he dado cuenta de que esto es similar al problema clásico en el que necesitamos encontrar el número de subcadenas distintas de una cadena. Estaba pensando en la posibilidad de construir una matriz de sufijos y resolverla de manera similar (en tiempo ). Pero no he podido averiguar cómo modificar eso para que funcione aquí. Por ejemplo, si usamos una matriz de sufijos para a = [ 1 , 2 , 1 ] obtendremos 5 casos en lugar de los cuatro aceptables. ¿Es posible hacer esto usando matrices de sufijos o estoy pensando en la dirección incorrecta?O(n)a=[1,2,1]

También hay una dirección más en la que he estado pensando. Divide y vencerás. Como si dividiera la matriz en dos partes cada vez hasta que se reduzca a un solo elemento. Un solo elemento puede tener una suma. Ahora, si combinamos dos elementos individuales, se puede hacer de dos maneras: si ambos rangos individuales tienen el mismo elemento, obtenemos 2 sumas diferentes, o si ambos tienen elementos diferentes, obtenemos 3 sumas diferentes. Pero no puedo generalizar esto para fusionar matrices de longitud mayor que 1. ¿Es posible fusionar matrices de dos m de tamaño y obtener la respuesta en ?O(m)

Salena
fuente
O(n lg n)
Sugeriría comenzar con el siguiente problema: ¿qué tan difícil es decidir si hay dos intervalos con la misma suma? Es tentador probar la dureza 3SUM de este problema, pero hasta ahora no he podido.
Yuval Filmus

Respuestas:

2

O(n2)Θ(n2)

[1,2,4,8,,2n]n(n+1)2


El "casi seguro" se debe al hecho de que el problema no requiere los valores de las sumas como salida. Sin embargo, no creo que se puedan evitar los duplicados sin determinar al menos la mayoría de los valores.

FrankW
fuente
No veo ninguna razón particular por la que no debería haber una manera de evitar de alguna manera pasar por alto todas las posibilidades sin dejar de encontrar la respuesta correcta. Los algoritmos de programación dinámica lo hacen de manera rutinaria.
Yuval Filmus