### 977 - Old West Rumours

Posted:

**Tue Feb 10, 2009 12:28 pm**Questions:

1. Billy starts from town 0, but where does the rumor starts from?

2. If the rumor starts from town 0, then Billy arrived at town 0 the same time as the rumor, so Billy saved only 1 town and the rumor stopped?

3. It seemed no 2 is incorrect since the sample output says Billy can save 4 towns (reach those 4 towns before the rumors), so the statement "Billy will be able to kill the rumour only if he manages to reach a town at least at the same time the rumour gets there." is wrong? or the rumor doesn't start from 0.

4. If the rumor doesn't start from town 0 (it can start from any town) then how do Billy make sure he has stopped the rumor without visiting all the town?

After looking the 1st and 2nd picture could it be that:

1. The rumor is assumed to start from town 0, then mark the time of all earliest time for the rumor to arrive at the other towns.

2. Now Billy will pick a path p0, p1, p2, p3, ..., pK such that billyArrivalTime[pi] <= rumorArrivalTime[pi], we want to maximize K. (note: from px to py can have other sub-path but we only interested on towns in the path that can be saved)

3. This seemed to agree with the sample output but contradicts with the Q2 above if the rumor starts at town 0.

So anyone can help make this thing clear?

1. Billy starts from town 0, but where does the rumor starts from?

2. If the rumor starts from town 0, then Billy arrived at town 0 the same time as the rumor, so Billy saved only 1 town and the rumor stopped?

3. It seemed no 2 is incorrect since the sample output says Billy can save 4 towns (reach those 4 towns before the rumors), so the statement "Billy will be able to kill the rumour only if he manages to reach a town at least at the same time the rumour gets there." is wrong? or the rumor doesn't start from 0.

4. If the rumor doesn't start from town 0 (it can start from any town) then how do Billy make sure he has stopped the rumor without visiting all the town?

After looking the 1st and 2nd picture could it be that:

1. The rumor is assumed to start from town 0, then mark the time of all earliest time for the rumor to arrive at the other towns.

2. Now Billy will pick a path p0, p1, p2, p3, ..., pK such that billyArrivalTime[pi] <= rumorArrivalTime[pi], we want to maximize K. (note: from px to py can have other sub-path but we only interested on towns in the path that can be saved)

3. This seemed to agree with the sample output but contradicts with the Q2 above if the rumor starts at town 0.

So anyone can help make this thing clear?