पिछले शनिवार को, रूसी कोड कप 2012 प्रोग्रामिंग प्रतियोगिता का दूसरा क्वालीफाइंग दौर आयोजित किया गया था ।



रूसी कोड कप एक व्यक्तिगत खेल प्रोग्रामिंग प्रतियोगिता है जो प्रतिवर्ष Mail.Ru Group द्वारा आयोजित की जाती है। यह पारंपरिक रूप से तीन चरणों में होता है: गर्मियों की शुरुआत में तीन क्वालीफिकेशन राउंड होते हैं, फिर क्वालीफाइंग राउंड में सर्वश्रेष्ठ भाग लेते हैं, फाइनल में क्वालीफाइंग राउंड प्रतियोगिता के पहले पचास विजेता। व्यक्तिगत उपस्थिति के लिए केवल उनमें से अंतिम की आवश्यकता होगी, जबकि शेष ऑनलाइन आयोजित की जाती है। सभी फाइनलिस्ट को बहुमूल्य उपहार से सम्मानित किया जाएगा, और प्रथम स्थान वाले प्रतिभागी के लिए पुरस्कार $ 10,000 होगा। दूसरे और तीसरे स्थान के लिए 5,000 और 3,000 डॉलर का भरोसा करते हैं।

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

यह रविवार, 10 जून, सुबह 11:00 बजे, अंतिम क्वालीफाइंग राउंड होगा, जिसमें से दो सौ प्रतिभागी "सेमीफाइनल" - क्वालीफाइंग राउंड को आगे बढ़ाएंगे। दूसरे दौर में, इसके लिए यह दो समस्याओं को हल करने के लिए पर्याप्त था - एक सरल और एक कठिन, और एक ही समय में आधे आवंटित समय को पूरा करना। हम रविवार को आपका इंतजार कर रहे हैं और आपको शुभकामनाएं देते हैं!

खैर, अब चलिए कार्यों को आगे बढ़ाते हैं।

"सरल कार्य"

जाहिर है, "टॉकिंग" नाम और सामग्री के साथ यह कार्य वार्म अप करने के लिए था - इसे जल्दी और पहले प्रयास में हल किया जाना था। प्रतिभागी के कार्यक्रम को जवाब देना चाहिए कि क्या कार्य सरल कार्य के लिए मापदंड की जाँच करके सरल है। इनपुट पर, शाखा ऑपरेटरों (ओबी) और लूप ऑपरेटरों (ओटी) की संख्या दी गई थी, और हाँ दो मामलों में से एक में प्रदर्शित किया जाना चाहिए:
- 1 ओम से अधिक नहीं और 2 ओसी से अधिक नहीं,
- 2 ओम से अधिक नहीं और 1 ओसी ​​से अधिक नहीं।
अन्य सभी मामलों में, "नहीं" आउटपुट होना चाहिए।

पूरी स्थिति, साइट पर देखें रशियनकोड Cup.ru

यहाँ इस कार्य का विस्तार से विश्लेषण करने का कोई मतलब नहीं है - यह वास्तव में बहुत सरल है।

यह दिलचस्प है कि इस समस्या का समाधान एक सरल कार्य की परिभाषा को पुनरावृत्ति करता है। इसके सबसे सुरुचिपूर्ण समाधानों में से एक है प्रवेश किए गए मूल्यों के वर्गों की राशि की जांच करना: (ओबी * ओबी + ओटी * ओटी) <6।

सत्यापन के लिए कुल 1261 फैसले भेजे गए थे, जिनमें से सही 722 (57%) थे। रूसी कोड कप में 77% प्रतिभागियों ने इस कार्य को पूरा किया। पहला फैसला आंद्रेई मैकेसे ने दौर शुरू होने के 1 मिनट 37 सेकंड बाद किया।

कुंजी

यह कार्य थोड़ा अधिक जटिल है। समस्या की स्थिति से, हमारी स्ट्रिंग एन्क्रिप्टेड स्ट्रिंग के केंद्र के सापेक्ष प्रतिबिंबित होती है, इसलिए, सिफर निम्नलिखित निर्माण है:

(एन अक्षर) स्ट्रिंग (एम अक्षर) एकॉर्ट्स (एन अक्षर),

सभी मामलों के लिए जब उपसर्ग और प्रत्यय एक दूसरे के साथ प्रतिच्छेद नहीं करते हैं। एक उदाहरण, जब यह संभव है, तो समस्या कथन में प्रदर्शित किया गया था - फिर प्रत्यय और उपसर्ग ने समान वर्ण निर्धारित किए: ababc को एन्क्रिप्ट किया गया बाबा था।

पूरी स्थिति, साइट पर देखें रशियनकोड Cup.ru

