Constraints पढ़ें, Complexity चुनें

हर समस्या n और मानों की सीमाएँ बताती है। ये सीमाएँ चुपचाप संकेत देती हैं कि प्रश्न बनाने वाला किस जटिलता की अपेक्षा करता है। 🔍

कुछ भी डिज़ाइन करने से पहले सीमाओं में दिया गया सबसे बड़ा n ढूँढ़िए। n का आकार तय करता है कि द्विघाती, रैखिक या लघुगणकीय तरीका आवश्यक है।

जब n अधिकतम 20 हो, तो घातांकीय हर-संभावना-जाँच वाला तरीका भी चल जाता है। छोटी सीमाएँ बिना डर हर संयोजन आज़माने का निमंत्रण होती हैं।

यदि n कुछ सौ तक पहुँचता है, तो O(n^3) वाला समाधान अभी भी सफल हो जाता है। यहाँ तीन लूप या युग्मों पर आधारित मूल DP उचित विकल्प हैं।

n = 5000 के आसपास O(n^2) का लक्ष्य रखिए। ऐरे पर नेस्टेड लूप लगभग 2.5 गुना 10^7 चरण लेते हैं, जो अभी भी बजट में आ जाते हैं।

जब n 10^5 या 10^6 तक पहुँचता है, तो आपको O(n log n) या O(n) चाहिए। क्रमबद्ध करना, संचयी योग और दो संकेतक आपके मुख्य औज़ार बन जाते हैं।

यदि n एक अरब है, तो n पर चलने वाला कोई लूप सफल नहीं होगा। गणित या उत्तर पर द्विआधारी खोज का उपयोग करके आपको O(log n) या O(1) का होना चाहिए।

मानों की सीमाएँ भी महत्वपूर्ण हैं। बड़ी संख्याएँ दूसरी भाषाओं में अतिप्रवाह की चेतावनी देती हैं और मॉड्यूलर अंकगणित का संकेत दे सकती हैं।

बहु-परीक्षण वाली समस्याएँ अक्सर हर n के बजाय n के योग की सीमा देती हैं। इसे ध्यान से पढ़िए, क्योंकि इससे तय होता है कि आपके लूप सुरक्षित रूप से कितने बड़े हो सकते हैं।

n के आधार पर लक्ष्य जटिलता चुनिए, फिर ऐसा एल्गोरिद्म चुनिए जो उसे प्राप्त करे। n को डिज़ाइन का मार्गदर्शक बनने देना अनुमान लगाकर बाद में दोबारा लिखने से बेहतर है।

इस तालिका को याद रखिए। सीमा-से-जटिलता का मानचित्र प्रतियोगिता के दौरान सीमाओं पर एक त्वरित नज़र को तुरंत योजना में बदल देता है।

अब आप सीमाओं को लक्ष्य के रूप में पढ़ते हैं: छोटा n हर-संभावना-जाँच की अनुमति देता है, 10^5 के लिए n log n चाहिए और 10^9 के लिए log या गणित चाहिए। n को तरीका चुनने दीजिए। 🗺️