Maximizing Mission Points
Problem Statement :
Xander Cage has a list of cities he can visit on his new top-secret mission. He represents each city as a tuple of . The values of , , and are distinct across all cities. We define a mission as a sequence of cities, , that he visits. We define the total of such a mission to be the sum of the 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 . The absolute difference in between adjacent visited cities in his mission must be at most . The absolute difference in between adjacent visited cities in his mission must be at most . Given , , and the definitions for cities, find and print the maximum possible total that Xander can earn on a mission. Input Format The first line contains three space-separated integers describing the respective values of , , and . Each line of the subsequent lines contains four space-separated integers denoting the respective , , , and for a city. Constraints Output Format Print a single integer denoting the maximum possible that Xander can earn on a mission.
Solution :
Solution in C :
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;
}
Solution in C++ :
In C++ :
//#define _GLIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define fst first
#define snd second
#define forn(i, n) for (int i = 0; i < int(n); ++i)
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef vector<ll> vll;
typedef pair<int, int> pii;
typedef vector<pii> vii;
#define sz(c) (int)(c).size()
#define ALL(c) (c).begin(), (c).end()
struct town
{
int x, y, h, p;
bool operator < (const town &o) const
{
return h < o.h;
}
};
struct segtree
{
vll vals;
int tsz;
segtree ()
{
vals.clear();
tsz = 0;
}
segtree (int n)
{
tsz = 1;
while (tsz <= n)
tsz *= 2;
vals.assign(2 * tsz, 0);
}
void put (int pos, ll what)
{
for (pos += tsz; pos > 0; pos >>= 1)
vals[pos] = max(vals[pos], what);
}
ll query (int l, int r)
{
ll ans = 0;
for (l += tsz, r += tsz; l < r; l >>= 1, r >>= 1)
{
if (l & 1)
ans = max(ans, vals[l++]);
if (r & 1)
ans = max(ans, vals[--r]);
}
return ans;
}
};
struct segtree2d
{
vvi who;
vector<segtree> data;
int tsz;
segtree2d (const vii &ps)
{
int X = 0;
const int n = sz(ps);
forn (i, n) X = max(X, ps[i].fst);
tsz = 1;
while (tsz <= X)
tsz *= 2;
data.resize(2 * tsz);
who.resize(2 * tsz);
forn (i, n)
who[ps[i].fst + tsz].pb(ps[i].snd);
for (int i = tsz; i < 2 * tsz; i++)
data[i] = segtree(sz(who[i]));
for (int i = tsz - 1; i >= 1; i--)
{
who[i].resize(sz(who[2 * i]) + sz(who[2 * i + 1]));
merge(ALL(who[2 * i]), ALL(who[2 * i + 1]), who[i].begin());
data[i] = segtree(sz(who[i]));
}
}
ll query (int v, int d, int u)
{
int rd = lower_bound(ALL(who[v]), d) - who[v].begin();
int ru = lower_bound(ALL(who[v]), u) - who[v].begin();
return data[v].query(rd, ru);
}
ll query (int l, int r, int d, int u)
{
r = min(r, tsz);
ll ans = 0;
for (l += tsz, r += tsz; l < r; l >>= 1, r >>= 1)
{
if (l & 1)
ans = max(ans, query(l++, d, u));
if (r & 1)
ans = max(ans, query(--r, d, u));
}
return ans;
}
void putnode (int v, int pos, ll what)
{
int cur = lower_bound(ALL(who[v]), pos) - who[v].begin();
assert(cur != sz(who[v]) && who[v][cur] == pos);
data[v].put(cur, what);
}
void put (int x, int y, ll what)
{
for (x += tsz; x > 0; x >>= 1)
putnode(x, y, what);
}
};
void solve (int n)
{
int mx, my;
cin >> mx >> my;
vector<town> v(n);
forn (i, n)
cin >> v[i].x >> v[i].y >> v[i].h >> v[i].p;
sort(ALL(v));
vii ps(n);
forn (i, n) ps[i] = mp(v[i].x, v[i].y);
segtree2d data(ps);
vll dp(n);
forn (i, n)
{
int cx = v[i].x, cy = v[i].y;
int lx = max(0, cx - mx), ly = max(0, cy - my);
int rx = cx + mx, ry = cy + my;
dp[i] = data.query(lx, rx + 1, ly, ry + 1) + v[i].p;
data.put(cx, cy, dp[i]);
}
ll ans = max(0LL, *max_element(ALL(dp)));
cout << ans << endl;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
int n;
while (cin >> n)
solve(n);
}
Solution in Java :
In Java :
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)); }
}
Solution in Python :
In Python3 :
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)
View More Similar Problems
Contacts
We're going to make our own Contacts application! The application must perform two types of operations: 1 . add name, where name is a string denoting a contact name. This must store name as a new contact in the application. find partial, where partial is a string denoting a partial name to search the application for. It must count the number of contacts starting partial with and print the co
View Solution →No Prefix Set
There is a given list of strings where each string contains only lowercase letters from a - j, inclusive. The set of strings is said to be a GOOD SET if no string is a prefix of another string. In this case, print GOOD SET. Otherwise, print BAD SET on the first line followed by the string being checked. Note If two strings are identical, they are prefixes of each other. Function Descriptio
View Solution →Cube Summation
You are given a 3-D Matrix in which each block contains 0 initially. The first block is defined by the coordinate (1,1,1) and the last block is defined by the coordinate (N,N,N). There are two types of queries. UPDATE x y z W updates the value of block (x,y,z) to W. QUERY x1 y1 z1 x2 y2 z2 calculates the sum of the value of blocks whose x coordinate is between x1 and x2 (inclusive), y coor
View Solution →Direct Connections
Enter-View ( EV ) is a linear, street-like country. By linear, we mean all the cities of the country are placed on a single straight line - the x -axis. Thus every city's position can be defined by a single coordinate, xi, the distance from the left borderline of the country. You can treat all cities as single points. Unfortunately, the dictator of telecommunication of EV (Mr. S. Treat Jr.) do
View Solution →Subsequence Weighting
A subsequence of a sequence is a sequence which is obtained by deleting zero or more elements from the sequence. You are given a sequence A in which every element is a pair of integers i.e A = [(a1, w1), (a2, w2),..., (aN, wN)]. For a subseqence B = [(b1, v1), (b2, v2), ...., (bM, vM)] of the given sequence : We call it increasing if for every i (1 <= i < M ) , bi < bi+1. Weight(B) =
View Solution →Kindergarten Adventures
Meera teaches a class of n students, and every day in her classroom is an adventure. Today is drawing day! The students are sitting around a round table, and they are numbered from 1 to n in the clockwise direction. This means that the students are numbered 1, 2, 3, . . . , n-1, n, and students 1 and n are sitting next to each other. After letting the students draw for a certain period of ti
View Solution →