UTS Open '15 #4 - Subway

View as PDF

Submit solution


Points: 25 (partial)
Time limit: 2.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 (1 \leq T \leq 2000) minutes. The subway system is a network of N stations (2 \leq N \leq 2000) numbered from 1 to N which are connected to each other by M one-way links (1 \leq M \leq 2000). The i^\textbf{th} link connects station a_i to station b_i (1 \leq a_i,b_i \leq N, a_i \neq b_i) and could take anywhere from x_i to y_i minutes to traverse (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 and 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 when she reaches a station without any outgoing links.

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

Portion of marksConstraints on NConstraints on MConstraints on T
20\%N=2M \leq 2000T \leq 2000
50\%N \leq 100M \leq 100T \leq 100
30\%N \leq 2000M \leq 2000T \leq 2000

Input Format

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

Output Format

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

Sample Input 1

2 1 4
1 2 1 100000

Sample Output 1

2.5000000000

Explanation

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

Sample Input 2

3 2 3
1 2 1 100000
2 3 1 100000

Sample Output 2

2.6666666667

Sample Input 3

3 3 2000
1 3 1 1
1 2 1 1
2 1 1 1

Sample Output 3

3.0000000000

Explanation

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

Sample Input 4

2 3 10
1 2 6 10
1 2 1 2015
1 2 8 17

Sample Output 4

8.2203841034

Sample Input 5

3 4 3
1 2 1 2
2 3 2 2
2 3 1 6
1 3 1 10

Sample Output 5

2.4938271605

Picture


Comments


  • 1
    kobortor  commented on May 5, 2015, 9:10 p.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 5, 2015, 10:52 p.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.


      • 1
        kobortor  commented on May 8, 2015, 6:34 p.m.

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


  • 1
    pyrexshorts  commented on April 30, 2015, 11:13 p.m.

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


    • 8
      bruce  commented on May 1, 2015, 9:16 p.m.

      The time taken is an integer number of minutes chosen uniformly at random from all integers between xi and yi 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