Page 1 of 1

977 - Old West Rumours

Posted: Tue Feb 10, 2009 12:28 pm
by fh

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?

Re: 977 - Old West Rumours

Posted: Wed Feb 11, 2009 6:06 am
by fh
Consider this input:

Code: Select all

3 2
1 1 1
0 1 10
1 2 10
Town 0 will hear the gossip in hour 0.
Town 1 will hear the gossip in hour 10.
Town 2 will hear the gossip in hour 20.
Regardless of which town Billy visit, is that true?

Suppose that Billy starts from Town 0, clear the gossip in 1 hour, then arrived at town 1 at hour = 6.
Now, does Billy stops the rumor completely here? or the rumor will still continue to town 2 even though Billy has cut the line in town 1?
If the rumor can still continue, then Billy will still have to visit town 2.

What is the correct output for this scenario? 2 or 3? clearly not 1 since the sample output of the problem allows the rumor to spread out of town 0.