DIS - Editorial

PROBLEM LINK:

Practice
Contest

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.

1 Like

The solution links aren’t working…

I think there is an error in formation of question. In the question it is mentioned that:

“Each road has a positive (not necessarily integer) length”

But consider a case such as this: Arya and Aryan have distance of x between them, and two other cities lie at the midpoint. Or pictorially, let cities be A,B,C,D. Then a case such as:

Image link on imgur

should mean distance of BC is 0, so answer should be “No” in this case also.

Please tell me is the question correct or there is error

I used triangle inequality condition on vectors of length ai,bi and aN for i=1 to N. Its pretty easy to visualize on vectors.

solution_link