HackerRank Billboards Problem Solution

In this Post, we will solve 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.
For example, if there are n = 7 billboards, and k = 3 is the maximum number of consecutive billboards that can be active, with revenues = [5, 6, 4, 2, 10, 8, 4], then the maximum revenue that can be generated is 37:5+6+4+10+8+4=37.

Function Description

Complete the billboards function in the editor below. It should return an integer that represents the maximum revenue that can be generated under the rules.

billboards has the following parameter(s):

k: an integer that represents the longest contiguous group of billboards allowed
revenue: an integer array where each element represents the revenue potential for a billboard at that index

Input Format
The first line contains two space-separated integers, n (the number of billboards) and k (the maximum number of billboards that can stand together on any part of the road). Each line of the n subsequent lines contains an integer denoting the revenue value of billboard & (where 0 < i < n).

Output Format

Print a single integer denoting the maximum profit ADZEN can earn from Main street after complying with the city’s ordinance.

Sample Input 0

Sample Output 0

Explanation
There are n = 6 billboards, and we must remove some of them so that no more than k = 2 billboards are immediately next to one another.
We remove the first and fourth billboards, which gives us the configuration 2 3 6 10 and a profit of 2+3+6+10=21. As no other configuration has a profit greater than
21, we print 21 as our answer.

Sample Input 1

Sample Output 1

Explanation 1
There are n = 5 billboards, and we must remove some of them so that no more than
k = 4 billboards are immediately next to one another.
We remove the first billboard, which gives us the configuration_ 2 3 4 5 and a profit of
2+3+4+5=14. As no other configuration has a profit greater than 14, we print 14 as our answer.

Billboards C Solution

#include<stdio.h>

long long int arr[100001];
long long  int sum[100001];
long long  int including[100001],excluding[100001];
long long int maxim(long long int a,long long int b)
{if(a>b) return a;return b;}

int main()
{
int N,K;
scanf("%d%d",&N,&K);
for(int i=0;i<N;++i)scanf("%lld",&arr[i]);

sum[0]=arr[0];
including[0]=sum[0];
excluding[0]=sum[0];
for(int i=1;i<K;++i)
{
    sum[i]+=sum[i-1]+arr[i];
    including[i]=sum[i];
    excluding[i]=sum[i];
}

long long int maxi=0,temp=0;
for(int i=K;i<N;++i)
{
    sum[i]+=sum[i-1]+arr[i];
    for(int j=1;j<=K;++j)
    {
        temp=sum[i]-sum[i-j];
        if(i-j-1>=0)
        temp+=including[i-j-1];
        if(temp>maxi)maxi=temp;
    }
    including[i]=maxi;
    excluding[i]=including[i-1];
}
printf("%lld",maxim(including[N-1],excluding[N-1]));
}

Billboards C++ Solution

#include <bits/stdc++.h>

using namespace std;

vector<string> split_string(string);

/*
 * Complete the billboards function below.
 */
long long int billboards(int k, vector<long long int> revenue) {
    /*
     * Write your code here.
     */
    long long int offset = 0;
    std::priority_queue<pair<long long int, int>> q;
    q.push(make_pair(0, -1));
    for (int i = 0; i < revenue.size(); ++i) {
        offset += revenue.at(i);
        q.push(make_pair(q.top().first - revenue.at(i), i));
        while (q.top().second < i - k) q.pop();
    }
    return q.top().first + offset;
}

int main()
{
    ofstream fout(getenv("OUTPUT_PATH"));

    string nk_temp;
    getline(cin, nk_temp);

    vector<string> nk = split_string(nk_temp);

    int n = stoi(nk[0]);

    int k = stoi(nk[1]);

    vector<long long int> revenue(n);

    for (int revenue_itr = 0; revenue_itr < n; revenue_itr++) {
        long long int revenue_item;
        cin >> revenue_item;
        cin.ignore(numeric_limits<streamsize>::max(), '\n');

        revenue[revenue_itr] = revenue_item;
    }

    long long int result = billboards(k, revenue);

    fout << result << "\n";

    fout.close();

    return 0;
}

vector<string> split_string(string input_string) {
    string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
        return x == y and x == ' ';
    });

    input_string.erase(new_end, input_string.end());

    while (input_string[input_string.length() - 1] == ' ') {
        input_string.pop_back();
    }

    vector<string> splits;
    char delimiter = ' ';

    size_t i = 0;
    size_t pos = input_string.find(delimiter);

    while (pos != string::npos) {
        splits.push_back(input_string.substr(i, pos - i));

        i = pos + 1;
        pos = input_string.find(delimiter, i);
    }

    splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));

    return splits;
}

Billboards C Sharp Solution

