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("%lld\n", 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;
}
0 Comments