You are not logged in. Please login at www.codechef.com to post your questions!

×

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.

This question is marked "community wiki".

asked 24 Jan, 00:55

watcher's gravatar image

7★watcher
35
accept rate: 0%

edited 27 Jan, 20:33

admin's gravatar image

0★admin ♦♦
19.8k350498541


The solution links aren't working....

link

answered 27 Jan, 20:41

vivek_ghosh's gravatar image

4★vivek_ghosh
1
accept rate: 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

link

answered 28 Jan, 11:45

samjoe's gravatar image

3★samjoe
1
accept rate: 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

link

answered 28 Jan, 21:32

nvdrag123's gravatar image

4★nvdrag123
11
accept rate: 0%

edited 28 Jan, 21:33

toggle preview
Preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "title")
  • 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

question asked: 24 Jan, 00:55

question was seen: 1,234 times

last updated: 10 Feb, 23:50