HackerRank Maximizing Mission Points Solution

In this post, we will solve HackerRank Maximizing Mission Points Problem Solution.

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, longitude, 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 d1 at.
The absolute difference in longitude between adjacent visited cities in his mission must be at most d1 ong.

Given d_lat, d_long, and the definitions for n cities, find and print the maximum possible total points that Xander can earn on a mission.
Input Format
The first line contains three space-separated integers describing the respective values of n
d_lat, and d_long.
Each line i of the n subsequent lines contains four space-separated integers denoting the respective latitude, longitude, height, and points for a city

Output Format

Print a single integer denoting the maximum possible points that Xander can earn on a mission.

Sample Input 0

Sample Output 0

Explanation 0
Xander can start at city 1, then go to city 2, and then go to city 3 for a maximum value of
total points=3+-1+3=5

Note that he cannot go directly from city 1 to city 3 as that would violate his rules that the absolute difference in latitude between adjacent visited cities be < d_lat and the absolute difference in longitude between adjacent visited cities be <d_long. Because d_lat= 1 and d_long = 1, he cannot directly travel between those cities.

HackerRank Maximizing Mission Points Problem Solution

Maximizing Mission Points Java Solution


import java.io.ByteArrayInputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.util.InputMismatchException;

public class D {
	InputStream is;
	PrintWriter out;
	String INPUT = "";
	
	void solve()
	{
		int n = ni();
		int x = ni(), y = ni();
		int[][] co = new int[n][];
		for(int i = 0;i < n;i++){
			co[i] = new int[]{ni(), ni(), ni(), ni()};
		}
//		Arrays.sort(co, new Comparator<int[]>() {
//			public int compare(int[] a, int[] b) {
//				return a[2] - b[2];
//			}
//		});
		StaticRangeTreeRMQ2 st = new StaticRangeTreeRMQ2(co, 200005);
//		for(int i = 0;i < n;i++){
//			st.update(co[i][0], co[i][1], Long.MAX_VALUE / 2);
//		}
		mergesort(co, 0, n);
		long max = Long.MIN_VALUE;
		long[] dp = new long[n];
		for(int i = 0;i < n;i++){
			long min = -st.min(co[i][0]-x, co[i][0]+x+1, co[i][1]-y, co[i][1]+y+1);
			long val = co[i][3] + Math.max(min, 0);
			dp[i] = val;
			st.update(co[i][0], co[i][1], -dp[i]);
			max = Math.max(max, dp[i]);
		}
		out.println(max);
	}
	
	private static int[][] stemp = new int[200005][];
	
	public static void mergesort(int[][] a, int s, int e)
	{
		if(e - s <= 1)return;
		int h = s+e>>1;
		mergesort(a, s, h);
		mergesort(a, h, e);
		int p = 0;
		int i= s, j = h;
		for(;i < h && j < e;)stemp[p++] = a[i][2] < a[j][2] ? a[i++] : a[j++];
		while(i < h)stemp[p++] = a[i++];
		while(j < e)stemp[p++] = a[j++];
		System.arraycopy(stemp, 0, a, s, e-s);
	}
	
	public static void mergesort0(int[][] a, int s, int e)
	{
		if(e - s <= 1)return;
		int h = s+e>>1;
		mergesort0(a, s, h);
		mergesort0(a, h, e);
		int p = 0;
		int i= s, j = h;
		for(;i < h && j < e;)stemp[p++] = a[i][0] < a[j][0] || a[i][0] == a[j][0] && a[i][1] < a[j][1] ? a[i++] : a[j++];
		while(i < h)stemp[p++] = a[i++];
		while(j < e)stemp[p++] = a[j++];
		System.arraycopy(stemp, 0, a, s, e-s);
	}
	
	public static class StaticRangeTreeRMQ2 {
		public int M, H, N;
		public SegmentTreeRMQL[] st;
		public int[][] maps;
		public long[][] vals;
		public int[] count;
		public long I = Long.MAX_VALUE;
		
