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









चैंपियनशिप की शुरुआत ने अप्रत्याशित रूप से उच्च प्रदर्शन के साथ सभी को आश्चर्यचकित किया: 1 दौर की शुरुआत के समय, 5,000 से अधिक प्रतिभागियों ने पहले ही चैंपियनशिप के लिए पंजीकरण किया था। तुलना के लिए, 2013 में, 3,500 से अधिक प्रोग्रामर ने चैम्पियनशिप में भाग लिया। और आवेदनों की संख्या लगातार बढ़ रही है, क्योंकि आप अंतिम योग्यता दौर की शुरुआत तक पंजीकरण कर सकते हैं।



सभी वर्षों के प्रतिभागियों की रिकॉर्ड संख्या ने दौर में भाग लिया - 1255! ऐसा हुआ नहीं! पिछले साल, पहले दौर में 754 प्रतिभागी थे। इस लोकप्रियता के बढ़ते पक्ष और बढ़े हुए भार को सर्वर के साथ तकनीकी समस्याएं थीं जो पूरे दौर में देखी गईं। कार्यों और परिणामों वाले पृष्ठ उपलब्ध नहीं थे या लंबे विलंब से उपलब्ध थे। और यदि सर्वर गिर नहीं गया, तो पहले दौर में कम से कम 3,000 प्रतिभागियों को स्वीकार किया जाएगा, लॉग से अनुरोधों की संख्या पर डेटा द्वारा।



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



1) 200 सर्वश्रेष्ठ प्रतिभागी , जिन्होंने कठिनाइयों के बावजूद दौर में हिस्सा लिया, वे क्वालीफाइंग दौर में गए।



2) रविवार, 1 जून, 2014 को 13-00 एक और, चौथा योग्यता दौर आयोजित किया जाएगा। इसके परिणामों के अनुसार, अन्य 200 सर्वश्रेष्ठ प्रतिभागी भी क्वालीफाइंग दौर में प्रवेश करेंगे। इस प्रकार, 800 प्रोग्रामर इसमें भाग लेंगे, न कि 600। आरसीसी 2014 टी-शर्ट उन सभी को भेजी जाएगी, जो क्वालिफाइंग राउंड में पास हुए थे।



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

आंकड़े

प्रतिभागियों ने 5945 फैसले भेजे, जिनमें से 1982 को सिस्टम ने सच माना। उपयोग की जाने वाली प्रोग्रामिंग भाषाएं इस प्रकार थीं:

• जीएनयू सी ++ समाधान: 2369
• दृश्य सी ++ समाधान: 1707
• जावा सॉल्यूशंस: 927
• सी # समाधान: 461
• पायथन सॉल्यूशंस: 309

सभी तीन समस्याओं को केवल तीन लोगों द्वारा हल किया गया था (क्वालीफाइंग राउंड में प्रवेश करने के लिए 233 मिनट से अधिक नहीं के तीन समस्याओं को हल करना आवश्यक था)।

पहले क्वालीफिकेशन राउंड के टास्क

टास्क ए गेम ।

आइडिया: एंड्री कोमारोव।

कार्यान्वयन: अन्ना मालोवा।

विश्लेषण: मालोवा अन्ना

इस समस्या में, यह जांचना आवश्यक था कि क्या खेल मैदान अच्छा है। एक अच्छे क्षेत्र को एक क्षेत्र कहा जाता था जिसमें एक मुक्त सेल या दो पड़ोसी कोशिकाएं होती हैं जिसमें समान संख्याएं होती हैं।

समस्या का समाधान खेल के मैदान की सभी कोशिकाओं और पड़ोसी कोशिकाओं के जोड़े की जांच करना है, चाहे वे उपरोक्त शर्तों को पूरा करें। कुल कठिनाई: O (n2)।



टास्क B. टाइमर ।

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

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

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

समस्या में, आपको अधिकतम संभव संख्या खोजने की आवश्यकता है जो कि टी सेकंड के बाद टाइमर पर हो सकती है, अगर इसे टाइमर पर संख्या को बदलने की अनुमति नहीं है तो टाइमर पर संख्या को x से कम और y द्वारा विभाज्य नहीं है।

