Anzahl der Multisets, so dass jede Zahl von 1 bis

11

Mein Problem. Mit nn möchte ich die Anzahl der gültigen Multisets S zählenS . Ein Multiset S.S ist gültig, wenn

  • Die Summe der Elemente von SS ist nn und
  • Jede Zahl von 11 bis nn kann eindeutig als Summe einiger Elemente von S ausgedrückt werden S.

Beispiel. Wenn beispielsweise n = 5n=5 ist, sind { 1 , 1 , 1 , 1 , 1 } , { 1 , 2 , 2 } , { 1 , 1 , 3 }{1,1,1,1,1},{1,2,2},{1,1,3} gültig.

Jedoch S = { 1 , 1 , 1 , 2 } ist ungültig , weil 2 kann durch beide gebildet werden { 1 , 1 } und { 2 } (dh 2 kann als beide ausgedrückt werden 2 = 1 + 1 und 2 = 2 ) , so dass die zweite Bedingung nicht gilt. In ähnlicher Weise kann 3 durch { 2 , 1 } und { 1 , 1 , 1 } gebildet werden .S={1,1,1,2}{1,1}{2}2=1+12=2{2,1}{1,1,1}

S={1,2,4S={1,2,4} is also invalid because all numbers from 11 to 55 can be uniquely made, but the sum of the elements of SS is not 55.


I've tried to find a good algorithm for this problem for quite some time but cannot solve it. It is from codechef. I've seen some of the submitted solutions but I still couldn't get the logic for solving the problem. NOTE: The time limit for the question is 10 seconds and n<109n<109

Für ein Multiset verwende ich die Notation S = { ( a 1 , c 1 ) , ( a 2 , c 2 ) . . . } A i < a j , wenn i < j , was bedeutet , a i auftritt c i mal in multiset S.S={(a1,c1),(a2,c2)...} ai<aji<jaici

Bis jetzt habe ich einige Schlussfolgerungen gezogen

  • Das erste Element des erforderlichen sortierten Multisets sollte 1 sein1
  • Sei S = { 1 , a 2a k } | a 1a 2a k ist eine Menge, die den beiden Eigenschaften folgt, dann ist r < k a r + 1 = a r  oder  ( r i = 0 a i ) + 1S={1,a2ak}|a1a2ak  r<k  ar+1=ar or (ri=0ai)+1
  • Let S={(1,c1),(a2,c2)(ak,ck)}|a1a2akS={(1,c1),(a2,c2)(ak,ck)}|a1a2ak, where aiai is occurring cici times, follows the required properties then from the above conclusion we can say that i ai|n+1i ai|n+1 and ai|ajai|aj if j>ij>i .
    Proof: ai+1=(aici+ai1)+1ai|ai+1ai+1=(aici+ai1)+1ai|ai+1
  • Now consider S={1,11d1,d,dd,dm1,dm1dm1,dm2,dm2dm2,}S={1,11d1,d,dd,dm1,dm1dm1,dm2,dm2dm2,} i.e. all the subsequent numbers after 1 will be a multiple of dd. So let f(n)f(n) be the count of such multiset possible then f(n)=d|n+1,d1f(n(d1)d)f(n)=d|n+1,d1f(n(d1)d) where I am summing over all possible number of 1s1s(=d1=d1). In other terms f(n1)=g(n)=d|n,dng(d)f(n1)=g(n)=d|n,dng(d)

Finally my problem is reduced to this - find g(n)g(n) in an efficient way so that it doesnt exceed the time limit.

justice league
quelle
2
Have you checked whether it is appropriate to ask for other people to publicly post solutions and algorithms for practice problems? The Codechef FAQ seems to expect that solutions will not be posted publicly (except for some very basic problems). Would posting a solution here be "spoiling" the practice problems for others, or is that considered OK? I'm not familiar with the Codechef community's norms and etiquette.
D.W.
I didn't find anything related to not posting question on public domain in faq and this restriction is on ongoing contest problems not on practice problem.
justice league
1
@D.W. I don't think they would mind if we discuss prblems which are not from ongoing contests.
Ravi Upadhyay
1
You are looking for the number of partitions of the input number. I suggest you do some research using this buzzword.
Raphael
2
@Raphael, I agree, the poster should read up on those techniques. It's not exactly the same problem -- the poster's first condition requires that this be a partition, but the second condition imposes additional restrictions (for unique change-making) -- but it might be possible to apply the same techniques used to count the number of partitions, with some modifications to deal with the additional requirement.
D.W.

Antworten:

2

Here is what the fastest solution is doing. It is indeed computing your function g(n)=dnd<ng(d),g(1)=1.

g(n)=dnd<ng(d),g(1)=1.
Given nn, we factor it (see below) and then compute all factors (see below) f1,,fmf1,,fm in some order such that fi|fjfi|fj implies ijij (property P). We now compute gg according to the formula by going over the factors in the given order. Property P ensures that when we compute g(d)g(d), we have already computed g(e)g(e) for all non-trivial factors ee of dd. There is also an optimization (see below).

In more detail, we go over the factors in order, and for each factor fifi, we find all of its non-trivial factors by checking which of f1,,fi1f1,,fi1 divides fifi.

Factoring: Preprocessing: we make a list of all primes below 109109 using the Eratosthenes sieve. Given nn, we simply use trial division.

Generating all factors: This is done recursively. Suppose n=pk11pkttn=pk11pktt. We run tt nested loops l1{0,,k1},,lt{0,,kt}l1{0,,k1},,lt{0,,kt}, and output pl11plttpl11pltt. You can prove property P by induction.

Optimization: Since the program is run on several inputs, we can use memoization to save time across different inputs. We only memoize small values (up to 105105), and this allows us to store all memoized values in an array. The array is initialized with zeroes, and so we can tell which values are already known (since all computed values are positive).


If the prime factorization of n+1n+1 is pk11,,pkttpk11,,pktt, then f(n)f(n) depends only on (k1,,kt)(k1,,kt), and in fact only on the sorted version of this vector. Every number below 109109 has at most 2929 prime factors (with repetition), and since p(29)=4565p(29)=4565, it seems feasible to compute ff (or rather gg) for all of them, recursively. This solution could be faster if there were many different inputs; as it is, there are at most 1010.

It is also possible that this function, mapping partitions to the corresponding gg, has an explicit analytic form. For example, g(pk)=2k1g(pk)=2k1, g(p1pt)g(p1pt) is given by A000670, and g(p21p2pt)g(p21p2pt) is given by A005649 or A172109.

Yuval Filmus
quelle
1

OK, so you have a recurrence relation for g()g() (see the end of your question).

At this point it seems like a natural approach would be to write down the recursive algorithm to compute g(n)g(n), and apply memoization so you don't compute g(i)g(i) more than once. In other words, when you compute g(i)g(i), you store it in a hash table that maps ig(i)ig(i); if you need to know g(i)g(i) again in the future, you can look it up in the hash table.

This does require factoring nn, but there are efficient algorithms for factoring nn when n109n109.

You might also look up the sequence g(1),g(2),g(3),g(4),g(5),g(1),g(2),g(3),g(4),g(5), in the On-Line Encyclopedia of Integer Sequences. If you find the sequence in their encyclopedia, sometimes they will provide additional helpful information (e.g., efficient algorithms for computing the sequence). That admittedly might take the fun out of things, though.

D.W.
quelle
0

Here's a hint to get you started. Apply standard dynamic programming algorithms for enumerating the set of partitions of an integer, and add some logic to check which of those allows for unique change-making by iteratively checking all sums, making change, and verifying uniqueness.

In a bit more detail: Suppose you have a multiset SS. Given a number ii with 1in1in, how could you identify a submultiset of SS that sums to ii? How could you check whether that submultiset is unique? Try to adapt standard dynamic programming techniques for making change. (See also this question.)

Given a multiset SS, how could you check whether it satisfies the second condition, i.e., whether every number from 1 to nn can be uniquely expressed as a sum of a submultiset of SS (the unique change-making condition)? This should be pretty easy, if you solved the previous one.

let P(n)P(n) denote the list of multisets that satisfy both of your conditions. If you knew P(1),P(2),,P(n)P(1),P(2),,P(n), how could you use that information to construct P(n+1)P(n+1)? Here you might want to adapt standard dynamic programming techniques for enumerating the partitions of an integer.


Here's an approach that will probably be better.

Suppose SS is a multiset that satisfies both of your conditions (for nn). How can we extend it to get a multiset TT that has one element more? In other words, how can we identify all the ways to add one more element to SS, to get a new multiset TT that satisfies both of your conditions (for some nn)?

Answer: if xx can be expressed as a sum of some of the elements of SS, then there's no point in adding it to SS: that would cause TT to violate the uniqueness condition. So, we can enumerate all integers xx that cannot be expressed as a sum of some of the elements of SS; each one is something that could potentially be added to SS to get a new multiset TT that will satisfy both conditions (for some other nn).

Moreover, it is possible to enumerate which integers can be expressed as a sum of some of the elements of SS, and which cannot, using dynamic programming. You build a two-dimensional array A[1|S|,1n]A[1|S|,1n] of booleans, where A[i,j]A[i,j] is true if there is a way to express the integer jj as a sum of some of the first i elements of S (only the first i elements of S are eligible to be used; where S has been sorted, so S={s1,s2,,sk} and s1s2sk). Note that A[i,j] can be computing using the values of A[1i1,1j1]: in particular, A[i,j]=A[i1,j]A[i1,jsi] if j>si, or A[i,j]=A[i1,j] otherwise. This enables us to identify all numbers that are candidates to be added to S.

Next, for each candidate extension T of S (obtained by adding one element to S), we want to check whether T satisfies both conditions. Let n denote the sum of elements of S, and n the sum of elements of T. We need to check whether every integer in the range n+1,n+2,,n can be expressed as a sum of some of the elements of T. This too can be solved using dynamic programming, using standard algorithms for change-making. (In fact, if you still have the array A mentioned above you can easily extend it a little bit to solve this problem: we make it an array A[1|T|,1n], continue to fill in all of the additional entries, and make sure that A[|T|,n+1],A[|T|,n+2],,A[|T|,n] are all true.) So, now we can enumerate all multisets T that extend S by a single element and that satisfy both conditions.

This immediately suggests an algorithm to enumerate all multisets S that satisfy your condition, for all n up to some bound, say n20. We'll have an array P[120], where P[5] stores all multisets S that sum to 5, and generally, P[n] stores the set of all multisets S that sum to n.

Next, we can fill in P[n] iteratively. Start by setting P[1] to contain just the one multiset {1}. Next, for each n (counting up from 1 to 20), for each SP[n], enumerate all possible extensions T of S (using the techniques above), let n denote the sum of the elements of T, and insert T into P[n] if it isn't already present and if n20.

This should be pretty doable. Good luck! Have fun! Working through the details will be a good learning-exercise in dynamic programming.

D.W.
quelle
I cannot enumerate all the integer partitions because it will be exponential. I have edited the question and included the range of n and some of my thoughts but still I am stuck. May be you can help.
justice league