 # DRGNDEN - Editorial

Author & Editorialist: Cisco Ortega

Tester : Encho Mishinev

Medium

# PREREQUISITES:

Data Structures on Trees, Stack, Greedy

# PROBLEM:

A “mountain range” can be modeled by a polyline in a 2D plane that passes through N points p_1 = (1,h_1), p_2 = (2, h_2), \ldots, p_N = (N, h_N), in this order, where h_i is a positive integer for each valid i. This polyline divides the set of points \{(x, z): 1 \le x \le N\} into two regions. The “solid” part of the mountain range is the “bottom” region, i.e. the region that contains the x-axis.

Each point p_i is initially assigned the value a_i. Chef can glide from point to point, and the total value of a journey is just the sum of the values of all points visited. However, there are some restrictions,

• Chef can only glide from a higher den to a strictly lower den, i.e. if he glides from a den at p_i to a den at p_j, then h_i \gt h_j must hold.
• Chef can only glide in one direction and never look back, i.e. if he starts travelling in the direction of decreasing x, he must keep travelling in that direction until the end of the journey, and if he starts travelling in the direction of increasing x, he must keep travelling in that direction until the end of the journey too.
• Chef cannot travel through solid mountain, i.e. he can only glide from a den at p_i to a den at p_j if the line segment connecting the points p_i and p_j does not intersect the “solid” part of the mountain range. However, it may touch the border of the mountain range, i.e. the polyline itself.

You must process Q queries. There are two types of queries:

• 1 b k: The value of point p_b should be changed to k instead for all future queries.
• 2 b c: Find the maximum possible value of all journeys that start at p_b and end at p_c

# QUICK EXPLANATION:

Suppose that b \leq c.

1. It is always optimal to visit as many points as possible on the journey.
2. Suppose we want to plan a journey from p_b \to \dots \to p_c. Let i be the greatest integer less than c such that h_i > h_c, i.e. p_i is the point nearest p_c to its left that is higher up than it. Then, it is always optimal to visit p_i, i.e. the journey goes p_b \to \dots \to p_i \to p_c. Call i the “optimal previous” of c.
3. For the journey p_b \to \dots \to p_c, we should start at c, then visit its optimal previous, then visit its optimal previous, and so on, until we arrive at b.
4. For each 1 \leq c \leq N, connect c with its optimal previous. This creates a rooted forest.
5. If b is not an ancestor of c, then the journey is impossible. Otherwise, the answer is the sum of the a_i of all nodes on the path from c to b.
6. Point updates and path sum queries can be handled by flattening the tree, rudimentary heavy-light decomposition, etc.

For when b > c, create another rooted forest that represents motion in the other direction.

# EXPLANATION:

To simplify things, let’s assume that b \leq c for all queries of the second type. So, Chef is always traveling with increasing x-coordinates.

Since all values are positive, a journey from b to c can always be improved if we can squeeze in another point to be visited. So, let’s try to determine a point that we for sure will visit on the way from p_b\to \dots \to p_c.

Let i be the greatest integer less than c such that i < c and h_i > h_c, i.e. p_i is the point nearest p_c to its left that is higher up than it. Call i the “optimal previous” of c. Since no other point between i and c is higher than h_c, we know it is always possible to travel from p_i to p_c.

We call i the optimal previous because we can show that it is always optimal to include p_i in Chef’s journey. Consider any optimal journey from p_b to p_c that does not include p_i. We can then improve the score of that journey by first passing through p_i and then ending on p_c.

This reduces the problem then to finding the maximum possible value of all journeys that start at p_b and end at p_i. But then, by the same argument, we know we have to pass through the optimal previous of i, and so on.

So, we now can build the journey with the following algorithm. Start at c, then visit its optimal previous, then visit its optimal previous, and so on, until we end up at b. If we don’t end up at b, then the journey is impossible.

