# ABSOLUTEDIFF - Editorial

Tester: tabr
Editorialist: iceknight1093

2581

# PREREQUISITES:

Detecting negative cycles in a graph

# PROBLEM:

There’s an array A of length N. You know the following pieces of information about it:

• M constraints of the form (pos, val), stating that A_{pos} = val.
• K constraints of the form (u, v, d), stating that |A_u - A_v| \leq d

Find out whether a valid array A exists.

# EXPLANATION:

First, notice that we can replace the second inequality, on absolute values, by a couple of plain inequalities:
A_u - A_v \leq d and A_v - A_u \leq d

Inequalities of this type can be nicely ‘chained’ together, because (A_u - A_v) + (A_v - A_w) = (A_u - A_w).
So, if we know constraints on (A_u, A_v) and (A_v, A_w), we also implicitly have a constraint on (A_u, A_w).
Of course, this applies to longer chains as well.

This information can be nicely represented by constructing an appropriate directed weighted graph.

In particular, consider a directed graph on vertices 1, 2, \ldots, N+1, with edges defined as follows:

• If |A_u - A_v| \leq d is known, add the edges u \to v and v \to u, both with weight d.

This graph has a rather nice property: for any two vertices u and v, if there is a u \to v walk with weight D, then A_u - A_v\leq D will hold.
That is, the ‘chaining’ of inequalities is represented by walks in this graph.

Now, we also have to bring in the A_{pos} = val information here.
That can be done by treating this as the pair of inequalities A_{pos} \geq val and A_{pos} \leq val, or more specifically, A_{pos} - 0 \leq val and 0 - A_{pos} \leq -val.

So, let’s add a new vertex 0 to the graph, whose value we’ll pretend is always 0.
Now, if A_{pos} = val, add the edges 0 \to pos with weight -val and pos\to 0 with weight val.

Now that we have all our constraints, we need to check if they’re valid.

It can be seen that all the constraints are valid if and only if the graph doesn’t contain negative cycles.

Proof

If the graph contains a negative cycle, then for any vertex i on this cycle we have the constraint A_i \lt A_i, which is obviously absurd.

Conversely, suppose the constraints aren’t all valid, meaning there’s always a conflict somewhere.
Then, there must exist some vertices u and v and a value d such that:

• Via some sequence of constraints, we know A_u - A_v \leq d
• Via some other sequence of constraints, we know A_u - A_v \gt d; which means A_v - A_u \lt -d

In particular, this gives us a u\to v walk of weight \leq d, and a v\to u walk of weight \lt -d

Joining these walks, we obtain a closed walk whose weight is negative.
Any such walk must contain a negative cycle as well, proving our claim.

Detecting whether a directed graph contains a cycle is a standard application of the Bellman-Ford algorithm, as seen here for example.

# TIME COMPLEXITY

\mathcal{O}(N\cdot (M + K)) per testcase.

# CODE:

Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
vector <pair <int,long long> > g[2010];
long long dist[2010];
void solve(){
int n,m,k;
cin>>n>>m>>k;
for (int i=0; i<=n; i++) g[i].clear();
for (int i=1; i<=m; i++){
int pos,val;
cin>>pos>>val;
g[pos].push_back({0,-val});
g[0].push_back({pos,val});
}
for (int i=1; i<=k; i++){
int u,v,d;
cin>>u>>v>>d;
g[u].push_back({v,d});
g[v].push_back({u,d});
}
for (int i=0; i<=n; i++) dist[i]=0;
bool relaxed=0;
for (int iters=0; iters<=n; iters++){
relaxed=0;
for (int i=0; i<=n; i++){
for (pair <int,long long> j:g[i]){
if (dist[i]+j.second<dist[j.first]){
dist[j.first]=dist[i]+j.second;
relaxed=1;
}
}
}
if (!relaxed){
cout<<"YES\n";
return;
}
}
cout<<"NO\n";
}
int main(){
ios_base::sync_with_stdio(0); cin.tie(0);
int t; cin>>t;
while (t--) solve();
}

Tester's code (C++)
#include <bits/stdc++.h>
using namespace std;
#ifdef tabr
#include "library/debug.cpp"
#else
#define debug(...)
#endif

struct input_checker {
string buffer;
int pos;

const string all = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
const string number = "0123456789";
const string upper = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string lower = "abcdefghijklmnopqrstuvwxyz";

input_checker() {
pos = 0;
while (true) {
int c = cin.get();
if (c == -1) {
break;
}
buffer.push_back((char) c);
}
}

assert(pos < (int) buffer.size());
string res;
while (pos < (int) buffer.size() && buffer[pos] != ' ' && buffer[pos] != '\n') {
res += buffer[pos];
pos++;
}
return res;
}

