Guards and demand

Question

You have N guards in a line each with a demand of coins. You can skip paying a guard only if his demand is less than what you have totally paid before reaching him. Find the least number of coins you spend to cross all guards.

I think its a DP problem but can't come up with a formula. Another approach would be to binary search on the answer, but how do I verify if a number of coins is a possible answer?

Answer 1

This is indeed a dynamic programming problem.

Consider the function f(i, j), which is true (one) if there is an assignment of the first i guards which give you cost j. You can arrange function f(i, j) in a table of size n x S, where S is the sum of all the guards demand.

Let us denote d_i as the demand of guard i. You can easily compute the column f(i+1) if you have f(i) by simply scanning f(i) and assigning f(i+1, j + d_i) as one if f(i + 1, j) is true and j < d_i, or f(i + 1, j) if j >= d_i.

This runs in O(nS) time and O(S) space (you only need to keep two columns per time), which is only pseudopolynomial (and quadratic-like if demands are somehow bounded and does not grow with n).

A common trick to reduce the complexity of a DP problem is to get an upper bound B on the value of the optimal solution. This way, you can prune unnecessary rows, obtaining a time complexity of O(nB) (well, even S is an upper-bound, but a very naïve one).

It turns out that, in our case, B = 2M, where M is the maximum demand of a guard. In fact, consider the function best_assignment(i), which gives you the minimum amount of coins to pass the first i guards. Let j be the guard with demand M. If best_assignment(j - 1) > M, then obviously the best assignment for the whole sequence is pay the guards for the best assignment of the first j-1 guards and skip the others, otherwise the upper-bound is given by best_assignment(j - 1) + M < 2M. But how much best_assignment(j - 1) can be in the first case? It cannot be more than 2M. This can be proven by contradiction. Let us suppose that best_assignment(j - 1) > 2M. In this assignment, the guard j-1 is paid? No, because 2M - d_{j-1} > d_{j-1}, thus it does not need to be paid. The same argument holds for j-2, j-3, ... 1, thus no guard is paid, which is absurd unless M = 0 (a very naïve case to be checked).

Since the upper-bound is proved to be 2M, the DP illustrated above with n columns and 2M rows solves the problem, with time complexity O(nM) and space complexity O(M).

Answer 2

function crossCost(amtPaidAlready, curIdx, demands){
    //base case: we are at the end of the line
    if (curIdx >= demands.size()){
        return amtPaidAlready;
    }

    costIfWePay = crossCost(amtPaidAlready + demands[curIdx], curIdx+1, demands);
    //can we skip paying the guard?
    if (demands[curIdx] < amtPaidAlready){
        costIfWeDontPay = crossCost(amtPaidAlready, curIdx+1, demands);
        return min(costIfWePay, costIfWeDontPay);
    }
    //can't skip paying
    else{
        return costIfWePay;
    }
}

This runs in O(2^N) time because it may call itself twice per execution. It's a good candidate for memoization, because it is a pure function with no side effects.