Internet Problem Solving Contest

IPSC 2007

Solution to Problem B – Bus Story

Solution of this problem relies mostly on parsing of the input. The input stories were automatically generated and after a slight effort one could easily get a list of patterns used, and translate them into pure numbers. After having correct information about the history of people boarding/leaving the bus, there are just few cases we have to worry about:

If we know how many people were initially in the bus, we can just simulate the trip and make sure that during the trip the number of passengers is not negative, and that at the end it is zero.

If we don't know the initial number of people, we can simulate the entire process backwards, starting from the zero people at the terminal.

An alternate idea is to realize that the story can be true if and only if there were never less people in the bus than at the end. In other words, when reading the input we can always estimate, at least how many people were there in the bus. If at any moment the number of passengers should turn negative, we increase our estimate. At the end we know the minimal number of passengers that arrived at the terminal. If the story claims that there were less, it is false, otherwise it is true.