एल्गोरिथ्म्स और डेटा स्ट्रक्चर्स

उत्तर पर बाइनरी सर्च (Binary Search the Answer) - पेड़ों को विरल तरीके से लगाना

दिए गए n स्थानों (spots) में आप पेड़ लगाना चाहते हैं, और लक्ष्य यह है कि ये पेड़ एक-दूसरे से यथासंभव दूर हों, ताकि आने वाले वर्षों में वे एक-दूसरे को बाधित न करें। इन स्थानों के निर्देशांक (coordinates) पूर्णांक के रूप में दिए गए हैं।
आपकी जिम्मेदारी है कि यदि आप इन n में से t पेड़ लगाएं, तो उन पेड़ों के बीच की न्यूनतम दूरी यथासंभव अधिकतम हो। अंत में, आपको पेड़ों के बीच की वह न्यूनतम दूरी निकालनी है जो संभव हो सके।

इनपुट

इनपुट की पहली पंक्ति में दो पूर्णांक n (1 ≤ n ≤ 100 000) और t (2 ≤ t ≤ n) दिए होते हैं, जहाँ n पेड़ लगाने के संभावित स्थानों की संख्या है और t वह संख्या है जितने पेड़ आपको लगाने हैं।
अगली पंक्ति में n विलग (distinct) पूर्णांक (0 ≤ ≤ ) दिए होते हैं, जो पेड़ लगाने के संभावित स्थानों के निर्देशांक हैं।

आउटपुट

प्रोग्राम को एक पूर्णांक d छापना चाहिए, जो उन पेड़ों के बीच की न्यूनतम दूरी को दर्शाता है (जब पेड़ यथासंभव विरल तरीके से लगाए गए हों)।

उदाहरण

इनपुट
आउटपुट
5 3 1 2 8 4 9
3

स्पष्टीकरण

हम पेड़ 1, 4, और 9 पर लगाते हैं, तो न्यूनतम दूरी 4 - 1 = 3 बनती है।
 

ट्यूटोरियल

इस समस्या का समाधान “उत्तर पर बाइनरी सर्च” (binary search on the answer) करके किया जा सकता है। इस पद्धति में हम उस संभावित मान (पेड़ों के बीच की न्यूनतम दूरी) पर द्विआधारी खोज करते हैं और प्रत्येक चरण में जाँचते हैं कि क्या दिए गए अंतर पर पेड़ लगाना संभव है या नहीं। यह करने के लिए कुछ अहम शर्तें पूरी होनी चाहिए:
  • हमें दिए गए संभावित उत्तर के लिए यह जाँचने में सक्षम होना चाहिए कि क्या वह समस्या के अनुरूप है (जैसे, किसी दूरी d के लिए चेक कर सकें कि क्या पेड़ों को कम से कम d की दूरी पर लगाना संभव है)।
  • जाँचने वाली फ़ंक्शन def check(x): सत्य (True) लौटाएगा यदि उसे दिए गए x के साथ पेड़ लगाना संभव है, अन्यथा असत्य (False)।
  • अलग-अलग मूल्यों के लिए यह फ़ंक्शन दो तरह के पैटर्न दे सकता है:
    • False False False True True (impossible for the first several numbers and then possible for larger ones). In this case, we’re looking for the first True (the smallest valid value).
    • True True True True False False (possible for small numbers and impossible for larger ones). In this case, we’re looking for the last True (the largest valid value).
      • In our case, we would like to plant the trees as sparsely as possible. So, we would like the minimum distance to be as large as possible. If it’s possible to plant trees with a minimum distance of x, then it’s definitely possible to plan them denser and get a smaller x. Therefore, in our case, the values of the checking function will be True True True True False False and we aim to find the last True in this list (the largest (most sparse) minimal distance between the planted trees).
 
- False False False True True (जिसमें छोटे मानों पर असंभव, और बड़े मानों पर संभव होता है)। उस स्थिति में हमें पहला True ढूंढना होता है।
- True True True True False False (जिसमें छोटे मानों पर संभव, पर बहुत बड़े मानों पर असंभव होता है)। इस स्थिति में हमें अंतिम True का मान चाहिए।
 
हमारे मामले में, हम पेड़ों के बीच की दूरी को यथासंभव अधिक रखना चाहते हैं, यानी अगर किसी दूरी x पर पेड़ लगाना संभव है, तो उससे छोटी दूरी पर पेड़ लगाना निश्चित ही संभव होगा। ऐसे में जाँच फ़ंक्शन का पैटर्न True True True True False False जैसा होगा, और हमें सबसे आख़िरी True को खोजने की ज़रूरत होगी (अर्थात, वह अधिकतम दूरी जो अब भी संभव हो)।
n, t = ...
x = sorted(x)

def check(d):
    """ चेक करें कि क्या हम t पेड़ों को कम से कम d की दूरी पर लगा सकते हैं """
    planted = 0               # हमें t पेड़ लगाने हैं (अभी 0 लगाए)
    prev = float('-inf')      # पिछले लगाए गए पेड़ का निर्देशांक
    for xi in x:
        if xi - prev >= d:    # अगर हम xi पर अगला पेड़ लगा सकते हैं
            planted += 1
            prev = xi
    return planted >= t
ऊपर दिए गए जाँच फ़ंक्शन का उपयोग करके, हम बाइनरी सर्च के ज़रिए सबसे अच्छा (अधिकतम) ‘न्यूनतम अंतर’ निकाल सकते हैं:
l, r = 1, max(x)         # संभावित उत्तर का दायरा [l; r) में
while r - l > 1:         # जब तक बीच में चेक करने लायक कम से कम एक मान बचा हो
    mid = (l + r) // 2   # बीच का मान लें
    if check(mid):       # अगर mid अंतर पर पेड़ लगाना संभव है => l = mid
        l = mid
    else:                # नहीं तो r = mid
        r = mid

print(l)
 

Constraints

Time limit: 4 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue