रूसी कोड कप: अंतिम दौर के परिणाम

18 सितंबर को, ऑल-रूसी प्रोग्रामिंग कप रूसी कोड कप का अंतिम दौर हुआ । इस साल, 50 प्रोग्रामर ओलंपियाड के फाइनल में पहुंचे - 27 रूस से, 11 यूक्रेन से, बेलारूस 7, यूएसए से दो और एक आर्मेनिया, जॉर्जिया और स्विट्जरलैंड से।



विजेता मास्को से पीटर मित्रीचेव था। उन्हें $ 10 हजार का पुरस्कार मिला। दूसरा स्थान सेंट पीटर्सबर्ग से यूजीन कापुन ने लिया, उन्हें 5 हजार अमेरिकी डॉलर मिले। तीसरे स्थान पर 3 हजार अमेरिकी डॉलर के पुरस्कार के साथ सेंट पीटर्सबर्ग के मिखाइल ड्वोर्किन हैं। लोगों को बधाई और उन्हें लगातार सफलता की कामना!

इस लेख में, हम अंतिम दौर से कार्यों का विश्लेषण करेंगे।

कार्यों का पूरा विवरण यहां पाया जा सकता है ।

टास्क ए क्लॉक ट्रांसफर

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

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

अब हम उन घटनाओं पर विचार करेंगे, जिसमें वे एक पूर्ण पैमाने पर होती हैं। पिछले समय से वर्तमान घटना तक, देश में असुविधा लगातार थी।

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

शहरों में शिफ्ट के एक निश्चित सेगमेंट पर कुल समय शिफ्ट की गणना करने के लिए, साथ ही साथ एक सेगमेंट में शहरों की संख्या की गणना करने के लिए, आप उपयोग कर सकते हैं, उदाहरण के लिए, सेगमेंट का एक पेड़ या एक फेनविक पेड़।

समस्या B. उलटे कछुए की समस्या

इस समस्या में, किसी दिए गए नंबर k के लिए, एक भूलभुलैया का निर्माण करना आवश्यक था जिसमें ऊपरी बाएँ से निचले दाएं सेल तक के मार्ग उपलब्ध थे, बशर्ते कि इसे केवल दाएं और नीचे जाने की अनुमति हो, k के बराबर होगा।

निम्नलिखित पर ध्यान दें। मान लें कि हमारे पास दो लेबिरिंथ हैं जिनमें ऊपर से नीचे दाईं ओर जाने के तरीकों की संख्या क्रमशः a और b के बराबर है।
फिर, उन्हें समानांतर में रखते हुए, जैसा कि चित्र में दिखाया गया है, हम एक भूलभुलैया प्राप्त कर सकते हैं जिसमें a + b ऊपरी बाएँ से निचले दाएं सेल में जाने के तरीके हैं, और उन्हें क्रमिक रूप से रखते हुए - एक भूलभुलैया प्राप्त करें जिसमें ab पथ हैं।



ध्यान दें कि खाली 2 × 2 भूलभुलैया में दो रास्ते हैं, और 1 × 1 भूलभुलैया में एक पथ। इसलिए, संख्या k को एक बाइनरी नंबर सिस्टम में विस्तारित करके और वर्णित विधि का उपयोग करके, हम ऊपरी बाएं से निचले दाएं सेल के लिए कश्मीर पथ के साथ एक भूलभुलैया प्राप्त कर सकते हैं।

K = 19 के लिए इस तरह के भूलभुलैया का एक उदाहरण चित्र में दिखाया गया है।



ध्यान दें कि संख्या k के प्रत्येक निर्वहन के लिए, 5 कोशिकाओं को क्षैतिज रूप से आवश्यक है, और 2 ⁶⁰ > 10 ¹⁸ , इसलिए उपरोक्त योजना आपको 300 × 300 के आकार के साथ एक भूलभुलैया बनाने की अनुमति देती है, जैसा कि समस्या की स्थिति में आवश्यक है।

समस्या सी। तालिका विभाजन

इस समस्या में, शून्य और एक तालिका के विभाजनों की संख्या को 9 भागों में गणना करना आवश्यक था, ताकि इन पांच भागों में इकाइयों की संख्या समान हो।



