MS1908's blog

By MS1908, history, 6 months ago, In English,

So I'm having the following problem, which appeared in my university programming contest.

Problem: Given positive integers $$$M$$$ and $$$N$$$ $$$(1\le M\le 500,\,1\le N\le 100)$$$ and a $$$N$$$-tuple of positive integers $$$(a_1,a_2,...,a_N)$$$ $$$(1\le a_i\le 10,\, 1\le i\le N)$$$. Find the number of positive integers $$$N$$$-tuple $$$(k_1,k_2,...,k_N)$$$ such that $$$a_1k_1+a_2k_2+\cdots+a_Nk_N=M$$$.

Input: First line will be $$$N$$$ and $$$M$$$ $$$(1\le M\le 500,\,1\le N\le 100)$$$. Second line will be the tuple $$$(a_1,a_2,...,a_N)$$$ $$$(1\le a_i\le 10,\, 1\le i\le N)$$$.

Output: The number of solutions of the equation.

 
 
 
 
  • Vote: I like it
  • +13
  • Vote: I do not like it

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

At the very first step just subtract the sum of all the coefficients from M, since this will allow us to use zeroes in the tuple, which is very helpful.

First precompute number of ways to sum up to a given value after using a certain number of numbers (dp[sum][count_numbers_used]). Should be M^3. Include zeroes. This is also helpful because it takes order into account already.

Group the coefficients into bins of 10, since each coefficient is from 1 to 10. Then do a dp with [current_coefficient][sum]. At each step of the current_coefficient find number of ways to get every value from 0 to 500 using only numbers with that certain coefficient. This is obtainable from the precomputation in constant time (just divide the target sum you're adding by the coefficient). The end result will just be dp[N][M]. This step will take NM^2.

Total complexity is M^3.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Just a small question: 500^3 seems to be greater than 10^9. Is it possible that the run time exceeds one second?

    • »
      »
      »
      6 weeks ago, # ^ |
        Vote: I like it +8 Vote: I do not like it

      500^3 = 1.25e8

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

        I think there exists an $$$O(M*N)$$$ solution that uses the same technique for unbounded knapsack.
        Let's $$$M' = M - \sum_{i} a_i$$$
        And $$$S(i, j)$$$ be the number of tuples $$$(k_1, ..., k_i)$$$ that $$$\sum_{t=1}^{i} a_t * k_t = j$$$
        We have:

        $$$ S(i, j) = S(i - 1, j) + S(i - 1, j - w_i) $$$

        The answer is $$$S(N, M')$$$.
        Reference: An FPTAS for #Knapsack and Related Counting Problems

      • »
        »
        »
        »
        6 weeks ago, # ^ |
          Vote: I like it 0 Vote: I do not like it

        Oops that is a silly mistake.

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

Edit: I am talking about finding number of non-negative tuples. A little modification of the above problem.
A long time ago, I found an $$$O(S * n + S * logS * logM), S = \sum_{i} a_i$$$ solution for this problem.
The idea is to represent $$$f(x)$$$, the number of tuples when $$$M = x$$$, as a linear recursive sequence:

$$$ f(x) = \mathop{{\sum_{i} f(x - a[i])}} - \mathop{\sum_{i < j} f(x - a[i] - a[j])} + \mathop{\sum_{i < j < k} f(x - a[i] - a[j] - a[k])} - ... $$$

Then use companion matrix to calculate $$$M-th$$$ element fast.
P/S: If the terms companion matrix or Cayley Hamilton are strange to you. You should read an article in codechef here to understand how to do fast calculation for recursive sequence.

My implementation that works in $$$O(S * n + S^2 * logM)$$$: ideone
Use FFT instead of simple polynomial multiplication will make it $$$O(S * n + S * logS * logM)$$$

I don't recall much, but there's exist an algorithm that uses something like $$$dp[0..a_0 - 1][0..a_1 - 1]...[0..log10(M)]$$$ and works in about $$$O(log_{10}(M) * \mathop{{\prod_{i} a_i}})$$$.

These solution are pretty good but do not satisfy me. I try searching for an improvement but couldn't.
So I want to ask:
- Is there exist a better solution for $$$1 \leq S \leq 10^5$$$. Something like $$$O(S * n + S * logM)$$$?

»
5 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

I've added a harder version of this problem to SPOJ: COUNTDIO where $$$1 \leq M \leq 10^{18}$$$ and $$$1 \leq \sum_{i} a_i \leq 60 000$$$.
Enjoy solving.