HackerRank Maximizing Mission Points problem solution

YASH PAL,

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.

Xander Cage has a list of cities he can visit on his new top-secret mission. He represents each city as a tuple of (latitude,longitute,height,points). The values of latitude, longitude and height are distinct across all cities.

We define a mission as a sequence of cities, c1,c2,c3,……ck, that he visits. We define the total points of such a mission to be the sum of the points of all the cities in his mission list.

Being eccentric, he abides by the following rules on any mission:

  • He can choose the number of cities he will visit (if any).
  • He can start the mission from any city.
  • He visits cities in order of strictly increasing height.
  • The absolute difference in latitude between adjacent visited cities in his mission must be at most dlat.
  • The absolute difference in longitude between adjacent visited cities in his mission must be at most dlong.

HackerRank Maximizing Mission Points problem solution

HackerRank Maximizing Mission Points 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)

Maximizing Mission Points 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;
}

Algorithms coding problems solutions

Leave a Reply

Your email address will not be published. Required fields are marked *