MS1908's blog

By MS1908, history, 5 years 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

| Write comment?
»
5 years 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.

  • »
    »
    5 years 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?