एबीबीवाई कप: डिब्रीफिंग

ABBYY के चालाक बीवर लंबे समय से रिसर्च इंस्टीट्यूट ऑफ साइटोलॉजी एंड जेनेटिक्स में सहयोग कर रहे हैं। हाल ही में, इस शोध संस्थान के कर्मचारियों ने बेवर को एक नया कार्य करने की पेशकश की। समस्या का सार इस प्रकार था।

एन प्रोटीन का एक सेट है (जरूरी नहीं कि अलग हो)। प्रत्येक गिलहरी एक तार है जिसमें लैटिन वर्णमाला के छोटे अक्षर होते हैं। स्मार्ट बीवर के वैज्ञानिकों द्वारा चुनौती दी गई है कि प्रोटीन के मूल सेट से पावर k का सबसेट चुनें और प्रोटीन के चुने हुए सबसेट का प्रतिनिधित्व अधिकतम होना चाहिए।

ABBYY के चतुर बीवर ने एक छोटा अध्ययन किया और इस निष्कर्ष पर पहुंचे कि प्रोटीन के एक समूह की प्रतिनिधित्वशीलता का मूल्यांकन एक ही संख्या के साथ किया जा सकता है, जिसकी गणना करना काफी सरल है। मान लीजिए कि हमारे पास प्रोटीनों का वर्णन करने वाली k लाइनों की { a ₁ , ..., a _k } का सेट है। इस सेट की प्रतिनिधित्व मात्रा निम्नलिखित है:
जहाँ f ( x , y ) लाइनों x और y के सबसे बड़े सामान्य उपसर्ग की लंबाई है; उदाहरण के लिए, f ("abc", "abd") = 2, और f ("ab", "bcd") = 0. इस प्रकार, प्रोटीन के समुच्चय का निरूपण {"abc", "abd", "abe"} 6 , और सेट {"आ", "बा", "बा"} - 2।

इस खोज के बाद, एबीबीवाई क्लेवर बीवर ने कप प्रतिभागियों से एक कार्यक्रम लिखने के लिए कहा, जो कि दिए गए प्रोटीन के सेट से चुनता है जिसमें सबसे अधिक संभव प्रतिनिधि मूल्य है। उसे इस समस्या को हल करने में मदद करें!

समस्या के पूर्ण समाधान के लिए तुरंत आगे बढ़ें। आइए लाइनों को क्रमबद्ध रूप से क्रमबद्ध करें और lcp [ i ] - लाइनों की सबसे बड़ी सामान्य उपसर्ग की लंबाई i और i + 1. यह साबित करना आसान है कि किसी भी दो लाइनों i और j का सबसे बड़ा सामान्य उपसर्ग अब min ( lpp [ i ], lcp [ i + 1] है) , ..., lcp [ j - 1]) (प्रत्यय सरणी का उपयोग करते समय एक समान कथन का उपयोग किया जाता है)। यह मददगार है।

अब डायनामिक प्रोग्रामिंग विधि लागू करें। हम इस तरह की एक डीपी बनाते हैं: एफ ( i , j , k ) समस्या का अधिकतम संभव उत्तर है यदि वास्तव में k लाइनों को लाइनों के साथ संख्याओं i से चुना जाना है ... j । संक्रमण इस प्रकार है: हम न्यूनतम lcp [ p ], फिर F ( i , j , k ) = अधिकतम _{q = 0 ... k} ( F ( i , p , q ) + F ( p +) के साथ i : j - 1 को न्यूनतम pcp के साथ स्थिति p पर पाते हैं। 1, j , k - q ) + q · ( k - q ) · lcp [ p ]), अर्थात, हम मानते हैं कि q को पंक्तियों से i ... p , k - q पंक्तियों से p + 1 ... j , और के लिए चुना जाता है। इन पंक्तियों के सभी जोड़ों में, सबसे बड़े सामान्य उपसर्ग की लंबाई lcp [ p ] है (यह पहले पैराग्राफ में कथन से निम्नानुसार है)।

