रूसी कोड कप 2014 के चौथे योग्यता दौर के कार्यों का विश्लेषण

रविवार, 1 जून को, रूसी कोड कप 2014 का चौथा, अंतिम, योग्यता दौर आयोजित किया गया था।



राउंड में भाग लेने के लिए 5428 लोगों ने पंजीकरण कराया। 730 प्रतिभागियों द्वारा कम से कम एक समाधान भेजा गया था। कुल मिलाकर, 4793 फैसले प्रति राउंड भेजे गए, जिनमें से 1531 सही थे।



अधिकांश GNU C ++ समाधान 1786 हैं।

पायथन में 307 समाधान हैं, जिनमें से 86 सही हैं।

93 PHP समाधान हैं, जिनमें से 15 सही हैं।

पर्ल में 6 समाधान हैं, जिनमें से 2 सही हैं।



पहला कार्य ए को दिमित्री फिलिप्पोव (दिमाफिल) द्वारा 2:42 मिनट में हल किया गया था, वह 12:09 में समस्या बी को हल करने वाला पहला व्यक्ति था। टास्क सी और डी को पहले अलेक्जेंडर ओबेडनिकोव (एओबी) द्वारा क्रमशः 12:25 और 37:44 मिनट पर तय किया गया था। पहला कार्य E को 45:22 मिनट पर Fefer Ivan (Fefer.Ivan) द्वारा हल किया गया था। इवान भी 1 घंटे 8 मिनट में सभी कार्यों को पूरा करने वाला पहला था। 12 लोगों द्वारा केवल 5 समस्याओं को हल किया गया था। 10 प्रतिभागियों को न्यायाधीशों द्वारा अयोग्य घोषित किया गया था।



कुल 4 क्वालीफाइंग राउंड के लिए, 8 जून को फाइनल में 802 प्रतिभागियों ने एक-दूसरे के लिए क्वालीफाई किया।



टास्क ए। जनमत सर्वेक्षण

विचार: एंड्री स्टानकेविच

अहसास: निकोले वेदरनिकोव

विश्लेषण: निकोले वेदरनिकोव



कार्य में प्रतिभागियों की न्यूनतम और अधिकतम संभव संख्या खोजने की आवश्यकता है जो समस्या का समाधान करेंगे। यदि सभी में n प्रतिभागी हैं, तो उनमें से समस्या को हल करने में सक्षम हैं, और b कार्य प्रतिभागियों के विपरीत है।



चूंकि समस्या की शर्तों के अनुसार इसे केवल उन लोगों द्वारा हल किया जाएगा जिनके लिए यह घृणित नहीं है और हल करने में सक्षम है, समस्या को हल करने की कोशिश करने वालों की संख्या n - b के बराबर या उससे कम होगी। यही है, अगर उन सभी के बीच जो समस्या को हल करने की कोशिश करते हैं तो वे हैं जो कर सकते हैं, तो यह अधिकतम होगा जो इसे हल करेंगे। यह न्यूनतम ( ए , एन - बी ) है।



न्यूनतम पर पहुंच जाता है यदि हर कोई जो कार्य का विरोध करता है, समस्या को हल करने में सक्षम होगा, तो उत्तर अधिकतम (0, ए - बी ) है।



टास्क बी। एक सौ

विचार: विटाली अक्षोनोव

एहसास: पावेल क्रोटकोव

विश्लेषण: पावेल क्रोटकोव



समस्या का समाधान एक ऐसा कार्यक्रम है जो कई सरल मामलों पर ध्यान से विचार करता है। सबसे सरल मामला तब है जब x में अंकों की संख्या k +1 है। इस स्थिति में, is1 को प्रिंट करना आवश्यक है यदि संख्या में एक शून्य नहीं है, और शून्य है यदि संख्या में कम से कम एक शून्य है।



यदि संख्या x में संख्याओं की संख्या k से कम से कम तीन से अधिक है, तो इस स्थिति को अधिक सावधानी से संभालने की आवश्यकता है। हम अंत से दूसरे शून्य के बीच पाते हैं। सुनिश्चित करें कि इसके पीछे k + 1 अंक से अधिक नहीं है। सभी गैर-अंकीय अंकों को पार करें जो अंत से दूसरे शून्य के पीछे हैं, और अंत से दूसरे शून्य से तुरंत पहले अंकों की आवश्यक संख्या को भी पार करते हैं। ध्यान दें कि पहला अंक कभी भी पार नहीं किया जाता है, जिसका अर्थ है कि अंतिम संख्या में कोई अग्रणी शून्य नहीं होगा।



