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:
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.