string readString(int min_len, int max_len, const string& pattern = "") {
assert(min_len <= max_len);
assert(min_len <= (int) res.size());
assert((int) res.size() <= max_len);
for (int i = 0; i < (int) res.size(); i++) {
assert(pattern.empty() || pattern.find(res[i]) != string::npos);
}
return res;
}

int readInt(int min_val, int max_val) {
assert(min_val <= max_val);
assert(min_val <= res);
assert(res <= max_val);
return res;
}

long long readLong(long long min_val, long long max_val) {
assert(min_val <= max_val);
assert(min_val <= res);
assert(res <= max_val);
return res;
}

vector<int> readInts(int size, int min_val, int max_val) {
assert(min_val <= max_val);
vector<int> res(size);
for (int i = 0; i < size; i++) {
if (i != size - 1) {
}
}
return res;
}

vector<long long> readLongs(int size, long long min_val, long long max_val) {
assert(min_val <= max_val);
vector<long long> res(size);
for (int i = 0; i < size; i++) {
if (i != size - 1) {
}
}
return res;
}

assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}

assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}

assert((int) buffer.size() == pos);
}
};

int main() {
input_checker in;
int sn = 0;
int sk = 0;
while (tt--) {
int m = in.readInt(0, n - 1);
sn += n;
sk += k;
vector<pair<long long, int>> a;
set<int> st;
for (int i = 0; i < m; i++) {
x--;
assert(!st.count(x));
st.emplace(x);
y += (int) 1e9;
a.emplace_back(y, x);
}
vector<vector<pair<int, long long>>> g(n);
sort(a.begin(), a.end());
for (int i = 1; i < (int) a.size(); i++) {
g[a[i - 1].second].emplace_back(a[i].second, a[i].first - a[i - 1].first);
g[a[i].second].emplace_back(a[i - 1].second, a[i - 1].first - a[i].first);
}
for (int i = 0; i < k; i++) {
x--;
y--;
// assert(x != y);
g[x].emplace_back(y, z);
g[y].emplace_back(x, z);
}
vector<long long> d(n, (long long) 1e18);
for (auto [y, x] : a) {
d[x] = y;
}
for (int i = 0; i < n; i++) {
for (int v = 0; v < n; v++) {
for (auto [to, c] : g[v]) {
if (d[to] > d[v] + c) {
d[to] = d[v] + c;
}
}
}
}
string ans = "YES";
for (int i = 0; i < n; i++) {
for (auto [j, c] : g[i]) {
if (d[j] > d[i] + c) {
ans = "NO";
}
}
}
cout << ans << '\n';
}
cerr << sn << " " << sk << endl;
assert(sn <= 2000);
assert(sk <= 3000);
return 0;
}

Editorialist's code (Python)
for _ in range(int(input())):
n, m, k = map(int, input().split())
edges = []
for i in range(m):
u, x = map(int, input().split())
edges.append((0, u, -x))
edges.append((u, 0, x))
for i in range(k):
u, v, d = map(int, input().split())
edges.append((u, v, d))
edges.append((v, u, d))

dist = [0] * (n+1)
ans = 'No'
for itr in range(n+1):
change = False
for u, v, w in edges:
if dist[u] + w < dist[v]:
dist[v] = dist[u] + w
change = True
if not change:
ans = 'Yes'
break
print(ans)

1 Like

This problem can be solved in K*logN time complexity using maths.
Find my solution below.
Solution
Feel free to ping me for an explanation.

This problem can be solved in O(K + N) using kinda nothing. Just store the range of the possible values of Ai and merge them K times and check if merging is possible.

code

1 Like

@yash5507 and @ssingh_934 Your Code is wrong , lucky there were weak test cases . Check out this test case .

1
6 2 7
1 3
2 8
1 3 2
2 4 1
3 5 1
4 5 1
1 5 3
3 6 0
1 6 1


Author’s Code is correct .
@iceknight1093 and @yash5507 Please check this out .

4 Likes

The Graph construct is well defined for all the inequalities to satisfy but it does’nt cater upon the fact that how are we ensuring that the node we are adding is actually 0 in the final solution (if found) but i suppose we can say that if we found a solution and our dummy node is non zero we can just subtract the value of our dummy node from all the nodes of our graph and this would also be a valid solution as all the inequalities are just difference inequalities.

1 Like

How do you prove that taking ranges will give wrong answer ? Just curious.

Let’s say that for Index 2 you have the possible range as [5,7] while for Index 1 you have the possible range [2,4] , and let’s say that you also got an condition that Index 1 and Index 2 differs atmost by |3| , so the range for Index 1 and Index 2 remains intact because for each number in the range there is atleast another number in the other range which satisfies the above condition example (2,5),(3,5) etc. But can we have 2 from Index 1 and 6 from Index 2 ? absolutely not . So this proves that this problem won’t solve by just taking intersection of ranges because some of the information is not conveyed solely by taking ranges.

2 Likes

Thanks.