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 f(i,j) be the chance of arriving on time if you're at station i with j minutes left.

Let ex(i,j) be the expected value of X if you're at station i with j minutes left.

Let g(i,j)=f(i,j) \cdot ex(i,j).

Let b_{mn} be the value of b_i corresponding to the n^{th} edge leaving station m. x_{mn} and y_{mn} are defined similarly.

Let q_i be the number of edges leaving station i.

Then:

\displaystyle f(i,j)=\sum_{k=1}^{q_i} \dfrac{1}{q_i} \left( \dfrac{\sum_{z=j-x_{ik}}^{j-y_{ik}} f(b_{ik},z)}{y_{ik}-x_{ik}+1} \right)

\displaystyle g(i,j)=\dfrac{1}{f(i,j)} \sum_{k=1}^{q_i} \dfrac{1}{q_i} \left( \dfrac{\sum_{z=j-x_{ik}}^{j-y_{ik}} g(b_{ik},z)}{y_{ik}-x_{ik}+1} \right)

\displaystyle ex(i,j)=\dfrac{g(i,j)}{f(i,j)}

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 \mathcal{O}((N^2+M)T) solution, which can be improved to \mathcal{O}((N+M)T) by storing the values of f and g with a prefix sum array.

Complexity: \mathcal{O}((N+M)T)


Comments

There are no comments at the moment.