रूसी कोड कप 2014 का क्वालिफाइंग दौर: परिणाम और कार्यों का विश्लेषण

पिछले रविवार को, रूसी कोड कप 2014 का क्वालीफाइंग दौर हुआ। इसमें 802 प्रोग्रामरों ने भाग लिया, जिन्होंने चार योग्यताओं में सर्वश्रेष्ठ परिणाम दिखाए। इस स्तर पर, प्रतिभागियों को 3 घंटे में छह समस्याओं को हल करना था, जो एक घंटे और योग्यता राउंड में एक से अधिक कार्य है। और कार्य पिछले वाले की तुलना में बहुत अधिक जटिल थे। 802 की प्रतियोगिता के दौरान, केवल 444 प्रतिभागी कम से कम एक समस्या को हल करने में सक्षम थे। कुल 3271 समाधान भेजे गए थे, जिनमें से 1402 सही थे।



जीएनयू सी ++ में अधिकांश समाधान 1516 हैं।

जावा 7 में 333 समाधान हैं।

जावा 8 - 106 समाधान।



पहला कार्य A 2:52 मिनट में Gennady Korotkevich (पर्यटक) द्वारा हल किया गया था। Gennady ने क्रमशः B, C और D को क्रमशः 7:05, 24:29 और 13:05 मिनट पर हल किया। समस्या ई को पहले दिमित्री ईगोरोव (दिमित्री_एगोरोव) द्वारा 40:59 मिनट पर हल किया गया था। समस्या एफ रूसी कोड कप के इतिहास में सबसे कठिन में से एक बन गई - सभी प्रतिभागियों में से, केवल तीन लोगों ने इसे सही ढंग से हल किया, और समस्या एफ को हल करने वाले पहले आरसीसी 2013 पेट्र मित्रीचेव (पेट्र) के विजेता 2:25:46 में थे।



सभी कार्यों को पूरा करने वाले पहले 2 घंटे 47 मिनट में Pavel Kunyavskiy (PavelKunyavskiy) था। 3 लोगों द्वारा केवल 6 समस्याओं को हल किया गया था, 5 और अधिक समस्याओं को 100 लोगों द्वारा हल किया गया था। पोषित शीर्ष 50 में अंतिम रोमन बेली (रोमाव्हाइट) था, जिसने शुरू होने के 2 घंटे 30 मिनट बाद पांचवां कार्य पारित किया।



जीतने की इच्छा के लिए, हम Egor कुलिकोव (Egor) को नोट करते हैं, जिन्होंने 7 वें प्रयास में एक कार्य को पारित करते हुए शीर्ष 50 में प्रवेश किया। और पेट्र मित्रीचेव (पेट्र), जिन्होंने समस्या C को हल करने के तरीके का पता नहीं लगाया, इसे हल करने की कोशिश करने से इनकार कर दिया, सबसे मुश्किल काम F को हल करने वाला पहला था। और फिर, कार्य C पर लौटते हुए, इसे अंत से 4 मिनट पहले पारित किया और कुल 3 लिया। जगह।



इस दौर में प्रतिभागियों का क्षेत्रीय वितरण निम्नानुसार था:

रूस	515
यूक्रेन	112
बेलोरूस	77
कजाखस्तान	26
अमेरिका	17
आर्मीनिया	8
उज़्बेकिस्तान	8
स्विट्जरलैंड	6
जर्मनी	4
लातविया	4
ऑस्ट्रिया	2
बुल्गारिया	2
यूनाइटेड किंगडम	2
जॉर्जिया	2
मोलदोवा	2
पोलैंड	2
सिंगापुर गणराज्य	2
आज़रबाइजान	1
अर्जेंटीना	1
आयरलैंड	1
कनाडा	1
साइप्रस	1
लिथुआनिया	1
कोरिया गणराज्य	1
स्लोवाकिया	1
टर्की	1
स्वीडन	1
जापान	1

उसी समय, रूसी कोड कप में पहली बार ऐसे प्रतिभागी थे जो ऑस्ट्रिया, अर्जेंटीना और जापान से रूसी भाषा नहीं जानते थे! उनमें से एक के रूप में, उन्होंने ऑनलाइन अनुवाद सेवाओं के माध्यम से दौर के कार्यों की शर्तों का अनुवाद किया।



क्वालीफाइंग दौर में मुकाबला तीव्र था। नतीजतन, 50 सबसे मजबूत प्रोग्रामर फाइनल में पहुंचे। हम उनके बारे में बाद में विस्तार से बात करेंगे।



टास्क ए कार्यों का विश्लेषण



विचार: अन्ना मालोवा

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

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



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