Each point has a unique optimal previous, if it has one at all. Determining the optimal previous of all points can be done in \mathcal{O}(N) using a stack.

If we connect each point to its optimal previous, we end up defining a rooted tree (or rather, a forest). Checking if it is possible to get from p_b to p_c is a matter of checking if b is an ancestor of c in its tree. Then, the value of the maximum possible journey is simply the sum of the values of all nodes on the path from b to c.

What about when b > c? Simple—just create two different forests, one for left-to-right motion, and one for right-to-left motion. Maintain updates on both, and use the appropriate one when querying.

Handling point updates and path sum queries can easily be maintained using your favorite tree data structure—you could flatten the tree, or use Heavy Light, or whatever you want.

The runtime is thus \mathcal{O}(\log n) (with Tree Flattening) or \mathcal{O}(\log^2 N) (with Heavy-Light Decomposition) per query. We are okay with letting \mathcal{O}(\log^2 N) solutions pass if they are optimized (both the setter’s Heavy-Light and Tree Flattening solution finish in 0.20s).

I will briefly discuss one method for solving this, which is by flattening the tree, since it is the simpler one of the two.

For our problem, we may get a forest, so create a dummy node 0 that is root of all our trees.

Now, we perform a DFS tree traversal starting from the root. We maintain a global timer which starts at 0, and maintain two arrays entr and ext, corresponding to the entry and exit time of each node.

• When you enter a node u, record entr[u]=timer; then increment timer += 1;
• When you exit a node u, record ext[u]=timer then increment timer += 1;

Our tree has n+1 vertices, so each of the integers from 0 to 2n+1 is associated with a particular node, on either entry or exit. You can imagine tracing the tree traversal with a continuous line, then unwrapping and flattening it out (seriously, draw a picture, it will help).

Now, note that the entr and ext of all nodes in the subtree of some u must appear between entr[u] and ext[u], which can be more easily visualized if you have a picture of the traced path.

How can we check if b is an ancestor of c? That’s equivalent to c being a descendant of b, i.e. c exists in the subtree of b. So, we just check if entr[b] <= entr[c] and ext[c] <= ext[b] (actually it doesn’t matter if we use entr[c] or ext[c] for each check).

How about the path queries? We create an array flat, then set flat[entr[u]] = a[u] and flat[ext[u]] = -a[u]. If b is an ancestor c, then the sum of all nodes on the path from b to c is just the sum of flat[entr[u]] until flat[entr[c]]. Why?

This range contains all the nodes that we visit before c. If it is on the path directly between b and c, then only its entr is in the range and not its ext, because we only exit each of those nodes after we are done with all its descendants (and c is one of them). However, if a node is not on that path, we must have entered and then exited it before arriving at c. That means both its entr and exit are in the given range, and they will cancel each other out when summed.

Here is another way to visualize this. Consider the stack of recursive calls for our DFS. When you enter a node u, push u onto the stack. When you exit a node u, pop u from the stack. When you reach c, the only nodes on the stack are those on the path from b to c.

Now, instead instead of pushing u onto stack, push a[u]. And, instead of popping u from the stack, push -a[u]. Then, we see that the sum of the values of the nodes on the path from b to c is equal to the sum of some consecutive range of “recursive calls”. This range is what entr[b] and entr[c] keeps track of.

When doing a point update on u, make sure to update both flat[entr[u]] and flat[ext[u]].

We can maintain point updates and range sum queries with either a segment tree or a Fenwick tree, giving \mathcal{O}(\log n) time per query.

Question: Suppose you should start at b but you can choose whatever ending point c that you want. How can answer those queries quickly?

Question: What do you do for path queries from u to v where one is not the ancestor of another?

Question: Why does this trick not work with range max or range min queries?

# SOLUTIONS:

