IOI2012 के साथ एक कार्य को पार्स करना

सभी को नमस्कार! सितंबर में, अंतर्राष्ट्रीय प्रोग्रामिंग ओलंपियाड, IOI 2012 आयोजित किया गया था। और हम, रूसी टीम, इसे बहुत सफलतापूर्वक चला गया , जैसा कि आप देख सकते हैं।

मैं मैक्स अख्मेडोव हूं। मुझे जनता के साथ साझा करने की पेशकश की गई कि इस तरह की प्रतियोगिताएं क्या हैं और हमें किन कार्यों को हल करना है। मैं "जॉशिंग टूर्नामेंट" के दूसरे दौर के अंतिम कार्य के बारे में बात करूंगा। हालत का एक अंग्रेजी संस्करण यहां पाया जा सकता है । वैसे, यह उस दिन के तीन कार्यों में से सबसे सरल है :-)

किंवदंती

यह कार्य मिलान के गवर्नर, ड्यूक ऑफ़ लोदोविको सफ़्ज़ा और ड्यूक ऑफ़ बीट्राइस डी'एस्टे के सगाई समारोह के बारे में है, जो 1491 में हुआ था। ड्यूक ने अपने अच्छे दोस्त लियोनार्डो दा विंची को उत्सव का आयोजन करने और सांस्कृतिक कार्यक्रम का प्रबंधन करने के लिए आमंत्रित किया, जिसने उन्हें विशेष रूप से एक ठाठ नाइट की व्यवस्था की। टूर्नामेंट।

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

ऐसी रोमांचक कहानी।

औपचारिक स्थिति

नाइट टूर्नामेंट इस प्रकार है। एक पंक्ति में शूरवीरों की एक संख्या है। प्रत्येक अगली लड़ाई से पहले, एक न्यायाधीश बाहर निकलता है और पदों में खड़े शूरवीरों को कॉल करता है जो एक निरंतर खंड को एक द्वंद्वयुद्ध में बनाते हैं, जिसके परिणामस्वरूप विजेता निर्धारित होता है। विजेता अपनी जगह पर लौटता है, और हारने वाले शूरवीर बाहर निकल जाते हैं। इसके बाद, कई शूरवीर चलते हैं, खाली स्थान लेते हैं। औपचारिक रूप से: एक पंक्ति में N शूरवीर होते हैं, जज दो नंबर l और r का नाम देता है, जिसके बाद शूरवीर, जो बाएं से दाएं की ओर जाने के क्रम में l से r तक के स्थानों पर कब्जा कर लेता है, लड़ाई करता है और केवल विजेता पंक्ति में रहता है। उसके बाद, बाद की लड़ाइयां उसी सिद्धांत पर होती हैं, जब तक कि केवल एक शूरवीर न बचा हो, जिसे टूर्नामेंट का विजेता घोषित किया जाता है।

फिलहाल, सभी N - 1 शूरवीरों, एक को छोड़कर, पहले से ही पंक्ति में अपने स्थान ले चुके हैं। लियोनार्डो के पास शुरुआत या अंत सहित, पंक्ति में किसी भी स्थान पर पसंदीदा पहुंचने का अवसर है। लड़ाइयों का क्रम और उनमें भाग लेने वाले शूरवीरों के पदों का निर्धारण पहले ही किया जा चुका है। लियोनार्डो प्रत्येक नाइट के लिए अपने सार "शक्ति" के मूल्य को जानता है, जिसे 0 से N तक पूर्णांक के रूप में व्यक्त किया जाता है - 1. इस कार्य के हिस्से के रूप में, यह माना जाता है कि युद्ध में जिसमें कुछ शूरवीर भाग लेते हैं, वह जो सबसे अधिक जीतता है बलों। ऐसा हुआ कि एक टूर्नामेंट में सभी शूरवीरों की ताकत अलग-अलग होती है, अर्थात किसी भी लड़ाई में विजेता को उनके अर्थों के ज्ञान के आधार पर स्पष्ट रूप से निर्धारित किया जाता है। लियोनार्डो यह सुनिश्चित करना चाहता है कि, टूर्नामेंट के परिणामों के अनुसार, जितने लड़ाइयों में भीड़ की पसंदीदा जीत संभव है, और सभी पदों से इस तरह के परिणाम के लिए, वह सबसे बाईं ओर का चयन करना चाहता है। कृपया ध्यान दें: हमारे शूरवीर के लिए पूरे टूर्नामेंट का विजेता बनना आवश्यक नहीं है! यह उन लड़ाइयों की संख्या को अधिकतम करने के लिए पर्याप्त है जिनसे वह विजयी हुईं।

आइए एक उदाहरण देखें। बता दें कि 5 नाइट टूर्नामेंट में भाग लेते हैं। पंक्तियों में खड़ी शूरवीरों में शक्ति मान होता है [1, 0, 2, 4] जब बाएं से दाएं देखा जाता है। जैसा कि आप देख सकते हैं, एक लेट नाइट में ताकत का एक मान होता है 3. मान लीजिए, उदाहरण के लिए, एक टूर्नामेंट में तीन राउंड होते हैं, जो कि पदों (2, 4), (1, 2) और (1, 2) की विशेषता होती है। आइए हम इसका मतलब बताते हैं।

• पहले में, शूरवीर लड़ रहे हैं, दूसरे से बाएं से चौथे से स्थानों पर खड़े हैं।
• शेष शूरवीरों के दूसरे भाग में, वे दो जो पहले बाईं ओर और दूसरे स्थान पर बाईं ओर खड़े होंगे।
• अंतिम दौर में, शेष दो शूरवीर मिलेंगे, पहली बाईं तरफ और दूसरी बाईं तरफ।

इस तरह के टूर्नामेंट को पेड़ के रूप में अधिक स्पष्ट रूप से प्रदर्शित किया जा सकता है:

इसके अलावा, हम इसी तरह के पेड़ों पर लौट आएंगे।

हम समझेंगे कि टूर्नामेंट की तस्वीर कैसे दिखेगी, उदाहरण के लिए, लियोनार्डो अन्य सभी शूरवीरों के बाईं ओर एक पसंदीदा डालता है। प्रारंभ में, शूरवीरों की शक्ति का मान बाएं से दाएं [3, 1, 0, 2, 4] के रूप में दिखता है।

• पहले दौर में, 1, 0 और 2 के साथ शूरवीर लड़ेंगे। विजेता 2 शक्ति के साथ एक शूरवीर होगा, वह अपनी जगह पर लौट आएगा, और पंक्ति [3, 2, 4] की तरह दिखाई देगी।
• दूसरे दौर में, हमारा पसंदीदा शक्ति 3 और ताकत के साथ एक शूरवीर के साथ लड़ेगा। भीड़ में से पसंदीदा विजयी होगा, वह वापस आ जाएगा, और पंक्ति [3, 4] की तरह दिखाई देगी।
• अंतिम दौर में, हमारा पसंदीदा 4 की ताकत के साथ शूरवीर से हार जाएगा, जो टूर्नामेंट का विजेता बन जाएगा।

इस प्रकार, हमारे शूरवीर रिटायर होने से पहले केवल एक लड़ाई जीतेंगे। सबसे अच्छा समाधान यह होगा कि उसे 1 और 0 रैंक के शूरवीरों के बीच एक स्थिति में रखा जाए, जिससे [1, 3, 0, 2, 4] की श्रृंखला बने।

• पहले दौर में, वह 0 और 2 की सेनाओं के साथ एक लड़ाई में भाग लेगा, जिसमें से वह विजयी होगा। कई शूरवीरों के पास अब रूप [1, 3, 4] है।
• दूसरे दौर में, वह 1 की ताकत के साथ लड़ेगा, जिसे वह हराएगा।
• तीसरे दौर में, वह 4 के बल द्वारा टूर्नामेंट के विजेता से हार जाता है।

नतीजतन, पसंदीदा दो लड़ता है।

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

