Cellar_Door's blog

By Cellar_Door, 6 years ago, In English,

Can any one explain me the solution of the following problem->

Sam visits the most famous sweet shop in his city. The shop has an assortment of sweets of different variety. It contains a1 sweets of 1st kind, a2 sweets of 2nd kind, and so on, upto N.

Now Sam has been restricted by his mother, to select exactly S number of sweets from the shop to eat. You have to help him find out the number of ways in which he can select S sweets. Sam may have multiple queries for you and you are expected to answer them all. Input Format

First line contains integer N, such that there are N different kinds of sweets.

The following N lines represent the amount of sweets of each kind, i.e., the integer on i-th line represents the number of sweets of i-th kind.

Next line contains an integer Q, the number of queries to follow.

The following Q lines contain an integer S each, such that you have to report the number of ways in which S sweets can be selected modulo (10^9 + 7).

Output Format

The output consists of Q lines, such that each line consists of the output of the corresponding query, i.e., the number of ways in which S sweets can be selected.

Constraints

N ≤ 10^6 1 ≤ Amount of sweets of each kind ≤ 10^3 1 ≤ Q ≤ 10^4 1 ≤ S ≤ 2000

Sample Input

2

2

3

6

1

2

3

4

5

6

Sample Output

2

3

3

2

1

0

SOURCE-

http://www.codechef.com/IOPC2014/problems/IOPC14L

 
 
 
 
  • Vote: I like it
  • -3
  • Vote: I do not like it

»
6 years ago, # |
  Vote: I like it 0 Vote: I do not like it

an idea. N is up to 10^6, but it can be reduced to 10^3. for (i = 0; i < n; ++i) ++cnt[a[i]];.

  • »
    »
    6 years ago, # ^ |
    Rev. 2   Vote: I like it 0 Vote: I do not like it

    Yes, but if you want to do naive DP on each type, you need O(S2) time per type, yielding an algorithm with complexity O(S3) instead of O(NS). Not much win.

    • »
      »
      »
      6 years ago, # ^ |
      Rev. 9   Vote: I like it +16 Vote: I do not like it

      You have to find coefficients of xs in (1 + x + x2 + ... + xa1) * (1 + x + x2 + ... + xa2) * ...(1 + x + x2 + ... + xan).

      We know n is very large, (1 ≤ n ≤ 106), but ai is not very large (0 ≤ qi ≤ 103). We need to somehow make use of the small constraints of ai. We will have many of the terms in (1 + x + x2 + ... + xa1) * (1 + x + x2 + ... + xa2) * ...(1 + x + x2 + ... + xan) being same and mulitplied many times, So clubing the same together and rearraning the expression, we get (1 + x)c1 * (1 + x + x2)c2 * ...(1 + x + x2 + ... + xa1000)c1000.

      Now using the geometic progression sum, we can re-write the expression as (x2 - 1)c1 * (x3 - 1)c2 * .. * (x1001 - 1)c1000 * (x - 1) - n

      Now we need to find out coefficient of xk (0 ≤ k ≤ 2000). Let us split the expression into two parts. First part being (x2 - 1)c1 * (x3 - 1)c2 * .. * (x1001 - 1)c1000 and second part being (x - 1) - n.

      We need to find coefficient of xk (0 ≤ k ≤ 2000) in the both the expression and later we can just muliply both the parts directly to get actual coefficients required in .

      Now let us focus on finding coefficients of xk in the first part only. We can do this in time using dp. Note that we can find coefficient of xk in (xi - 1)ci easily. All the coefficients in (xi - 1)ci will be of only of powers of xi, coefficients of all other powers of x will be zero.

      Now we can do a dp for the above purpose. Let dp[i][s] denotes coefficient of s in first i terms of the given expression (x2 - 1)c1 * (x3 - 1)c2 * .. * (x1001 - 1)c1000.

      Now let us say we are currently at ith position in the expression (ie at (xi - 1)ci), we will try all multiplies of i + 1 as possible powers of x and will do a transition to the previous state in the dp. See the exact code for details about the transition function.

      Note that we are making transition per step due to which our complexity will be like where H is haromic function. As Hn is bounded by logn. We can say overall complexity is .

      Now let us focus to second part of the expression. How to find coefficient of xk in (x - 1) - n ?. Please follow the following link for entire explanation negative exponent in binomial theorem

      Please see the commented code for full understanding of the dp states.
      authors solution
      testers solution
      [user:tourist] solution
      Complexity of the entire solution is which will easily pass within the time.

      P.S. If something is unclear, please point out that, I would be glad to help that out. Thank you all!!

»
6 years ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

Incorrect solution in the previous edit