		public StaticRangeTreeRMQ2(int[][] co, int n)
		{
			N = n;
			M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
			H = M>>>1;
			
			mergesort0(co, 0, co.length);
//			Arrays.sort(co, new Comparator<int[]>() { // x asc
//				public int compare(int[] a, int[] b) {
//					if(a[0] != b[0])return a[0] - b[0];
//					return a[1] - b[1];
//				}
//			});
			maps = new int[M][];
			vals = new long[M][];
			st = new SegmentTreeRMQL[M];
			count = new int[M];
			for(int i = 0;i < co.length;i++){
				count[H+co[i][0]]++;
			}
			int off = 0;
			for(int i = 0;i < n;i++){
				maps[H+i] = new int[count[H+i]];
				for(int j = 0;j < count[H+i];j++,off++){
					maps[H+i][j] = co[off][1];
				}
				st[H+i] = new SegmentTreeRMQL(count[H+i]);
			}
			
			for(int i = H-1;i >= 1;i--){
				if(maps[2*i+1] == null){
					maps[i] = maps[2*i];
					count[i] = count[2*i];
				}else{
					count[i] = count[2*i] + count[2*i+1];
					maps[i] = new int[count[i]];
					int l = 0;
					for(int j = 0, k = 0;j < count[2*i] || k < count[2*i+1];l++){
						if(j == count[2*i]){
							maps[i][l] = maps[2*i+1][k++];
						}else if(k == count[2*i+1]){
							maps[i][l] = maps[2*i][j++];
						}else if(maps[2*i][j] < maps[2*i+1][k]){
							maps[i][l] = maps[2*i][j++];
						}else if(maps[2*i][j] > maps[2*i+1][k]){
							maps[i][l] = maps[2*i+1][k++];
						}else{
							maps[i][l] = maps[2*i][j++];
							k++;
						}
					}
					if(l != count[i]){ // uniq
						count[i] = l;
						maps[i] = Arrays.copyOf(maps[i], l);
					}
				}
				if(count[i] <= 25){ // 10% faster
					vals[i] = new long[count[i]];
					Arrays.fill(vals[i], Long.MAX_VALUE / 2);
				}else{
					st[i] = new SegmentTreeRMQL(count[i]);
				}
			}
		}
		
		public void update(int x, int y, long v)
		{
			outer:
			for(int pos = H+x;pos >= 1;pos>>>=1){
				if(st[pos] != null){
					int ind = Arrays.binarySearch(maps[pos], y);
					if(ind >= 0){
						st[pos].update(ind, v);
						continue;
					}
				}else{
					for(int i = 0;i < count[pos];i++){
						if(maps[pos][i] == y){
							vals[pos][i] = v;
							continue outer;
						}
					}
				}
				throw new RuntimeException(String.format("access to non-existing point : (%d,%d):%d", x, y, v));
			}
		}
		
		public long min(int xl, int xr, int yl, int yr) { return min(xl, xr, yl, yr, 0, H, 1); }
		
		public long min(int xl, int xr, int yl, int yr, int cl, int cr, int cur)
		{
			if(xl <= cl && cr <= xr){
				if(st[cur] != null){
					int indl = Arrays.binarySearch(maps[cur], yl);
					int indr = Arrays.binarySearch(maps[cur], yr);
					if(indl < 0)indl = -indl - 1;
					if(indr < 0)indr = -indr - 1;
					return st[cur].minx(indl, indr);
				}else{
					long min = I;
					for(int i = 0;i < count[cur] && maps[cur][i] < yr;i++){
						if(maps[cur][i] >= yl && vals[cur][i] < min) min = vals[cur][i];
					}
					return min;
				}
			}else{
				int mid = cl+cr>>>1;
				long ret = I;
				if(cl < xr && xl < mid)ret = Math.min(ret, min(xl, xr, yl, yr, cl, mid, 2*cur));
				if(mid < xr && xl < cr)ret = Math.min(ret, min(xl, xr, yl, yr, mid, cr, 2*cur+1));
				return ret;
			}
		}
	}
	
	public static class SegmentTreeRMQL {
		public int M, H, N;
		public long[] st;
		
		public SegmentTreeRMQL(int n)
		{
			N = n;
			M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
			H = M>>>1;
			st = new long[M];
			Arrays.fill(st, 0, M, Long.MAX_VALUE/2);
		}
		