Setter's Tree Flattening Solution
#include <iostream>
#include <stack>
#include <vector>
#define M (L+R)/2
using namespace std;
typedef long long LL;
struct SegmentTree //0-indexed point add update, range sum query
{
int n;
vector<LL> a;
void pull(int node){ a[node] = a[node<<1]+a[(node<<1)+1]; }
void build(vector<LL>& arr, int L, int R, int node)
{
if(L==R)
{
a[node] = arr[L];
return;
}
build(arr,L,M,node<<1);
build(arr,M+1,R,(node<<1)+1);
pull(node);
}
void update(int L, int R, int pt, LL val, int node)
{
if(L==R)
{
a[node] = val;
return;
}
if(pt <= M)
update(L,M,pt,val,node<<1);
else
update(M+1,R,pt,val,(node<<1)+1);
pull(node);
}
void update(int pt, LL val){ update(0,n-1,pt,val,1); }
LL query(int L, int R, int left, int right, int node)
{
if(L > R || R < left || L > right)
return 0;
if(left <= L && R <= right)
return a[node];
else
return query(L,M,left,right,node<<1)+query(M+1,R,left,right,(node<<1)+1);
}
LL query(int left, int right){ return query(0,n-1,left,right,1); }
SegmentTree(vector<LL>& arr)
{
n = arr.size();
a = vector<LL>(4*(arr.size()+1));
build(arr,0,n-1,1);
}
SegmentTree(){}
};
struct FlattenedTree
{
int root, n;
vector<int> entr, ext;

int timer = 0;
void dfs(int u, int prev)
{
entr[u] = timer++;
if(v != prev)
dfs(v,u);
ext[u] = timer++;
}
SegmentTree segmentTree;
FlattenedTree(vector<int>& p, vector<int>& s)
{
n = p.size();

for(int u = 0; u < n; u++)
if(p[u]!=-1)
{
}
else
root = u;

entr = vector<int>(n);
ext = vector<int>(n);

dfs(root, -1);

vector<LL> flattenedTree(2*n);
for(int u = 0; u < n; u++)
{
flattenedTree[entr[u]] = s[u];
flattenedTree[ext[u]] = -s[u];
}
segmentTree = SegmentTree(flattenedTree);
}
void update(int pt, LL val)
{
segmentTree.update(entr[pt],val);
segmentTree.update(ext[pt],-val);
}
bool is_ancestor(int u, int v) //is u an ancestor of v ?
{
return entr[u] <= entr[v] && ext[v] <= ext[u];
}
LL query(int u, int v)
{
if(!is_ancestor(u,v))
return -1;
else
return segmentTree.query(entr[u],entr[v]);
}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

int n, q; cin >> n >> q;
vector<int> h(n+1,0), s(n+1,0);
//0 is a dummy point, to be the "root" of the tree
for(int i = 1; i <= n; i++)
cin >> h[i];
for(int i = 1; i <= n; i++)
cin >> s[i];

stack<int> travelToRight, travelToLeft;
vector<int> pRight(n+1), pLeft(n+1);
pRight = pLeft = -1;

auto iterate = [](int i, stack<int>& traveled, vector<int>& p, vector<int>& h)
{
while(!traveled.empty() && !(h[traveled.top()] > h[i]))
traveled.pop();
if(traveled.empty())
p[i] = 0;
else
p[i] = traveled.top();
traveled.push(i);
};
for(int i = 1; i <= n; i++)
iterate(i,travelToRight,pRight,h);
for(int i = n; i >= 1; i--)
iterate(i,travelToLeft,pLeft,h);

FlattenedTree flat_right(pRight,s), flat_left(pLeft,s);
while(q--)
{
int t, u, v; cin >> t >> u >> v;
if(t==1)
{
flat_right.update(u,v);
flat_left.update(u,v);
}
else
{
if(u <= v)
cout<<flat_right.query(u,v)<<'\n';
else
cout<<flat_left.query(u,v)<<'\n';
}
}
cout<<flush;
}

