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
The Strange Function
One of the most important skills a programmer needs to learn early on is the ability to pose a problem in an abstract way. This skill is important not just for researchers but also in applied fields like software engineering and web development. You are able to solve most of a problem, except for one last subproblem, which you have posed in an abstract way as follows: Given an array consisting
View Solution →Self-Driving Bus
Treeland is a country with n cities and n - 1 roads. There is exactly one path between any two cities. The ruler of Treeland wants to implement a self-driving bus system and asks tree-loving Alex to plan the bus routes. Alex decides that each route must contain a subset of connected cities; a subset of cities is connected if the following two conditions are true: There is a path between ever
View Solution →Unique Colors
You are given an unrooted tree of n nodes numbered from 1 to n . Each node i has a color, ci. Let d( i , j ) be the number of different colors in the path between node i and node j. For each node i, calculate the value of sum, defined as follows: Your task is to print the value of sumi for each node 1 <= i <= n. Input Format The first line contains a single integer, n, denoti
View Solution →Fibonacci Numbers Tree
Shashank loves trees and math. He has a rooted tree, T , consisting of N nodes uniquely labeled with integers in the inclusive range [1 , N ]. The node labeled as 1 is the root node of tree , and each node in is associated with some positive integer value (all values are initially ). Let's define Fk as the Kth Fibonacci number. Shashank wants to perform 22 types of operations over his tree, T
View Solution →Pair Sums
Given an array, we define its value to be the value obtained by following these instructions: Write down all pairs of numbers from this array. Compute the product of each pair. Find the sum of all the products. For example, for a given array, for a given array [7,2 ,-1 ,2 ] Note that ( 7 , 2 ) is listed twice, one for each occurrence of 2. Given an array of integers, find the largest v
View Solution →Lazy White Falcon
White Falcon just solved the data structure problem below using heavy-light decomposition. Can you help her find a new solution that doesn't require implementing any fancy techniques? There are 2 types of query operations that can be performed on a tree: 1 u x: Assign x as the value of node u. 2 u v: Print the sum of the node values in the unique path from node u to node v. Given a tree wi
View Solution →