Consider array $A=(a_1,a_2,...,a_n)$ such that $a_i$s are positive integers. Moreover, we have $k$ binary tuples, each with length $n$. In each iteration, we choose one of those tuples, and decrease it from the array. For example, if $A=(5,7,4,2)$ and we decrease $(1,0,0,1)$ from it, it will become $(4,7,4,1)$. We cannot use a tuple more than one time. Moreover, we know that sum of all those $k$ tuples is $A$. What is the minimum number of tuples we need to decrease from $A$, in order that $A$ be sorted in decreasing order?
I want to know whether it is an NP-hard problem.
The answer is 4. By subtracting (0,1,1,1),(0,1,1,1),(0,0,1,1) and (1,0,0,1), we will have [1,1,1,1] which is decreasingly sorted. We used 4 tuples, and it is not possible with fewer tuples(at least, I could not).