इस समस्या को हल करने के लिए कई दृष्टिकोण संभव हैं; हम उनमें से एक पर विचार करेंगे। C1, c2, r1 और r2 को ठीक करें। ध्यान दें कि जब r2 को एक समता से बढ़ाया जाता है, तो भागों A5, A7, और A9 में इकाइयों की संख्या में परिवर्तन नहीं होता है यदि पंक्ति r2 में समान संख्या में इकाइयाँ और अन्यथा परिवर्तन होते हैं। इसलिए, निश्चित c1, c2 और r1 के लिए, यह समझना आसान है कि कौन से r2 उपयुक्त हैं - वांछित भागों में इकाइयों की संख्या की समता के आधार पर, r2 = n - 1 के लिए, या तो r2 ऐसी कि r2 + 1 से n तक की पंक्तियों में इकाइयों की संख्या सम है, या है। अजीब। हमें ओ (एन ³ ) के लिए एक समाधान मिलता है, जो आवंटित समय सीमा को पूरा करने के लिए पर्याप्त नहीं है। हालाँकि, एक समान तर्क अब c1 और c2 पर लागू किया जा सकता है। फिक्स्ड आर 1, आर 2 और सी 1 के लिए, सी 2 में एक की वृद्धि कॉलम सी 2 में इकाइयों की संख्या की समता द्वारा समानता को बदल देती है। इसलिए, r1 को ठीक करना, r2 = n - 1 को सेट करना और c1 को ठीक करना, c2 के मानों की संख्या ज्ञात करना आसान है, जिसके लिए r2 बड़ी रेखाओं में सम या विषम राशि के साथ उपयुक्त हैं।

इस समाधान का स्पर्शोन्मुख व्यवहार पहले से ही ओ (एन ² ) है, जो दी गई बाधाओं के तहत पर्याप्त है।

टास्क डी। अभिलेखागार

इस कार्य के लिए कम से कम दो अलग-अलग दृष्टिकोण संभव हैं: गतिशील प्रोग्रामिंग या एक लालची एल्गोरिथ्म।

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

डायनेमिक प्रोग्रामिंग का उपयोग करते हुए समाधान इस प्रकार है: प्रत्येक शीर्ष पर यू हम सबटाइटल के लिए न्यूनतम कुल पेनल्टी पी [यू] [x] जमा करेंगे यदि हम इस शीर्ष पर संख्या x लिखते हैं। ध्यान दें कि शीर्ष पर यह केवल उस संख्या को लिखने के लिए सार्थक है जो सबट्री में पत्तियों में से किसी एक में होती है, इसलिए कुल विकल्पों की संख्या जिस पर विचार किया जाना चाहिए वह है ओ (एन लॉग एन)।

पुनर्गणना निम्न प्रकार से की जाती है: बच्चों और v के साथ शीर्ष u पर विचार करें। मान लीजिए, हमारे पास x का मान लिखने की योजना है। यदि दोनों p [v] [x] और p [w] [x] परिभाषित हैं, तो x को u में रखने के विकल्पों में से एक दोनों बच्चों में x लगाना है, इस विकल्प की कीमत p [v] [x] + p [w है ] [x]। केवल एक बच्चे में एक्स लगाने का विकल्प भी है। मान लीजिए कि हमने x को v में रखने की योजना बनाई है, तो इस विकल्प की लागत p [v] [x] + minp [w] + 1 है, जहां minp [w] सभी y के लिए p [w] [y] का न्यूनतम मूल्य है।

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

हम एक अभ्यास के रूप में प्रस्तुत एल्गोरिथ्म की शुद्धता का प्रमाण छोड़ देंगे।

समस्या ई। ब्लैकजोन

इस समस्या में, अंशों (कार्ड) का सबसेट चुनना आवश्यक है ताकि उनकी राशि एक के बराबर हो। इस प्रकार, यह समस्या बैकपैक समस्या का एक विशेष मामला है। समस्या को हल करने के संभावित दृष्टिकोणों में से एक सभी भागों को एक आम भाजक में लाना है। हालांकि, सभी संभावित हर प्रकार के सबसे छोटे सामान्य मल्टीपल (LCL) 232,792,560 हैं, जो कि परिणामी "क्लासिक" बैकपैक समस्या के आगे समाधान के लिए बहुत बड़ी संख्या है।

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

