 DIS - Editorial

#1

Author: Michael Nematollahi
Tester: Teja Vardhan Reddy
Editorialist: Michael Nematollahi

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 eq 0. In this case, the answer is obviously “No” because the distance from every vertex to itself should be 0.

2_ b_N eq 0. This is similar to the case above.

3_ a_N eq 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.

#2

#3

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: