PROBLEM LINK:
Practice
Contest, div. 1
Contest, div. 2
Author: Hasan Jaddouh
Tester: Teja Vardhan Reddy
Editorialist: Oleksandr Kulkov
DIFFICULTY:
MEDIUM
PREREQUISITES:
Negative cycles detection, shortest paths with negative edges
PROBLEM:
N people gave Chef M pieces of information. Each piece is described by 4 integers t, u, v and c. If t=1 it means that u-th person is older than v-th by at least c years. If t=2 it means that u-th person is not older than v-th by at least c years. Additionally you know that age of first person is 0 and all ages are (not necessarily positive) integers. You have to determine if it’s possible to uniquely determine the ages of all people and find them if yes.
EXPLANATION:
You have two types of inequalities: a_u - a_v \geq c and a_u - a_v < c. Note that first one is equivalent to a_v-a_u \leq -c and the second one is equivalent to a_u-a_v \leq c-1. Thus we may assume that all inequalities actually look like a_u - a_v \leq c which should be interpreted as two separate bounds: upper bound a_u \leq a_v + c and lower bound a_v \geq a_u - c.
Next thing to note is that those bounds might be combined:
And if you look further into it, you may see that it resembles the way distance is measured in graphs. So let’s say that inequality a_u \leq a_v + c generates directed edge v \to u with weight c. Then combination of inequalities mentioned above works in the same way as distance in such graph. In first example we have two edges w \to v and v \to u and on this basis we make an assumption about distance between w and u.
In this particular problem we have some anchor we may start from, which is a_1 =0. By considering shortest path from it to any vertex we’ll make some upper bound on this vertex’s age. In particular consider the path 1 \to v_1 \to v_2 \to \dots \to v_k with edges having weights c_1, c_2, \dots, c_k. Edges from this path correspond to chain of inequalities:
Keeping in mind that a_1=0 and eliminating inequalities one by one we end up having following bound for the age of vertex v_k: a_{v_k} \leq c_1+c_2+\dots+c_k. Thus each path from vertex 1 to vertex v corresponds to some upper bound on a_v and shortest path would provide the strictest of such bounds. And turns out it is actually exact upper bound by which I mean that if any solution exists then there also exists a solution in which all upper bounds are reached.
Assume it’s not true then there is a contradiction with some specific inequality a_u - a_v \leq c. Let R_v be the upper bound we obtained above for vertex v, contradiction mentioned above means that we obtained R_u - R_v > c. But it can’t be because if shortest path to v is equal to R_v then shortest path to u would surely be at most R_v+c because there’s an edge of weight c going from v to u.
Thus such absurd outcome might be only when there’s no solution at all and it’s impossible to maintain correct upper bounds. By some further thoughts we may understand that it means that there’s a negative cycle and we had to use bounds of kind R_u=R_v=-\infty.
In similar manner we may construct graph in which for inequality a_v \geq a_u - c there’s an edge u \to v with weight -c. Longest path from vertex 1 to vertex v would maintain lower bound for a_v. Thus in similar way we may obtain lower bounds L_v and claim that if we were able to correctly set them then there’s a solution which matches them exactly. So either all bounds match and we know the solution or we have two different solutions which we should mention.
Now to some technical details. We may keep everything in two graphs:
vector<vector<pair<int, int>>> g[2];
for(int i = 0; i < M; i++) {
int t, u, v, c;
cin >> t >> u >> v >> c;
if(t == 1) {
c = -c;
swap(u, v);
} else {
c--;
}
g[0][v].push_back({u, c});
g[1][u].push_back({v, -c});
}
Instead of finding longest path we may say that weight of edge is c instead of -c and find shortest path. In this way we will later use the same code for finding best bounds in both graphs:
g[0][v].push_back({u, c});
g[1][u].push_back({v, c});
Note though that graphs may have negative edges so it’s not possible to utilize anything like Dijkstra algorithm and you have to use Ford-Bellman algorithm. Moreover there is a possibility that graph contains negative cycles and you have to detect it because if there’s a negative cycle it means that there’s -\infty upper bound for some ages which is infeasible.
Now if there are no negative cycles, we’ll end up with our best upper and lower estimates after we use some algorithm for shortest paths in graphs with negative edges. Here’s example with SPFA:
vector<int> dist(int z, int M) {
int n = g[z].size();
vector<int> dist(n, inf), in_que(n);
deque<int> que = {0};
dist[0] = 0;
while(!que.empty()) {
M--;
if(M < 0) {
return {-1};
}
int v = que[0];
que.pop_front();
in_que[v] = 0;
for(auto it: g[z][v]) {
int u = it.first, c = it.second;
if(dist[v] + c < dist[u]) {
dist[u] = dist[v] + c;
if(!in_que[u]) {
in_que[u] = true;
que.push_back(u);
}
}
}
}
return dist;
}
After that we will have bounds for each age: L_i \leq a_i \leq R_i. It stands for minimum and maximum possible values we may take of each variable so it still would be possible to satisfy all constraints. As already was mentioned if L_i=R_i for all i, then the solution exists and unique. Otherwise if L_i < R_i for some i it means that there’re at least two distinct solutions: having a_i = L_i and having a_i=R_i.
So if our bounds matched, we should output our solution and print No otherwise.
auto le = dist(0, M);
auto ge = dist(1, M);
for(auto &it: ge) {
it = -it;
}
if(le == ge) {
cout << "YES" << endl;
for(auto it: le) {
cout << it << ' ';
}
cout << endl;
} else {
cout << "NO" << endl;
}
Total complexity of solution is equal to the complexity of SPFA which is O(NM).
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.