Número de conjuntos múltiples de modo que cada número de 1 a se pueda expresar de forma única como una suma de algunos de los elementos del conjunto múltiple

11

Mi problema. Dado , quiero contar el número de conjuntos múltiples válida . Un multiset es válido sinSS

  • La suma de los elementos de es , ySn
  • Cada número de a se puede expresar de forma única como una suma de algunos de los elementos de .1nS

Ejemplo. Por ejemplo, si entonces son válidos.n=5{1,1,1,1,1},{1,2,2},{1,1,3}

Sin embargo, no es válido porque 2 puede estar formado por ambos y (es decir, 2 puede expresarse como y ), por lo que la segunda condición no se cumple. Del mismo modo, 3 pueden estar formados por y .S={1,1,1,2}{1,1}{2}2=1+12=2{2,1}{1,1,1}

S={1,2,4 } también es inválido porque todos los números del al pueden hacer de manera única, pero la suma de los elementos de no es .15S5


He intentado encontrar un buen algoritmo para este problema durante bastante tiempo, pero no puedo resolverlo. Es de codechef . He visto algunas de las soluciones enviadas, pero todavía no pude obtener la lógica para resolver el problema. NOTA: El límite de tiempo para la pregunta es de 10 segundosn<109

Para un conjunto la notación si , lo que significa que ocurre veces en el conjunto múltiple S.a i < a j i < j a i c iS={(a1,c1),(a2,c2)...} ai<aji<jaici

Hasta ahora he sacado algunas conclusiones

  • El primer elemento del conjunto múltiple ordenado requerido debe ser1
  • Deje sea ​​un conjunto que siga las dos propiedades y luegor < k a r + 1 = a r  o  ( r i = 0 a i ) + 1S={1,a2ak}|a1a2akr<k  ar+1=ar or (i=0rai)+1
  • Deje , donde ocurre veces, sigue las propiedades requeridas y luego de la conclusión anterior podemos decir que y si . Prueba:a i c ii a i | n + 1 a i | a j j > i a i + 1 =S={(1,c1),(a2,c2)(ak,ck)}|a1a2akaicii ai|n+1ai|ajj>i
    ai+1=(aici+ai1)+1ai|ai+1
  • Ahora considere es decir, todos los números posteriores después de 1 serán un múltiplo de . Deje que sea ​​el recuento de tal multiset posible, entonces donde estoy sumando todos los posibles números de ( ). En otros términosd f ( n ) f ( n ) = d | n + 1S={1,11d1,d,dd,dm1,dm1dm1,dm2,dm2dm2,}df(n)1s=d-1f(n-1)=g(n)=d| n,dng(d)f(n)=d|n+1,d1f(n(d1)d)1s=d1f(n1)=g(n)=d|n,dng(d)

Finalmente, mi problema se reduce a esto: encuentre de manera eficiente para que no exceda el límite de tiempo.g(n)

Liga de la Justicia
fuente
2
¿Ha verificado si es apropiado pedirle a otras personas que publiquen públicamente soluciones y algoritmos para problemas de práctica? Las preguntas frecuentes de Codechef parecen esperar que las soluciones no se publiquen públicamente (excepto por algunos problemas muy básicos). ¿Publicar una solución aquí estaría "estropeando" los problemas de práctica para otros, o se considera eso correcto? No estoy familiarizado con las normas y la etiqueta de la comunidad Codechef.
DW
No encontré nada relacionado con no publicar preguntas en el dominio público en las preguntas frecuentes y esta restricción está en los problemas del concurso en curso, no en el problema de la práctica.
liga de la justicia
1
@DW No creo que les importe si hablamos de problemas que no son de concursos en curso.
Ravi Upadhyay
1
Está buscando el número de particiones del número de entrada. Le sugiero que investigue un poco con esta palabra de moda.
Raphael
2
@Raphael, estoy de acuerdo, el póster debería leer sobre esas técnicas. No es exactamente el mismo problema: la primera condición del afiche requiere que sea una partición, pero la segunda condición impone restricciones adicionales (para realizar cambios únicos ), pero podría ser posible aplicar las mismas técnicas utilizadas para contar el número de particiones, con algunas modificaciones para hacer frente al requisito adicional.
DW

Respuestas:

2