प्रत्येक समूह में, चयनित अंशों का योग पूर्णांक होना चाहिए, यहां तक ​​कि संभवतः शून्य भी। प्रत्येक समूह के लिए बैकपैक समस्या का समाधान करते हुए, हम यह पता लगाते हैं कि क्या समूह में भिन्नता का चयन करना संभव है ताकि एक निश्चित पूर्णांक प्राप्त किया जा सके। To100 से 100 तक केवल पूर्णांक ब्याज के होते हैं, क्योंकि 100 से अधिक अंशों का योग, जिनमें से प्रत्येक modulo एक से अधिक नहीं होता है, modulo 100 से अधिक नहीं होता है। हम यह भी ध्यान दें कि अंतिम समूह के सभी संभावित हर का नियंत्रण रेखा केवल 5040 है, फिर कुल के लिए संभावित विकल्पों की संख्या 1 008 001 से अधिक नहीं है। यह तथ्य हमें आवंटित समय में प्रत्येक समूह में एक बैकपैक की समस्या को हल करने की अनुमति देता है।

यह जानकर कि प्रत्येक समूह में कौन से पूर्णांक प्राप्त किए जा सकते हैं, यह जाँचना आवश्यक है कि क्या प्रत्येक समूह में एक पूर्णांक का चयन करके, किसी एक के बराबर राशि प्राप्त की जा सकती है। डायनेमिक प्रोग्रामिंग विधि का उपयोग करके इस समस्या को हल किया जा सकता है। हम मात्रा को एक _i , _{j से परिचित कराते हैं} - क्या यह संभव है, पहले i समूहों का उपयोग करके, बिल्कुल j का योग प्राप्त करने के लिए। आधार का मान ₀ , ₀ = true और a ₀ , _j = j से j100 से 100 तक शून्य को छोड़कर होगा। संक्रमण निम्न प्रकार से किया जाता है: एक _i , _j = true, यदि कम से कम एक k सच है ( _i-1 , _jk और b _{i, k} ), और गलत है, तो b _{i, k} एक मान है जो इंगित करता है समूह i, राशि k के साथ भिन्न का चयन करता है। समस्या का उत्तर _{5.1 का} मान होगा।

भिन्नों के सेट को खोजने के लिए जिन्हें लेने की आवश्यकता है, यह पाया गया गतिशीलता मूल्यों का उपयोग करने के लिए पर्याप्त है, और प्रत्येक समूह के लिए बैकपैक समस्या के लिए उत्तर को पुनर्स्थापित करने के मानक तरीके का उपयोग करें।

टास्क एफ केक काटना

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

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

अगर वहाँ एक क्षैतिज अच्छी लाइन काफी सरल है जाँच कर रहा है। ऐसा करने के लिए, अधिकतम और न्यूनतम निर्देश के साथ चेरी से गुजरने वाली क्षैतिज रेखाओं की जांच करें। उत्तर के लिए शेष उम्मीदवार गुलाब से चेरी के उत्तल पतवार तक स्पर्शरेखा हैं।

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

आप स्पर्शरेखा खोजने के लिए एक अधिक कुशल विधि के साथ आ सकते हैं। हम एक और अवलोकन का उपयोग करने का सुझाव देते हैं। मान लीजिए कि एक दिए गए बिंदु से एक उत्तल आकृति का एक दिलचस्प स्पर्शरेखा कोण tang है। आज्ञा देना ≤ ≤ α ≤ ≤ / 2। फिर एक दिलचस्प कोण α के साथ इस आंकड़े के स्पर्शरेखा में से एक इस आंकड़े और बिंदु को अलग करता है।



अंतिम अवलोकन का उपयोग करके, कोई यह जांच सकता है कि क्या एक अच्छी रेखा मौजूद है जिसका दिलचस्प कोण α से अधिक नहीं है। ऐसा करने के लिए, हम चेरी के उत्तल पतवार के लिए सभी स्पर्शरेखाएँ खींचते हैं जिनमें एक दिलचस्प कोण α होता है। उसके बाद, हम जांचते हैं कि कम से कम एक गुलाब है, जैसे कि एक स्पर्शरेखा के सापेक्ष यह और चेरी विपरीत पक्षों पर झूठ बोलते हैं। यह रैखिक समय में करना आसान है।



यदि कम से कम एक गुलाब अंधेरे क्षेत्र में नहीं है, तो इसका उत्तर α से अधिक नहीं है। आक्षेप भी सत्य है।

उसके बाद, वांछित कोण बाइनरी खोज द्वारा पाया जा सकता है।

नतीजतन, हम एसिम्पोटिक्स ओ (एन (एन एन + आई)) के साथ एक समाधान प्राप्त करते हैं, जहां एन = एन + एम, और मैं बाइनरी खोज के पुनरावृत्तियों की संख्या है।

रूसी कोड कप 2012 में मिलते हैं!

टीम रूसी कोड कप।