संकेतों को बदलें: प्रतिस्पर्धी प्रोग्रामिंग प्रश्न को हल करने के लिए गतिशील प्रोग्रामिंग का उपयोग कैसे करें

यदि आप मेरे जैसे प्रतिस्पर्धी प्रोग्रामर हैं, तो दुनिया की सबसे अच्छी भावनाओं में से एक, आपके प्रोग्राम को सबसे प्रसिद्ध प्रोग्रामिंग प्लेटफ़ॉर्म, कोडशीफ में से एक पर पहले प्रयास में स्वीकार किए जाते हुए देख रहा है।

मैं अंडरग्रेजुएट के दौरान एक शौकीन चावला प्रतिस्पर्धी प्रोग्रामर था, और फिर डेवलपर @Hike के रूप में काम करने के दौरान इसके साथ संपर्क खो दिया। हालांकि, मैंने हाल ही में प्रोग्रामिंग की इस साहसिक दुनिया में फिर से शुरुआत की, सभी मेरे दोस्त दिव्या गोदयाल के लिए धन्यवाद।

CodeChef मई 2018 लंबी चुनौती लगभग एक घंटे पहले समाप्त हो गई, और मैंने इस लेख को प्रतियोगिता में एक प्रश्न का वर्णन करने वाली पोस्ट के रूप में लिखने का फैसला किया।

किसी भी अधिक समय को बर्बाद किए बिना, आइए इसे प्राप्त करें।

समस्या कथन को उजागर करना

आइए कुछ उदाहरणों को बेहतर ढंग से समझने के लिए कि समस्या कथन क्या पूछ रहा है।

निम्नलिखित संख्या अनुक्रम पर विचार करें।

4 3 1 2

अब सवाल हमें एक निश्चित ऑपरेशन करने के लिए कहता है (संभवतः 0 बार, अनुक्रम को अपरिवर्तित छोड़कर)। हम संख्याओं के एक निश्चित क्रम को नकार सकते हैं और एक नया अनुक्रम प्राप्त कर सकते हैं।

-4 3 1 2
4 -3 1 -2
4 3 -1 2
4 3 1 -2
-4 -3 1 2 आदि।

प्रश्न कहता है कि परिणामी अनुक्रम को निम्नलिखित अवरोध को पूरा करना चाहिए:

1 से अधिक लंबाई वाले किसी भी विकल्प के तत्वों का योग सख्ती से सकारात्मक है।

स्पष्ट रूप से, निम्नलिखित अनुक्रम मान्य नहीं हैं:

-4 3 1 2
4 -3 1 -2
4 3 1 -2
-4 -3 1 2
-4 -3 -1 -2
4 3 -1 -2

हमारे पास केवल 2 वैध परिणाम हैं जो ऊपर उल्लिखित ऑपरेशन करके प्राप्त किए जा सकते हैं। नोट: हमने सभी संभावित परिणामों को नीचे नहीं लिखा है। यह 2 ^ n होगा, जो इस मामले में 16 है, क्योंकि हर संख्या के लिए हमारे पास दो विकल्प हैं। या तो इसे नकारना है, या नहीं।

तो दो मान्य क्रम हैं:

4 3 1 2

तथा

4 3 -1 2

मूल अनुक्रम हमेशा मान्य अनुक्रमों में से एक होगा क्योंकि इसमें सभी संख्याएं सकारात्मक हैं।

अब सवाल हमें न्यूनतम राशि के साथ अनुक्रम खोजने के लिए कहता है। इसलिए हमने जो उदाहरण दिया है, उसके लिए आवश्यक अनुक्रम 4 3 -1 2 होगा।

क्या लालची काम करेंगे?

इस प्रश्न में एक लालची दृष्टिकोण यह होगा कि यदि दिए गए अवरोधों को संतुष्ट करते हुए किसी संख्या को नकारना संभव है, तो हमें उस संख्या को नकारना चाहिए। यह दृष्टिकोण हालांकि, हमेशा सही परिणाम नहीं देगा। निम्नलिखित उदाहरण पर विचार करें।

4 1 3 2

यहां, इन तीन मान्य संख्याओं का होना संभव है:

4 1 3 2 4 -1 3 2 4 1 3 -2