Esto es lo que está haciendo la solución más rápida . De hecho, está calculando su función Dado , lo factorizamos (ver a continuación) y luego calcule todos los factores (ver a continuación) en algún orden tal que implique (propiedad P). Ahora calculamos acuerdo con la fórmula al repasar los factores en el orden dado. La propiedad P asegura que cuando calculamos , ya hemos calculado para todos los factores no triviales de . También hay una optimización (ver más abajo).n f 1 , , f m f i | f j i j g g ( d ) g ( e ) e d

g(n)=dnd<ng(d),g(1)=1.
nf1,,fmfi|fjijgg(d)g(e)ed

En más detalle, revisamos los factores en orden, y para cada factor , encontramos todos sus factores no triviales al verificar cuál de divide .f 1 , , f i - 1 f ifif1,,fi1fi

Factoring: preprocesamiento: hacemos una lista de todos los primos por debajo de utilizando el tamiz de Eratóstenes. Dado , simplemente usamos la división de prueba. n109n

Generando todos los factores: esto se hace de forma recursiva. Supongamos que . Corremos anidada bucles , y la salida . Puede probar la propiedad P por inducción. t l 1{ 0 , ... , k 1 } , ... , l t{ 0 , ... , k t } p l 1 1p l t tn=p1k1ptkttl1{0,,k1},,lt{0,,kt}p1l1ptlt

Optimización: dado que el programa se ejecuta en varias entradas, podemos usar la memorización para ahorrar tiempo en diferentes entradas. Solo memorizamos valores pequeños (hasta ), y esto nos permite almacenar todos los valores memorizados en una matriz. La matriz se inicializa con ceros, por lo que podemos saber qué valores ya se conocen (ya que todos los valores calculados son positivos).105


Si la factorización prima de es , entonces depende solo de , y de hecho solo de la versión ordenada de este vector Cada número por debajo de tiene como máximo factores primos (con repetición), y dado que , parece factible calcular (o más bien ) para todos ellos, de forma recursiva. Esta solución podría ser más rápida si hubiera muchas entradas diferentes; tal como están las cosas, hay como máximo .p k 1 1 , , p k t t f ( n ) ( k 1 , , k t ) 10 9 29 p ( 29 ) = 4565 f g 10n+1p1k1,,ptktf(n)(k1,,kt)10929p(29)=4565fg10

También es posible que esta función, que asigna particiones a la correspondiente , tenga una forma analítica explícita. Por ejemplo, , viene dada por A000670 , y está dada por A005649 o A172109 .g ( p k ) = 2 k - 1 g ( p 1p t ) g ( p 2 1 p 2p t )gg(pk)=2k1g(p1pt)g(p12p2pt)

Yuval Filmus
fuente
1

OK, entonces tiene una relación de recurrencia para (vea el final de su pregunta).g()

En este punto, parece que un enfoque natural sería escribir el algoritmo recursivo para calcular y aplicar la memorización para no calcular más de una vez. En otras palabras, cuando calcula , la almacena en una tabla hash que asigna ; Si necesita conocer nuevamente en el futuro, puede buscarlo en la tabla hash.g ( i ) g ( i ) i g ( i ) g ( i )g(n)g(i)g(i)ig(i)g(i)

Esto requiere factorizar , pero existen algoritmos eficientes para factorizar cuando .n n 10 9nnn109

También puede buscar la secuencia en la Enciclopedia en línea de secuencias enteras . Si encuentra la secuencia en su enciclopedia, a veces le proporcionarán información útil adicional (por ejemplo, algoritmos eficientes para calcular la secuencia). Sin embargo, eso ciertamente podría quitarle la diversión a las cosas.g(1),g(2),g(3),g(4),g(5),

DW
fuente
0

Aquí hay una pista para comenzar. Aplique algoritmos de programación dinámica estándar para enumerar el conjunto de particiones de un número entero y agregue algo de lógica para verificar cuál de ellos permite la realización de cambios únicos al verificar de forma iterativa todas las sumas, realizar cambios y verificar la unicidad.

En un poco más de detalle: supongamos que tiene un varios conjuntos . Dado un número con , ¿cómo podría identificar un subconjunto de que sume a ? ¿Cómo podría verificar si ese submultiset es único? Intente adaptar las técnicas de programación dinámica estándar para realizar cambios . (Ver también esta pregunta ).i 1 i n S iSi1inSi

