title: Dynamic Programming: Sum-of-products
body: <p>Let's say you have two lists, L1 and L2, of the same length, N.  We define prodSum as:</p>
  
  <pre><code>def prodSum(L1, L2) :
      ans = 0
      for elem1, elem2 in zip(L1, L2) :
          ans += elem1 * elem2
  
      return ans
  </code></pre>
  
  <p>Is there an efficient algorithm to find, assuming L1 is sorted, the number of permutations of L2 such that prodSum(L1, L2) &lt; some pre-specified value?</p>
  
  <p>If it would simplify the problem, you may assume that L1 and L2 are both lists of integers from [1, 2, ..., N].</p>
  
  <p>Edit:  Managu's answer has convinced me that this is impossible without assuming that L1 and L2 are lists of integers from [1, 2, ..., N].  I'd still be interested in solutions that assume this constraint.</p>