ऐसा निर्णय 50 अंक प्राप्त करने के लिए पर्याप्त है। अब तक, ऐसा लगता है कि इस समाधान की जटिलता ओ ( एन ⁴ ) के आदेश की है। यह दर्शाता है कि वास्तव में इस समाधान को लागू करना संभव है, ताकि इसकी जटिलता ओ ( एन ² ) के बराबर हो। इसके साथ शुरू करने के लिए, हम ध्यान दें कि अलग-अलग सेगमेंट i ... j जिस पर हम फ़ंक्शन एफ के मूल्यों में रुचि रखते हैं, वास्तव में वास्तव में 2% हैं। 1, ओ ( एन ² ) नहीं। ऐसा क्यों है यह हमारे डीपी के संक्रमण से समझा जा सकता है। खंड 1 ... एन को दो खंडों में विभाजित किया गया है 1 ... पी और पी + 1 ... एन , इनमें से प्रत्येक खंड को दो और खंडों में विभाजित किया गया है, और इसी तरह; हम देखते हैं कि किसी भी i के लिए I और I + 1 के पदों के बीच में एक बार DP की पूरी गणना के लिए "कट" होगा, और यह कट दो नए सेगमेंट उत्पन्न करेगा जिसमें हम DP के मानों में रुचि रखते हैं। यहां से हमें आवश्यक खंडों के 2 एन - 1 का अनुमान मिलता है, इसलिए, हमारे समाधान में पहले से ही ओ ( एन ³ ) से अधिक जटिलता नहीं है।

अंतिम और सबसे कठिन बात यह अनुमान लगाना है कि उपरोक्त समाधान में जटिलता ओ ( एन ² ) हो सकती है। उदाहरण के लिए, आप इसे इस तरह से लागू कर सकते हैं। आइए एक पुनरावर्ती फ़ंक्शन F ( i , j ) प्राप्त करें जो लंबाई की एक सरणी देता है j - i + 2 - वास्तव में DP मान F ( i , j , k ) (यह स्पष्ट है कि हम केवल 0 से j - i + 1 के अंतराल से कश्मीर के मूल्यों में रुचि रखते हैं। )। इस फ़ंक्शन के अंदर, हम निम्न कार्य करते हैं: p ढूंढें, F ( i , p ) और F ( p + 1, j ) को कॉल करें, अब 0 से p - i + 1 तक का पुनरावृति x , 0 से j - p के लिए iterate y और मान F को अपडेट करें। ( i , j , x + y ), अगर इसमें सुधार हुआ है (आप लेखक के समाधान में अधिक देख सकते हैं, तो वहां सब कुछ बहुत पारदर्शी है) फ़ंक्शन एफ का अधिकतम ऑपरेटिंग समय, अंतराल पर बुलाया जाता है ... जे की लंबाई जे - आई + 1 = एन , टी ( एन ) = अधिकतम _{एक्स = 1 .. एन - 1} ( टी ( एक्स ) + टी ( एन - एक्स ) के रूप में लिखा जा सकता है _। + ( X + 1) · ( N - X + 1))। यह समझना बाकी है कि टी ( एन ) = ओ ( एन ² )। यह किया जा सकता है, उदाहरण के लिए, टी की गणना करने के लिए एक साधारण डीपी लिखकर । यदि आप इसके बारे में सोचते हैं, तो आप इसे इस तरह से समझ सकते हैं: जब हम x = 0 ... p - i - 1 और y = 0 ... j - p के माध्यम से लूप करते हैं, तो कल्पना करें कि हम कुछ पंक्तियों के माध्यम से छांटते हैं: x = i ... p और y = p + 1 ... j (यहां, x और y से अधिक पुनरावृति एक पुनरावृत्ति को कम कर देती है, लेकिन यह महत्वपूर्ण नहीं है); फिर डीपी की पूरी गणना के लिए प्रत्येक जोड़ी लाइनों को एक बार ठीक किया जाएगा, जो हमें अंतिम जटिलता ओ ( एन ² ) देता है।

यहां आप लेखक का समाधान पा सकते हैं।

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