स्पष्ट रूप से, संख्या 2 और 1 दोनों को नकारा जा सकता है। लेकिन एक ही समय में दोनों नहीं। यदि हम किसी संख्या को लालच से नकारते हैं - अर्थात, यदि कोई संख्या को नकारा जा सकता है, तो हम इसे नकारते हैं - तब यह संभव है कि हम संख्या को नकारते हुए समाप्त हो सकते हैं। १. तब आप संख्या २ को नकार नहीं पाएंगे। २. यह हमें एक उप-अपनाने वाला समाधान देगा।

इसलिए यह लालची दृष्टिकोण यहाँ काम नहीं करेगा। हमें "एक नंबर के लिए नकारा नहीं जाए या नहीं और क्या इष्टतम समाधान हमें देता है देखें" की एक विशिष्ट पसंद का प्रयास करना है।

इससे डायनामिक प्रोग्रामिंग जैसी महक आती है।

अच्छा ol 'डायनामिक प्रोग्रामिंग

सबसे दिलचस्प एल्गोरिथम तकनीकों में से एक है, और संभवतः सबसे खतरनाक में से एक, गतिशील प्रोग्रामिंग है। यह वह तकनीक है जिसका उपयोग हम इस विशेष समस्या को हल करने के लिए करने जा रहे हैं।

किसी भी गतिशील प्रोग्रामिंग समस्या में दो सबसे महत्वपूर्ण चरण हैं:

  1. आवर्तक संबंध की पहचान करना।
  2. पता लगाना कि क्या याद रखना है। (याद नहीं: पी)

डीपी-आधारित दृष्टिकोण यहाँ दो बुनियादी भागों में विभाजित है।

  • एक मुख्य पुनरावृत्ति है जिसका उपयोग हम अंतिम सेट की न्यूनतम राशि का पता लगाने के लिए करते हैं। ध्यान दें, डायनामिक प्रोग्रामिंग का उपयोग सीधे अंतिम सेट प्राप्त करने के लिए नहीं किया जाता है, बस संख्याओं के अंतिम सेट का योग है। तो हमारे गतिशील प्रोग्रामिंग दृष्टिकोण को सही तरीके से ऊपर दिए गए उदाहरण के लिए 8. 4 + 3 + (-1) + 2 = 8 के रूप में मिलेगा।
  • वास्तव में हमें जिन चीज़ों की आवश्यकता होती है, वे संख्याओं का अंतिम संशोधित सेट है, जहाँ संख्याओं में से कुछ (संभवतः कोई नहीं) नकार दी जाती हैं। हम संख्याओं के वास्तविक सेट का पता लगाने के लिए एक पेरेंट पॉइंटर और बैकट्रैकिंग की अवधारणा का उपयोग करते हैं।

हमारे गतिशील प्रोग्रामिंग दृष्टिकोण के लिए हमारे पुनरावर्तन संबंध पर आगे बढ़ें।

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

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

हमें ओ (1) में यह जानना होगा कि क्या कोई संख्या नकारात्मक हो सकती है या नहीं। चूंकि हम संस्मरण-आधारित समाधान के साथ एक पुनरावृत्ति का अनुसरण कर रहे हैं, जब भी हम पुनरावृत्ति में एक इंडेक्स i पर होते हैं, तो हमें यकीन है कि संख्या को दाईं ओर (i + 1 आगे) इस बिंदु तक संसाधित नहीं किया गया है। इसका मतलब है कि वे सभी अभी भी सकारात्मक हैं।

सूचकांक i की संख्या को नकारा जा सकता है, इस बात का चुनाव दाएं हाथ की तरफ (यदि एक है तो) और बाएं हाथ की तरफ (यदि एक है) पर निर्भर है। दाहिना हाथ आसान है। हम सभी की जरूरत है अगर जाँच करने के लिए है

संख्या [i] <संख्या [i + 1]

क्योंकि अगर यह सच नहीं है, तो इन दोनों को जोड़ने से प्रतिस्थापन के लिए एक नकारात्मक मूल्य होगा [i, i + 1] इस प्रकार यह एक अवैध संचालन बना रहा है।

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

तो मान लें कि हमारे पास संख्या 4 1 2 1 का यह सेट है और हमने पहले 1 को नकार दिया था और अब हम अंतिम संख्या (1) को संसाधित कर रहे हैं।

4 -1 2 [1]

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

-1 2 -1

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

हम निम्नलिखित दृष्टिकोण को सीधे यहाँ लागू नहीं कर सकते हैं:

यदि संख्या [i] <संख्या [i - 1] है, तो नकार पर जाना अच्छा है।

क्योंकि, यद्यपि 1 <2, अगर हम उस अंतिम 1 को नकारते हैं और साथ ही हमारे पास संख्याओं का एक अवैध सेट होगा जैसा कि ऊपर देखा गया है। इसलिए यह सरल तरीका या जाँच यहाँ काम नहीं करेगा।

यहां बूलियन वैरिएबल आता है जो हमें बताता है कि, क्या एक इंडेक्स i, i - 2 पर संख्या नकारात्मक थी या नहीं। दो परिदृश्यों पर विचार करें।

  • हां, इंडेक्स I - 2 की संख्या को उदाहरण में दर्शाया गया था जैसे कि केवल दर्शाया गया हो। उस स्थिति में, i - 2 पर संख्या की उपेक्षा करने से i पर संख्या की क्षमता में कमी होगी - 1. उदाहरण 4 4 2 1 में, 1 पर अनुक्रमणिका 1 (0 आधारित अनुक्रमण) को नकारने से संख्या की क्षमता कम हो जाएगी। 2 (सूचकांक 2 पर) 1 से। हम संख्याओं के शेष मूल्यों का उल्लेख यहां की क्षमताओं के रूप में करते हैं। हमें इस कम क्षमता पर विचार करने की आवश्यकता है कि चेक करते समय यह देखने के लिए कि कोई संख्या नकारात्मक हो सकती है या नहीं।
संख्या [i] <घटाई क्षमता ONumberAt (i - 1)
  • यदि सूचकांक I - 2 पर संख्या उपेक्षित नहीं है, तो i - 1 की संख्या इसकी पूर्ण क्षमता पर है। साधारण जाँच
संख्या [i] <संख्या [i - 1]

यह देखने के लिए पर्याप्त होगा कि क्या हम सूचकांक I पर संख्या को नकार सकते हैं।

आइए उपरोक्त सभी विचारों वाले पुनरावर्तन के लिए कोड को देखें।

यह सब अच्छा है और बांका है। लेकिन, यह केवल पुनरावृत्ति है, और शीर्षक गतिशील प्रोग्रामिंग कहता है। इसका मतलब है कि वहाँ अतिव्यापी उपप्रकारों होगा। आइए हम पुनरावर्तन वृक्ष को देखें कि क्या कोई हैं।

जैसा कि आप देख सकते हैं, पुनरावृत्ति पेड़ में अतिव्यापी उपप्रकार हैं। इसलिए हम संस्मरण का उपयोग कर सकते हैं।

संस्मरण के रूप में सरल है:

"" "यह सबसे ऊपर आता है। हम जाँचते हैं कि क्या राज्य सूचकांक के गुच्छे द्वारा दर्शाया गया है और बूलियन चर पहले से ही कैश किया गया है" "
अगर (मेमो [i] [is_prev_negated]! = INF)
{
    वापसी ज्ञापन [i] [is_prev_negated];
}
...... CODE
# इस सूचकांक से न्यूनतम राशि कैश करें।
ज्ञापन [i] [is_prev_negated] = min (सकारात्मक, नकारात्मक);
# अंतिम सेट का पता लगाने के लिए पैरेंट पॉइंटर का उपयोग किया जाता है
जनक [i] [is_prev_negated] = min (स्थिति, ऋणात्मक) == स्थिति? 1 1;

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

हालाँकि, यह प्रश्न हमें वास्तव में संख्याओं के अंतिम सेट को छापने के लिए कहता है, जो ऐसे संशोधन करने के बाद न्यूनतम राशि देता है। उसके लिए, हमें एक पेरेंट पॉइंटर का उपयोग करने की आवश्यकता है जो हमें हर इंडेक्स और बूलियन वैरिएबल__पर्व_नेगेट के मान पर बताएगा कि क्या इष्टतम कार्रवाई की गई थी।

जनक [i] [is_prev_negated] = min (स्थिति, ऋणात्मक) == स्थिति? 1 1;

इसलिए हम केवल 1 या 1 को स्टोर करते हैं, जो इस बात पर निर्भर करता है कि इंडेक्स i (यदि संभव हो तो!) की संख्या हमें कम से कम दी गई है या अगर इसे अनदेखा करने का विकल्प दिया जाए तो यह न्यूनतम योग है।

