<p><strong>Theorem 1.</strong> <em>The problem has an <span class="math-container">$O(m\log m)$</span>-time algorithm, where <span class="math-container">$m=|M|$</span>.</em></p>
<p><em>Proof sketch.</em>
Fix an instance of the problem.
Assume without loss of generality that <span class="math-container">$M\subseteq (0, 1)$</span>.
(Otherwise an optimal solution <span class="math-container">$a_1,\ldots, a_n$</span> for <span class="math-container">$M$</span>
can be obtained by computing an optimal solution <span class="math-container">$a'_1, a'_2, \ldots, a'_{n'}$</span> for <span class="math-container">$M'=M\cap (0, 1)$</span>,
then prepending the elements in <span class="math-container">$M\cap [1, \infty)$</span> in decreasing order.)</p>
<p>By rewriting, the problem is equivalent to finding
<span class="math-container">$p=(p_1, p_2, \ldots, p_n) \subseteq M$</span> maximizing
<span class="math-container">$$\text{value}(p) = \sum_{i=1}^n \big(\textstyle\prod_{j=1}^{i-1} p_j\big)  (1-p_i) g(p_i),~~~~~~~~~(1)$$</span>
where <span class="math-container">$g(z) = f(z)z/(1-z)$</span>.</p>
<hr />
<p><em>Remark for intuition.</em> This interpretation is nice because then <span class="math-container">$\text{value}(p)$</span> is the expectation of the value returned by the following random process:</p>
<ol>
<li>for <span class="math-container">$i \gets 1, 2, \ldots, n$</span>:</li>
<li><span class="math-container">$~~~$</span> with probability <span class="math-container">$1-p_i$</span>, halt and return <span class="math-container">$g(p_i)$</span> (otherwise (with probability <span class="math-container">$p_i$</span>) continue)</li>
<li>return 0</li>
</ol>
<p>With this interpretation, it is not too hard to see that we should use <em>all</em> elements of <span class="math-container">$M$</span> (in some order), and further that we should use them greedily---in order of decreasing <span class="math-container">$g(p_i)$</span>.
The proof below gives the details.</p>
<hr />
<p>Here is the algorithm:</p>
<ol>
<li>let <span class="math-container">$q=(q_1, q_2, \ldots, g_m)$</span> be <span class="math-container">$M$</span> sorted by decreasing <span class="math-container">$g(q_i)$</span> (breaking ties arbitrarily).</li>
<li>return <span class="math-container">$q$</span></li>
</ol>
<p>Clearly this can be done in <span class="math-container">$O(m\log m)$</span> time.
To finish we show that <span class="math-container">$q$</span> is an optimal solution.</p>
<p>By inspection of (1), there is an optimal solution
that uses all elements of <span class="math-container">$M$</span> (as appending unused elements
to any solution cannot decrease the cost).
Let <span class="math-container">$p=(p_1, p_2, \ldots, p_m)$</span> be any such optimal solution.
Define an <em>inversion</em> in <span class="math-container">$p$</span> to be a pair <span class="math-container">$i, j\in [m]$</span>
such that <span class="math-container">$i &lt; j$</span> and <span class="math-container">$r(i) &gt; r(j)$</span>,
where <span class="math-container">$r(i)$</span> is the rank of <span class="math-container">$p_i$</span> in <span class="math-container">$q$</span>
(so <span class="math-container">$q_{r(i)} = p_i$</span>).
If there are no inversions, then <span class="math-container">$p=q$</span> so <span class="math-container">$q$</span> is optimal, and we are done.
Otherwise, there is an inversion <span class="math-container">$(i, i+1)$</span>.
Consider modifying <span class="math-container">$p$</span> by swapping <span class="math-container">$p_i$</span> with <span class="math-container">$p_{i+1}$</span>.
By calculation, this swap
increases the solution value by <span class="math-container">$\prod_{j=1}^{i-1} p_j$</span> times
<span class="math-container">$$
\begin{aligned}
   &amp;(1-p_{i+1}) g(p_{i+1})+ p_{i+1} (1-p_i) g(p_i) \\
 {}-{} &amp; p_i (1-p_{i+1}) g(p_{i+1}) - (1-p_i) g(p_i) \\
 {}={} &amp; [g(p_{i+1}) - g(p_i)] (1-p_i)(1-p_{i+1}) \\
 {}\ge{} &amp; 0 &amp; (\text{using } r(i) &gt; r(i+1), \text{ so } g(p_i) \le g(p_{i+1})).