जाहिर है, एक स्ट्रिंग को पुनर्स्थापित करने के लिए, आपको एक अनुक्रम खोजने की आवश्यकता है जिसमें एक सटीक दर्पण छवि है। अर्थात्, पदों की अधिकतम निरंतर अनुक्रम जिसके लिए शर्त [i] = s [l - i - 1] पूरी होती है, वांछित रेखा का गठन करती है।

ऐसा करने के लिए, हम प्रत्येक स्थिति के लिए गणना कर सकते हैं i - k का मान - सबसे बड़ी सबस्ट्रिंग s की लंबाई [i - k..i], जिसमें सभी वर्ण हमारी स्थिति को संतुष्ट करते हैं। पाए गए मान सरणी में संग्रहीत किए जाते हैं, जिसके बाद हम इसमें अधिकतम मूल्य के सबसे बाईं घटना की स्थिति पाते हैं।

प्रतिस्थापन पी [i] की लंबाई की गणना करने के लिए, हम पहले से गणना की गई मूल्य p [i - 1] का उपयोग करेंगे, इससे समय और संसाधन बहुत कम हो जाएंगे।

• p [i] = 0 अगर s [i] <> s [l - i - १]
• p [i] = १ अगर i = ० और s [०] = s [l –१]
• p [i] = p [i-१] + १ अगर i> ० और s [i] = s [l - i - १]

संख्या	0	1	2	3	4	5	6	7	8	9	10
चार	ग	एक्स	ख	एक	y	घ	z	एक	ख	एक्स	ई
s [i] = s [li-1]?	ग = ई?	x = x?	बी = बी?	a = a?	y = z?	d = d	z = y?	a = a?	बी = बी?	x = x?	ई = ग?
जवाब	नहीं	हां	हां	हां	नहीं	हां	नहीं	हां	हां	हां	नहीं
पी [i]	0	0 + 1 =	1 + 1 =	2 + 1 =	0	0 + 1 =	0	0 + 1 =	1 + 1 =	2 + 1 =	0
	0	1	2	3	0	1	0	1	2	3	0
अधिकतम				3						3	0

उत्तर लंबाई पी का एक विकल्प है [अधिकतम] संख्या अधिकतम के साथ एक चरित्र में समाप्त होता है, जहां अधिकतम सरणी पी में अधिकतम मूल्य के बाईं सबसे बड़ी घटना की स्थिति है।

कुल मिलाकर, 1,158 फैसले सत्यापन के लिए भेजे गए, जिनमें से 337 सही (29%) थे। 36% रूसी कोड कप QR2 प्रतिभागियों ने इस कार्य को पूरा किया। पहला निर्णय कर्टोव निकोले के दौर की शुरुआत के 9 मिनट बाद आया।

"चतुर्पाश्वीय"

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

पूरी स्थिति, साइट पर देखें रशियनकोड Cup.ru

आपको याद दिला दूं कि एक tetrahedron एक पॉलीहेड्रॉन है जिसके चेहरे चार त्रिकोण हैं (दूसरे शब्दों में, एक त्रिकोणीय पिरामिड)।

यह सब इस तथ्य से शुरू होता है कि हम टेट्राहेड्रोन के किनारों के संभावित मैचों को सुलझाते हैं। हम एबीसीडी के रूप में वांछित टेट्राहेड्रोन को दर्शाते हैं। उसकी छह पसलियाँ हैं: AB, AC, AD, BC, BD और CD। सभी 6 से अधिक चलते हैं! = 720 विकल्प, जो मैच किस किनारे से मेल खाता है। अब यह सत्यापित करना बाकी है कि संबंधित टेट्राहेड्रॉन मौजूद है।

टेट्राहेड्रोन के अस्तित्व की जांच कैसे करें? यहां कम से कम तीन समाधान हैं।

पहला समाधान टेट्राहेड्रोन की मात्रा की गणना पर आधारित है। सरलतम उपाय यह है कि टेट्राहेड्रोन की मात्रा की गणना उसके चेहरे द्वारा की जाए। यह कार्य अपने आप में आसान नहीं है, मैं यहाँ सूत्र दूंगा:



तदनुसार, यदि समानता का दाहिना हाथ नकारात्मक हो जाता है या चेहरे (त्रिकोण असमानता) में त्रिकोण का निर्माण करना असंभव है, तो टेट्राहेड्रॉन अभिसरण नहीं करेगा।

रुचि रखने वालों के लिए, यहां यह सूत्र प्रदर्शित किया गया है: http://www.mccme.ru/free-books/mmmf-lectures/book.21.pdf

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

