HackerRank Billboards problem solution

In this HackerRank Billboards problem solution, ADZEN is a popular advertising firm in your city that owns all n billboard locations on Main street. The city council passed a new zoning ordinance mandating that no more than k consecutive billboards may be up at any given time. For example, if there are n=3 billboards on Main street and k=1, ADZEN must remove either the middle billboard, the first two billboards, the last two billboards or the first and last billboard.

Being a for-profit company, ADZEN wants to lose as little advertising revenue as possible when removing the billboards. They want to comply with the new ordinance in such a way that the remaining billboards maximize their total revenues (i.e., the sum of revenues generated by the billboards left standing on Main street).

Given n, k, and the revenue of each of the n billboards, find and print the maximum profit that ADZEN can earn while complying with the zoning ordinance. Assume that Main street is a straight, contiguous block of n billboards that can be removed but cannot be reordered in any way.

HackerRank Billboards problem solution in Python.

#!/bin/python3

import os
import sys

#
# Complete the billboards function below.
#
def billboards(k, revenue):
    N = len(revenue)
    
    total = sum(revenue)
    
    if k == N:
        return total
    else:
        x = revenue[: k + 1]
        
        min_value = min(x)
        min_index = x.index(min_value)
        
        for i in range(k + 1, N):
            if i - min_index >= k:
                min_value = min(x[i - (k + 1) : i + 1])
                min_index = x.index(min_value)
            
            x.append(min_value + revenue[i])
            
            if x[i] < min_value:
                min_value = x[i]
                min_index = i
        
        return total - min(x[N - (k + 1) :])

if __name__ == '__main__':
    fptr = open(os.environ['OUTPUT_PATH'], 'w')

    nk = input().split()

    n = int(nk[0])

    k = int(nk[1])

    revenue = []

    for _ in range(n):
        revenue_item = int(input())
        revenue.append(revenue_item)

    result = billboards(k, revenue)

    fptr.write(str(result) + 'n')

    fptr.close()

Billboards problem solution in Java.

import java.util.Scanner;

public class Billboards {

    static int n;
    static int k;
    static long a[];
    static long f[];
    static int heap[];
    static int heapSize;
    static int where[];

    static void swap(int a[], int i, int j) {
        int tmp = a[i];
        a[i] = a[j];
        a[j] = tmp;
    }

    static boolean lessThan(int i, int j) {
        return f[i - 1] + a[i] < f[j - 1] + a[j];
    }

    static void siftUp(int i) {
        if (i > 1 && lessThan(heap[i], heap[i / 2])) {
            swap(heap, i, i / 2);
            swap(where, heap[i], heap[i / 2]);
            siftUp(i / 2);
        }
    }

    static void siftDown(int i) {
        int which = i;
        if (2 * i <= heapSize && lessThan(heap[2 * i], heap[which])) which = 2 * i;
        if (2 * i + 1 <= heapSize && lessThan(heap[2 * i + 1], heap[which])) which = 2 * i + 1;
        if (which != i) {
            swap(heap, i, which);
            swap(where, heap[i], heap[which]);
            siftDown(which);
        }
    }

    static void insert(int element) {
        where[element] = ++heapSize;
        heap[heapSize] = element;
        siftUp(heapSize);
    }

    static void remove(int element) {
        if (where[element] < heapSize) {
            where[heap[heapSize]] = where[element];
            heap[where[element]] = heap[heapSize--];

            siftDown(where[element]);
            siftUp(where[element]);
        } else heapSize--;
        where[element] = 0;
    }

    public static void main(String[] args) {
        Scanner cin = new Scanner(System.in);

        n = cin.nextInt();
        k = cin.nextInt();
        a = new long[n + 1];
        f = new long[n + 1];
        heap = new int[n + 1];
        where = new int[n + 1];

        long sum = 0;
        for (int i = 1; i <= n; i++) {
            a[i] = cin.nextLong();
            sum += a[i];
        }

        for (int i = 1; i <= k; i++)
            insert(i);
        for (int i = k + 1; i <= n; i++) {
            insert(i);
            f[i] = f[heap[1] - 1] + a[heap[1]];
            remove(i - k);
        }

        System.out.println(sum - f[n]);

        cin.close();
    }
}

Problem solution in C++.

/* Enter your code here. Read input from STDIN. Print output to STDOUT */

#include <iostream>
#include <queue>
#include <vector>
#include <math.h>

using namespace std;

struct Profit {
    long long value;
    int pos;
};

class CompareProfit {
    public:
    bool operator()(Profit& t1, Profit& t2)
    {
        return t1.value > t2.value;
    }
};

int main(int argc, char** argv) {
    int N, K;
    std::cin >> N >> K;
    
    long long curr;
    std::priority_queue<Profit, vector<Profit>, CompareProfit> q;
    
    Profit p;
    Profit p2;
    long long sum = 0;
    
    for (int i = 0; i < N; i++) {
        std::cin >> curr;
        sum += curr;
        
        if (K!=N) {
            if (i <= K) {
                p.value = curr;
                p.pos = i;
                q.push(p);
            } else {
                p = q.top();
                while (p.pos < i - (K+1)) {
                    q.pop();
                    p = q.top();
                }
                p2.value = curr + p.value;
                p2.pos = i;
                q.push(p2);
            }
        }
    }
    if (K == N) {
        std::cout << sum << std::endl;
    } else {
        p = q.top();
        while(p.pos < N - (K+1)) {
            q.pop();
            p = q.top();
        }
        std::cout << (sum - p.value) << std::endl;
    }
    return 0;
}

Problem solution in C.

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

int main(){

	int n,k,i,j;
	
	scanf("%d %d",&n,&k);
	long int *v=(long int *)malloc((n+1)*sizeof(long int));
	long int *p=(long int *)malloc((n+1)*sizeof(long int));	
	
	for(i=1;i<=n;i++)
		scanf("%ld",&v[i]);

	v[0]=0;
	for(i=1;i<=n;i++)
		v[i]+=v[i-1];
	
	for(i=1;i<=k;i++)
		p[i]=v[i];

	long int removed;
	int maxi=-1;
	for(i=k+1;i<=n;i++){
		if(maxi>0 && v[i]-v[i-1]>removed) {
			p[i]=p[i-1]+v[i]-v[i-1];
			maxi--;
		}
		else{
			long int max=-1;
			j=i-k;
			while(j<=i){
				long int profit=p[j-1]+(v[i]-v[j]);
				if(profit>max) {max=profit; maxi=j-i+k; removed=v[j]-v[j-1];}
				j++;
			}
			p[i]=max;
		}
	}
		
	printf("%ldn",p[n]);
	
return 0;
}