यह भूलना महत्वपूर्ण था कि किसी अंक को हटाने की कार्रवाई को संख्या की लंबाई के लिए नहीं किया जाना चाहिए - इस तरह की त्रुटि वाले समाधानों को तीसरे परीक्षण में समय सीमा से अधिक प्राप्त हुआ।



टास्क सी। यात्रा करने के लिए वृद्धि

विचार: जॉर्ज कोर्निव

कार्यान्वयन: बोरिस मिनाएव

विश्लेषण: बोरिस मिनाएव



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



टास्क डी। SNM

विचार: आर्टेम वासिलिव

कार्यान्वयन: आर्टेम वासिलिव

विश्लेषण: आर्टीम वासिलिव



कार्य ने रैंक हेयुरिस्टिक के साथ, लेकिन पथ संपीड़न हेयुरिस्टिक्स के साथ असहमति सेट की एक प्रणाली के कार्यान्वयन का वर्णन किया। हम प्रत्येक रूट ट्री के लिए समस्या को स्वतंत्र रूप से हल करेंगे, हमें चक्रों की उपस्थिति के मामले पर भी विचार करना चाहिए।



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



यू के शीर्ष पर एक रूट के साथ एक सबट्री पर विचार करें। यदि रैंक _u = r है , तो शीर्ष पर u में 0, 1, ..., r -1 रैंक वाले बच्चे मौजूद होने चाहिए। यह दिखाना आसान है कि यह स्थिति पर्याप्त है: यदि आप बेटे की रैंक बढ़ाने के लिए संघ संचालन करते हैं, तो सभी ऑपरेशन सही तरीके से चलेंगे।



इसलिए एक ही पेड़ का हल:

1. पुन: ट्री रूट के सभी बच्चों के लिए एक समाधान का निर्माण करें।
2. जाँच करें कि सभी ज के लिए 0 से रैंक _रूट - 1 रैंक एच के साथ एक बेटा है।
3. हम बच्चे की रैंक बढ़ाने के क्रम में यूनियन ( रूट , चाइल्ड _आई ) का संचालन करते हैं।

एसएनएम को लागू करना भी संभव है और सीधे सभी ऑपरेशनों की जांच करके यह सुनिश्चित करें कि परिणामी मूल सरणी आपके द्वारा आवश्यक मिलान से मेल खाती है।



समाधान का रनटाइम O ( n log ( n )) है।



टास्क ई। nanorobots

विचार: विटाली अक्षोनोव

कार्यान्वयन: एंड्री कोमारोव

विश्लेषण: एंड्री कोमारोव



समस्या में, दो भागों में स्थानांतरित होने या विभाजित होने की न्यूनतम संख्या के लिए, सभी नैनोरोबोट्स को ऊपरी बाएँ से निचले दाईं ओर स्थानांतरित करना आवश्यक है।



हम गतिशील प्रोग्रामिंग का उपयोग करके इस समस्या को हल करेंगे। Dp [ w ] [ x ] [ y ] चरणों की न्यूनतम संख्या, जिसमें सेल ( x , y ) से मास w के रोबोट को अंतिम सेल ( n , m ) तक लाना संभव है। प्रारंभिक मान dp [ w ] [ n ] [ m ] = ० इंगित करते हैं कि लक्ष्य सेल से कहीं भी जाने की आवश्यकता नहीं है। डीपी की गणना के बाद, उत्तर सेल डीपी [ w ] [१] [१] में समाहित हो जाएगा।



Dp गिनना सीखें। Dp [ w ] [ i ] [ j ] की गणना करने के लिए, हम दो काम करते हैं:

• हम रोबोट को टुकड़ों में तोड़ने के बिना फिनिश लाइन तक पहुंचते हैं। ऐसा करने के लिए, गहराई से टहलने का उपयोग करते हुए, हम प्रतिरोधी कोशिकाओं के माध्यम से फिनिश लाइन के लिए सबसे छोटा रास्ता पाएंगे।
• या हम किसी प्रकार की कोशिका तक पहुँचेंगे, दो भागों में टूटेंगे और वहाँ से पहुँचेंगे।

ताकि यह समझने में कोई समस्या न हो कि डायनामिक्स के मूल्यों को गिनने के लिए आप इस पर विचार कर सकते हैं। एल्गोरिथ्म की कुल जटिलता: O ( w ² n ² m ² )।