		public SegmentTreeRMQL(long[] a)
		{
			N = a.length;
			M = Integer.highestOneBit(Math.max(N-1, 1))<<2;
			H = M>>>1;
			st = new long[M];
			for(int i = 0;i < N;i++){
				st[H+i] = a[i];
			}
			Arrays.fill(st, H+N, M, Long.MAX_VALUE);
			for(int i = H-1;i >= 1;i--)propagate(i);
		}
		
		public void update(int pos, long x)
		{
			st[H+pos] = x;
			for(int i = (H+pos)>>>1;i >= 1;i >>>= 1)propagate(i);
		}
		
		private void propagate(int i)
		{
			st[i] = Math.min(st[2*i], st[2*i+1]);
		}
		
		public long minx(int l, int r){
			long min = Long.MAX_VALUE;
			if(l >= r)return min;
			while(l != 0){
				int f = l&-l;
				if(l+f > r)break;
				long v = st[(H+l)/f];
				if(v < min)min = v;
				l += f;
			}
			
			while(l < r){
				int f = r&-r;
				long v = st[(H+r)/f-1];
				if(v < min)min = v;
				r -= f;
			}
			return min;
		}
		
		public long min(int l, int r){ return l >= r ? 0 : min(l, r, 0, H, 1);}
		
		private long min(int l, int r, int cl, int cr, int cur)
		{
			if(l <= cl && cr <= r){
				return st[cur];
			}else{
				int mid = cl+cr>>>1;
				long ret = Long.MAX_VALUE;
				if(cl < r && l < mid){
					ret = Math.min(ret, min(l, r, cl, mid, 2*cur));
				}
				if(mid < r && l < cr){
					ret = Math.min(ret, min(l, r, mid, cr, 2*cur+1));
				}
				return ret;
			}
		}
		
		public int firstle(int l, long v) {
			int cur = H+l;
			while(true){
				if(st[cur] <= v){
					if(cur < H){
						cur = 2*cur;
					}else{
						return cur-H;
					}
				}else{
					cur++;
					if((cur&cur-1) == 0)return -1;
					if((cur&1)==0)cur>>>=1;
				}
			}
		}
		
		public int lastle(int l, long v) {
			int cur = H+l;
			while(true){
				if(st[cur] <= v){
					if(cur < H){
						cur = 2*cur+1;
					}else{
						return cur-H;
					}
				}else{
					if((cur&cur-1) == 0)return -1;
					cur--;
					if((cur&1)==1)cur>>>=1;
				}
			}
		}
	}

	
	void run() throws Exception
	{
		is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes());
		out = new PrintWriter(System.out);
		
		long s = System.currentTimeMillis();
		solve();
		out.flush();
		if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms");
	}
	
	public static void main(String[] args) throws Exception { new D().run(); }
	
	private byte[] inbuf = new byte[1024];
	public int lenbuf = 0, ptrbuf = 0;
	
	private int readByte()
	{
		if(lenbuf == -1)throw new InputMismatchException();
		if(ptrbuf >= lenbuf){
			ptrbuf = 0;
			try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); }
			if(lenbuf <= 0)return -1;
		}
		return inbuf[ptrbuf++];
	}
	
	private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); }
	private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; }
	
	private double nd() { return Double.parseDouble(ns()); }
	private char nc() { return (char)skip(); }
	
	private String ns()
	{
		int b = skip();
		StringBuilder sb = new StringBuilder();
		while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ')
			sb.appendCodePoint(b);
			b = readByte();
		}
		return sb.toString();
	}
	
	private char[] ns(int n)
	{
		char[] buf = new char[n];
		int b = skip(), p = 0;
		while(p < n && !(isSpaceChar(b))){
			buf[p++] = (char)b;
			b = readByte();
		}
		return n == p ? buf : Arrays.copyOf(buf, p);
	}
	
	private char[][] nm(int n, int m)
	{
		char[][] map = new char[n][];
		for(int i = 0;i < n;i++)map[i] = ns(m);
		return map;
	}
	
	private int[] na(int n)
	{
		int[] a = new int[n];
		for(int i = 0;i < n;i++)a[i] = ni();
		return a;
	}
	
	private int ni()
	{
		int num = 0, b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private long nl()
	{
		long num = 0;
		int b;
		boolean minus = false;
		while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-'));
		if(b == '-'){
			minus = true;
			b = readByte();
		}
		
		while(true){
			if(b >= '0' && b <= '9'){
				num = num * 10 + (b - '0');
			}else{
				return minus ? -num : num;
			}
			b = readByte();
		}
	}
	
	private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); }
}

