PROBLEM LINK:Author: 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.
This question is marked "community wiki".
asked 24 Jan, 00:55

I think there is an error in formation of question. In the question it is mentioned that:
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: 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

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.
answered 28 Jan, 21:32
