1
$\begingroup$

This is a problem from Interview Street in Dynamic Programming section. https://www.interviewstreet.com/challenges/dashboard/#problem/4f2c2e3780aeb

Billboards(20 points)

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.

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

My Solution (Psuedocode):

Let Profit[i] denote the Profit from ith billboard.
(i, j) denotes the range of billboards
MaxProfit(i, j) for all (i, j) such that i<=j and i-j+1 <= K is:
    MaxProfit(i, j) = Profit[i] + Profit[i+1] + ... + Profit[j];

For other (i,j) MaxProfit equals,

MaxProfit(i, j)
{
        if(MaxProfit(i, j) is already calculated)
            then return its value;
    max = 0;
    for all k such that i<=k<=j // k denotes that, that position has no   billboard
    {
        temp = MaxProfit(i, k-1) + MaxProfit(k+1, j);
        if(temp > max)
        max = temp;
    }
return max;
}

My solution is of order $$N^2$$. So I get TLE and Segmentation fault for larger N. I have already passed 6/10 test cases. I need to pass remaining 4. Help needed.

$\endgroup$
  • $\begingroup$ from my understanding, this is the knapsack problem. en.wikipedia.org/wiki/Knapsack_problem .. I did not check your solution yet. $\endgroup$ – AJed Oct 21 '12 at 16:39
  • $\begingroup$ Sort of, but the time complexity is N^2 using Dynamic Programming. I need to reduce the time complexity and space complexity. Both are N^2 for my solution or Knapsack. If N=10^5, I get TLE and I'm using way too much memory. $\endgroup$ – Neeraj Kumar Singh Oct 21 '12 at 16:52
  • 2
    $\begingroup$ @NeerajKumarSingh: Perhaps codereview.SE is the right place for all this code? Or perhaps codeGolf.SE? Large chunks of code, especially from contests, may not be the right fit here. $\endgroup$ – PKG Oct 21 '12 at 21:40
  • $\begingroup$ You should be able to reduce the time to $O(N$*$K)$ and the space to $O(N)$, but I suspect to win you will have to reduce the time further; maybe to something like $O(N \log N)$. Think about it. $\endgroup$ – Peter Shor Oct 22 '12 at 0:41
  • 2
    $\begingroup$ @NeerajKumarSingh Please tailor your question to the standards of this site, i.e. avoid full source code listings and give the problem in your own words (with attribution). $\endgroup$ – Raphael Oct 22 '12 at 13:54
8
$\begingroup$

You can do it in $O(N \log N)$ time and $O(N)$ space.

Instead of finding the billboards that you want to keep, find the billboards that you want to get rid of. You need to find the minimum cost set of billboards such that there is no gap of more than $K$ between two billboards. Do this by constructing a table where the $i$th entry is the minimum cost to remove the $i$th billboard and enough previous billboards to make this legal. Now, to add an entry to the table, you need to find the minimum of the previous $K$ entries to the table. You can do this in $O(\log N)$ time using a priority queue.

If $K \ll N$, you might want to use a fancier priority queue that takes $O(\log K)$ time instead; but I'd guess that for large $K$, the simpler priority queues such as heaps that don't admit deletion of a non-MIN item are quicker for this problem. I don't know how tight time limits Interview Street has set for this problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.