PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: nicholask
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
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);
}
}
string readOne() {
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);
string res = readOne();
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);
int res = stoi(readOne());
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);
long long res = stoll(readOne());
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++) {
res[i] = readInt(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
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++) {
res[i] = readLong(min_val, max_val);
if (i != size - 1) {
readSpace();
}
}
return res;
}
void readSpace() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == ' ');
pos++;
}
void readEoln() {
assert((int) buffer.size() > pos);
assert(buffer[pos] == '\n');
pos++;
}
void readEof() {
assert((int) buffer.size() == pos);
}
};
int main() {
input_checker in;
int tt = in.readInt(1, 100);
in.readEoln();
int sn = 0;
int sk = 0;
while (tt--) {
int n = in.readInt(1, 2000);
in.readSpace();
int m = in.readInt(0, n - 1);
in.readSpace();
int k = in.readInt(1, 3000);
in.readEoln();
sn += n;
sk += k;
vector<pair<long long, int>> a;
set<int> st;
for (int i = 0; i < m; i++) {
int x = in.readInt(1, n);
in.readSpace();
int y = in.readInt(-1e9, 1e9);
in.readEoln();
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++) {
int x = in.readInt(1, n);
in.readSpace();
int y = in.readInt(1, n);
in.readSpace();
int z = in.readInt(0, 1e9);
in.readEoln();
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);
in.readEof();
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)