Table of Contents
Billboards – HackerRank Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
Solutions of Algorithms Data Structures Hard HackerRank:
Here are all the Solutions of Hard , Advanced , Expert Algorithms of Data Structure of Hacker Rank , Leave a comment for similar posts
C++ Billboards HackerRank Solution
#include <iostream>
#include <list>
const int maxn = 100001;
long long mindec[maxn];
long long answer;
int main(){
int n,k;
std::cin>>n>>k;
std::list<int> prev;
mindec[0] = 0;
prev.push_back(0);
for (int i=1; i<=n; ++i){
long long v;
std::cin>>v;
answer += v;
if (prev.front() < i-k-1) prev.pop_front();
mindec[i] = v + mindec[prev.front()];
while (! prev.empty() && mindec[prev.back()] >= mindec[i]) prev.pop_back();
prev.push_back(i);
}
if (prev.front() < n-k) prev.pop_front();
std::cout<<answer-mindec[prev.front()]<<std::endl;
}
Java Billboards HackerRank Solution
import java.io.*;
import java.util.*;
import java.math.*;
public class Solution {
public static void main(String args[]) throws Exception {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int K = sc.nextInt();
int step=K/10;
int P[] = new int[N+16];
long maxSum[] = new long[N+16];
int maxSumEle[] = new int[N+16];
long max[] = new long[N+16];
int maxCount[] = new int[N+16];
int ii=0;
for(int i=0; i < N; ii++,i++) {
P[ii] = sc.nextInt();
if(P[ii]==0&&(ii==0||P[ii-1]==0))
ii--;
}
if(ii>0&&P[ii-1]==0)
ii--;
N=ii;
int mycount=0;
int n=N-1;
for(int i=0;n>=0&&(i<K||(i==K&&P[n]==0));i++,n--) {
max[n]=P[n]+max[n+1];
if(P[n]==0)
i=-1;
maxCount[n]=i+1;
//System.out.println(n+" "+P[n]+" "+max[n]+" "+maxCount[n]);
}
int NN=N;
NN=n+1;
long currSum=0;
long currMax=-1;
int currMaxEle=-1;
int end=K+3<N-NN+3?K+3:N-NN+3;
for(int i=0;i<end;i++) {
if(currSum+max[NN+i+1]>=currMax) {
if(currSum+max[NN+i+1]>currMax||currMaxEle>i+1)
currMaxEle=i+1;
currMax=currSum+max[NN+i+1];
}
if(currSum+max[NN+i+2]>=currMax) {
if(currSum+max[NN+i+2]>currMax||currMaxEle>i+2)
currMaxEle=i+2;
currMax=currSum+max[NN+i+2];
}
maxSum[i]=currMax;
//System.out.println(N+" "+K+" "+P[i+NN]+" "+i+" "+maxSum[i]+" "+maxSumEle[i]);
maxSumEle[i]=currMaxEle;
currSum+=P[i+NN];
}
//System.out.println(i+" "+n+" "+P[n]+" "+max[n]);
int mid=-1;
if(step>=1)
mid=NN-step;
for(;n>=0;n--) {
long res=max[n+1];
int resCount=0;
currSum=0;
int i=0;
end=K<NN-n?K:NN-n;
for(i=0;i<end;i++) {
currSum+=P[n+i];
if(res<=max[n+i+2]+currSum) {
if(res<max[n+i+2]+currSum||resCount>i+1)
resCount=i+1;
res=max[n+i+2]+currSum;
}
//System.out.println(i+" "+n+" "+P[n]+" "+res+" "+resCount);
}
if((i+n)<N) {
if(i<K) {
long currSum2=currSum+maxSum[K-i];
int currSumEle=i-1+maxSumEle[K-i];
if(res<=currSum2) {
if(res<currSum2||resCount>currSumEle)
resCount=currSumEle;
res=currSum2;
}
//System.out.println(i+" "+n+" "+P[n]+" "+res+" "+resCount);
} else {
i--;
if(i>=0&&res<=max[n+i+3]+currSum) {
if(res<max[n+i+3]+currSum||resCount>i+1)
resCount=i+1;
res=max[n+i+3]+currSum;
}
}
}
if(maxCount[n+1]<K&&res<=max[n+1]+P[n]) {
if(res<max[n+1]+P[n]||resCount>maxCount[n+1]+1)
resCount=maxCount[n+1]+1;
res=max[n+1]+P[n];
}
max[n]=res;
maxCount[n]=resCount;
if(n==mid) {
NN=n+1;
currSum=0;
currMax=-1;
currMaxEle=-1;
end=K+3<N-NN+3?K+3:N-NN+3;
for(i=0;i<end;i++) {
if(currSum+max[NN+i+1]>=currMax) {
if(currSum+max[NN+i+1]>currMax||currMaxEle>i+1)
currMaxEle=i+1;
currMax=currSum+max[NN+i+1];
}
if(currSum+max[NN+i+2]>=currMax) {
if(currSum+max[NN+i+2]>currMax||currMaxEle>i+2)
currMaxEle=i+2;
currMax=currSum+max[NN+i+2];
}
maxSum[i]=currMax;
//System.out.println(N+" "+K+" "+P[i+NN]+" "+i+" "+maxSum[i]+" "+maxSumEle[i]);
maxSumEle[i]=currMaxEle;
currSum+=P[i+NN];
}
//if(mid>1000)
mid-=step;//mid*9/10;
//else
// mid=-1;
if(mid<=0)
mid=-1;
mycount++;
}
//System.out.println(n+" "+P[n]+" "+res+" "+resCount);
}
System.out.println(max[0]);//+" "+mycount);
}
}
/*
time java Solution < myin10
99915808645418
real 0m26.662s
user 0m32.146s
sys 0m17.673s
*/
Python 3 Billboards HackerRank Solution
Suggest in comments
Python 2 Billboards HackerRank Solution
# Enter your code here. Read input from STDIN. Print output to STDOUT
size, limit = [ int(i) for i in raw_input().split(' ') if i ]
cache = {0: 0}
count = 0
while count < size:
count += 1
i = int(raw_input())
max_value = 0
for j in cache:
v = cache[j]
if v > max_value:
max_value = v
new_cache = {}
for j in cache:
if j == limit:
continue
v = cache[j] + i
if v > max_value:
new_cache[j + 1] = v
cache = new_cache
cache[0] = max_value
print max(cache.values())
C Billboards HackerRank Solution
/* Enter your code here. Read input from STDIN. Print output to STDOUT */
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <assert.h>
typedef long long LONG_T;
char buf[200000];
//#define INPUT fgets(buf,sizeof(buf),FD)
//#define USEFILEIO
#define INPUT gets(buf)
#define MAX(x,y) ((x) > (y) ? (x) : (y))
#define MIN(x,y) ((x) < (y) ? (x) : (y))
#define MAXN (100000)
#define GROUPSIZE (316)
#define MAXGROUP ((MAXN/GROUPSIZE) + 1)
#define MAXINT (1ULL<<62)
LONG_T BOARD[MAXN];
LONG_T MAXVAL[MAXN+2];
LONG_T LASTCUT[MAXN+2];
LONG_T COST[MAXN*2];
LONG_T GROUP[MAXGROUP];
LONG_T
calc_max (int N, int K) {
memset(MAXVAL,0,sizeof(MAXVAL));
MAXVAL[N-1] = BOARD[N-1];
MAXVAL[N] = 0;
MAXVAL[N+1] = 0;
int i;
for (i = N-2;i >=0;i--) {
LONG_T max = MAXVAL[i+1];
LONG_T ltotal = 0;
int j;
for (j = 0; j < K;j++) {
if (i+j >= N) {
break;
}
ltotal += BOARD[i+j];
max = MAX(ltotal+MAXVAL[i+j+2],max);
}
MAXVAL[i] = max;
}
return (MAXVAL[0]);
}
LONG_T
calc_max_fast (int N, int K) {
MAXVAL[N] = 0;
MAXVAL[N+1] = 0;
int i;
for (i=N-1;i>= N-K;i--) {
MAXVAL[i] = BOARD[i] + MAXVAL[i+1];
}
if (i < 0) {
return (MAXVAL[0]);
}
for (;i >=0;i--) {
LONG_T max = MAXVAL[i+1];
LONG_T ltotal = 0;
int j;
for (j = 0; j < K;j++) {
if (i+j >= N) {
break;
}
ltotal += BOARD[i+j];
if (ltotal+MAXVAL[i+j+2] >= max) {
max = ltotal+MAXVAL[i+j+2];
}
}
MAXVAL[i] = max;
}
return (MAXVAL[0]);
}
LONG_T
calc_max_fastest (int N, int K) {
int i,j,min_index,group,nextgroup;
LONG_T min,groupmin;
LONG_T total=0;
COST[i] = 0;
min = 0;
min_index = N;
group = N / GROUPSIZE;
GROUP[group] = 0;
if (N % GROUPSIZE) {
groupmin = 0;
} else {
groupmin = MAXINT;
}
for (i=N-1;i>=0;i--) {
// brute search
min = MAXINT;
for (j=i+1; j<=i+1+K;j++) {
if ((j % GROUPSIZE) == 0) {
break;
}
if (j > N) {
break;
}
min = MIN(min,COST[j]);
}
for (; j<=i+1+K;j+=GROUPSIZE) {
if (j + GROUPSIZE > i+1+K) {
break;
}
if (j + GROUPSIZE > N) {
break;
}
assert ((j % GROUPSIZE) == 0);
group = j / GROUPSIZE;
min = MIN(min,GROUP[group]);
}
if (j <= i+1+K) {
for (; j<=i+1+K;j++) {
if (j > N) {
break;
}
min = MIN(min,COST[j]);
}
}
COST[i] = min + BOARD[i];
groupmin = MIN(groupmin,COST[i]);
if ((i % GROUPSIZE) == 0) {
group = i / GROUPSIZE;
GROUP[group] = groupmin;
min = MAXINT;
for (j = i; j < i+GROUPSIZE;j++) {
if (j > N) {
break;
}
min = MIN(min,COST[j]);
}
assert(groupmin == min);
groupmin = MAXINT;
}
total += BOARD[i];
}
min = (1ULL << 62);
for (i=0;i<=K;i++) {
min = MIN(min,COST[i]);
}
return (total - min);
}
LONG_T
calc_max_faster (int N, int K) {
int i,j,min_index;
LONG_T min;
LONG_T total=0;
COST[N] = 0;
min = 0;
min_index = N;
for (i=N-1;i>=0;i--) {
if (i+1+K < min_index) {
// brute search
min = MAXINT;
for (j=i+1; j<=i+1+K;j++) {
if (j > N) {
break;
}
if (COST[j] < min) {
min = COST[j];
min_index = j;
}
}
}
COST[i] = min + BOARD[i];
total += BOARD[i];
}
min = (1ULL << 62);
for (i=0;i<=K;i++) {
min = MIN(min,COST[i]);
}
return (total - min);
}
LONG_T
calc_max_slow (int N, int K) {
int i,j;
LONG_T min;
LONG_T total=0;
COST[N] = 0;
for (i=N-1;i>=0;i--) {
min = MAXINT;
for (j=i+1; j<=i+1+K;j++) {
min = MIN(min,COST[j]);
}
COST[i] = min + BOARD[i];
total += BOARD[i];
}
min = (1ULL << 62);
for (i=0;i<=K;i++) {
min = MIN(min,COST[i]);
}
return (total - min);
}
int main (int argc, char *argv[]) {
FILE *FD;
char *saveptr;
char *tok;
int i;
int N, K;
#ifdef USEFILEIO
FD = fopen(argv[1], "r");
if (!FD) {
printf("error cannot open %s\n",argv[1]);
return -1;
}
#endif
INPUT;
tok = strtok_r(buf," ",&saveptr);
N = atoi(tok);
tok = strtok_r(NULL," ",&saveptr);
K = atoi(tok);
for (i = 0; i < N; i++) {
INPUT;
int val;
tok = strtok_r(buf," ",&saveptr);
val = atoi(tok);
BOARD[i] = val;
}
#if 0
int testn;
for (testn = 0; testn < 100;testn++) {
N = rand() % 100000;
N = 100000;
for (i = 0; i < N; i++) {
BOARD[i] = rand() % 1000000000;
}
K = rand() % 100000;
K = 100000;
K = MIN(N,K);
LONG_T total;
total = calc_max_faster(N,K);
printf("%lld\n",total);
LONG_T fast_total;
fast_total = calc_max_fastest(N,K);
printf("%lld\n",fast_total);
// total = fast_total;
if (total != fast_total) {
assert (0);
}
}
#endif
LONG_T fast_total;
fast_total = calc_max_fastest(N,K);
printf("%lld\n",fast_total);
return 0;
}
Warmup
Implementation
Strings
Sorting
Search
Graph Theory
Greedy
Dynamic Programming
Constructive Algorithms
Bit Manipulation
Recursion
Game Theory
NP Complete
Debugging
Leave a comment below
