Indian Computing Olympiad

Searching→Post Election Transfers(IOITC 2006)

A new government has been elected in Siruseri and has begun the usual process of shuffling all the officials appointed by the previous regime. One of the departments affected is the railways.

The railway network in Siruseri is just a single straight line, with N stations. Of these N stations, L have station masters, distributed at various stations along the line. The government has decided to transfer all station masters so as to keep them as far apart as possible. Unfortunately for the government, there is a clause in the contract negotiated with the railway union by which a station master may be transferred at most K stations from his current posting. The task before the government is to achieve its goal of transferring station masters to maximize the minimum distance between any pair within the restrictions of the contract.

For instance, suppose there are 10 stations, numbered 1,2,...,10, and there are 3 station masters, currently assigned to stations 5, 7 and 8. Further, let us suppose that no station master can move more than 2 stations away from the current station. Then, the best the government can do is to move the station master at station 5 to station 3 and the station master at station 8 to station 10. In the new arrangement, the station masters are at stations 3, 7 and 10 and the minimum gap is 2 stations, between stations 7 and 10. (Note that, in addition, the station master at station 7 could be moved to station 6, in which case the minimum gap of 2 would be betweens stations 3 and 6.)

Input bounds: L ≤ 10⁵, N and K are integers.

Suppose we fix an answer A for the distanct separating the station masters. Can we arrange the station masters if we insist that they are all separated by A?

Let OP(i) be the original position of station master i and let NP(i) be the new position to which we move station master i.

We move the first station master as far left as possible, given that we can shift him by at most K.

NP(1) = max(1,P(1)-K)

For i+1,

NP(i+1) =	max(NP(i)+A,P(i+1)-K)	if NP(i)+A < P(i+1)
	NP(i)+A,	if P(i+1) ≤ NP(i)+A ≤ P(i+1)+K
	impossible	otherwise

Thus, in one linear scan, we can check if a solution exists for a fixed A.

We know that the final solution lies between 1 and N. Since we can solve this problem easily for a fixed A, we can find a good choice of A by binary search by starting with A = N.

This takes time L log N.

---