चेहरे रखने के लिए दो सीमित विकल्प हैं, जिसमें टेट्राहेड्रॉन एक सपाट आकृति में बदल जाता है। पहला - जब चेहरों को एक-दूसरे (सीएबी और सीबीडी) के सापेक्ष 180 डिग्री घुमाया जाता है, और दूसरा - जब वे "मुड़े हुए" होते हैं और एक "शून्य कोण" (सीएडीडी और सीडीबी) बनाते हैं। एक दूसरे के सापेक्ष चेहरे की सभी अनुमेय स्थिति इन सीमा के बीच की सीमा में हैं। अंतिम छोर (AD) पहले सीमित संस्करण (AD) में अपनी सबसे बड़ी लंबाई तक पहुँचता है, और अंतिम (A'D) में सबसे छोटा होता है। नतीजतन, एक टेट्राहेड्रॉन मौजूद होगा यदि अंतिम किनारे की यह लंबाई हमारे द्वारा पाई गई सीमा (ए डी डी से एडी) में फिट होती है।

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

कार्यक्रम की जांच करनी चाहिए कि शेष चेहरे की लंबाई निर्दिष्ट सीमाओं में फिट होती है या नहीं। यदि ऐसा है, तो ऐसी लंबाई के एक टेट्राहेड्रॉन को "इकट्ठा" किया जा सकता है।




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

कई मामलों में, समाधान केवल इस तक सीमित था; इस बीच, ऐसी स्थितियां हैं जब संकेतित पक्षों के साथ त्रिकोण का निर्माण किया जा सकता है, और उनके लिए एक टेट्राहेड्रोन को इकट्ठा करना असंभव है।

उदाहरण के लिए, यदि हमारे पास चेहरे (100,100,2,101,100,2) हैं, तो त्रिकोण (100,100,2) और (101,100,2) त्रिकोण की असमानता को औपचारिक रूप से संतुष्ट करते हैं, लेकिन ऐसे त्रिभुजों से एक चतुर्भुज को जोड़ना असंभव है। आंकड़े से, हम देखते हैं कि एज एसी लगभग एबी के समानांतर है, जिसका अर्थ है कि डी से सी तक की दूरी एबी के सापेक्ष एबीडी के किसी भी झुकाव के लिए शायद ही बदल जाएगी, जिससे हम यह निष्कर्ष निकाल सकते हैं कि डीबी लगभग बीसी के लंबवत है। इस स्थिति में, डीसी को लगभग पैरों के वर्गों के योग की जड़ के रूप में अनुमानित किया जा सकता है, अर्थात, डीसी लगभग 10 होना चाहिए, और 2 बिल्कुल नहीं, जैसा कि हमने स्थिति में मान लिया था।



इसलिए, चेहरों में त्रिकोणों के लिए जाँच के अलावा, त्रिकोणीय कोणों के लिए एक अतिरिक्त परीक्षण करना आवश्यक है। त्रिवेणी कोण के अस्तित्व के लिए दो आवश्यक और पर्याप्त शर्तें हैं:

• त्रिभुज कोण के सपाट कोणों का योग 360 डिग्री से कम होना चाहिए,
• त्रिक कोण के प्रत्येक विमान कोण दो अन्य विमान कोणों के योग से कम होना चाहिए।

समतल कोण त्रिभुज के लिए कोसाइन प्रमेय के माध्यम से पाया जाता है।

कुल मिलाकर, 1088 फैसलों की जाँच करने का लक्ष्य था, जिनमें से केवल 74 (7%) सही थे। 8% रूसी कोड कप QR2 प्रतिभागियों ने इस कार्य को पूरा किया। पहला निर्णय दौर की शुरुआत के 30 मिनट बाद एविक्टॉर उपनाम वाले प्रतिभागी से आया।

"कार्य"

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

पूरी स्थिति, साइट पर देखें रशियनकोड Cup.ru

इस समस्या का मुख्य समाधान सबसेट (मास्क) के लिए एक गतिशील प्रोग्रामिंग विधि का चयन करना है। विधि में आगे के संचालन की सुविधा के लिए बिट सीक्वेंस के माध्यम से सेट को एन्कोडिंग करना शामिल है। छोटे सेट बिट संचालन के माध्यम से काम करना आसान है। विशेष रूप से, किसी विषय सेट को कोड करने के लिए 18 बिट्स की आवश्यकता होती है। फिर संख्या के द्विआधारी संकेतन में i-th बिट के लिए जिम्मेदार होगा कि क्या i-th विषय (1) पहले से ही लिया गया है या नहीं (0)। नतीजतन, एक मानक 32-बिट पूरे में आप सभी कई विषयों को स्टोर कर सकते हैं। कुल में, 2 ^ 18 मुखौटे प्राप्त होते हैं, 2 ^ 18 सबसेट को परिभाषित करते हैं।

बिट्स में सबसेट का भंडारण भी सुविधाजनक है क्योंकि बिटवाइज़ के मानक संचालन और आपको सेट्स को इंटरसेक्ट करने की अनुमति मिलती है, और बिटवाइज़ OR (OR) आपको सेटों को संयोजित करने की अनुमति देता है।

चूंकि समस्या के बयान में एक प्रतिबंध है कि आवश्यकता है कि जटिलता के प्रत्येक स्तर के एक कार्य को प्रस्तुत किया जाए, हम एक और आयाम - सरणी डीपी [i] [जे] को पेश करते हैं। वह निर्धारित करेगा कि क्या, पहले i स्तरों के कठिनाई से कार्य लेते हुए, बिट मास्क j द्वारा परिभाषित विषयों का एक सेट एकत्र करना संभव है, बिना किए गए कार्यों के बीच के विषयों को प्रतिच्छेद किए बिना।

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

for (int[] t : P) { Arrays.fill(t, -1);} //   “-1” P[0][0] = -2; //    for (int i = 0; i < tl.length; ++i) { //     for (Task t : tl[i]) { //    for (int mask = 0; mask < P[i].length; ++mask) { //     if ((mask & t.mask) == 0 && P[i][mask] != -1) { //         //       dp[i + 1][mask | t.mask] = t.num; } } } } //         if (dp[d][(1 << m) - 1] == -1) { out.println("Impossible"); // …   } else { out.println("OK"); int[] ans = new int[d]; int mask = (1 << m) - 1; //      for (int i = d; i > 0; --i) { ans[i - 1] = dp[i][mask] + 1; mask ^= mm[dp[i][mask]]; } for (int i : ans) { out.print(i + " "); } } 

सत्यापन के लिए कुल 407 फैसले भेजे गए, जिनमें से केवल 115 सही (28%) थे। रूसी कोड कप QR2 प्रतिभागियों के 12% ने इस कार्य को पूरा किया। पहला निर्णय निकिता इओफ़े से दौर शुरू होने के 16 मिनट बाद आया।

"टेक्स्ट एडिटर"

इनपुट में कार्य में, हम स्थिति और वर्ण में प्रवेश करते हैं (अल्फाबेटिक + ब्रैकेट), और आउटपुट पर, ब्रैकेट के प्रत्येक इनपुट के साथ, हमें पहले से दर्ज जोड़ी ब्रैकेट की स्थिति को वापस करना होगा, या brack1 यदि जोड़ी ब्रैकेट मौजूद नहीं है। यह स्थिति को सही ढंग से संभालने के लिए आवश्यक है कि इनपुट डेटा एक पहले जोड़े गए ब्रैकेट को दूसरे में बदल सकता है, साथ ही इस तथ्य को भी कि बहुत सारे वर्ण और कोष्ठक हो सकते हैं (पाठ आकार - 100000)।

पूरी स्थिति, साइट पर देखें रशियनकोड Cup.ru

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

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

एक एल्गोरिथ्म जो खंडों के एक पेड़ की अवधारणा को लागू करता है, वह यहां पाया जा सकता है: e-maxx.ru/algo/segment_ree ।

हमारे मामले में, लाइन ट्री में हम पाठ में प्रत्येक स्थिति के लिए ब्रैकेट अनुक्रम की वर्तमान "गहराई" को संग्रहीत करेंगे। यह पेड़ की पत्तियों में संग्रहीत किया जाएगा, सबसे ऊपर गणना की गई न्यूनतम पेड़ों को संग्रहीत किया जाएगा, पेड़ की जड़ में - पूरे पेड़ में न्यूनतम न्यूनतम।

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

ब्रैकेट सम्मिलित करते समय, सभी तत्वों को इसके दाईं ओर पुनर्गणना करना आवश्यक है, साथ ही इन तत्वों को कवर करने वाले कोने पर सभी मिनीमा। यहाँ तथाकथित है "विलंबित" अपडेट - परिवर्तन के बारे में जानकारी सबसे ऊपर रहती है और जब आप उन्हें एक्सेस करने की आवश्यकता होती है तो "पत्तियों" पर उतरते हैं।

सत्यापन के लिए कुल 159 निर्णय भेजे गए, जिनमें से केवल 8 (5%) सही थे। रूसी कोड कप QR2 प्रतिभागियों के 1% से भी कम ने इस कार्य को पूरा किया। पहला फैसला सर्गेई फेडोरोव के दौर की शुरुआत के 54 मिनट बाद हुआ।

---

• पहली योग्यता से डिबेटिंग
  तीसरी योग्यता से कार्यों का विश्लेषण
  
  
  अलाइव रऊफ
  अनुसंधान और शिक्षा निदेशक
  प्रोजेक्ट मैनेजर रूसी कोड कप
  Mail.Ru Group