1

there are two threads that describe this problem:

  1. Removal of billboards from given ones
  2. Algorithm to find maximum sum of elements in an array such that not more than k elements are adjacent

I restate the problem as found on Hacker Rank, again here for convenience:

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.

My solution to the problem is based on the observation that given K you can have K+1 different ways to remove the billboards when K<N and if K==N then only 1. Thus, in the case where K<N I create K+1 buckets where each one corresponds to a solution. Each bucket will hold the billboard revenues that won't be included in its corresponding solution. Therefore, the best solution is the one that has the minimum sum of revenues. My code is the following:

public class Billboards {


public static void main(String[] args) throws IOException {
    BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
    String[] nums = in.readLine().split("\\s+");
    int n = Integer.parseInt(nums[0]);
    int k = Integer.parseInt(nums[1]);
    HashMap<Integer,Long> map = new HashMap<Integer, Long>();
    
    long number;
    int index;
    int bucketsNumber = k+1;
    long sum = 0;
    for(int i=0; i<n; i++){
        number = Long.parseLong(in.readLine());
        sum+=number;
        index = i%bucketsNumber;
        if (map.containsKey(index)){
            map.put(index, map.get(index) + number);
        } else {
            map.put(index, number);
        }
    }
     long min = Long.MAX_VALUE;
     for (int key : map.keySet()){
         if (map.get(key)<min){
             min = map.get(key);
         }
     }
     if(k==n)
         System.out.println(sum);
     else
         System.out.println(sum-min);

}

}

However, this code does not solve all cases but I can't seem to find out why. Is there a problem in the logic of my solution?

4

0 回答 0