यह समस्या एक लालची एल्गोरिथ्म द्वारा हल की गई है। हम एक जूरी सदस्य का चयन करते हैं जो पहले से शुरू होने वाली अधिकतम समस्याओं को हल कर सकता है। उसे बताएं कि k समस्याओं को कैसे हल करें। फिर, हम वह चुन लेते हैं जो जानता है कि अधिकतम समस्याओं को कैसे हल करना है, जो कि kth से शुरू होता है। हम इस तरह से जारी रखेंगे जब तक कि सभी कार्यों को हल नहीं किया जाता है। फिर समस्या का उत्तर m · t + q · c है , जहाँ q प्रतिस्थापित प्रतिस्थापन की संख्या है।



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



यह समाधान O (n · m) के लिए काम करता है ।



आप गतिशील प्रोग्रामिंग का उपयोग करके एक सरल समाधान भी लिख सकते हैं। dp [ i ] [ j ] उस न्यूनतम समय के बराबर है जिसे खर्च किया जाता है यदि मैं कार्य डिसेबल्ड किया गया था और i- th जूरी सदस्य डिसाइड किया गया था। इस सरणी को आसानी से O (n ² m) के रूप में गिना जा सकता है।



सुदूर अमेज़ॅन पर समस्या बी



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

कार्यान्वयन: डेमिड कुचेरेंको

विश्लेषण: डेमिड कुचेरेंको



इस समस्या में, एक सीधा ग्राफ बनाना आवश्यक है जिसमें n शीर्ष रेखाएँ हों जिनमें निम्न स्थितियाँ संतुष्ट हों:

• ग्राफ में चक्र नहीं होना चाहिए;
• प्रत्येक किनारे पर अधिकतम एक किनारे होता है;
• ग्राफ़ में बिल्कुल एक कोने होने चाहिए जिसमें से बाहर जाने वाले किनारे मौजूद हों;
• ग्राफ़ में बिलकुल कोने होने चाहिए जिसमें आने वाले किनारे मौजूद हों।

शुरू करने के लिए, हम मामलों का विश्लेषण करेंगे जब जवाब "IMPOSSIBLE" होगा। ये ऐसे मामले हैं जब कम से कम एक स्थिति सत्य है:

• बेटियों की तुलना में अधिक माताओं;
• n -1 से अधिक माताएँ हैं (सभी माताएँ नहीं हो सकती हैं);
• n -1 से अधिक बेटियां।

यदि इस तरह के ग्राफ का निर्माण करना संभव है, तो पहले हम किनारों की एक श्रृंखला का निर्माण करते हैं। इस प्रकार, हमारे पास एक +1 महिला शामिल होगी, और हमारी एक मां और एक बेटियां होंगी। जिसके बाद, हम किसी भी माताओं की बेटियों के पूरक हैं ताकि बेटियां बिल्कुल बी बन जाएं। ऐसा हो सकता है कि कुछ महिलाएं न तो मां हैं और न ही बेटियां, लेकिन यह कार्य की स्थिति के विपरीत नहीं है।



समस्या सी। प्रयोगशाला भौतिकी



विचार: विटालिक अक्सेनोव

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

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



इस समस्या में, यह निर्धारित करना आवश्यक है कि ठंडे और गर्म पानी के साथ दो जहाजों से पानी मिलाकर पानी का तापमान क्या हो सकता है। किसी दिए गए तापमान पर ऐसे कई अनुरोधों का जवाब देना आवश्यक था।



हम पानी के तापमान के लिए सूत्र लिखते हैं यदि हम वॉल्यूम ग _{i के} साथ एक बर्तन से ठंडा पानी मिलाते हैं और मात्रा h _j : T = p / q = (C · c _i + H · h _j ) / (c _i + h _j ) के साथ एक बर्तन से गर्म पानी मिलाते हैं। इस सूत्र से, हमें यह पता चलता है कि (H · q - p) / (p - C · q) = c _i / h _j इस प्रकार, हमने इस समस्या को निम्नलिखित में कम कर दिया: एक अनियमित अंश और संख्याओं और हर का एक सेट दिया गया है, क्या एक अंश का चयन करना संभव है और भाजक ताकि दिए गए अंश प्राप्त हो?



हम संकेतन A _x , सभी c _i / x के समुच्चय का परिचय देते हैं, जहाँ c _i , x से विभाज्य है। इसी तरह, बी _y सभी h _i / y का सेट है, जहाँ h _i को y से विभाजित किया जाता है। तब irreducible भिन्न p / q का प्रतिनिधित्व किया जा सकता है यदि और केवल यदि A _p और B _q प्रतिच्छेद हो। यह ध्यान देने योग्य है कि सभी सेट ए _एक्स और बी _वाई का कुल आकार ओ ( एम लॉग एम ) है, जहां एम जहाजों की मात्रा पर प्रतिबंध है (इस समस्या में, एम 10 10 है)।



