UTS Open '15 #4 - Subway - Olympiads 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 \le T \le 2000)~ minutes. The subway system is a network of $N$ ~N~ stations $(2 \le N \le 2000)$ ~(2 \le N \le 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 \le M \le 2000)~. The $i^\text{th}$ ~i^\text{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 \le a_i,b_i \le N, a_i \ne 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 \le x_i \le y_i \le 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 \le 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 \le 2000~	$T \le 2000$ ~T \le 2000~
$50\%$ ~50\%~	$N \le 100$ ~N \le 100~	$M \le 100$ ~M \le 100~	$T \le 100$ ~T \le 100~
$30\%$ ~30\%~	$N \le 2000$ ~N \le 2000~	$M \le 2000$ ~M \le 2000~	$T \le 2000$ ~T \le 2000~

Input Specification

The first line will contain $N$ ~N~, $M$ ~M~, and $T$ ~T~. The $i^\text{th}$ ~i^\text{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

2 1 4
1 2 1 100000

Sample Output 1

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}$ ~\dfrac{1+2+3+4}{4}=\dfrac{5}{2}~.

Sample Input 2

3 2 3
1 2 1 100000
2 3 1 100000

Sample Output 2

2.6666666667

Sample Input 3

Sample Output 3

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

Picture for Sample Input 3

$\text{[math]}$

Sample Input 4

Sample Output 4

8.2203841034

Sample Input 5

Sample Output 5

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