\end{aligned}
$$</span>
So this swap reduces the number of inversions by one
and yields another optimal solution.
So repeatedly swapping yields an optimal solution <span class="math-container">$p$</span> with no inversions, i.e., with <span class="math-container">$p=q$</span>, so <span class="math-container">$q$</span> is optimal.<span class="math-container">$~~~~\Box$</span></p>

CC BY-SA 4.0
2022-03-22T21:01:59.000Z
Thank you so much for this thorough response! I wasn't sure if it was easy or hard at first glance.
Linda Cai
CC BY-SA 4.0
2022-03-22T21:10:06.040Z
Sure.  One thing: in general it improves posts to add some context about where the problem comes from, what you've tried, and so on.  See https://cstheory.stackexchange.com/help for more advice.
Neal Young
CC BY-SA 4.0
2022-03-22T23:33:43.383Z
Yeah this makes sense! I will give more context in the future. (The original problem I was considering was that there are a bunch of boxes, each one with probability $p_i$ has a prize of value $h_i$, and remaining probability with nothing. Our task is to order them in advance and then inspect them one by one, once we see a prize we have to take it and leave. When we can order them however we like it's clear we should inspect box in decreasing $h_i$, but what if some of the boxes have fixed position that we cannot change? The special case of 1-box fixed can be converted to my posted Q. )
Linda Cai
CC BY-SA 4.0
2022-03-22T23:34:09.920Z
(Our objective is to have the highest expected prize value.)
Linda Cai
CC BY-SA 4.0
2022-03-23T02:28:53.747Z
Interesting.  How can the case with one box fixed be reduced to your posted question?  If you'd like to ask about the more general question, I guess you can make another post.
Neal Young
CC BY-SA 4.0
2022-03-25T01:19:21.107Z
Sorry turns out I made a mistake in my calculation and the one box version is not exactly equivalent to what I described (f(1- p_i) sometimes depend on the position of the box and not just the value p_i). I posted my original problem in another post (posting the link here in case you are interested). https://cstheory.stackexchange.com/questions/51247/prize-box-ordering-problem-with-position-constraints-easy-or-hard
Linda Cai
CC BY-SA 4.0
2022-03-22T15:12:55.613Z
2022-03-23T12:17:26.013Z
2022-03-23T12:17:26.013Z
Neal Young
<p>I have this strange problem where we have a set of positive numbers <span class="math-container">$M$</span>, a fixed number <span class="math-container">$n$</span>, and a function <span class="math-container">$f: M \rightarrow R^+$</span> mapping each number in M to another positive number. We want to know if we can select non-repetitive numbers <span class="math-container">$a_1, \cdots, a_n \in M$</span>, such that the sum over weighted prefix product <span class="math-container">$\sum_{i=1}^n f(a_i) \cdot \prod_{j=1}^{i} a_j$</span> is maximized. Does anyone know if this is NP-hard?</p>
<p>Edit: What about for some fixed <span class="math-container">$m \in [n]$</span> and <span class="math-container">$p \in (0, 1)$</span>, maximizing <span class="math-container">$\sum_{i=1}^m f(a_i) \cdot \prod_{j=1}^{i} a_j + p \cdot \sum_{i=m+1}^n f(a_i) \cdot \prod_{j=1}^{i} a_j$</span>?</p>

<np-hardness><np-complete>
Is the weighted sum of subset prefix product problem NP-hard?
Linda Cai
# Is the weighted sum of subset prefix product problem NP-hard?

(Asked by: username_0 on 2022-03-22)

I have this strange problem where we have a set of positive numbers $M$, a fixed number $n$, and a function $f: M \rightarrow R^+$ mapping each number in M to another positive number. We want to know if we can select non-repetitive numbers $a\_1, \cdots, a\_n \in M$, such that the sum over weighted prefix product $\sum\_{i=1}^n f(a\_i) \cdot \prod\_{j=1}^{i} a\_j$ is maximized. Does anyone know if this is NP-hard?

Edit: What about for some fixed $m \in [n]$ and $p \in (0, 1)$, maximizing $\sum\_{i=1}^m f(a\_i) \cdot \prod\_{j=1}^{i} a\_j + p \cdot \sum\_{i=m+1}^n f(a\_i) \cdot \prod\_{j=1}^{i} a\_j$?

**Tags:** np-hardness, np-complete

---

## 1 answers

### Answer by username_1 on 2022-03-22. Score: 3 | Accepted answer

**Theorem 1.** *The problem has an $O(m\log m)$-time algorithm, where $m=|M|$.*

*Proof sketch.*
Fix an instance of the problem.
Assume without loss of generality that $M\subseteq (0, 1)$.
(Otherwise an optimal solution $a\_1,\ldots, a\_n$ for $M$
can be obtained by computing an optimal solution $a'\_1, a'\_2, \ldots, a'\_{n'}$ for $M'=M\cap (0, 1)$,
then prepending the elements in $M\cap [1, \infty)$ in decreasing order.)

