×

DIS - Editorial

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 \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.

This question is marked "community wiki".

7★watcher
35
accept rate: 0%

19.8k350498541

 0 The solution links aren't working.... answered 27 Jan, 20:41 1 accept rate: 0%
 0 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 answered 28 Jan, 11:45 3★samjoe 1 accept rate: 0%
 0 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 answered 28 Jan, 21:32 1●1 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×15,680
×366
×202
×39