Maximizing Mission Points C++ Solution

//start of jonathanirvings' template v3.0.3 (BETA)

#include <bits/stdc++.h>
using namespace std;

typedef long long LL;
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
typedef pair<string,string> pss;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<pii> vii;
typedef vector<LL> vl;
typedef vector<vl> vvl;

double EPS = 1e-9;
int INF = 1000000005;
long long INFF = 1000000000000000005LL;
double PI = acos(-1);
int dirx[8] = {-1,0,0,1,-1,-1,1,1};
int diry[8] = {0,1,-1,0,-1,1,-1,1};

#ifdef TESTING
  #define DEBUG fprintf(stderr,"====TESTING====\n")
  #define VALUE(x) cerr << "The value of " << #x << " is " << x << endl
  #define debug(...) fprintf(stderr, __VA_ARGS__)
#else
  #define DEBUG 
  #define VALUE(x)
  #define debug(...)
#endif

#define FOR(a,b,c) for (int (a)=(b);(a)<(c);++(a))
#define FORN(a,b,c) for (int (a)=(b);(a)<=(c);++(a))
#define FORD(a,b,c) for (int (a)=(b);(a)>=(c);--(a))
#define FORSQ(a,b,c) for (int (a)=(b);(a)*(a)<=(c);++(a))
#define FORC(a,b,c) for (char (a)=(b);(a)<=(c);++(a))
#define FOREACH(a,b) for (auto &(a) : (b))
#define REP(i,n) FOR(i,0,n)
#define REPN(i,n) FORN(i,1,n)
#define MAX(a,b) a = max(a,b)
#define MIN(a,b) a = min(a,b)
#define SQR(x) ((LL)(x) * (x))
#define RESET(a,b) memset(a,b,sizeof(a))
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define ALL(v) v.begin(),v.end()
#define ALLA(arr,sz) arr,arr+sz
#define SIZE(v) (int)v.size()
#define SORT(v) sort(ALL(v))
#define REVERSE(v) reverse(ALL(v))
#define SORTA(arr,sz) sort(ALLA(arr,sz))
#define REVERSEA(arr,sz) reverse(ALLA(arr,sz))
#define PERMUTE next_permutation
#define TC(t) while(t--)

inline string IntToString(LL a){
  char x[100];
  sprintf(x,"%lld",a); string s = x;
  return s;
}

inline LL StringToInt(string a){
  char x[100]; LL res;
  strcpy(x,a.c_str()); sscanf(x,"%lld",&res);
  return res;
}

inline string GetString(void){
  char x[1000005];
  scanf("%s",x); string s = x;
  return s;
}

inline string uppercase(string s){
  int n = SIZE(s); 
  REP(i,n) if (s[i] >= 'a' && s[i] <= 'z') s[i] = s[i] - 'a' + 'A';
  return s;
}

inline string lowercase(string s){
  int n = SIZE(s); 
  REP(i,n) if (s[i] >= 'A' && s[i] <= 'Z') s[i] = s[i] - 'A' + 'a';
  return s;
}

inline void OPEN (string s) {
  #ifndef TESTING
  freopen ((s + ".in").c_str (), "r", stdin);
  freopen ((s + ".out").c_str (), "w", stdout);
  #endif
}

//end of jonathanirvings' template v3.0.3 (BETA)

int n,x,y;
pair<pii,pii> data[200005];
pii P[200005];
int p[200005];

vector<int> pos[800005];
vector<LL> val[800005];
int sz[800005];

void preassign(int ix,int L,int R,int x)
{
  ++sz[ix];
  if (L == R) return;
  int M = (L + R) >> 1;
  if (x <= M) preassign(ix*2+1,L,M,x);
  else preassign(ix*2+2,M+1,R,x);
}

void assign(int ix,int L,int R,int x,int y)
{
  // pos[ix].pb(y);
  --sz[ix];
  pos[ix][sz[ix]] = y;
  if (L == R) return;
  int M = (L + R) >> 1;
  if (x <= M) assign(ix*2+1,L,M,x,y);
  else assign(ix*2+2,M+1,R,x,y);
}