दी गई बाधाओं के तहत, एक संख्या प्राप्त करना हमेशा संभव होता है जो y द्वारा विभाज्य है। पहले क्षण पर विचार करें जब टाइमर पर ऐसा नंबर दिखाई दिया। यह दिखाया जा सकता है कि यह संख्या x से कम और y द्वारा विभाज्य संख्याओं में सबसे छोटी होगी। इसे z द्वारा अस्वीकार करें।

टाइमर पर z पाने के लिए दो अलग-अलग इष्टतम तरीके नहीं हैं। पहला तरीका टाइमर के पहले टिक से पहले भेद्यता का शोषण करना है। इस मामले में, हम भेद्यता और शून्य सेकंड का एक उपयोग करते हैं। दूसरा तरीका भेद्यता का उपयोग करना और सेकंड की आवश्यक संख्या की प्रतीक्षा करना नहीं है। यह विधि केवल तभी संभव है जब z - x is t और z- x सेकंड लेता है और भेद्यता का शून्य उपयोग करता है।

हम के रूप में z प्राप्त करने के बाद समय को निरूपित करते हैं, और शेष संख्या को ko के रूप में उपयोग करते हैं।

टाइमर पर z दिखाई देने के बाद, पेट्या की क्रियाएं असंदिग्ध हो जाती हैं। हमारे लिए यथासंभव अधिक कमजोरियों का उपयोग करना फायदेमंद है, क्योंकि वे अतिरिक्त y -1 सेकंड जोड़ते हैं।

इसलिए उत्तर z + min (to, ko) • (y -1) + से है।

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



समस्या सी। सबसे बड़ी बढ़ती हुई अनुवर्ती समस्या ।

विचार: एंड्री स्टानकेविच, निकोले वेदरनिकोव।

कार्यान्वयन: निकोले वेदरनिकोव।

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

सबसे बड़ी बढ़ती बाद की गतिशील प्रोग्रामिंग समस्या को हल करने के लिए, सरणी से मूल अनुक्रम को पुनर्स्थापित करना आवश्यक था।

इस समस्या को रचनात्मक रूप से हल किया जा सकता है। उदाहरण के लिए, इस तरह: d [i] = a [i] • n - i + 1, जहां n अनुक्रम की लंबाई है। आइए हम साबित करें कि यह क्रम उपयुक्त है।

∀ i <j जिसके लिए d [i] <d [j], यह पूरा होगा: (d [j] - d [i]) • n ≥ n, और (j - i) <n ⇒ a [i] < एक [जे]। इसी तरह दूसरा तरीका।

∀ i <j जिसके लिए d [i] = d [j], वह पूरा होगा: a [i]> a [j]।

इसके अलावा, एक टोपोलॉजिकल सॉर्टिंग एल्गोरिथ्म का उपयोग करके एक समाधान है।



समस्या डी। तीन-रंग शतरंज ।

विचार: विटालि डीमनिअनुक।

बोध: विटालि दुमंजुक।

विश्लेषण: विटाली डमींजुक

कार्य में, n × m बोर्ड के प्रत्येक अप्रकाशित सेल को तीन रंगों में पेंट करने के तरीकों की संख्या की गणना करना आवश्यक था ताकि किसी भी दो पड़ोसी कोशिकाओं को एक ही रंग में चित्रित न किया जाए।

यह एक टूटी हुई प्रोफ़ाइल पर गतिशील प्रोग्रामिंग के लिए एक कार्य है।

हम सभी रंगों की संख्या। प्रत्येक राज्य चार संख्याओं (x, y, c, मास्क) से मेल खाता है, जहां (x, y) उस कक्ष के निर्देशांक हैं, जिस पर प्रोफाइल ब्रेक शुरू होता है। राउंड-टॉप ऑर्डर में प्रोफ़ाइल की सभी कोशिकाओं पर विचार करें। फिर c प्रोफ़ाइल में पहली सेल का रंग है। प्रोफ़ाइल के आई-वें सेल और कई रंगों पर विचार करें, जिसमें इसे चित्रित नहीं किया गया है। इस सेट में दो रंग होते हैं। तब ith मास्क बिट 0 है यदि प्रोफाइल सेल का रंग i + 1 इस सेट के न्यूनतम के बराबर है, तो अधिकतम 1।