जब A _x और B _y को क्रमबद्ध सूचियों के रूप _में प्रस्तुत किया जाता है, तो एक क्वेरी को O (M / max (x, y)) में निष्पादित किया जा सकता है। यदि हम ए और बी _वाई को बिट सेट के रूप में दर्शाते हैं, तो हमें प्रति अनुरोध ओ ( एम / 64) में एक समाधान मिलता है।



सबसे तेज़ समाधान प्राप्त किया जाता है, यदि आप कई बार एक ही अंश के उत्तरों की गणना नहीं करते हैं। इस मामले में, समाधान कार्य समय के लिए अधिक सटीक अनुमान साबित करना संभव है। आइए हम अनुमान O ((M + k) sqrt (M)) सिद्ध करें, जहाँ k प्रश्नों की संख्या है। यदि p और q की अधिकतम sqrt (M) से अधिक है, तो क्वेरी को O (sqrt (M)) में सेट के छोटे के सभी तत्वों को देखते हुए निष्पादित किया जा सकता है। अन्य सभी प्रश्नों के लिए निष्पादन समय का योग का अनुमान लगाएं। O (M / x) में निष्पादित होने वाले 2 से अधिक एक्स क्वेरी नहीं हैं। सभी एक्स पर सारांशित करना और यह ध्यान रखना कि x sqrt (M) से बड़ा नहीं है, हम अनुमान O ((M + k) sqrt (M)) प्राप्त करते हैं: समाधान का कुल समय: O ((M + k) sqrt (M) ।



टास्क डी। आरी का निर्माण



विचार: निकोले वेदरनिकोव

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

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



कार्य को क्रमपरिवर्तन की संख्या की आवश्यकता होती है, जैसे:

• एक _{2 · i -1} ≤ एक _{2 · i}
• एक _{2 · i} ≥ एक _{2 · i + 1}

सभी के लिए मैं 1 से n We 2 तक। हम इस तरह के क्रमचय में वृद्धि की वृद्धि को कहते हैं।



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



जाहिर है, यदि क्रमपरिवर्तन की लंबाई 0 या 1 है, तो उत्तर 1 है।



मान लीजिए कि हम 0 से n तक की सभी लंबाई के लिए उत्तर जानते हैं, हम उत्तर को +1 के लिए पाते हैं। हम कुल संख्या अनुक्रमों पर विचार करेंगे। बढ़ती हुई संख्या प्राप्त करने के लिए, आपको अनुक्रमों की कुल संख्या को 2 से विभाजित करने की आवश्यकता है, क्योंकि बढ़ती संख्या घटने की संख्या के बराबर है।



चलो n +1 को 2 · k पर रखा जाए, फिर पहले हमारे पास 2 · k an1 की लंबाई के साथ एक बढ़ती हुई कटाव है, और फिर n ·2 · k +1 की लंबाई के साथ एक बढ़ती sawtooth है। पहले 2 · k positions1 पदों के लिए, हम किसी भी n संख्या को चुन सकते हैं। कुल में, हम प्राप्त करते हैं कि लंबाई n + 1 के क्रमपरिवर्तन की संख्या जिसके लिए संख्या n + 1 स्थिति में है 2 · k : ans _{2 · k} · ₁ · ans _{n ·2 · k +1} · Binom ( n , 2 / k −1) ।



N +1 को स्थिति 2 · k +1 पर रखा जाए, फिर पहले हमारे पास 2 oth k की लंबाई के साथ एक घटता हुआ sawtooth है, और फिर n ·2 · k की लंबाई के साथ बढ़ रहा है। पहले 2 · k पदों के लिए, हम किसी भी n संख्या को चुन सकते हैं। कुल हमें यह मिलता है कि लंबाई n + 1 के क्रमपरिवर्तन की संख्या जिसके लिए नंबर n + 1 स्थिति 2 · k + 1: ans _{2 · k} · ans _{n −2 · k} · Binom ( n , 2 · k )।



कुल, लंबाई n +1 के sawtooth दृश्यों की कुल संख्या: ans _{n +1} = _k ⁿ _{k = 0} ans _k · ans _{n - k} · Binom (n, k) ।



टास्क ई। वेतन



विचार: अन्ना मालोवा

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

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



इस समस्या में, एक निर्देशित ग्राफ़ दिया गया है। सभी पसलियों को तीन भागों में वर्गीकृत किया जा सकता है:

• इस रिब के शीर्ष पर वेतन और बोनस की किसी भी व्यवस्था में, नेतृत्व की शर्त पूरी की जाएगी;
• नेतृत्व की शर्तों को पूरा करने के लिए, या तो इस रिब के दोनों छोरों पर एक बोनस के साथ वेतन को बदलना आवश्यक है, या किसी भी परिवर्तन के लिए नहीं;
• मैनुअल की शर्तों को पूरा करने के लिए, इस रिब के कोने में से एक पर बोनस के साथ वेतन को बदलना आवश्यक है।

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



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



टास्क एफ रोबोट



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

कार्यान्वयन: बोरिस मिनाएव, आर्टेम वासिलिव

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



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



पहले, बिना किसी शर्त के एक सेल से दूसरे सेल में जाने के तरीकों की संख्या ज्ञात करें कि आप अंतिम सेल से पहले अंतिम सेल पर नहीं जा सकते हैं। इस समस्या को निर्देशांक द्वारा स्वतंत्र रूप से हल किया जा सकता है, और फिर एक समन्वय में कितनी चालें बनाई गईं, और दूसरे में कितनी संख्या में पुनरावृत्ति हुई है। कैसे एक आयामी मामले में समस्या को हल करने के लिए? बता दें कि रोबोट में शुरुआत में निर्देशांक x _{1 है} , और अंत में इसके पास निर्देशांक x ₂ होना चाहिए। A = | x ₂ - x ₁ | और कुल t चालें बनाई गईं। तब विभिन्न विधियों की संख्या t ( t - a ) / 2 ( t - के साथ संयोजन की संख्या के बराबर होगी - एक गैर-नकारात्मक और सम होनी चाहिए)। हालांकि, किसी को यह ध्यान रखना चाहिए कि यात्रा के दौरान रोबोट केवल एक सकारात्मक समन्वय रख सकता है। ऐसा करने के लिए, सेल से प्राप्त करने के तरीकों की संख्या से घटाएं - x ₁ से x ₂ । यह सच है, क्योंकि x ₁ से पथों के बीच एक-से-एक पत्राचार दिखाया जा सकता है जो समन्वय की सकारात्मकता की आवश्यकता का उल्लंघन करता है, साथ ही साथ x ₁ से सभी पथ। एक दूसरे से संबंधित रास्तों में पहले भाग में दर्पण होगा (जब तक कि वे सेल 0 में प्रवेश न करें) और आम दूसरे भाग।



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



अब विचार करें कि इस तथ्य को कैसे ध्यान में रखा जाए कि अंतिम चरण तक रोबोट अंतिम सेल में प्रवेश नहीं कर सकता है। हम गतिशील प्रोग्रामिंग का उपयोग करके उत्तर पर विचार करेंगे। बता दें कि टी मूव से कम सेल में पहुंचने के तरीकों की संख्या पहले ही गिनी जा चुकी है। टी मूव्स के लिए इन मानों की गणना करने के लिए, टी चालों में ऐसा करने के लिए कुल तरीकों पर विचार करें और इससे सभी तरीकों को घटाएं जो टी से पहले अंतिम सेल में प्रवेश करते हैं। ऐसा करने के लिए, हम पहले कदम की संख्या को हल करेंगे, जिसमें रोबोट अंतिम सेल पर जाएगा और सेल से बाहर निकलने के तरीकों की संख्या से संबंधित तरीकों की संख्या को गुणा करेगा ( x ₂ , y ₂ ) और शेष समय में उस पर वापस लौटें। उसी समय, रोबोट अंतिम सेल में जितनी बार आवश्यक हो (दूसरे भाग में) का दौरा कर सकता है।



ध्यान दें कि अब तक उल्लिखित समाधान t ^{2 के} लिए काम करता है। तेजी से समाधान के लिए, किसी को कार्य उत्पन्न करने के मामले में कारण होना चाहिए। Denote f (x) = f ₀ x ⁰ + f ₁ x ¹ + ... + f _t x ^t + ... , जहाँ f _i का उत्तर है, कोई समस्या नहीं है। इसी प्रकार, हम गणना (x) को परिभाषित करते हैं - रास्तों की संख्या के लिए जनरेटिंग फ़ंक्शन, अंतिम मोड़ पर पहली प्रविष्टि की शर्तों को ध्यान में रखे बिना, चक्र (x) - अंतिम सेल से स्वयं के लिए पथों की संख्या के लिए जनरेटिंग फ़ंक्शन। च _{i के} लिए पुनरावृत्ति संबंधों से, हम संबंध कार्यों को व्युत्पन्न कर सकते हैं: f (x) = count (x) - f (x) चक्र (x) , whence f (x) = count (x) / (चक्र) (x) + 1) = गिनती (x) (चक्र (x) + 1) ^-1 । च की गणना करने के लिए , आपको दाईं ओर अंश के पहले t + 1 सदस्यों को गिनने की आवश्यकता है। यह चक्र (x) + 1 बहुपद modulo x ^{t + 1} के व्युत्क्रम की गणना करके, और परिणाम के साथ गिनती (x) गुणा करके किया जा सकता है। व्युत्क्रम बहुपद मॉडुलो x ^{t + 1} को तेजी से फूरियर रूपांतरण का उपयोग करके समय O ( t log t ) में लिया जा सकता है। कुल रन समय: ओ ( टी लॉग टी )।