Nombre de multisets de sorte que chaque nombre de 1 à

11

Mon problème. Compte tenu de , je veux compter le nombre de multijeux valide S . Un multiset S est valide sinSS

  • La somme des éléments de est n , etSn
  • Chaque numéro de à n peut être exprimée de manière unique comme une somme de quelques - uns des éléments de S .1nS

Exemple. Par exemple , si alors { 1 , 1 , 1 , 1 , 1 } , { 1 , 2 , 2 } , { 1 , 1 , 3 } sont valides.n=5{1,1,1,1,1},{1,2,2},{1,1,3}

Cependant, n'est pas valide car 2 peut être formé à la fois par { 1 , 1 } et { 2 } (c'est-à-dire que 2 peut être exprimé comme 2 = 1 + 1 et 2 = 2 ) , donc la deuxième condition ne tient pas. De même 3 peut être formé par { 2 , 1 } et { 1 , 1 , 1 } .S={1,1,1,2}{1,1}{2}2=1+12=2{2,1}{1,1,1}

} est également invalide car tous les nombres de 1 à 5 peuvent être créés de manière unique, mais la somme des éléments de S n'est pas 5 .S={1,2,415S5


J'ai essayé de trouver un bon algorithme pour ce problème depuis un certain temps, mais je ne peux pas le résoudre. C'est du codechef . J'ai vu certaines des solutions soumises, mais je n'ai toujours pas pu obtenir la logique pour résoudre le problème. REMARQUE: la limite de temps pour la question est de 10 secondes et n<109

Pour un multiset j'utiliserai la notation a i <S={(a1,c1),(a2,c2)...} si i < j , ce qui signifie qu'un i se produit c i fois en multiset S.ai<aji<jaici

Jusqu'à présent, j'ai tiré quelques conclusions

  • Le premier élément du multiset trié requis doit être 1
  • Soit soit un ensemble suivant les deux propriétés alors r < k a r + 1 = a r  ou  (S={1,a2ak}|a1a2akr<k  ar+1=ar or (i=0rai)+1
  • Soit , où a iS={(1,c1),(a2,c2)(ak,ck)}|a1a2akai se produit fois, suit les propriétés requises, puis de la conclusion ci-dessus nous pouvons dire que i a i | n + 1 etcii ai|n+1 si j > i . Preuve: a i + 1 = ( a i c i + a i - 1 ) + 1 a i | a i + 1ai|ajj>i
    ai+1=(aici+ai1)+1ai|ai+1
  • Considérons maintenant c'est-à-dire tous les les nombres suivants après 1 seront un multiple de d . Soit donc f ( n )S={1,11d1,d,dd,dm1,dm1dm1,dm2,dm2dm2,}df(n)être le compte d'un tel multiset possible alors où je suis sommant sur tout nombre possible de1's(=d-1). En d'autres termes,f(n-1)=g(n)=f(n)=d|n+1,d1f(n(d1)d)1s=d1f(n1)=g(n)=d|n,dng(d)

Enfin mon problème est réduit à ceci - trouver d'une manière efficace afin qu'il ne dépasse pas la limite de temps.g(n)

ligue de justice
la source
2
Avez-vous vérifié s'il est approprié de demander à d'autres personnes de publier publiquement des solutions et des algorithmes pour les problèmes de pratique? La FAQ Codechef semble s'attendre à ce que les solutions ne soient pas publiées publiquement (à l'exception de certains problèmes très basiques). Est-ce que publier une solution ici "gâcherait" les problèmes de pratique pour les autres, ou est-ce considéré comme OK? Je ne connais pas les normes et l'étiquette de la communauté Codechef.
DW
Je n'ai rien trouvé concernant le fait de ne pas publier de question sur le domaine public dans la FAQ et cette restriction concerne les problèmes de concours en cours et non les problèmes de pratique.
justice league
1
@DW Je ne pense pas que cela les dérangerait si nous discutons de problèmes qui ne proviennent pas de concours en cours.
Ravi Upadhyay
1
Vous recherchez le nombre de partitions du numéro d'entrée. Je vous suggère de faire des recherches en utilisant ce mot à la mode.
Raphael
2
@Raphael, je suis d'accord, l'affiche devrait lire sur ces techniques. Ce n'est pas exactement le même problème - la première condition de l'affiche nécessite que ce soit une partition, mais la deuxième condition impose des restrictions supplémentaires (pour une modification unique ) - mais il pourrait être possible d'appliquer les mêmes techniques utilisées pour compter le nombre de partitions, avec quelques modifications pour faire face à l'exigence supplémentaire.
DW

Réponses:

2

