Removal of billboards from given ones

Question

I came across this question

ADZEN is a very popular advertising firm in your city. In every road you can see their advertising billboards. Recently they are facing a serious challenge , MG Road the most used and beautiful road in your city has been almost filled by the billboards and this is having a negative effect on
the natural view. On people's demand ADZEN has decided to remove some of the billboards in such a way that there are no more than K billboards standing together in any part of the road. You may assume the MG Road to be a straight line with N billboards.Initially there is no gap between any two adjecent billboards. ADZEN's primary income comes from these billboards so the billboard removing process has to be done in such a way that the billboards remaining at end should give maximum possible profit among all possible final configurations.Total profit of a configuration is the sum of the profit values of all billboards present in that configuration. Given N,K and the profit value of each of the N billboards, output the maximum profit that can be obtained from the remaining billboards under the conditions given.

Input description

1st line contain two space seperated integers N and K. Then follow N lines describing the profit value of each billboard i.e ith line contains the profit value of ith billboard.

    Sample Input
    6 2 
    1
    2
    3
    1
    6
    10 

    Sample Output
    21

Explanation

In given input there are 6 billboards and after the process no more than 2 should be together. So remove 1st and 4th billboards giving a configuration _ 2 3 _ 6 10 having a profit of 21. No other configuration has a profit more than 21.So the answer is 21.

    Constraints
    1 <= N <= 1,00,000(10^5)
    1 <= K <= N
    0 <= profit value of any billboard <= 2,000,000,000(2*10^9)

I think that we have to select minimum cost board in first k+1 boards and then repeat the same untill last,but this was not giving correct answer for all cases. i tried upto my knowledge,but unable to find solution. if any one got idea please kindly share your thougths.

Answer 1

It's a typical DP problem. Lets say that P(n,k) is the maximum profit of having k billboards up to the position n on the road. Then you have following formula:

 P(n,k) = max(P(n-1,k), P(n-1,k-1) + C(n))
 P(i,0) = 0 for i = 0..n

Where c(n) is the profit from putting the nth billboard on the road. Using that formula to calculate P(n, k) bottom up you'll get the solution in O(nk) time.

I'll leave up to you to figure out why that formula holds.

edit

Dang, I misread the question.

It still is a DP problem, just the formula is different. Let's say that P(v,i) means the maximum profit at point v where last cluster of billboards has size i. Then P(v,i) can be described using following formulas:

P(v,i) = P(v-1,i-1) + C(v) if i > 0 
P(v,0) = max(P(v-1,i) for i = 0..min(k, v)) 
P(0,0) = 0

You need to find max(P(n,i) for i = 0..k)).

Answer 2

This problem is one of the challenges posted in www.interviewstreet.com ...

I'm happy to say I got this down recently, but not quite satisfied and wanted to see if there's a better method out there.

soulcheck's DP solution above is straightforward, but won't be able to solve this completely due to the fact that K can be as big as N, meaning the DP complexity will be O(NK) for both runtime and space.

Another solution is to do branch-and-bound, keeping track the best sum so far, and prune the recursion if at some level, that is, if currSumSoFar + SUM(a[currIndex..n)) <= bestSumSoFar ... then exit the function immediately, no point of processing further when the upper-bound won't beat best sum so far.

The branch-and-bound above got accepted by the tester for all but 2 test-cases. Fortunately, I noticed that the 2 test-cases are using small K (in my case, K < 300), so the DP technique of O(NK) suffices.

Answer 3

soulcheck's (second) DP solution is correct in principle. There are two improvements you can make using these observations:

1) It is unnecessary to allocate the entire DP table. You only ever look at two rows at a time.

2) For each row (the v in P(v, i)), you are only interested in the i's which most increase the max value, which is one more than each i that held the max value in the previous row. Also, i = 1, otherwise you never consider blanks.