Algorithm


Problem Name: Data Structures - Burger Happiness

Problem Link: https://www.hackerrank.com/challenges/burger-happiness/problem?isFullScreen=true

In this HackerRank in Data Structures - Burger Happiness solutions,

In Burger Town new burger restaurants will be opened! Concretely, N restaurants will open in N days, while restaurant i will be opened on day i nd will be located at Xi- The town should be imagined as an one dimensional line in which every object's location can be described by the x coordinate.

Tim has just recently arrived the town after a very bad result in a programming contest. Thus he wants to cheer himself up by starting a trip to try out some new burgers.

Every burger restaurant i is associated with two integers Ai and Bi . If Tim eats a burger from i , then his happiness will increase by Ai , which can also be negative, depending on the deliciousness of the burger. On the other hand, if Tim looks through the window of an opened restaurant i , from which he will not eat a burger, then his happiness decreases by Bi , since Tim gets sad by only seeing the burgers. Tim's journey can start from any day d at the burger restaurant d and eats a burger from there. On each subsequent day n > d Tim has the following options:

  • Stay at the previous restaurant p.
  • Or go to the new restaurant n to eat a burger from there.

If he decides for the latter option, then on the path from p to n he will look through all the windows that are on his path and maybe lose some happiness. Concretely, if Xp < Xn, then he will look through the window of every opened restaurant i having Xp <= Xi <= Xn . Similar for the case Xn < Xp.

Since Tim is a very good friend of yours you should help him finding a trip that will maximize his happiness. If he should stay at home since no trip would cheer him up, then print 0.

 

Note: Tim's happiness is 0 at the beginning of the trip and is allowed to be negative throughout the time.

 

Input Format

N will be given on the first line, then N lines will follow, describing the restaurants numbered from 1 to N accordingly. Restaurant i will be described by Xi,Ai and Bi separated by a single space.

Output Format

 

Output the maximium happiness on one line.

 

Constraints

  • 1 <= N <= 10**5
  • |Ai| <= 10**6
  • 0 <= Bi <= 10**6
  • 0 <= Xi <= 10**9 and no two restaurants will have the same X coordinates.

Sample Input

 

 3
 2 -5 1
 1 5 1
 3 5 1

 

Sample Output

 

8

 

Sample Input

 

 4
 4 10 0
 1 -5 0
 3 0 10
 2 10 0

 

Sample Output

 

 15

 

Sample Input

 

 3
 1 -1 0
 2 -2 0
 3 -3 0

 

Sample Output

 

 0

First testcase: His trip starts on day 2 at restaurant 2 located at X2 = 1 . He gains A2 = 5 happiness points there by eating a burger. On the next day he goes from restaurant 2 to 3, but will look through the window of restaurant 2 and 1. Therefore he loses B2 = 1 and B1 = 1 points on the way to restaurant 3. There he eats a burger and gains another A3 = 5 points. In total his happiness is equal to 5 - 1 - 1 + 5 = 8 and this is optimal.

Second testcase: His trip starts on day 1 at restaurant 1. Then his actions on day 2, 3 and 4 will be go to restaurant 2, stay at restaurant 2 and go to restaurant 4 respectively. The happiness of this optimal trip is equal to 10 - 5 + 10 = 15. Third testcase: It's not worth to start the trip from any of the restaurant since he will only have negative happiness. That's why he should stay at home and 0 should be printed.

 

 

 

 

Code Examples

#1 Code Example with C Programming

Code - C Programming


#include <stdio.h>
#include <stdlib.h>
#define INF 1000000000000000000LL
typedef struct Node {
  long long offt;
  long long cmax;
} node;
void init( int n );
long long range_sum( int i, int j );
void update( int i, long long val );
void updated(int n, int b, int e, int i, int j, long long val,node* tree);
long long query(int n, int b, int e, int i, int j, long long offt,node* tree);
long long max(long long a,long long b);
void sort_a2(int*a,int*b,int size);
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size);
int X[100000],A[100000],B[100000],idx[100000],N;
long long tree[300000],ans[100000];
node left[400000]={0},right[400000]={0};