Voici ce que fait la solution la plus rapide . C'est en effet calculer votre fonction Étant donné n , nous le factorisons (voir ci-dessous), puis calculons tous les facteurs (voir ci-dessous) f 1 , , f m dans un ordre tel que f i | f j implique i j (propriété P). Nous calculons maintenant g selon la formule en passant en revue les facteurs dans l'ordre donné. La propriété P garantit que lorsque nous calculons g ( d ) , nous avons déjà calculé g ( e ) pour tous les facteurs non triviaux e

g(n)=dnd<ng(d),g(1)=1.
nf1,,fmfi|fjijgg(d)g(e)ede . Il existe également une optimisation (voir ci-dessous).d

Plus en détail, nous passons en revue les facteurs dans l'ordre, et pour chaque facteur , nous trouvons tous ses facteurs non triviaux en vérifiant lequel de f 1 , , f i - 1 divise f i .fif1,,fi1fi

Affacturage: prétraitement: nous faisons une liste de tous les nombres premiers inférieurs à utilisant le tamis Eratosthène. Étant donné n , nous utilisons simplement la division d'essai.109n

Générer tous les facteurs: cela se fait de manière récursive. Supposons que . Nous exécutons t boucles imbriquées l 1{ 0 , , k 1 } , , l t{ 0 , , k t } , et sortons p l 1 1p l tn=p1k1ptkttl1{0,,k1},,lt{0,,kt} . Vous pouvez prouver la propriété P par induction.p1l1ptlt

Optimisation: le programme étant exécuté sur plusieurs entrées, nous pouvons utiliser la mémorisation pour gagner du temps sur différentes entrées. Nous ne mémorisons que de petites valeurs (jusqu'à ), ce qui nous permet de stocker toutes les valeurs mémorisées dans un tableau. Le tableau est initialisé avec des zéros, et ainsi nous pouvons dire quelles valeurs sont déjà connues (puisque toutes les valeurs calculées sont positives).105


Si la factorisation première de est p k 1 1 , , p k t t , alors f ( n ) ne dépend que de ( k 1 , , k t ) , et en fait uniquement de la version triée de ce vecteur . Chaque nombre inférieur à 10 9 a au plus 29 facteurs premiers (avec répétition), et puisque p ( 29 ) = 4565 , il semble possible de calculer fn+1p1k1,,ptktf(n)(k1,,kt)10929p(29)=4565f(ou plutôt ) pour tous, récursivement. Cette solution pourrait être plus rapide s'il y avait de nombreuses entrées différentes; en l'état, il y en a au maximum 10 .g10

Il est également possible que cette fonction, mappant les partitions au correspondant , ait une forme analytique explicite. Par exemple, g ( p k ) = 2 k - 1 , g ( p 1p t ) est donné par A000670 , et g ( p 2 1 p 2p t ) est donné par A005649 ougg(pk)=2k1g(p1pt)g(p12p2pt) A172109 .

Yuval Filmus
la source
1

OK, vous avez donc une relation de récurrence pour (voir la fin de votre question).g()

À ce stade, il semble qu'une approche naturelle serait d'écrire l'algorithme récursif pour calculer et d'appliquer la mémorisation afin de ne pas calculer g ( i ) plus d'une fois. En d'autres termes, lorsque vous calculez g ( i ) , vous le stockez dans une table de hachage qui mappe i g ( i ) ; si vous avez besoin de connaître g ( i )g(n)g(i)g(i)ig(i)g(i) à l'avenir, vous pouvez le rechercher dans la table de hachage.

nnn109 .

g(1),g(2),g(3),g(4),g(5),

DW
la source
0

Voici un indice pour vous aider à démarrer. Appliquer des algorithmes de programmation dynamique standard pour énumérer l'ensemble des partitions d'un entier et ajouter une logique pour vérifier laquelle permet une modification unique en vérifiant de manière itérative toutes les sommes, en effectuant des modifications et en vérifiant l'unicité.

Si1inSi

SnS (la condition unique de changement)? Cela devrait être assez facile, si vous avez résolu le précédent.

P(n)P(1),P(2),,P(n)P(n+1)


Voici une approche qui sera probablement meilleure.

SnTSTn

xSSTxSSTn

SA[1|S|,1n]A[i,j]jiSiSSS={s1,s2,,sk}s1s2skA[i,j]A[1i1,1j1]A[i,j]=A[i1,j]A[i1,jsi]j>siA[i,j]=A[i1,j]S

TSSTnSnTn+1,n+2,,nTAA[1|T|,1n]A[|T|,n+1],A[|T|,n+2],,A[|T|,n]TS

Snn20P[120]P[5]SP[n]Sn

P[n]P[1]{1}nSP[n]TSnTTP[n]n20

Cela devrait être assez faisable. Bonne chance! S'amuser! Travailler à travers les détails sera un bon exercice d'apprentissage en programmation dynamique.

DW
la source
n