क्योंकि इस रूप में, सम्मेलन के प्रतिभागियों ने उनके साथ संघर्ष किया और क्योंकि अंग्रेजी हाइड्रा की आधिकारिक भाषा थी। कार्य इस प्रकार दिखते हैं:

5:53 पर शुरू, केवल 4 मिनट:

और यहाँ है कि कैसे उन लोगों के साथ एक फ्लिपकार्ट ने अपना निर्णय लिया:

सतह पर, इस तरह का एक समाधान है: सभी प्रतिकृतियों के वजन का योग, सभी भारों के योग में 0 से एक यादृच्छिक संख्या उत्पन्न करें, फिर एक i-प्रतिकृति चुनें, ताकि प्रतिकृति का योग 0 से (i-1) वें तक का यादृच्छिक संख्या से कम हो, और प्रतिकृति वजन का योग। 0 से i-th तक - इससे अधिक। यह एक प्रतिकृति चुनने के लिए निकलेगा, और अगले एक का चयन करने के लिए, आपको चयनित प्रतिकृति पर विचार किए बिना पूरी प्रक्रिया को दोहराने की आवश्यकता होगी। इस तरह के एक एल्गोरिथ्म के साथ, एक प्रतिकृति को चुनने की जटिलता ओ (एन) है, के प्रतिकृतियां चुनने की जटिलता हे (एन · के) ~ ओ (एन ² ) है।

द्विघात जटिलता खराब है, लेकिन इसमें सुधार किया जा सकता है। ऐसा करने के लिए, वजन के क्षेत्रों के लिए खंडों का एक पेड़ बनाएं। यह लॉग एन की गहराई के साथ एक पेड़ का उत्पादन करेगा, जिसके पत्तों में प्रतिकृति भार होंगे, और शेष नोड्स में आंशिक रकम, पेड़ की जड़ में सभी वजन के योग तक। इसके बाद, हम 0 से सभी वेट के योग तक एक यादृच्छिक संख्या उत्पन्न करते हैं, ith प्रतिकृति ढूंढते हैं, इसे पेड़ से हटाते हैं, और शेष प्रतिकृतियों की खोज करने के लिए प्रक्रिया दोहराते हैं। इस तरह के एक एल्गोरिथ्म के साथ, एक पेड़ बनाने की जटिलता ओ (एन) है, आईथ प्रतिकृति खोजने और इसे पेड़ से हटाने की जटिलता ओ (लॉग एन) है, के प्रतिकृतियां चुनने की जटिलता हे (एन + लॉग एन) ~ ओ (एन लॉग एन) ।

रैखिक-लॉगरिदमिक जटिलता द्विघात जटिलता की तुलना में अच्छा है, विशेष रूप से बड़े के लिए।

यह एल्गोरिथ्म वोस्टोक परियोजना से क्लस्टर क्लस्टर लाइब्रेरी के कोड में लागू किया गया है ।

34:50 पर शुरू करें, केवल 6 मिनट:

समाधान सतह पर है: सभी दस्तावेजों को क्रमबद्ध करें (उदाहरण के लिए, क्विकॉर्ट का उपयोग करके), फिर एन + एस दस्तावेज लें। इस मामले में, औसतन सॉर्टिंग की जटिलता ओ (एम एलजी एम) है, सबसे खराब में - ओ (एम ² )।

जाहिर है, तब सभी एम दस्तावेजों को छांटना तब उनमें से केवल एक छोटा सा हिस्सा लेना ही अक्षम है। सभी दस्तावेजों को क्रमबद्ध नहीं करने के लिए, क्विकसेक एल्गोरिथ्म उपयुक्त है , जो आवश्यक दस्तावेजों के एन + एस का चयन करता है (उन्हें किसी भी एल्गोरिथ्म द्वारा क्रमबद्ध किया जा सकता है)। इस मामले में, जटिलता औसत ओ (एम) तक घट जाती है, और सबसे खराब स्थिति वही रहती है।

हालांकि, आप इसे और भी अधिक कुशलता से कर सकते हैं - बाइनरी हीप स्ट्रीमिंग एल्गोरिथ्म का उपयोग करें। इस मामले में, पहले एन + एस दस्तावेजों को न्यूनतम या अधिकतम-ढेर (छंटाई की दिशा के आधार पर) में जोड़ा जाता है, और फिर प्रत्येक बाद के दस्तावेज़ की तुलना पेड़ की जड़ से की जाती है, जिसमें इस समय न्यूनतम या अधिकतम दस्तावेज़ शामिल हैं, और यदि आवश्यक हो तो पेड़ में जोड़ा जाता है। । इस मामले में, सबसे खराब स्थिति में जटिलता तब होती है जब आपको पेड़ को लगातार पुनर्निर्माण करना पड़ता है - ओ (एम एलजी (एन + एस)), औसत जटिलता ओ (एम) है, जैसे कि एक्सीलेक्ट।

हालांकि, इस तथ्य के कारण हीप स्ट्रीमिंग अधिक प्रभावी है, क्योंकि इसके मूल तत्व के साथ एक तुलना के बाद, अधिकांश दस्तावेजों को ढेर के पुनर्निर्माण के बिना त्याग दिया जा सकता है। सर्किट में विकसित और उपयोग किए जाने वाले ज़ेबरा दस्तावेज़ इन-मेमोरी डेटाबेस में इस तरह की छंटनी लागू की जाती है।

सतह पर एक समाधान: पहले और दूसरे तत्व के राज्यों का आदान-प्रदान, फिर पहला और तीसरा, फिर पहला और चौथा, और इसी तरह। प्रत्येक विनिमय के बाद, एक तत्व की स्थिति वांछित स्थिति में होगी। आपको O (N) क्रमपरिवर्तन करना होगा और O (N · M) समय बिताना होगा।

रैखिक समय एक लंबा समय है, इसलिए आप जोड़े में तत्वों की स्थिति का आदान-प्रदान कर सकते हैं: पहले के साथ दूसरा, चौथे के साथ तीसरा, और इसी तरह। प्रत्येक विनिमय के बाद, प्रत्येक दूसरे तत्व की स्थिति वांछित स्थिति में होगी। हमें O (log N) क्रमपरिवर्तन करना होगा और O (M log N N) समय बिताना होगा।

हालांकि, आप बदलाव को और अधिक प्रभावी बना सकते हैं - रैखिक में नहीं, बल्कि निरंतर समय में। ऐसा करने के लिए, पहले चरण में, आपको पहले तत्व की स्थिति को अंतिम के साथ बदलने की जरूरत है, दूसरे को दंड के साथ, और इसी तरह। अंतिम तत्व की स्थिति वांछित स्थिति पर होगी। और अब आपको दूसरे तत्व की स्थिति को अंतिम, तीसरे के साथ तब्दील करने की आवश्यकता है। एक्सचेंजों के इस दौर के बाद, सभी तत्वों के राज्य सही स्थिति में होंगे। कुल में, O (2M) ~ O (1) क्रमपरिवर्तन किया जाएगा।

ऐसा समाधान एक गणितज्ञ को आश्चर्यचकित नहीं करेगा जो अभी भी याद करता है कि रोटेशन दो अक्षीय समरूपता की एक रचना है। वैसे, यह तुच्छ रूप से सामान्यीकृत है, न कि के <एन पदों द्वारा। (ठीक इसी तरह से टिप्पणियों में लिखें।)