UTS Open '15 #4 - Subway - DMOJ: Modern Online Judge

UTS Open '15 #4 - Subway

Points: 17 (partial)

Time limit: 1.0s

Memory limit: 256M

Author:

Problem types

Ms. Evans is meeting some venture capitalists who may be able to fund her startup. Unfortunately, she is running late, and the meeting is in $T$ $T$ $(1 \le T \le 2000)$ $(1 \leq T \leq 2000)$ minutes. The subway system is a network of $N$ $N$ stations $(2 \le N \le 2000)$ $(2 \leq N \leq 2000)$ numbered from $1$ $1$ to $N$ $N$ which are connected to each other by $M$ $M$ one-way links $(1 \le M \le 2000)$ $(1 \leq M \leq 2000)$ . The $i^\text{th}$ $i^{th}$ link connects station $a_i$ $a_{i}$ to station $b_i$ $b_{i}$ $(1 \le a_i,b_i \le N, a_i \ne b_i)$ $(1 \leq a_{i}, b_{i} \leq N, a_{i} \neq b_{i})$ and could take anywhere from $x_i$ $x_{i}$ to $y_i$ $y_{i}$ minutes to traverse $(1 \le x_i \le y_i \le 10^5)$ $(1 \leq x_{i} \leq y_{i} \leq 10^{5})$ . The time taken is an integer number of minutes chosen uniformly at random from all integers between $x_i$ $x_{i}$ and $y_i$ $y_{i}$ inclusive.

TTC subway map

The subway system is very unpredictable.

Since the system is complicated, Ms. Evans follows a simple procedure: at every point, she uses a link selected uniformly at random from all links leaving her current station. Ms. Evans ends her trip when she reaches the meeting or reaches a station without any outgoing links.

Ms. Evans starts at station $1$ $1$ and the meeting will be held in station $N$ $N$ . Ms. Evans arrived at the meeting after $X$ $X$ minutes, and she was on time (that is, $X \le T$ $X \leq T$ ). Calculate the expected value of $X$ $X$ .

Portion of marks	Constraints on $N$ $N$	Constraints on $M$ $M$	Constraints on $T$ $T$
$20\%$ $20 %$	$N=2$ $N = 2$	$M \le 2000$ $M \leq 2000$	$T \le 2000$ $T \leq 2000$
$50\%$ $50 %$	$N \le 100$ $N \leq 100$	$M \le 100$ $M \leq 100$	$T \le 100$ $T \leq 100$
$30\%$ $30 %$	$N \le 2000$ $N \leq 2000$	$M \le 2000$ $M \leq 2000$	$T \le 2000$ $T \leq 2000$

Input Specification

The first line will contain $N$ $N$ , $M$ $M$ , and $T$ $T$ . The $i^\text{th}$ $i^{th}$ of the next $M$ $M$ lines will contain $a_i$ $a_{i}$ , $b_i$ $b_{i}$ , $x_i$ $x_{i}$ , and $y_i$ $y_{i}$ in sequence. It is guaranteed that the chance of Ms. Evans arriving on time will exceed $10^{-11}$ $10^{- 11}$ .

Output Specification

A single line containing the answer to the problem. Your answer will be considered correct if its absolute or relative error does not exceed $10^{-6}$ $10^{- 6}$ .

Sample Input 1

Copy

2 1 4
1 2 1 100000

Sample Output 1

Copy

2.5000000000

Explanation for Sample Output 1

In this case, the answer is the average of the values that would let Ms. Evans be on time: $\dfrac{1+2+3+4}{4}=\dfrac{5}{2}$ $\frac{1 + 2 + 3 + 4}{4} = \frac{5}{2}$ .

Sample Input 2

Copy

3 2 3
1 2 1 100000
2 3 1 100000

Sample Output 2

Copy

2.6666666667

Sample Input 3

Copy

Sample Output 3

Copy

3.0000000000

Explanation for Sample Output 3

The answer is close to $(1)\left(\dfrac{1}{2}\right)+(3)\left(\dfrac{1}{4}\right)+\dots+(1999)\left(\dfrac{1}{2^{1000}}\right) \approx 3$ $(1) (\frac{1}{2}) + (3) (\frac{1}{4}) + \dots + (1999) (\frac{1}{2^{1000}}) \approx 3$ .

Picture for Sample Input 3

$\text{[math]}$

Sample Input 4

Copy

Sample Output 4

Copy

8.2203841034

Sample Input 5

Copy

Sample Output 5

Copy

2.4938271605

Picture for Sample Input 5

$\text{[math]}$

Comments

0

kobortor commented on May 6, 2015, 1:10 a.m.

Can someone please explain how sample 5 obtained that output? Even after doing it by hand I could only get ~2.12 as the answer.

3

pyrexshorts commented on May 6, 2015, 2:52 a.m. ← edit 3 →

1 to 3:

1/20 * 1

1/20 * 2

1/20 * 3

1 to 2:

1/4 * 1

1/4 * 2

2 to 3:

1/8 * 3

1/48 * 2

1/48 * 3

1/48 * 3

This totals to ~0.842.

0.842 / (1/8 + 3(1/48) + 3(1/20)) = ~2.494.

3

kobortor commented on May 8, 2015, 10:34 p.m.

Thanks m8 I'll tell bruce to give you a sticker next class.

0

pyrexshorts commented on May 1, 2015, 3:13 a.m.

Would the answer for test case 2 be 1.833333? It would be 1/6 2 + 1/6 3 + 1/3 * 3 no?

3

bruce commented on May 2, 2015, 1:16 a.m.

The time taken is an integer number of minutes chosen uniformly at random from all integers between $x_i$ $x_{i}$ and $y_i$ $y_{i}$ inclusive.

In sample case 2, the probability to station 2 for 1 minute is 1/100000, for 2 minutes is 1/100000. Similarly, the probability to station 3 for 1 minute is 0, for 2 minutes is (1/100000)*(1/100000), for 3 minutes is (1/100000)*(1/100000)+(1/100000)*(1/100000) (first term: move to 2 for 1 minute and from 2 to 3 for 2 minutes; second term: move to 2 for 2 minutes and from 2 to 3 for 1 minute).

So, the expected value to 3 is

{(2 minutes to 3)*(probability of 2 minutes to 3) + (3 minutes to 3)*(probability of 3 minutes to 3)}/(overall probability to 3 within 3 minutes)

= {2*(1/100000)*(1/100000)+3*[(1/100000)(1/100000)+(1/100000)\(1/100000)]} / [(1/100000)*(1/100000) + (1/100000)*(1/100000)+(1/100000)*(1/100000)]

= 8/3

= 2.6666666667