int main(){
  int M,i;
  long long max,max1,max2,lsum,rsum;
  scanf("%d",&M);
  for(i=0;i < M;i++){
    scanf("%d%d%d",X+i,A+i,B+i);
    idx[i]=i;
  }
  sort_a2(X,idx,M);
  for(i = 0; i  <  M; i++)
    X[idx[i]]=i;
  init(M);
  for(i = 0; i  <  M; i++){
    if(X[i]!=M-1)
      max1=query(1,0,M-1,X[i]+1,M-1,0,left);
    else
      max1=-INF;
    if(X[i])
      max2=query(1,0,M-1,0,X[i]-1,0,right);
    else
      max2=-INF;
    lsum=range_sum(0,X[i]);
    rsum=range_sum(X[i],M-1);
    max=(max1+lsum>max2+rsum)?max1+lsum:max2+rsum;
    if(max<0)
      max=0;
    ans[i]=A[i]+max;
    updated(1,0,M-1,X[i],X[i],ans[i],left);
    updated(1,0,M-1,X[i],X[i],ans[i],right);
    updated(1,0,M-1,X[i],M-1,-B[i],left);
    updated(1,0,M-1,0,X[i],-B[i],right);
    update(X[i],B[i]);
  }
  for(i = max = 0; i <  M; i++>
    if(ans[i]>max)
      max = ans[i];
  printf("%lld",max);
  return 0;
}
void init( int n ){
  N = 1;
  while( N < n ) N *= 2;
  int i;
  for( i = 1; i  <  N + n; i++ ) tree[i] = 0;
}
long long range_sum( int i, int j ){
  long long ans = 0;
  for( i += N, j += N; i  < = j; i = ( i + 1 ) / 2, j = ( j - 1 ) / 2 )
  {
    if( i % 2 == 1 ) ans += tree[i];
    if( j % 2 == 0 ) ans += tree[j];
  }
  return ans;
}
void update( int i, long long val ){
  long long diff = val - tree[i+N];
  int j;
  for( j = i + N; j; j /= 2 ) tree[j] += diff;
}
void updated(int n, int b, int e, int i, int j, long long val,node* tree>{
  if (b>e || i>j || b>j || e < i) return;
  if (b>=i && e<=j)
  {
    tree[n].offt += val;
    tree[n].cmax += val;
    return;
  }
  updated(n*2 , b , (b+e)/2 , i , j , val,tree);
  updated(n*2+1 , (b+e)/2 + 1 , e , i , j , val,tree);
  tree[n].cmax = max ( tree[n*2].cmax , tree[n*2+1].cmax ) + tree[n].offt;
}
long long query(int n, int b, int e, int i, int j, long long offt,node* tree){
  if (b>e || i>j || b>j || e < i) return -INF;
  if (b>=i && e<=j)
    return tree[n].cmax + offt;
  offt += tree[n].offt;
  return max ( query(n*2 , b , (b+e)/2 , i , j, offt,tree) , query(n*2+1 , (b+e)/2 + 1 , e , i , j, offt,tree) );
}
long long max(long long a,long long b){
  return (a>b)?a:b;
}
void sort_a2(int*a,int*b,int size){
  if (size  <  2)
    return;
  int m = (size+1)/2,i;
  int*left_a,*left_b,*right_a,*right_b;
  left_a=(int*)malloc(m*sizeof(int));
  right_a=(int*)malloc((size-m)*sizeof(int));
  left_b=(int*)malloc(m*sizeof(int));
  right_b=(int*)malloc((size-m)*sizeof(int));
  for(i = 0; i  <  m; i++){
    left_a[i]=a[i];
    left_b[i]=b[i];
  }
  for(i = 0; i  <  size-m; i++){
    right_a[i] = a[i+m];
    right_b[i] = b[i+m];
  }
  sort_a2(left_a,left_b,m);
  sort_a2(right_a,right_b,size-m);
  merge2(a,left_a,right_a,b,left_b,right_b,m,size-m);
  free(left_a);
  free(right_a);
  free(left_b);
  free(right_b);
  return;
}
void merge2(int*a,int*left_a,int*right_a,int*b,int*left_b,int*right_b,int left_size, int right_size){
  int i = 0, j = 0;
  while (i  <  left_size|| j < right_size) {
    if (i == left_size) {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      j++;
    } else if (j == right_size) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      i++;
    } else if (left_a[i]  < = right_a[j]) {
      a[i+j] = left_a[i];
      b[i+j] = left_b[i];
      i++;
    } else {
      a[i+j] = right_a[j];
      b[i+j] = right_b[j];
      j++;
    }
  }
  return;
}
Copy The Code & Try With Live Editor

#2 Code Example with C++ Programming

Code - C++ Programming


#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cassert>
using namespace std;
typedef long long ll;
const int MAX_N = 1e5;
const ll INF = 1LL << 62;
const int MAX_A = 1e6;
const int MAX_X = 1e9;
const int MAX_B = 1e6;

int N;
int X[MAX_N], A[MAX_N], B[MAX_N];
ll F[MAX_N];

int tmp[MAX_N];
struct SegmentTree {
  ll lazy[MAX_N * 4];
  ll T[MAX_N * 4];
  void init(){
    memset(lazy, 0, sizeof lazy);
    memset(T, 0, sizeof T);
  }
  void propagate(int n, int L, int R){
    T[n] += lazy[n];
    if(L != R){
      lazy[n * 2] += lazy[n];
      lazy[n * 2 + 1] += lazy[n];
    }
    lazy[n] = 0;
  }

  void update(int n, int L, int R, int i, int j, ll x){
    propagate(n, L, R);
    if(R < i || j  <  L) return;
    if(i <= L && R <= j){
      lazy[n] = x;
      propagate(n, L, R);
    } else {
      update(n * 2, L, (L + R) / 2, i, j, x);
      update(n * 2 + 1, (L + R) / 2 + 1, R, i, j, x);
      T[n] = max(T[n * 2], T[n * 2 + 1]);
    }
  }

  void update(int i, int j, ll x){
    if(i  < = j)
      update(1, 0, N - 1, i, j, x);
  }

  ll query(int n, int L, int R, int i, int j){
    if(R < i || j < L) return -INF;
    propagate(n, L, R);
    if(i  < = L && R <= j) return T[n];
    return max(query(n * 2, L, (L + R) / 2, i, j),
           query(n * 2 + 1, (L + R) / 2 + 1, R, i, j));
  }
  ll query(int i, int j>{
    if(i > j) return -INF;
    return query(1, 0, N - 1, i, j);
  }
};

SegmentTree T1; // Stores maximum f(x') + S[x' - 1]
SegmentTree T2; // Stores maximum f(x') - S[x']

ll query(int x, int a){
  ll S = -T2.query(x, x);  // S[x], since F[x] = 0
  ll S1 = T1.query(x, x);  // S[x - 1], since F[x] = 0
  // Case x' < x
  ll res1 = -S + a + T1.query(0, x - 1);
  // Case x  <  x'
  ll res2 = S1 + a + T2.query(x + 1, N - 1);
  // Case Beginning from x
  ll res3 = a;
  return max(max(res1, res2), res3);
}

void update(int x, int b){
  T1.update(x, x, F[x]);
  T1.update(x + 1, N - 1, +b);

  T2.update(x, x, F[x]);
  T2.update(x, N - 1, -b);
}

int main(){
  T1.init(), T2.init();
  scanf("%d", &N);
  assert(1  < = N && N <= MAX_N);
  for(int i = 0; i  <  N; i++){
    scanf("%d%d%d", X + i, A + i, B + i);
    assert(0  < = X[i] && X[i] <= MAX_X);
    assert(0 <= B[i] <= MAX_B);
    assert(-MAX_A  < = A[i] && A[i] <= MAX_A);
    tmp[i] = X[i];
  }
  sort(tmp, tmp + N);
  int m = unique(tmp, tmp + N) - tmp;
  for(int i = 0; i  <  N; i++){
    X[i] = lower_bound(tmp, tmp + m, X[i]) - tmp;
  }
  ll res = 0;
  for(int i = 0; i  <  N; i++){
    F[X[i]] = query(X[i], A[i]);
    update(X[i], B[i]);
    res = max(res, F[X[i]]);
  }
  printf("%lld\n", res>;
  return 0;
}
Copy The Code & Try With Live Editor

#3 Code Example with Java Programming

Code - Java Programming


import java.io.*;
import java.util.*;

public class BurgerHappiness {

    BufferedReader br;
    PrintWriter out;
    StringTokenizer st;
    boolean eof;

    static class Node {
        static final long INF = Long.MAX_VALUE / 4;
        int l, r;
        Node left, right;
        long add;
        long max;

        public Node(int l, int r) {
            this.l = l;
            this.r = r;
            if (r - l > 1) {
                int mid = (l + r) >> 1;
                left = new Node(l, mid);
                right = new Node(mid, r);
            }
        }

        long getMax() {
            return max + add;
        }

        long qMax(int ql, int qr) {
            if (l >= qr || ql >= r) {
                return -INF;
            }
            if (ql  < = l && r <= qr) {
                return getMax();
            }
            return Math.max(left.qMax(ql, qr), right.qMax(ql, qr)) + add;
        }
        
        long get(int pos) {
            if (l == pos && pos + 1 == r) { 
                return add;
            }
            return add + (pos  <  left.r ? left : right).get(pos);
        }
        
        void qAdd(int ql, int qr, long delta) {
            if (l >= qr || ql >= r) {
                return;
            }
            if (ql  < = l && r <= qr) {
                add += delta;
                return;
            }
            left.qAdd(ql, qr, delta);
            right.qAdd(ql, qr, delta);
            max = Math.max(left.getMax(), right.getMax());
        }
    }

    void solve() throws IOException {
        int n = nextInt();
        int[] x = new int[n];
        int[] a = new int[n];
        int[] b = new int[n];
        for (int i = 0; i  <  n; i++) {
            x[i] = nextInt();
            a[i] = nextInt();
            b[i] = nextInt();
        }
        int[] xx = x.clone();
        Arrays.sort(xx);
        for (int i = 0; i  <  n; i++) {
            x[i] = Arrays.binarySearch(xx, x[i]);
        }

        long ans = 0;

        Node pref = new Node(0, n);
        Node suff = new Node(0, n);

        for (int i = 0; i  <  n; i++) {
            int pos = x[i];
            long valL = suff.qMax(0, pos + 1) - suff.get(pos);
            long valR = pref.qMax(pos, n) - pref.get(pos);
            long val = Math.max(valL, valR) + a[i];
            ans = Math.max(ans, val);
            pref.qAdd(pos, n, -b[i]);
            suff.qAdd(0, pos + 1, -b[i]);
            pref.qAdd(pos, pos + 1, val);
            suff.qAdd(pos, pos + 1, val);
        }
        out.println(ans);
    }

    BurgerHappiness() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        out = new PrintWriter(System.out);
        solve();
        out.close();
    }

    public static void main(String[] args) throws IOException {
        new BurgerHappiness();
    }

    String nextToken() {
        while (st == null || !st.hasMoreTokens()) {
            try {
                st = new StringTokenizer(br.readLine());
            } catch (Exception e) {
                eof = true;
                return null;
            }
        }
        return st.nextToken();
    }

    String nextString() {
        try {
            return br.readLine();
        } catch (IOException e) {
            eof = true;
            return null;
        }
    }

    int nextInt() throws IOException {
        return Integer.parseInt(nextToken());
    }

    long nextLong() throws IOException {
        return Long.parseLong(nextToken());
    }

    double nextDouble() throws IOException {
        return Double.parseDouble(nextToken());
    }
}
Copy The Code & Try With Live Editor
Advertisements

Demonstration


Previous
[Solved] Almost Equal - Advanced solution in Hackerrank - Hacerrank solution C, C++, java,js, Python
Next
[Solved] Roy and alpha-beta trees solution in Hackerrank - Hacerrank solution C, C++, java,js, Python