Dado un varios conjuntos , ¿cómo podría verificar si cumple con la segunda condición, es decir, si cada número del 1 al puede expresarse de manera única como la suma de un submultiset de (la condición única de hacer cambios)? Esto debería ser bastante fácil, si resolvió el anterior.n SSnS

deje que denote la lista de multisets que satisfacen ambas condiciones. Si supieras , ¿cómo podrías usar esa información para construir ? Aquí es posible que desee adaptar las técnicas de programación dinámica estándar para enumerar las particiones de un número entero.P(n)P(1),P(2),,P(n)P(n+1)


Aquí hay un enfoque que probablemente será mejor.

Supongamos que es un conjunto múltiple que satisface ambas condiciones (para ). ¿Cómo podemos extenderlo para obtener una multiset que tiene un elemento más? En otras palabras, ¿cómo podemos identificar todas las formas de agregar un elemento más a , para obtener una nueva multiset que satisfaga ambas condiciones (para algunos )?SnTSTn

Respuesta: si puede expresarse como una suma de algunos de los elementos de , entonces no tiene sentido agregarlo a : eso causaría que viole la condición de unicidad. Entonces, podemos enumerar todos los enteros que no se pueden expresar como una suma de algunos de los elementos de ; cada uno es algo que podría agregarse potencialmente a para obtener un nuevo multiset que satisfaga ambas condiciones (para algún otro ).xSSTxSSTn

Además, es posible enumerar qué números enteros se pueden expresar como una suma de algunos de los elementos de , y cuáles no, utilizando la programación dinámica. Construye una matriz bidimensional de booleanos, donde es verdadero si hay una manera de expresar el entero como una suma de algunos de los primeros elementos de (solo los primeros elementos de son elegibles para ser utilizados; donde ha sido ordenado, entonces y ). Tenga en cuenta queSA[1|S|,1n]A[i,j]jiSiSSS={s1,s2,,sk}s1s2skA[i,j]se puede calcular utilizando los valores de : en particular, si , o contrario. Esto nos permite identificar todos los números que son candidatos para ser añadido a .A[1i1,1j1]A[i,j]=A[i1,j]A[i1,jsi]j>siA[i,j]=A[i1,j]S

A continuación, para cada extensión candidata de (obtenida al agregar un elemento a ), queremos verificar si cumple ambas condiciones. Deje denotar la suma de los elementos de , y la suma de los elementos de . Tenemos que comprobar si cada número entero en el rango pueden expresarse como una suma de algunos de los elementos de . Esto también se puede resolver mediante programación dinámica, utilizando algoritmos estándar para la realización de cambios. (De hecho, si todavía tiene la matrizTSSTnSnTn+1,n+2,,nTAmencionado anteriormente, puede extenderlo un poco fácilmente para resolver este problema: lo convertimos en una matriz , continuamos completando todas las entradas adicionales y nos aseguramos de que son todos verdaderos.) Entonces, ahora podemos enumerar todos los multisets que se extienden por un solo elemento y que satisfacen ambas condiciones.A[1|T|,1n]T SA[|T|,n+1],A[|T|,n+2],,A[|T|,n]TS

Esto sugiere inmediatamente un algoritmo para enumerar todos los conjuntos múltiples que satisfacen su condición, para todos hasta cierto límite, digamos . Tendremos una matriz , donde almacena todos los multisets que suman 5 y, en general, almacena el conjunto de todos los multisets que suman .n n 20 P [ 1 20 ] P [ 5 ] S P [ n ] S nSnn20P[120]P[5]SP[n]Sn

A continuación, podemos completar iterativa. Comience configurando para que contenga solo un conjunto múltiple . A continuación, para cada (contando de 1 a 20), para cada , enumere todas las posibles extensiones de (usando las técnicas anteriores), denote la suma de los elementos de , e inserte en si aún no está presente y si .P [ 1 ] { 1 } n S P [ n ] T S n T T P [ n ] n 20P[n]P[1]{1}nSP[n]TSnTTP[n]n20

Esto debería ser bastante factible. ¡Buena suerte! ¡Que te diviertas! Trabajar en los detalles será un buen ejercicio de aprendizaje en programación dinámica.

DW
fuente
No puedo enumerar todas las particiones enteras porque será exponencial. He editado la pregunta e incluí el rango de algunos de mis pensamientos, pero aún así estoy atascado. Puede ser que puedas ayudar. n
liga de la justicia