Setter's Heavy-Light Solution
#include <iostream>
#include <stack>
#include <vector>
#define M (L+R)/2
using namespace std;
typedef long long LL;
struct SegmentTree //0-indexed point add update, range sum query
{
int n;
vector<LL> a;
void pull(int node){ a[node] = a[node<<1]+a[(node<<1)+1]; }
void build(vector<LL>& arr, int L, int R, int node)
{
if(L==R)
{
a[node] = arr[L];
return;
}
build(arr,L,M,node<<1);
build(arr,M+1,R,(node<<1)+1);
pull(node);
}
void update(int L, int R, int pt, LL val, int node)
{
if(L==R)
{
a[node] = val;
return;
}
if(pt <= M)
update(L,M,pt,val,node<<1);
else
update(M+1,R,pt,val,(node<<1)+1);
pull(node);
}
void update(int pt, LL val){ update(0,n-1,pt,val,1); }
LL query(int L, int R, int left, int right, int node)
{
if(L > R || R < left || L > right)
return 0;
if(left <= L && R <= right)
return a[node];
else
return query(L,M,left,right,node<<1)+query(M+1,R,left,right,(node<<1)+1);
}
LL query(int left, int right){ return query(0,n-1,left,right,1); }
SegmentTree(vector<LL>& arr)
{
n = arr.size();
a = vector<LL>(4*(arr.size()+1));
build(arr,0,n-1,1);
}
SegmentTree(){}
};
struct HeavyLight
{
int root, n;
vector<int> p, size, depth, disc, head;
void dfs_heavy(int u, int p, int d=0)
{
size[u] = 1;
depth[u] = d;

int heavy_child = -1;
for(int i = 0; i < adj[u].size(); i++)
{
if(v != p)
{
dfs_heavy(v,u,d+1);
size[u] += size[v];
heavy_child = i;
}
}
if(heavy_child != -1)
}
int timer = 0;
void dfs_disc(int u, int p)
{

disc[u] = timer++;
for(int i = 0; i < adj[u].size(); i++)
{
if(v != p)
{
if(i==0)
else
dfs_disc(v,u);
}
}
}
bool is_ancestor(int u, int v) //is u an ancestor of v ?
{
if(u==root) return true;
if(u==v) return true;
if(depth[v] <= depth[u]) return false;

}
SegmentTree segmentTree;
HeavyLight(vector<int>& p, vector<int>& s)
{
n = p.size();

this->p = vector<int>(n);
copy(p.begin(),p.end(),(this->p).begin());

for(int u = 0; u < n; u++)
if(p[u]!=-1)
{
}
else
root = u;

size = vector<int>(n);
depth = vector<int>(n);
disc = vector<int>(n);

dfs_heavy(root, -1);
dfs_disc(root,-1);

vector<LL> flattenedTree(n);
for(int i = 0; i < n; i++)
flattenedTree[disc[i]] = s[i];
segmentTree = SegmentTree(flattenedTree);
}
void update(int pt, LL val)
{
segmentTree.update(disc[pt],val);
}
LL query(int u, int v)
{
if(!is_ancestor(u,v))
return -1;

LL ans = 0;
{
}
ans += segmentTree.query(disc[u],disc[v]);

return ans;
}
};
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);

int n, q; cin >> n >> q;
vector<int> h(n+1,0), s(n+1,0);
//0 is a dummy point, to be the "root" of the tree
for(int i = 1; i <= n; i++)
cin >> h[i];
for(int i = 1; i <= n; i++)
cin >> s[i];

stack<int> travelToRight, travelToLeft;
vector<int> pRight(n+1), pLeft(n+1);
pRight = pLeft = -1;

auto iterate = [](int i, stack<int>& traveled, vector<int>& p, vector<int>& h)
{
while(!traveled.empty() && !(h[traveled.top()] > h[i]))
traveled.pop();
if(traveled.empty())
p[i] = 0;
else
p[i] = traveled.top();
traveled.push(i);
};
for(int i = 1; i <= n; i++)
iterate(i,travelToRight,pRight,h);
for(int i = n; i >= 1; i--)
iterate(i,travelToLeft,pLeft,h);