using System;
using System.IO;
using System.Collections.Generic;
using System.Linq;
 
 public class Block {
	 public int Start { get; set; }
	 public int End { get; set; }
	 public long Sum { get; set; }

	 public Block(int start, int end, long sum) {
		 this.Start = start;
		 this.End = end;
		 this.Sum = sum;
	 }
 }
 
 public class Solution {

	void Run(TextReader rd) {
		string[] ln = rd.ReadLine().Split(' ');
		int N = int.Parse(ln[0]);
		int K = int.Parse(ln[1]);

		int[] boards = new int[N + 1];

		for(int i = 1; i <= N; i++) {
			boards[i] = int.Parse(rd.ReadLine());
		}

		LinkedList<Block>[] best = new LinkedList<Block>[N + 1];
		LinkedList<Block> firstColumn = new LinkedList<Block>();
		firstColumn.AddFirst(new Block(0, K, 0));
		best[0] = firstColumn;

		for (int j = 1; j <= N; j++) {
			LinkedList<Block> previousColumn = best[j - 1];
			LinkedList<Block> currentColumn = new LinkedList<Block>();
			currentColumn.AddLast(new Block(K, K, previousColumn.Last.Value.Sum));
			long withoutCurrentBoard = previousColumn.Last.Value.Sum;

			foreach (var block in previousColumn) {
				if (block.End == 0) continue;
				long withCurrentBoard = boards[j] + block.Sum;
				long max = Math.Max(withCurrentBoard, withoutCurrentBoard);
				int start = Math.Max(0, block.Start - 1);
				int end = Math.Max(0, block.End - 1);
				var lastBlock = currentColumn.Last.Value;

				if (max == lastBlock.Sum) {
					lastBlock.Start = start;
				} else {
					lastBlock = new Block(start, end, max);
					currentColumn.AddLast(lastBlock);
				}

			}

			best[j] = currentColumn;
		}

		Console.WriteLine(best[N].Last.Value.Sum);
	}

	public static void Main(string[] args) {
		TextReader rd = Console.In;
		if (args.Length > 0) rd = new StreamReader(File.OpenRead(args[0]));
		new Solution().Run(rd);
	}
 }

Billboards Java Solution

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();
    }
}

Billboards JavaScript Solution

'use strict';

const fs = require('fs');

process.stdin.resume();
process.stdin.setEncoding('utf-8');

let inputString = '';
let currentLine = 0;

process.stdin.on('data', function(inputStdin) {
    inputString += inputStdin;
});

process.stdin.on('end', function() {
    inputString = inputString.split('\n');

    main();
});

function readLine() {
    return inputString[currentLine++];
}

/*
 * Complete the 'billboards' function below.
 *
 * The function is expected to return an INTEGER.
 * The function accepts following parameters:
 *  1. INTEGER k
 *  2. INTEGER_ARRAY revenue
 */

function billboards( streakMaximumSize, revenue ) {
  let
    sumByStreakPosition = Array( streakMaximumSize + 1 ).fill( revenue[ revenue.length - 1 ]),
    skipValue = 0;

  sumByStreakPosition[ streakMaximumSize ] = 0;

  for ( let index = revenue.length - 2; index >= 0; index-- ) {
    skipValue = sumByStreakPosition[ 0 ];

    for ( let streak = 0; streak < streakMaximumSize; streak++ ) {
      sumByStreakPosition[ streak ] = Math.max( skipValue, sumByStreakPosition[ streak + 1 ] + revenue[ index ] );
    }

    sumByStreakPosition[ streakMaximumSize ] = skipValue;
  }

  return Math.max( ...sumByStreakPosition );
}

function main() {
    const ws = fs.createWriteStream(process.env.OUTPUT_PATH);

    const firstMultipleInput = readLine().replace(/\s+$/g, '').split(' ');

    const n = parseInt(firstMultipleInput[0], 10);

    const k = parseInt(firstMultipleInput[1], 10);

    let revenue = [];

    for (let i = 0; i < n; i++) {
        const revenueItem = parseInt(readLine().trim(), 10);
        revenue.push(revenueItem);
    }

    const result = billboards(k, revenue);

    ws.write(result + '\n');

    ws.end();
}

Billboards Python Solution

import sys


if __name__ == '__main__':
    N, K = list(map(int, sys.stdin.readline().split()))
    profits = [int(sys.stdin.readline()) for i in range(N)]
    
    total = sum(profits)
    
    if K == N:
        print(total)
    else:
        x = profits[: 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 + profits[i])
            
            if x[i] < min_value:
                min_value = x[i]
                min_index = i
        
        print(total - min(x[N - (K + 1) :]))

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python