हैश टकराव (Hash Collisions)
हैश फंक्शन पूरी तरह से परफेक्ट नहीं होते; कभी-कभी बिल्कुल अलग-अलग डेटा भी एक ही हैश रिज़ल्ट दे सकते हैं। यह इनपुट और हैश वैल्यू के बीच बनाए गए एक-से-एक (one-to-one) संबंध को तोड़ देता है। इसका मतलब है कि अलग-अलग स्ट्रिंग्स को एक ही हैश वैल्यू मिल सकती है या फिर दो संख्याओं की जोड़ी (a, b) का हैश एक ही हो सकता है। ऐसे हैश टकराव (collisions) से, जिस संदर्भ में वे होते हैं, सुरक्षा से जुड़ी समस्याएँ और परफॉर्मेंस से जुड़े मुद्दे पैदा हो सकते हैं। उदाहरण के लिए, एक साधारण हैश फ़ंक्शन जो (a, b) जोड़ियों को हैश वैल्यू में बदलता है, कई सारी (a, b) जोड़ियों को एक ही हैश वैल्यू पर मैप कर सकता है:
नीचे
(a, b) की कुछ उदाहरण जोड़ियाँ दी गई हैं, जो इसी हैश फ़ंक्शन के तहत एक ही हैश वैल्यू पर पहुँचती हैं:- h(1, 1) = (1997 + 1) mod 5077 = 1998
- h(1, 5078) = (1997 + 5078) mod 5077 = 1998
- h(5078, 1) = (10140766 + 1) mod 5077 = 1998
- …
इसलिए, अगर हमारे पास (a, b) जोड़ियों की कोई ऐसी सूची है, जिन्हें जानबूझकर समान हैश पैदा करने के लिए चुना गया हो, तो हमें बहुत से टकराव देखने को मिल सकते हैं। इसका नतीजा यह हो सकता है कि किसी मान को खोजने या यह जाँचने में कि क्या कोई (a, b) जोड़ी सूची में मौजूद है, हमें ज़्यादा समय लग जाए या गलत नतीजे भी मिलें — यह इस्तेमाल किए गए डेटा स्ट्रक्चर या एल्गोरिथ्म पर निर्भर करता है।
हैश टकराव सुरक्षा में भी कमज़ोरियाँ पैदा कर सकते हैं। आमतौर पर यूज़र पासवर्ड्स को सुरक्षा कारणों से हैश के रूप में स्टोर किया जाता है (ताकि अगर डेटा베स में सेंध भी लग जाए, तो पासवर्ड सीधे लीक न हों)। यदि हैश फ़ंक्शन ठीक तरह से काम नहीं करता और बहुत से टकराव पैदा करता है, तो हमलावर वास्तविक पासवर्ड का अंदाज़ा लगाए बिना ही अकाउंट हैक कर सकता है। अगर किसी रैंडम पासवर्ड का हैश किसी असली पासवर्ड के हैश से मिल जाता है, तो सिस्टम उसी यूज़र के तौर पर उसे मान लेगा।
एक अच्छा हैश फ़ंक्शन टकराव की संभावना को कम से कम रखने की कोशिश करता है। अक्सर, रैंडम इनपुट पर इस्तेमाल होने वाले बिल्ट-इन हैश फ़ंक्शन्स काफ़ी अच्छा काम करते हैं। फिर भी, अगर इनपुट डेटा किसी ख़ास प्रकार का हो या समस्या की कोई विशेष माँग हो, तो आपको अपना कस्टम हैश फ़ंक्शन बनाना पड़ सकता है।
चुनौती: टकराव की जाँच (Check for Collisions)
आपको एक ऐसे हैश फ़ंक्शन
h के बारे में जाँच करनी है, जो दो पूर्णांकों (a, b) को एक इंटीजर में मैप करता है। प्रोग्राम को देखना है कि क्या इस फ़ंक्शन में टकराव होता है, और अगर कोई टकराव नहीं है तो “Yes” प्रिंट करना है, वरना “No”।इनपुट (Input)
इनपुट की पहली पंक्ति में एक पूर्णांक
n (1 ≤ n ≤ 10 000) होगा, जो जोड़ों की संख्या बताएगा।अगली
n पंक्तियों में अंतराल से अलग किए गए (a_i, b_i) पूर्णांक होंगे (0 ≤ a_i, b_i ≤ 10^9)। यह गारंटी है कि दी गई (a_i, b_i) जोड़ियाँ एक-दूसरे से अलग होंगी।आउटपुट (Output)
यदि दिए गए इनपुट के लिए
h(a, b) फ़ंक्शन में कोई टकराव नहीं होता है, तो प्रोग्राम “Yes” प्रिंट करे; अन्यथा “No”।उदाहरण (Examples)
Input | Output |
3
0 4
1 5
2 9 | Yes |
2
0 0
0 1
542313474 3 | No |
Constraints
Time limit: 2 seconds
Memory limit: 512 MB
Output limit: 1 MB