PROBLEM LINK:
Author: Michael Nematollahi
Tester: Teja Vardhan Reddy
Editorialist: Michael Nematollahi
PREREQUISITES:
graphs
PROBLEM:
You’re given two arrays a and b of length N. Your task is to find out if it’s possible to construct an undirected graph with N vertices whose edges have positive lengths, in which the distance from 1 to every vertex v is equal to a_v and the distance from N to every other vertex v is equal to b_v.
QUICK EXPLANATION:
Add an edge from 1 to every vertex v with length a_v. Add an edge from N to every other vertex v with length b_v. The answer is “Yes” iff the arrays a and b are correct on this graph.
EXPLANATION:
First, let’s find out in which cases the answer is “No”. We’ll go over different cases one by one.
1_ a_1 \neq 0. In this case, the answer is obviously “No” because the distance from every vertex to itself should be 0.
2_ b_N \neq 0. This is similar to the case above.
3_ a_N \neq b_1. Since the edges are bidirectional, the distance from u to v should be equal to the distance from v to u.
4_ a_v = 0 where v is a vertex other than 1. This is true because the length of the edges are positive.
5_ b_v = 0 where v is a vertex other than N. This is similar to the case above.
6_ There exists a vertex v (1 \lt v \lt N) for whom the inequality a_v + b_v \lt a_N holds. This is true because in this case, there is a path from 1 to N whose length is less than a_N; so a_N is not the length of the shortest path from 1 to N.
7_ There is a vertex v (1 \lt v \lt N) for whom the inequality a_N + b_v \lt a_v holds. This is true because in this case, there exists a path from 1 to v whose length is less than a_v; so a_v is not the length of the shortest path from 1 to v.
8_ There is a vertex v (1 \lt v \lt N) for whom the inequality b_1 + a_v \lt b_v holds. This case is similar to case 7.
If none of these cases fit the given arrays, the answer is yes. One way to construct a graph with these arrays is to add an edge from 1 to every vertex v with length a_v and similarly add an edge from N to every vertex v with length b_v. It’s not hard to check that in this graph, the shortest path from 1 to every vertex v is equal to a_v and the shortest path from N to every vertex v is equal to b_v.
These cases can be checked in O(N). Refer to the setter’s solution to see the implementation.
AUTHOR’S AND TESTER’S SOLUTIONS:
Author’s solution can be found here.
Tester’s solution can be found here.
