Блог пользователя gXa

Автор gXa, история, 7 лет назад, По-английски

Hi, I have a question:

You are given 100 stations and distance between each adjacent stations. Now you have to select 10 stations(means 10 hops) among those 100 stations in such a way that maximum of distance between any 2 hops will be minimised. By default 1 and 100 stations are selected , so you need to choose only 8 more stations.

Here n=100 I have chosen but n can be large( so bruteforce won't work ).
  • Проголосовать: нравится
  • +8
  • Проголосовать: не нравится

»
7 лет назад, # |
  Проголосовать: нравится +3 Проголосовать: не нравится

Are posting this as a challenge or a question?

The tag suggests that you know how to solve it!

  • »
    »
    7 лет назад, # ^ |
    Rev. 2   Проголосовать: нравится +8 Проголосовать: не нравится

    No, a question!!

    I thought of choosing distance as binary search, see if using that as max distance, how many police stations I get? If less than 10( including 1st and last ), then I increase distance or I decrease distance and so on..

    However, I guess it doesn't minimise maximum distance between any two police station. Maybe I am missing something, if you could guide me?

    • »
      »
      »
      7 лет назад, # ^ |
        Проголосовать: нравится +21 Проголосовать: не нравится

      In binary search fix max allowed distance, the go from left to right greedily so that each distance <= mx. If you used <= 10 stations the this max distance is possible, otherwise not. So using bin.search you minimie it

»
7 лет назад, # |
Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

This problem can be modeled similar to this problem — https://www.codechef.com/MARCH17/problems/SCHEDULE/

You can consider the stations as 1's and distance as zeroes and can do a binary search. Of course you need not necessarily construct a string . A simple binary search would be enough.

In binary search the parameters would be l=0 and r=sum of distances between consecutive stations in the initial arrangement.