Take the 2-minute tour ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.

This is a problem from Interview Street in Dynamic Programming section.

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.

Input description

1st line contain two space separated 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 <= 100,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)
{
    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;
}

Code:

#include<stdio.h>
#include<stdlib.h>

long **DP;
long returnValue(long i, long j);
int main()
{
    long N, K;
    scanf("%ld", &N);
    scanf("%ld" ,&K);

    DP = (long**) malloc(sizeof(long *) * N);

    long ARR[N];
    long j, z, i=0;
    for(i=0;i<N;i++)
    {
        DP[i] = (long*)malloc(sizeof(long) * N);
        scanf("%ld", &ARR[i]);
    }


    for(i=0;i<N;i++)
    {
        long sum=0;
        for(j=1;j<=K && (i+j-1)<N;j++)
        {
            sum += ARR[i+j-1];
            DP[i][i+j-1] = sum;
        }
    }

    for(j=K+1;j<=N;j++)
    {
        for(i=0;i<=N-j;i++)
        {
            long max = 0;
            for(z=i;z<=i+j-1;z++)
            {
                long temp = returnValue(i, z-1) +     returnValue(z+1, i+j-1);
                if(temp > max)
                    max= temp;
            }
            DP[i][i+j-1] = max;
        }
    }
    printf("%ld\n", DP[0][N-1]); 
    for(i=0;i<N;i++)
    {
            free(DP[i]);
    }
    free(DP);
}

long returnValue(long i, long j)
{
    if(i<=j)
    {
        //printf("%d\n", DP[i][j]); 
        return DP[i][j];
    }
    else
        return 0;
}

My solution is of order O(N2). So I get TLE and Segmentation fault for larger N. I have already passed 6/10 test cases. I need to pass remaining 4.

share|improve this question
add comment

1 Answer 1

The inputs have to be limited with constraints you have listed, then

  • use a TreeSet to store the N objects in it
  • remove the K first
  • print the Set

few lines in Java (no malloc problem, memory managed by JVM):

  • read the first input
  • use String.split() the line,
  • use Integer.valueOf(String) to convert
  • compare N,K and stop if not correct or if negative
  • use a while(<N) for input,
  • test limits of input whith if and negative values
  • you can use toString() to print the Set, but you have to use a
  • foreach to sum the result
  • print result
share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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