HackerRank Maximizing Mission Points problem solution

In this HackerRank Maximizing Mission Points problem solution we have given d_lat, d_long, and the definitions for n cities. we need to find and print the maximum possible total points that Xander can earn on a mission.

Problem solution in Python.

from collections import namedtuple
from bisect import bisect_left
import sys

Place = namedtuple('Place', 'lat, long, height, points')

chunkplaces={} # places get inserted into lists contained here, grouped by keys of their locations
chunkvals={} # holds values

giant = False
def getkey(place, off_lat=0, off_long=0):
    return ((place.lat // d_lat + off_lat) * 200011) + place.long // d_long + off_long # unique for n<=200000

def recordvalue(place, val):
    if val < 0:
        return # not worth going here; no need to track
    key = getkey(place)
    if key not in chunkplaces:
        chunkplaces[key] = []
        chunkvals[key] = []
    if giant:
        if len(chunkvals[key]) == 0:
            chunkvals[key].append(-val)
            chunkplaces[key].append(place)
        else:
            if val < -chunkvals[key][0]:
                return
            else:
                chunkvals[key][0] = -val
                chunkplaces[key][0] = place
    else:
        i = bisect_left(chunkvals[key], -val)
        chunkplaces[key].insert(i, place)
        chunkvals[key].insert(i, -val)
        # print(i, val, [val for val in chunkvals[key]])

def getbestinchunk(place, key, best):
    # find best suitable match in chunk
    if key not in chunkvals:
        return 0
    for i, (cand, val) in enumerate(zip(chunkplaces[key], chunkvals[key])):
        # print("evaluating %s"%cand)
        if -val < best:
            # this is the best we have, but it's not as good as we've seen other places; abort
            return 0
        if abs(place.lat - cand.lat) <= d_lat 
            and abs(place.long - cand.long) <= d_long :
            # and cand.height > place.height: # height is given, assuming they're unique
            # suitable, return it
            return -val
    # no suitable match
    return 0
   
def getbest(place):
    # find best match in this and neighboring chunks, then pick the best
    best = 0 # always have the option to stop here
    for i in [0,1,-1]:
        for j in [0,1,-1]:
            key = getkey(place, i, j)
            ret = getbestinchunk(place, key, best)
            if ret > best:
                best = ret
    return best
    
def calculatevalue(place):
    val = place.points + getbest(place)
    recordvalue(place, val)
    return val

if __name__ == "__main__":
    n, d_lat, d_long = input().strip().split(' ')
    n, d_lat, d_long = [int(n), int(d_lat), int(d_long)]
    places = []
    if d_lat == 200000:
        giant = True
    for a0 in range(n):
        latitude, longitude, height, points = input().strip().split(' ')
        latitude, longitude, height, points = [int(latitude), int(longitude), int(height), int(points)]
        places.append(Place(latitude, longitude, height, points))
    places.sort(key=lambda p: -p.height) # compute highest first
    best = 0
    for p in places:
        ret = calculatevalue(p)
        if ret > best:
            best = ret
    print(best)

Problem solution in Java.

import java.util.*;

public class Solution1 {
    
    public static class Point {
          public int l;
          public int r;
          public int xt;
          public int yt;
          public long tot;

          public Point(int l, int r, int xt, int yt) {
              this.l = l;
              this.r = r;
              this.xt = xt;
              this.yt = yt;
              this.tot = 0;
          }
      }
    
  static final Scanner scanner = new Scanner(System.in);
  public static void main(String[] args) {
          int n = scanner.nextInt(), x = scanner.nextInt(), y = scanner.nextInt();
          HashMap<Integer, ArrayList<Point>> blocks = new HashMap<>();
          long maxPoints = Long.MIN_VALUE;
          int MAXIMUM = 200000;
          Point[] points = new Point[MAXIMUM];
          Arrays.fill(points, null);
          
          for (int i = 0; i < n; i++) {
              int l = scanner.nextInt(), r = scanner.nextInt(),xt = scanner.nextInt(), yt = scanner.nextInt();
              Point point = new Point(l, r, xt, yt);
              points[xt - 1] = point;
          }
          
          for (int i = 0; i < MAXIMUM; i++) {
              Point curPoint = points[i];
              if (points[i] != null) {
                  int blockNumber = points[i].l / x;
                  Point curMax = null;
                  Point max = null;
                  ArrayList<Point> prevBlock = getBlock(blockNumber - 1, blocks);
                  ArrayList<Point> curBlock = getBlock(blockNumber, blocks);
                  ArrayList<Point> nextBlock = getBlock(blockNumber + 1, blocks);
                  if (prevBlock != null) {
                      curMax = findMax(prevBlock, curPoint, x, y);
                      max = curMax;
                  }
                  curMax = findMax(curBlock, curPoint, x, y);
                  if (max == null) {
                      max = curMax;
                  } else {
                      if (curMax != null && curMax.tot >= max.tot) {
                          max = curMax;
                      }
                  }
                  curMax = findMax(nextBlock, curPoint, x, y);
                  if (max == null) {
                      max = curMax;
                  } else {
                      if (curMax != null && curMax.tot >= max.tot) {
                          max = curMax;
                      }
                  }
                  curPoint.tot = (max != null ? max.tot + curPoint.yt : curPoint.yt);
                  addPoint(curBlock, curPoint, 0, curBlock.size() - 1);
                  if (maxPoints < curPoint.tot) {
                      maxPoints = curPoint.tot;
                  }
              }
          }
          
          if (maxPoints == Long.MIN_VALUE) {
              System.out.println(0);
          } else {
              System.out.println(maxPoints);
          }
  }

  private static ArrayList<Point> getBlock(int blockNumber, HashMap<Integer, ArrayList<Point>> blocks) {
      if (blockNumber < 0) {
          return null;
      }
      ArrayList<Point> block = blocks.get(blockNumber);
      if (block == null) {
          block = new ArrayList<>();
          blocks.put(blockNumber, block);
      }
      return block;
  }

  private static Point findMax(ArrayList<Point> block, Point point, int ld, int rd) {
      for (int i = block.size(); i > 0; i--) {
          Point prevPoint = block.get(i - 1);
          if (Math.abs(prevPoint.r - point.r) <= rd
                  && Math.abs(prevPoint.l - point.l) <= ld) {
              return prevPoint;
          }
      }
      return null;
  }

  private static void addPoint(ArrayList<Point> block, Point point, int left, int right) {
      final long value = point.tot;
      if (block.isEmpty()) {
          block.add(point);
      } else if (right - left <= 1) {
          long leftValue = block.get(left).tot;
          long rightValue = block.get(right).tot;
          if (value < leftValue) {
              block.add(left, point);
          } else if (value >= leftValue && value <= rightValue) {
              block.add(right, point);
          } else {
              if (block.size() - 1 == right) {
                  block.add(point);
              } else {
                  int index = right + 1;
                  block.add(index, point);
              }
          }
      } else {
          int middle = (right + left) / 2;
          long middleValue = block.get(middle).tot;
          if (middleValue <= value) {
              addPoint(block, point, middle, right);
          } else {
              addPoint(block, point, left, middle);
          }
      }
  }
}

Problem solution in C++.

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 200000;
const long long INF = 1e15;

long long tree[MAXN * 4];

void makeTree() {
    for (int i = 1; i < MAXN * 4; ++i) {
        tree[i] = -INF;
    }
}
void update(int x, long long val, int u = 1, int l = 1, int r = MAXN) {
    if (l == r) {
        tree[u] = val;
        return;
    }
    int m = (l + r) / 2;
    if (x <= m) {
        update(x, val, 2 * u, l, m);
    }
    else {
        update(x, val, 2 * u + 1, m + 1, r);
    }
    tree[u] = max(tree[2 * u], tree[2 * u + 1]);
}

long long query(int x, int y, int u = 1, int l = 1, int r = MAXN) {
    if (x > r or y < l) {
        return -INF;
    }
    if (x <= l and r <= y) {
        return tree[u];
    }
    int m = (l + r) / 2;
    return max(query(x, y, 2 * u, l, m), query(x, y, 2 * u + 1, m + 1, r));
}

struct Point {
    int x, y, z, w;
    long long dp;
    bool operator < (const Point &o) const {
        return z < o.z;
    }
};
Point p[MAXN + 1];
long long DP[MAXN + 1];
int X_LIM, Y_LIM;
void merge(int l, int r) {
    int m = (l + r) / 2;

    vector<pair<int, int> > left;
    vector<pair<int, int> > right;
    for (int i = l; i <= m; ++i) {
        left.push_back({p[i].x, p[i].z});
    }       
    for (int i = m + 1; i <= r; ++i) {
        right.push_back({p[i].x, p[i].z});
    }
    sort(left.begin(), left.end());
    sort(right.begin(), right.end());

    int left_l = 0;
    int left_r = -1;
    for (auto u : right) {
        int i = u.second;
        int x = u.first;
        while (left_r + 1 < left.size() and left[left_r + 1].first - x <= X_LIM) {
            ++left_r;
            int who = left[left_r].second;
            update(p[who].y, p[who].dp);            
        }
        while (left_l < left.size() and x - left[left_l].first > X_LIM) {
            int who = left[left_l].second;
            update(p[who].y, -INF);
            ++left_l;
        }
        int yLow = max(1, p[i].y - Y_LIM);
        int yHigh = min(MAXN, p[i].y + Y_LIM);
        p[i].dp = max(p[i].dp, p[i].w + query(yLow, yHigh));
    } 
    while (left_l <= left_r) {
        int who = left[left_l].second;
        update(p[who].y, -INF);
        ++left_l;
    }
}
void solve(int l, int r) {
    if (l == r) {
        p[l].dp = max(p[l].dp, (long long)p[l].w);
        return;
    }
    int m = (l + r) / 2;
    solve(l, m);
    merge(l, r);
    solve(m + 1, r);
}
int main() {
    makeTree();
    int n;
    scanf("%d %d %d", &n, &X_LIM, &Y_LIM); 
    for (int i = 0; i < n; ++i) {
        scanf("%d %d %d %d", &p[i].x, &p[i].y, &p[i].z, &p[i].w);
        p[i].dp = -INF;
    }
    sort(p, p + n);
    for (int i = 0; i < n; ++i) {
        p[i].z = i;
    }
    solve(0, n - 1);
    long long ans = 0;
    for (int i = 0; i < n; ++i) {
        ans = max(ans, p[i].dp);
    }
    printf("%lldn", ans);
}

Problem solution in C.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct _tree
{
  int *y;
  long long *a;
  int size;
  int N;
  int *left_idx;
  int *right_idx;
} tree;
int diff(int x,int y);
long long max(long long x,long long y);
void init(int n,int *N);
long long range_sum( int i, int j);
void updatea(int i);
void build(int v);
void merge(tree *t,tree *x,tree *y);
int get_i(int*a,int num,int size);
int med(int*a,int size);
long long query(int v);
void update(int v,int idx);
int x1,x2,y1,y2,N,tl[800000],tr[800000];
long long val,*tt;
int lat[200000]={0},lon[200000]={0},poi[200000],tla[200000]={0};
tree t[800000];

int main()
{
  int n,x,y,c,i,j,max_idx=-1,a,b,C,d;
  long long max=0,dp;
  scanf("%d%d%d",&n,&x,&y);
  for(i=c=0;i<n;i++)
  {
    scanf("%d%d%d%d",&a,&b,&C,&d);
    if(d>0)
      c++;
    lat[C-1]=a;
    lon[C-1]=b;
    poi[C-1]=d;
    tla[a-1]=b;
  }
  if(!c)
  {
    printf("0");
    return 0;
  }
  tl[1]=0;
  tr[1]=199999;
  build(1);
  for(i=199999;i>=0;i--)
    if(lat[i])
    {
      if(max_idx!=-1 && diff(lat[max_idx],lat[i])<=x && diff(lon[max_idx],lon[i])<=y)
      {
        dp=max;
      }
      else
      {
        x1=lat[i]-x-1;
        x2=lat[i]+x-1;
        y1=lon[i]-y;
        y2=lon[i]+y;
        dp=query(1);
      }
      if(dp>0)
        dp+=poi[i];
      else
        dp=poi[i];
      if(dp>max){
        max=dp;
        max_idx=i;
      }
      if(dp>0){
        x1=lat[i]-1;
        y1=lon[i];
        val=dp;
        update(1,-1);
      }
    }
  printf("%lld",max);
  return 0;
}
int diff(int x,int y)
{
  return (x<y)?(y-x):(x-y);
}
long long max(long long x,long long y)
{
  return (x>y)?x:y;
}
void init(int n,int *N)
{
  (*N) = 1;
  while( (*N) < n ) (*N) *= 2;
}
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 = max(ans,tt[i]);
    if( j % 2 == 0 ) ans = max(ans,tt[j]);
  }
  return ans;
}
void updatea(int i)
{
  int j;
  for( j = i + N; j; j /= 2 ) tt[j] = max(tt[j],val);
}
void build(int v)
{
  if(tl[v]==tr[v])
  {
    t[v].size=1;
    t[v].y=(int*)malloc(t[v].size*sizeof(int));
    t[v].a=(long long*)malloc(4*t[v].size*sizeof(long long));
    memset(t[v].a,0,4*t[v].size*sizeof(long long));
    t[v].y[0]=tla[tl[v]];
    init(t[v].size,&t[v].N);
  }
  else
  {
    int tm=(tl[v]+tr[v])/2;
    tl[2*v]=tl[v];
    tl[2*v+1]=tm+1;
    tr[2*v]=tm;
    tr[2*v+1]=tr[v];
    build(v*2);
    build(v*2+1);
    merge(&t[v],&t[v*2],&t[v*2+1]);
  }
  return;
}
void merge(tree *t,tree *x,tree *y)
{
  int i=0,j=0;
  t->size=x->size+y->size;
  t->y=(int*)malloc(t->size*sizeof(int));
  t->left_idx=(int*)malloc(t->size*sizeof(int));
  t->right_idx=(int*)malloc(t->size*sizeof(int));
  t->a=(long long*)malloc(t->size*sizeof(long long)*4);
  memset(t->a,0,t->size*sizeof(long long)*4);
  init(t->size,&t->N);
  while(i<x->size || j<y->size)
  {
    if(i==x->size){
      t->y[i+j]=y->y[j];
      t->left_idx[i+j]=i-1;
      t->right_idx[i+j]=j;
      j++;
    } 
    else if(j==y->size)
    {
      t->y[i+j]=x->y[i];
      t->left_idx[i+j]=i;
      t->right_idx[i+j]=j-1;
      i++;
    }
    else if(x->y[i]<=y->y[j])
    {
      t->y[i+j]=x->y[i];
      t->left_idx[i+j]=i;
      t->right_idx[i+j]=j-1;
      i++;
    } 
    else{
      t->y[i+j]=y->y[j];
      t->left_idx[i+j]=i-1;
      t->right_idx[i+j]=j;
      j++;
    }
  }
  return;
}
int get_i(int*a,int num,int size)
{
  if(size==0)
  {
    return 0;
  }
  if(num>med(a,size))
  {
    return get_i(&a[(size+1)>>1],num,size>>1)+((size+1)>>1);
  }
  else
  {
    return get_i(a,num,(size-1)>>1);
  }
}
int med(int*a,int size)
{
  return a[(size-1)>>1];
}
long long query(int v)
{
  int i,j;
  if(tl[v]>x2 || tr[v]<x1 || !t[v].a[1])
    return 0;
  if(tl[v]>=x1 && tr[v]<=x2){
    i=get_i(t[v].y,y1,t[v].size);
    j=get_i(t[v].y,y2+1,t[v].size)-1;
    if(j<i)
      return 0;
    N=t[v].N;
    tt=t[v].a;
    return range_sum(i,j);
  }
  else if(tl[v]!=tr[v])
    return max(query(2*v),query(2*v+1));
  return 0;
}
void update(int v,int idx)
{
  if(tl[v]<=x1 && tr[v]>=x1)
  {
    if(idx==-1)
      idx=get_i(t[v].y,y1,t[v].size);
    N=t[v].N;
    tt=t[v].a;
    updatea(idx);
    if(tl[v]!=tr[v])
    {
      update(v*2,t[v].left_idx[idx]);
      update(v*2+1,t[v].right_idx[idx]);
    }
  }
  return;
}