PKU 1253 - Markov Trains

Autor da análise: gabrielrcpgabrielrcp

Link: http://acm.pku.edu.cn/JudgeOnline/problem?id=1253

Resumo

Temos $n \leq 12$ estações. São dados os horários de partida e chegada de $m \leq 100$ trens. Para cada trem é associada uma probabilidade de cancelamento daquele trem. Supõe-se que os trens sejam cancelados de maneira independente uns dos outros.
É dados ainda uma estação de origem, o horário mais cedo que podemos estar na estação de origem ($t_{\textrm{ori}}$), uma estação de destino e o horário máximo que temos para chegar até ela ($t_{\max}$).
Pede-se para encontrar uma sequência de estações tal que, se tentarmos sempre ir de uma estação à outra nessa sequência, sempre tomando o primeiro trem disponível, teremos a maior probabilidade de chegar ao nosso destino à tempo.

Solução

Antes de atacar o problema original, vamos tomar um outro mais simples. Se tivermos fixado uma sequência $E_0, \ldots , E_n$ de estações, e queremos calcular a probabilidade de irmos de $E_0$ à $E_n$, saindo em $t_{\textrm{ori}}$ e chegando antes de $t_{\max}$.

Isso pode ser resolvido por PD. Chame de $f(i, t)$ a probabilidade de, chegando em $E_i$ no tempo $t$, consigamos chegar ao nosso destino à tempo. A probabilidade procurada será $f(0, t_{\textrm{ori}} - 1)$ (esse $-1$ está aí porque não podemos pegar um trem que saia exatamente no mesmo minuto que chegamos à uma estação de trem, exceto pela primeira).

Os casos de fronteira dessa função são:

(1)
\begin{align} f(i, t) = \begin{cases} 0.0 & \textrm{se } t > t_{\max} \\ 1.0 & \textrm{se } t \leq t_{\max} \quad \textrm{ e } \quad i = n \end{cases} \end{align}

Agora fixe $i$ e $t$ que não sejam de fronteira. Chamemos de $T_1, \ldots T_k$ os trens que vão de $E_i$ para $E_{i+1}$ cujos tempo de partida seja estritamente maior que $t$. Ordene essa sequência pelos tempos de partida. Adote $\textrm{prob}(T_j)$ como a probabilidade de $T_j$ ser cancelado e $\textrm{chegada}(T_j)$ como o tempo de chegada de $T_j$ à $E_{i+1}$. Valerá a relação:

(2)
\begin{align} f(i, t) = \sum_{j=1}^k \left\{ \left[ \prod_{l =1}^{j-1} \textrm{prob}(T_l) \right] \left( 1 - \textrm{prob}(T_j) \right) f(i+1, \textrm{chegada}(T_j)) \right\} \end{align}

Com essas relações conseguimos calcular essa probabilidade em $\mathcal{O} ((n + m) t)$, onde $t$ é o tamanho do intervalo de tempo em que estamos considerando. ($n \leq 12$, $m \leq 100$, $t \leq 1400$). Note que podemos enxugar essa PD se tomarmos apenas os horários que tem algum trem partindo, como o número de trens é no máximo 100, isso diminui a complexidade para $\mathcal{O} ((n +m) m)$. Mas isso não é necessário (eu passei esse problema em $0s$ sem isso).

Bom, agora o que podemos fazer é listar todas as rotas entre as estações de origem e destino e calcular a suas probabilidades, guardando sempre a maior. Você pode diminuir um pouco o número de rotas se você nunca voltar para uma estação que já esteve, e tomar só rotas em que hajam trens que, caso não sejam cancelados, te levem da origem ao destino em tempo.

A complexidade final do algoritmo é $\mathcal O ((n+m) t K)$, onde $K$ é o número de rotas testadas. Eu não sei provar que esse número é pequeno. Mas minha intuição me diz que ele não pode ser muito grande, já que temos poucos trens, e ainda tem o tempo como fator.

Uma última observação, que não deve ser novidade para ninguém aqui, mas vou falar mesmo assim. Os tempos são dados no formato hh:mm, que não é muito fácil de trabalhar. Uma maneira de deixar isso mais tratável é converter o horário para a quantidade de minutos desde o começo do dia, ou seja $60 * h + m$. Com isso você pode trabalhar com os horários como um int normal.

Testes

Entrada

4
3
A 12:00 B 12:15 0.1
A 12:10 B 12:14 0.23
A 12:20 B 12:30 0.456
A 12:00 B 12:30
4
A 12:00 B 12:15 0.1
A 12:05 B 12:13 0.15
B 12:20 C 12:35 0.12
A 12:15 C 12:33 0.4
A 12:00 C 13:00
5
A 12:00 B 13:00 0.2
A 12:30 B 13:30 0.0
B 13:20 C 14:00 0.0
C 14:30 D 17:00 0.0
B 14:30 D 17:00 0.1
A 12:00 D 21:00
5
A 12:00 B 13:00 0.2
A 12:30 B 13:30 0.1
B 13:20 C 14:00 0.001
C 14:30 D 17:00 0.001
B 14:30 D 17:00 0.1
A 12:00 D 21:00

Saída

A B
0.9895
A B C
0.8668
A B D
0.9000
A B D
0.8820

Enquete

Qualidade do enunciado

Dificuldade do problema

Problema interessante

Discuta o problema

Add a New Comment
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License