DINCPATH - Editorial

PROBLEM LINK:

Practice
Contest, div. 1
Contest, div. 2

Author: Udit Sanghi
Tester: Teja Vardhan Reddy
Editorialist: Oleksandr Kulkov

DIFFICULTY:
EASY
PREREQUISITES:
Topological sort, directed acyclic graphs, dp
PROBLEM:
You’re given undirected graph with N nodes and M edges. Each node has value A_i assigned to it. We will call a path doubly-increasing if both values and differences of values of nodes are strictly increasing. Formally for path p_1, \dots, p_k it should hold that:

0 <A_{p_2} - A_{p_1} < A_{p_3} - A_{p_2} < \dots < A_{p_k} - A_{p_{k-1}}

You need to find the length of the longest double increasing path in graph.
EXPLANATION:
Consider edge (u,v) such that A_u<A_v. Let’s assign weight A_v - A_u to this edge and say that we may only move through it from u to v. Now we have directed graph, moreover this graph is acyclic. In this graph we should find the longest increasing path in terms of edges weights.

To do this we may store dp_{(u,v)} being equal to the maximum length of the path which we may obtain starting from the edge (u,v). You may see that if we sort all edges going from v by their weights, all edges (v,w) which may be used to extend path starting in (u,v) form contiguous suffix in this sorted list (according to condition A_w > 2A_v - A_u).

Thus we may take maximum possible dp_{(v,w)} by using binary search and keeping maximum values on suffixes in sorted lists of edges:

vector<int> p(N);
iota(begin(p), end(p), 0);
sort(begin(p), end(p), [&](int a, int b){return A[a] > A[b];});
int ans = 1;
for(auto u: p) {
	sort(begin(g[u]), end(g[u]), [&](int a, int b){return A[a] > A[b];});
	int cur = 2;
	for(auto v: g[u]) {
		auto it = lower_bound(begin(g[v]), end(g[v]), 2 * A[v] - A[u], 
			[&](int w, int c){
				return A[w] > c;
			});
		if(it != begin(g[v])) {
			cur = max(cur, 1 + dp[v][it - begin(g[v]) - 1]);
		}
		ans = max(ans, cur);
		dp[u].push_back(cur);
	}
}
cout << ans << endl;

AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
Editorialist’s solution can be found here.

Is this really easy ? :slight_smile:

4 Likes

Not really… I agree with you…

2 Likes

Could anyone provide, a simpler way to solve this question?

This is an easy version of this problem with similar technique, you can try this problem and I think the one mentioned above is itself one of the simpler way to solve this problem !!

4 Likes

Thanks @aman_robotics :smile:

In this problem, a directed graph is not given, however we have to find the length of the longest strictly-increasing trail in it. We utilize the statement of Aj-Ai>0, to form a directed graph such that the edges is directed from node j to node i, for all the edges.

After obtaining the directed graph. We consider this graph with n vertices and no edges, then just sort the given edges by their weights (non-decreasingly) and add them to the graph one by one.

Let dp [ v ] be the length of a longest increasing trail which ends in the vertex v . In the mentioned method, when you’re adding a directed edge xy to the graph, set dp[ y ] value to
max( dp[y], dp[x]+ 1) (because of trails which ends in y and use this edge).
However You need to take care of the situation of being some edges with equal weights; for this job we can add all edges of the same weights simultaneously.

5 Likes

Yes, I got your explanation. But I have a doubt, How to add the edges having equal weights simultaneously. I am stuck in a TLE here !!

I solved this question after learning how to solve a div2E question as link was given by @aman_robotics. I don’t think a variation of div2E question should be categorised under Easy.

can anyone please tell why this sol :https://www.codechef.com/viewsolution/34655763
gives TLE

was a easy ques