कार्यक्रम को प्राप्त होने वाले अंकों की संख्या निर्णय की प्रभावशीलता पर निर्भर करती है। यदि यह उन परिस्थितियों में एक सेकंड में सही उत्तर प्राप्त करने के लिए पर्याप्त तेजी से काम करता है जहां शूरवीरों की संख्या 500 से अधिक नहीं है, तो समाधान 100 में से 17 अंक प्राप्त करेगा। यदि यह 5000 तक पहुंचने वाले शूरवीरों की संख्या के साथ सही उत्तर की गणना करने का प्रबंधन करता है, तो इसका अनुमान 49 पर लगाया जाएगा। अंक। पूर्ण स्कोर प्राप्त करने के लिए, निर्णय के लिए टूर्नामेंटों को संसाधित करने का समय होना चाहिए, जिसमें एक लाख शूरवीरों तक शामिल हैं। हमारी टीम में, सभी चार लोगों ने समाधान लिखे जिसमें 100 अंक प्राप्त हुए - गोल पर कार्य सबसे आसान था।

माथे का फैसला

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

इस तरह के निर्णय को परीक्षणों के पहले समूह को पारित करना चाहिए जिसमें शूरवीरों की संख्या पांच सौ से अधिक नहीं है। आइए अनुमान लगाएं कि कार्यक्रम द्वारा किए गए संचालन की संख्या के क्रम की गणना करके यह कितना काम करेगा। प्रत्येक दौर में, सबसे खराब स्थिति में, हमें लगभग सभी शूरवीरों को बाईं ओर स्थानांतरित करने की आवश्यकता होती है, खाली स्थानों में भरना, अर्थात, श्रृंखला की लंबाई के लिए आनुपातिक संचालन की संख्या के लिए सबसे खराब मामलों की प्रक्रियाओं में एक गोल कार्यक्रम, जिसमें औसतन लगभग बोल, एन / 2 शूरवीर होते हैं। टूर्नामेंट में सबसे खराब स्थिति में राउंड एन - 1 के रूप में कई हो सकते हैं, और हमें अभी भी कई एन संभावित टूर्नामेंट के लिए प्रोत्साहित करना होगा - एक देर से नाइट के सभी संभावित पदों के लिए। यह शूरवीरों की संख्या के लिए निर्भरता N ^ 3/2 को चालू करता है, कार्यक्रम द्वारा शूरवीरों की संख्या पर एन।

वैसे, आधुनिक कंप्यूटर प्रति सेकंड लगभग 400-500 मिलियन सरल ऑपरेशन पूरा करने का प्रबंधन करते हैं। हमने एन = 500 के लिए हमारे समाधान की जटिलता का अनुमान लगाया लगभग 62 मिलियन सरल ऑपरेशन के रूप में, इसलिए हम उम्मीद कर सकते हैं कि यह मार्जिन के साथ समय सीमा में फिट होगा। वास्तव में, इस समाधान को लिखने से, आप एक अच्छी तरह से अर्जित सत्रह अंक प्राप्त कर सकते हैं - यह केवल तभी उपयोगी है क्योंकि इस तरह के समाधान आगे डिबगिंग और कार्य का परीक्षण करने में एक अच्छी मदद हो सकती है, लाभ बहुत ही सरलता से प्राप्त होता है।

हमें और गहरे जाने की जरूरत है

5000 शूरवीरों के साथ परीक्षणों पर एक सेकंड से अधिक समय तक काम करने के समाधान के लिए, एल्गोरिथ्म की घन जटिलता अब उपयुक्त नहीं है - आपको वर्ग एन के लिए कम से कम आनुपातिक अनुमान को कम करने की आवश्यकता है। ऐसे मामलों में, ओ-बड़ी शब्दावली का अक्सर उपयोग किया जाता है: हम जटिलता ओ के एल्गोरिथ्म के बारे में बात कर रहे हैं () एन ^ 2)।

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