बैक ट्रैकिंग

अब वह हिस्सा आता है जहाँ हम अपनी मूल समस्या का हल ढूंढने के लिए पीछे हटते हैं। ध्यान दें कि पहले नंबर के लिए निर्णय वही है जो आगे चलकर पुनरावृत्ति का प्रचार करता है। यदि पहले नंबर को नकार दिया गया था, तो दूसरा नंबर सकारात्मक होगा और तीसरे नंबर का निर्णय माता-पिता [2] [सत्य] का उपयोग करके पाया जा सकता है। इसी तरह, यदि पहली संख्या को नकारा नहीं गया है, तो हम दूसरे नंबर पर जाते हैं और यह निर्णय माता-पिता [1] [गलत] और इसी तरह का उपयोग करके पाया जा सकता है। कोड को देखते हैं।

एक बेहतर दृष्टिकोण

यदि आप सुझाए गए समाधान की अंतरिक्ष जटिलता पर एक नज़र डालते हैं, तो आप देखेंगे कि यह एक 2 आयामी गतिशील प्रोग्रामिंग समाधान है, क्योंकि पुनरावृत्ति की स्थिति को दो चर द्वारा दर्शाया जाता है अर्थात सूचकांक जो मैं विचार कर रहा हूं कि किस संख्या का प्रतिनिधित्व करता है और तब बूलियन वैरिएबल is_prev_negated है। तो अंतरिक्ष की जटिलता और समय की जटिलता O (n * 2) होगी जो अनिवार्य रूप से O (n) है।

हालाँकि, इस समस्या को हल करने के लिए थोड़ा बेहतर तरीका है, जैसा कि दिव्या गोदयाल ने सुझाया है। इस समस्या को 1 आयामी गतिशील प्रोग्रामिंग आधारित समाधान द्वारा भी हल किया जा सकता है।

अनिवार्य रूप से, बूलियन चर is_prev_negated हमें यह तय करने में मदद कर रहा है कि क्या हम इंडेक्स i पर दिए गए नंबर को नकार सकते हैं या नहीं जहाँ तक सरणी के बाएँ हाथ का संबंध है अर्थात 0 से सभी संख्याएँ .. i-1 क्योंकि दाहिने हाथ साइड वैसे भी सुरक्षित है क्योंकि उस तरफ के सभी नंबर पॉजिटिव हैं (जैसा कि रिकर्सन उन तक अभी तक नहीं पहुंचा है)। तो दाहिने हाथ की ओर के लिए हमने केवल i + 1 पर संख्या की जाँच की, लेकिन अनुक्रमणिका के बाएँ हाथ की ओर के लिए हमें बूलियन चर का उपयोग करना था।

यह पता चला है, कि हम इस बूलियन वैरिएबल को पूरी तरह से छोड़ सकते हैं और बस यह तय करने के लिए तत्पर हैं कि एक नंबर को नकारा जा सकता है या नहीं। जिसका सीधा सा मतलब है कि अगर आप किसी इंडेक्स i पर हैं, तो आप यह जांचते हैं कि क्या i + 2 में एलीमेंट के साथ उस एलिमेंट में i + 1 पर एलीमेंट को निगलने की क्षमता है या नहीं।

नंबर [i] + नंबर [i + 2]> = संख्या [i + 1 (SWALLOW)

यदि ऐसी कोई संभावना है, तो हम सीधे i + 3if पर जाते हैं हम i पर तत्व को नकारात्मक करते हैं क्योंकि i + 1 और i + 2 पर तत्व ऐसे परिदृश्य में नकारात्मक नहीं हो सकते।

यदि निगली हुई स्थिति संतुष्ट नहीं है और हम इंडेक्स i पर संख्या को नकारते हैं, तो हम इंडेक्स i + 2 पर जा सकते हैं क्योंकि किसी भी स्थिति में, लगातार दो संख्याओं को नकारा नहीं जा सकता है। इसलिए यदि i की संख्या को नकारा गया, तो i + 1 की संख्या को सकारात्मक होना चाहिए। निगल की जांच यह देखने के लिए है कि क्या i + 2 की संख्या निश्चित रूप से सकारात्मक होनी चाहिए या यदि हम इस विकल्प का उपयोग कर सकते हैं कि क्या नकारना है या नहीं।

बेहतर समझ के लिए कोड को देखें।

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

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