## Editorial for UTS Open '15 #4 - Subway

Remember to use this editorial

**only**when stuck, and**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.**Submitting an official solution before solving the problem yourself is a bannable offence.**Let be the chance of arriving on time if you're at station with minutes left.

Let be the expected value of if you're at station with minutes left.

Let .

Let be the value of corresponding to the edge leaving station . and are defined similarly.

Let be the number of edges leaving station .

Then:

The intuitive explanation of the above is that the expected value is the **weighted average** of the expected value of all possible next states, weighted according to (chance of reaching next state) × (chance of being on time from that state).

This leads immediately to an solution, which can be improved to by storing the values of and with a prefix sum array.

Complexity:

## Comments