CF553E Kyoya and Train

Kyoya Ootori wants to take the train to get to school. There are $ n $ train stations and $ m $ one-way train lines going between various stations. Kyoya is currently at train station $ 1 $ , and the school is at station $ n $ . To take a train, he must pay for a ticket, and the train also takes a certain amount of time. However, the trains are not perfect and take random amounts of time to arrive at their destination. If Kyoya arrives at school strictly after $ t $ time units, he will have to pay a fine of $ x $ . Each train line is described by a ticket price, and a probability distribution on the time the train takes. More formally, train line $ i $ has ticket cost $ c_{i} $ , and a probability distribution $ p_{i,k} $ which denotes the probability that this train will take $ k $ time units for all $ 1

N/A

N/A

The optimal strategy in the first case is as follows: First, travel along first train line. With probability $ 1/2 $ Kyoya will take $ 1 $ time unit. Otherwise, Kyoya will take $ 3 $ time units. If the train takes $ 1 $ time unit, travel along the 4th train line. Kyoya will make it to school in time with probability $ 1/2 $ . Otherwise, if the train takes 3 time units, travel along the 2nd train line. Kyoya will make it to school in time with probability $ 1/10 $ . Since the cost of all train lines are zero, we can just look at the probability that Kyoya will incur the penalty. The probability that Kyoya will have to pay the penalty is $ 1/2×1/2+1/2×9/10=7/10 $ . We can show that no other strategy is strictly better. The optimal strategy in the second case is to travel along $ 1→2→4 $ no matter what. Kyoya will incur the penalty with probability $ 3/4 $ , and the cost of the trains is $ 200 $ , thus the expected cost is $ 200.75 $ .