प्रत्येक राज्य में, हम बोर्ड के संबंधित भाग को चित्रित करने के तरीकों की संख्या को संग्रहीत करेंगे। मूल्यों की पुनर्गणना समान है। किसी भी अन्य गतिशील समस्या के रूप में

एक टूटी हुई प्रोफ़ाइल पर प्रोग्रामिंग। उत्तर प्राप्त करने के लिए, हम सभी सी और मास्क पर जाएंगे और राज्यों (एन, एम, सी, मास्क) में मूल्य जोड़ेंगे।

संचालन समय - O (nm 2 n)।



टास्क ई । एक नेटवर्क का निर्माण कैसे करें ।

विचार: बोरिस मिनाएव।

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

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

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

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

हम डिवाइस को बाएं से दाएं पर विचार करेंगे। यदि वर्तमान डिवाइस एक कंप्यूटर है, तो संतुलन को 1 से बढ़ाना होगा और इसकी लागत तदनुसार बदल गई है। यदि हम एक स्विच पर विचार कर रहे हैं, तो यह पता लगाना आवश्यक है कि कितने कंप्यूटर इससे जुड़े होंगे, और शेष राशि की लागत को ध्यान से पुनर्गणना करेंगे (शायद पहले कुछ कनेक्शन इसे बढ़ाएंगे, और अगले वाले घट जाएंगे)। ऐसा समाधान O (n 2 • (n + m)) के लिए काम करता है।

एक विधि पर विचार करें जो आपको एल्गोरिथ्म के चलने के समय को O (n • (n + m)) तक कम करने की अनुमति देता है। एल्गोरिथ्म का सबसे लंबा चलने वाला स्थान स्विच को संसाधित करते समय गतिशील प्रोग्रामिंग मूल्यों को अपडेट कर रहा है। हम छोटे से बड़े तक शेष राशि प्राप्त करने की लागत पाएंगे। उसी समय, हम उस कतार को बनाए रखेंगे जिसमें विभिन्न पिछली बैलेंस शीट राज्यों से वांछित शेष राशि प्राप्त करने की लागत संग्रहीत की जाती है। नए बैलेंस वैल्यू पर जाने पर, आपको कतार से पहला तत्व निकालने की आवश्यकता हो सकती है (यदि कंप्यूटर की आवश्यक संख्या को वर्तमान स्विच से कनेक्ट नहीं किया जा सकता है), तो स्विच का उपयोग किए बिना वर्तमान शेष राशि प्राप्त करने की क्षमता जोड़ें, और कतार में मौजूद सभी वर्तमान परिवर्तनों को भी बदलें - के लिए यह स्विच में दूरी जोड़ने (या घटाना) की आवश्यकता है। कतार में हमेशा मूल्यों का बढ़ता क्रम होना चाहिए। फिर वर्तमान शेष के लिए उत्तर हमेशा कतार में पहले स्थान पर होगा।

अब एक सर्कल के रूप में एक नेटवर्क विकल्प पर विचार करें। हम सर्कल को काटते हैं और कटौती के माध्यम से गुजरने वाले तारों की संख्या को ठीक करते हैं। यह आसानी से दिखाया जा सकता है कि यदि कोई इष्टतम उत्तर है जिसमें ठीक इतने सारे तार कट से गुजरते हैं, तो एक इष्टतम उत्तर है जिसमें ये तार संबंधित प्रकार के पहले उपकरणों से जुड़े होते हैं। इस प्रकार, हमने ओ (एन 2 • (एन + एम)) में डिस्क पर एक समाधान प्राप्त किया।



आप गोल परिणाम पृष्ठ पर परीक्षा परिणामों के साथ खुद को डाउनलोड और परिचित कर सकते हैं।