एक समाधान शूरवीरों की एक सरणी के बजाय किसी प्रकार की संरचना का उपयोग करना होगा जो आपको कम समय में खंडों को काटने की अनुमति देता है। लेकिन यह तरीका बहुत संदिग्ध है, क्योंकि इनमें से अधिकांश संरचनाएं O (लॉग एन) के दौरान तेजी से काम नहीं करती हैं, और O (N ^ 2 लॉग एन) की जटिलता बहुत खतरनाक है: 300 मिलियन ऑपरेशन इस बात की गारंटी नहीं देते हैं कि समाधान में जाएगा समय सीमा।

एक तथ्य यह है कि हम बहुत सारे अनावश्यक ऑपरेशन कर रहे हैं - किसी कारण से हम स्पष्ट रूप में शूरवीरों की स्थिति का समर्थन करते हैं। यदि आप एक टूर्नामेंट ट्री के रूप में ऐसी बात को याद करते हैं, तो यह स्पष्ट हो जाता है कि सभी लड़ाइयों के त्वरित आचरण के लिए इसका उपयोग कैसे करें। अगर हमें कुछ शीर्षों के अनुरूप एक गोल का संचालन करना है, तो यह हमारे लिए बच्चे के कोने के अनुरूप गोल करने के लिए पर्याप्त है, और फिर इन दौरों के विजेताओं में से सबसे मजबूत एक का चयन करें। यह किया जाता है, उदाहरण के लिए, टूर्नामेंट के पेड़ को गहराई से ट्रेस करते हुए। इस प्रकार, यदि कोई टूर्नामेंट ट्री है, तो हम रैखिक समय ओ (एन) में सभी लड़ाइयों का संचालन कर सकते हैं। बाहर, हमें अभी भी उस स्थिति को सुलझाना है जहां हम अपना पसंदीदा डालते हैं, जिसमें ओ (एन) जटिलता भी होती है। इसका अर्थ है कि हम इस वृक्ष के नीचे O (N ^ 2) के लिए वास्तविक उत्तर खोजने में सक्षम हैं।

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

इस प्रकार, हम एक समाधान के साथ O (N ^ 2) मेमोरी की आवश्यकता के साथ एक टूर्नामेंट ट्री और O (N ^ 2) बनाने के लिए आए थे, ताकि इस पर उत्तर मिल सके। एन <= 5000 के साथ ऐसा समाधान समय के एक मार्जिन के साथ जाना चाहिए और 49 अंक प्राप्त करना चाहिए।

हम पूर्ण स्कोर के समाधान को पंप करते हैं

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

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

आइए आगे तर्क देते हैं - टूर्नामेंट ट्री के शीर्ष पर कौन विजेता है? यह स्पष्ट रूप से पर्याप्त है कि यह शूरवीर है जो इस शिखर के अनुरूप सबट्री में सबसे मजबूत है। यह एक बहुत ही उपयोगी विचार है, यह हमें समझने की अनुमति देता है, उदाहरण के लिए, जब हमारा पसंदीदा सैद्धांतिक रूप से किसी चरम पर विजेता हो सकता है: इसके लिए यह आवश्यक और पर्याप्त है कि इस सबट्री में उसके मुकाबले कोई शूरवीर मजबूत नहीं है। और किसी चोटी का एक उपशीर्षक क्या है? यह एक श्रृंखला का एक खंड है जिसमें समयनिष्ठ शूरवीर पहले से ही खड़े हैं - हम इस पर सबसे मजबूत शूरवीर पा सकते हैं, उदाहरण के लिए, इस तरह के डेटा संरचना का उपयोग सेगमेंट के पेड़ के रूप में करते हैं ।

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

इस प्रकार, समाधान का दूसरा भाग भी ओ (एन लॉग एन) के लिए अनुकूलित किया गया था। एन <= 100000 के लिए, इस तरह की जटिलता के साथ एक समाधान, एक नियम के रूप में, एक समय सीमा के भीतर आता है - यह कार्य कोई अपवाद नहीं है। वास्तव में, इस तरह के निर्णय (मामूली विचलन के साथ) को लागू करने से हम चारों को पूर्ण स्कोर मिला।

ये पिस रहे हैं

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