HeavyLight HLD_right(pRight,s), HLD_left(pLeft,s);
while(q--)
{
int t, u, v; cin >> t >> u >> v;
if(t==1)
{
HLD_right.update(u,v);
HLD_left.update(u,v);
}
else
{
if(u <= v)
cout<<HLD_right.query(u,v)<<'\n';
else
cout<<HLD_left.query(u,v)<<'\n';
}
}
cout<<flush;
}

Tester's Solution
#include <iostream>
#include <stdio.h>
#include <vector>
using namespace std;
typedef long long llong;

int n,q;
int h;
llong a;

vector<int> st;
vector<int> Tree;
bool root;

int inCtr;
int inVal;
int lastIn;
int parent;

llong IT;
int LEAFOFFSET;

bool isChild(int t, int vp, int vc)
{
return inVal[t][vc] >= inVal[t][vp] && inVal[t][vc] <= lastIn[t][vp];
}

void recUpd(int t, int ver, int L, int R, int l, int r, llong val)
{
if (L >= l && R <= r)
{
IT[t][ver] += val;
return;
}
else if (L > r || R < l)
return;
else
{
recUpd(t, 2*ver, L, (L+R)/2, l, r, val);
recUpd(t, 2*ver+1, (L+R)/2+1, R, l, r, val);
}
}

void updVal(int t, int node, llong val)
{
int L = inVal[t][node];
int R = lastIn[t][node];

recUpd(t, 1, 1, LEAFOFFSET+1, L, R, val);
}

llong rootPath(int t, int node)
{
if (node == 0)
return 0LL;

int ind = inVal[t][node] + LEAFOFFSET;
llong ans = 0;

while(ind > 0)
{
ans += IT[t][ind];
ind /= 2;
}

return ans;
}

void flattenTree(int t, int ver)
{
int i;

inCtr[t]++;
inVal[t][ver] = inCtr[t];

for (i=0;i<Tree[t][ver].size();i++)
{
parent[t][ Tree[t][ver][i] ] = ver;
flattenTree(t, Tree[t][ver][i]);
}

lastIn[t][ver] = inCtr[t];
}

int main()
{
int i,j;

scanf("%d %d", &n, &q);

for (i=1;i<=n;i++)
{
scanf("%d", &h[i]);
}

for (i=1;i<=n;i++)
{
scanf("%lld", &a[i]);
}

LEAFOFFSET = 1;
while(LEAFOFFSET < n)
LEAFOFFSET *= 2;
LEAFOFFSET--;

for (i=1;i<=n;i++)
{
while(!st.empty() && h[st.back()] <= h[i])
st.pop_back();

if (!st.empty())
Tree[st.back()].push_back(i);
else
root[i] = true;

st.push_back(i);
}

st.clear();
for (i=n;i>=1;i--)
{
while(!st.empty() && h[st.back()] <= h[i])
st.pop_back();

if (!st.empty())
Tree[st.back()].push_back(i);
else
root[i] = true;

st.push_back(i);
}

for (i=1;i<=n;i++)
{
if (root[i])
flattenTree(0, i);

if (root[i])
flattenTree(1, i);
}

for (i=1;i<=n;i++)
{
updVal(0, i, a[i]);
updVal(1, i, a[i]);
}

for (i=1;i<=q;i++)
{
int cm, v, k;

scanf("%d %d %d", &cm, &v, &k);

if (cm == 1)
{
int change = k - a[v];
updVal(0, v, change);
updVal(1, v, change);
a[v] = k;
}
else
{
int t = 0;
if (v > k)
t = 1;

if (!isChild(t, v, k))
printf("-1\n");
else
printf("%lld\n", rootPath(t, k) - rootPath(t, parent[t][v]));
}

}
}

