Assume that \(A\) is sorted.

Instead of finding the probability that exactly \(k\) items are sold, we find the probability that at least \(k\) items are sold. At least \(k\) items are purchased if and only if:

• For \(i=1,2,\ldots,k\), at least \(k+1-i\) people have a budget of at least \(A_i\).

The necessity is clear. The sufficiency follows from the fact that if the above condition holds, it remains satisfied after any person performs their action.

By defining \(\mathrm{dp}[i][j]=\) the number of ways to determine which people have a budget of at least \(A_i\), with at least \(j\) people having their budgets decided, such that the conditions up to this point are satisfied,

and running the above dynamic programming for each \(k\), the problem can be solved in \(\mathrm{O}(N^4)\).

Proposed by: nok0