inline void update1D(int ix1,int ix2,int L,int R,int y,LL v)
{
  // debug("<<<<<<%d %d %d %d %d %lld\n",ix1,ix2,L,R,y,v);
  MAX(val[ix1][ix2],v);
  if (L == R) return;
  int M = (L + R) >> 1;
  if (y <= pos[ix1][M]) update1D(ix1,ix2*2+1,L,M,y,v);
  else update1D(ix1,ix2*2+2,M+1,R,y,v);
}

inline void update2D(int ix,int L,int R,int x,int y,LL v)
{
  // debug("<<%d %d %d %d %d %lld\n",ix,L,R,x,y,v);
  // int temp = lower_bound(ALL(pos[ix]),y) - pos[ix].begin();
  update1D(ix,0,0,SIZE(pos[ix])-1,y,v);
  if (L == R) return;
  int M = (L + R) >> 1;
  if (x <= M) update2D(ix*2+1,L,M,x,y,v);
  else update2D(ix*2+2,M+1,R,x,y,v);
}

inline LL query1D(int ix1,int ix2,int L,int R,int ya,int yb)
{
  // debug(">>>>>%d %d %d %d %d %d\n",ix1,ix2,L,R,ya,yb);
  if (ya <= pos[ix1][L] && pos[ix1][R] <= yb) return val[ix1][ix2];
  if (pos[ix1][R] < ya || yb < pos[ix1][L]) return 0;
  int M = (L + R) >> 1;
  return max(query1D(ix1,ix2*2+1,L,M,ya,yb),query1D(ix1,ix2*2+2,M+1,R,ya,yb));
}

inline LL query2D(int ix,int L,int R,int xa,int xb,int ya,int yb)
{
  // debug(">>%d %d %d %d %d %d %d\n",ix,L,R,xa,xb,ya,yb);
  if (xa <= L && R <= xb)
  {
    if (pos[ix].empty()) return 0;
    // if (tempa > tempb) return 0;
    return query1D(ix,0,0,SIZE(pos[ix])-1,ya,yb);
  }
  if (R < xa || xb < L) return 0;
  int M = (L + R) >> 1;
  return max(query2D(ix*2+1,L,M,xa,xb,ya,yb),query2D(ix*2+2,M+1,R,xa,xb,ya,yb));
}

bool f(pair<pii,pii> a, pair<pii,pii> b)
{
  return a.se.se > b.se.se;
}

int main()
{
  scanf("%d %d %d",&n,&x,&y);
  REP(i,n)
  {
    scanf("%d %d %d %d",&data[i].se.fi,&data[i].se.se,&data[i].fi.fi,&data[i].fi.se);
  }
  sort(ALLA(data,n),f);
  REP(i,n) preassign(0,0,200000,data[i].se.fi);
  FORN(i,0,800000)
  {
    // SORT(pos[i]);
    pos[i].resize(sz[i]);
    val[i].resize(sz[i]*4);
  }
  REP(i,n) assign(0,0,200000,data[i].se.fi,data[i].se.se);
  SORTA(data,n);
  REP(i,n)
  {
    P[i] = data[i].se;
    p[i] = data[i].fi.se;
  }
  // REP(i,n) assign(0,0,200000,P[i].fi,P[i].se);
  // FORN(i,0,800000)
  // {
  //   // SORT(pos[i]);
  //   val[i].resize(SIZE(pos[i])*4);
  // }
  LL risan = 0;
  // return 0;
  FORD(i,n-1,0)
  {
    // VALUE(i);
    int xa = max(0,P[i].fi-x);
    int xb = min(200000,P[i].fi+x);
    int ya = max(0,P[i].se-y);
    int yb = min(200000,P[i].se+y);
    LL temp = query2D(0,0,200000,xa,xb,ya,yb);
    // VALUE(temp);
    temp += p[i];
    MAX(risan,temp);
    update2D(0,0,200000,P[i].fi,P[i].se,temp);
  }
  printf("%lld\n",risan);
  return 0;
}

c C# C++ HackerRank Solutions java javascript python C cpp CSharp Hackerrank Solutions java javascript python

Maximizing Mission Points Java Solution

Maximizing Mission Points C++ Solution

Leave a Reply