By rewriting, the problem is equivalent to finding
$p=(p\_1, p\_2, \ldots, p\_n) \subseteq M$ maximizing
$$\text{value}(p) = \sum\_{i=1}^n \big(\textstyle\prod\_{j=1}^{i-1} p\_j\big) (1-p\_i) g(p\_i),~~~~~~~~~(1)$$
where $g(z) = f(z)z/(1-z)$.

---

*Remark for intuition.* This interpretation is nice because then $\text{value}(p)$ is the expectation of the value returned by the following random process:

1. for $i \gets 1, 2, \ldots, n$:
2. $~~~$ with probability $1-p\_i$, halt and return $g(p\_i)$ (otherwise (with probability $p\_i$) continue)
3. return 0

With this interpretation, it is not too hard to see that we should use *all* elements of $M$ (in some order), and further that we should use them greedily---in order of decreasing $g(p\_i)$.
The proof below gives the details.

---

Here is the algorithm:

1. let $q=(q\_1, q\_2, \ldots, g\_m)$ be $M$ sorted by decreasing $g(q\_i)$ (breaking ties arbitrarily).
2. return $q$

Clearly this can be done in $O(m\log m)$ time.
To finish we show that $q$ is an optimal solution.

By inspection of (1), there is an optimal solution
that uses all elements of $M$ (as appending unused elements
to any solution cannot decrease the cost).
Let $p=(p\_1, p\_2, \ldots, p\_m)$ be any such optimal solution.
Define an *inversion* in $p$ to be a pair $i, j\in [m]$
such that $i < j$ and $r(i) > r(j)$,
where $r(i)$ is the rank of $p\_i$ in $q$
(so $q\_{r(i)} = p\_i$).
If there are no inversions, then $p=q$ so $q$ is optimal, and we are done.
Otherwise, there is an inversion $(i, i+1)$.
Consider modifying $p$ by swapping $p\_i$ with $p\_{i+1}$.
By calculation, this swap
increases the solution value by $\prod\_{j=1}^{i-1} p\_j$ times
$$
\begin{aligned}
&(1-p\_{i+1}) g(p\_{i+1})+ p\_{i+1} (1-p\_i) g(p\_i) \\
{}-{} & p\_i (1-p\_{i+1}) g(p\_{i+1}) - (1-p\_i) g(p\_i) \\
{}={} & [g(p\_{i+1}) - g(p\_i)] (1-p\_i)(1-p\_{i+1}) \\
{}\ge{} & 0 & (\text{using } r(i) > r(i+1), \text{ so } g(p\_i) \le g(p\_{i+1})).
\end{aligned}
$$
So this swap reduces the number of inversions by one
and yields another optimal solution.
So repeatedly swapping yields an optimal solution $p$ with no inversions, i.e., with $p=q$, so $q$ is optimal.$~~~~\Box$

> **Comments:**
> **username_0**: Thank you so much for this thorough response! I wasn't sure if it was easy or hard at first glance.  
> **username_1**: Sure.  One thing: in general it improves posts to add some context about where the problem comes from, what you've tried, and so on.  See https://cstheory.stackexchange.com/help for more advice.  
> **username_0**: Yeah this makes sense! I will give more context in the future. (The original problem I was considering was that there are a bunch of boxes, each one with probability $p_i$ has a prize of value $h_i$, and remaining probability with nothing. Our task is to order them in advance and then inspect them one by one, once we see a prize we have to take it and leave. When we can order them however we like it's clear we should inspect box in decreasing $h_i$, but what if some of the boxes have fixed position that we cannot change? The special case of 1-box fixed can be converted to my posted Q. )  
> **username_0**: (Our objective is to have the highest expected prize value.)  
> **username_1**: Interesting.  How can the case with one box fixed be reduced to your posted question?  If you'd like to ask about the more general question, I guess you can make another post.  
> **username_0**: Sorry turns out I made a mistake in my calculation and the one box version is not exactly equivalent to what I described (f(1- p_i) sometimes depend on the position of the box and not just the value p_i). I posted my original problem in another post (posting the link here in case you are interested). https://cstheory.stackexchange.com/questions/51247/prize-box-ordering-problem-with-position-constraints-easy-or-hard  

---