23 Likes

Why does my implementation with Fenwick Tree give TLE on all TC’s?

My basic idea is to do it using the idea of the MO algorithm. I divided the array into sqrt(n) blocks and for each block calculated the maximum of that array and also stores 2 sets, 1 for iterating into decreasing index and another for iterating into increasing index from the maximum value of a block and then storing path in the set from prev block max value or next block max value depending on iterating direction. Then just compare the maximum values between blocks to check if path exist between two blocks. But I am receiving WA on other test cases except sample one. Can someone tell me what mistake I had done or provide some testcase in which my solution is failing. My submission

Edit:
Clean submission

2 Likes

Among other things, you are checking if p_b is an ancestor of p_c by literally climbing the tree, but that is too slow

Isn’t that just O(n)?

I used 3 Segment Trees and Stack Trick to solve the question

7 Likes

That’s completely wrong way to go, because there could be multiple Include/Exclude heights in a block.

TLE because what if the heights are 4,5,6,7,8,9…so in worst case you are doing n jumps, we need less complexity than that.

1 Like

Well, yes, but that should explain why it’s not passing the last two subtasks at least. I haven’t looked at your code too closely so there’s probably something else causing it to TLE on the first subtask.

I don’t think so. I used set for only that purpose. Give some testcases on which it is failing.

1 Like
7 Likes

QTREE with path sum, instead of max-edge.

2 Likes

I also used the same technique.
My sol: https://www.codechef.com/viewsolution/35511735

2 Likes

@shisuko There should be bit relaxation in constraint, instead of n=2100000 , n should be equal to 100000. I tried first using HLD, unable to get more than 10pts. See my HLD Implementation (Here) . It was giving O(log(n))^2, so also as per constraint it should not pass.
2. I did a euler tour of tree, at each entry I added the positive value of taste of node(+c) , and at exit negative of same value(-c). This way I got list of size (2
n) .Made a segment Tree over it.From Euler entry and exit point , I was able to identify ,if the one node is ancestor of one or not.If yes , the sum of starting point of a to starting point of b in segment tree gives the total taste from a to b else -1. For sum I was able to do it in O(log(2n)) but for update it takes 4O(log(2n)) after a bit optimization , it was still taking 2O(log(2n)). I maximum got 45 points. I unable to score 100pts.This is my euler Implementation(Here) . Please Suggest , How can I Improve my both solution , HLD and Eulers both

3 Likes

There is an \mathcal{O}(\log n)-per-query solution anyway that isn’t too different, so the bounds are fine. If you go through with the \mathcal{O}(\log^2 n)-per-query solution, it becomes your responsibility to make the constant factor not-too-bad. I also wrote a Heavy-Light solution and it only took 0.20s.

1 Like

is it possible to get testcases?. I was trying to solve Chef and dragon using merge sort tree. I was getting all the self made testcases answer correct but i don’t know why on submission i was getting WA not even a single ac. so i want to know where my code was failing. If anybody knows how to get testcases please tell me.

No way to get the official tests. You can request someone to generate random tests for you to test locally

1 Like

I had a small doubt regarding the statement: It’s mentioned that gliding is allowed so that you can “touch the polyline itself” as long as you don’t go thought the mountain.

And suppose we have the mountain as 5 4 4 2 with tastiness as 6 7 4 3 respectively. (Let’s say we want to travel from 1-4) Why can’t we glide to the first “4” which has a higher value and then go directly to 2, we won’t be going through the 2nd “4” would we?

We’ll just touch the edge which is allowed. Then we’ll go to 2. The path is 5 -> 4 -> 2 (4 being the one with the higher value)

I was trying it out like this initially but it gave me a WA verdict, but when I changed it to the “4” near the destination, it got accepted

2 Likes

Can you tell me why I am getting WA. I am not able to find testcase on which my solution is failing. Can you help me with this?

same here bro. Every testcase is giving right answer but still getting wa