Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Let us first find an algorithm that, for a given time 
~T~ (in seconds), checks if all messengers can get the news in the given time.
We will first show that there exists an optimal sequence of moving and shouting in which all shouting is done at the very end (after ~T~ seconds). Each sequence of moving and shouting can be modified so that messenger 
~A~, after he would shout the news to messenger 
~A+1~, continues following his movement exactly. That way, all shouting can be done at the end as well.
The algorithm to check if the news can spread in ~T~ seconds now becomes simple.
The first messenger runs ~T~ distance units towards the second village.
The second messenger knows exactly which space interval he must be in after ~T~ seconds to hear the news, and he always tries to go as far as possible from the first village.
The process continues for all messengers.
If, for any messenger, there is no way for him to be in the range of hearing his predecessor, then ~T~ seconds is not enough time to spread the news.
The output is found by binary searching over ~T~.
Comments