algorithm - SPOJ Problemset (Classical): 9386. Re-Arrange II #[MAIN112] -

-

समस्या का विवरण (सुविधा के लिए यहां उद्धृत):

एन पूर्णांक के अनुक्रम के लिए, ए 1, ए 2, ..... ए

हम स्थिरता कारक पी की गणना कर सकते हैं, जैसे

P = sum सभी में (एआईटी-एआई -1) * सी [आई]) जहां 2 & lt; = i & lt; = N

सी [i] एक संख्या डाल करने की लागत है स्थिति i

आपका कार्य उन सभी अलग-अलग क्रमपरिवर्तनों पर विचार करने के लिए दिए गए एन नंबरों के लिए न्यूनतम पी खोजता है।

मुझे सिर्फ सही दिशा में एक कुहनी से ढंकना चाहिए इस समस्या को हल करने के लिए सामान्य दृष्टिकोण (स्यूडोकोड के छोटे बिट्स का स्वागत है, लेकिन एक बार समग्र एल्गोरिथ्म सामान्य रूप से स्पष्ट हो जाने पर मुझे समाधान के लिए बहुत अधिक कोड पर भरोसा है)

मैंने इस बारे में थोड़ी देर के लिए सोचा है, लेकिन अभी भी किसी भी समाधान पर पहुंचने से, जो इस समस्या (N & lt; = 15) की बाधाओं को संतुष्ट करता है एक क्रूरता बल दृष्टिकोण केवल N = 10 तक अच्छा प्रदर्शन करता है।

सबसे पहले, सबसे बड़ा संभव परीक्षण का मामला एन = 15, मुझे विश्वास नहीं है कि आप सभी 15 की गणना करने और समझने में सक्षम हैं! आपके उत्तर को पर्याप्त समय में ढूंढने के क्रम में क्रमिकता, क्योंकि जटिलता वर्ग इस की अनुमति नहीं देगा।

इसलिए हमें इस खोज स्थान को कम करने के लिए कई सरल मान्यताओं को बनाने की आवश्यकता है। यह वह जगह है जहां मैं फँस गया हूं। या हो सकता है कि यह इस क्रमबद्धता की जगह को शुरू करने के लिए चालाक तरीके से नीचे आता है?

मैंने इस समस्या को हल करने के लिए गतिशील प्रोग्रामिंग का उपयोग करने की कोशिश की है, क्योंकि क्रमपरिवर्तन कई आम बिट्स साझा करते हैं, जो कि प्रीकॉप्टेड (यादगार) और संग्रहीत और पुन: उपयोग किया जाता है, जैसे। ए [] = 123456 & amp; ए [] = 123465 दोनों ही आंशिक राशि 1234 के लिए दे देंगे, लेकिन इससे कोई सफलता नहीं मिली क्योंकि आपको अभी तक 15 से गुजरना पड़ता है! क्रमबद्धता और इससे पहले TLE का रास्ता होगा, इसलिए यह कोई अच्छा नहीं है।

एक और विचार है सी और सी के सभी तत्वों के बीच के अंतर के सभी संभव क्रमपरिवर्तनों के साथ काम करना, और पहले जोड़ी कम से कम एब्स (ए [आई] -ए [जे]) का उत्पादन करेगा * सी [के] इन सभी से मूल्य, उन और असाइन करें; उन्हें इस्तेमाल के रूप में चिह्नित करें, फिर मैं या जम्मू में से एक के साथ अगले जोड़ी बनाने के लिए, फिर से दोहराने और दोहराने के साथ जारी रखें। यह बहुपद समय (n ^ 3 लगभग अनुमान लगा रहा है) में पूरा होना चाहिए, लेकिन कुछ उदाहरणों के लिए धारणा विफल हो जाती है।

मुझे नहीं लगता कि यह समस्या कुछ को इसमें बदलने में शामिल होना बहुत मुश्किल होनी चाहिए ग्राफ समस्या की तरह - जहां ए [आई], ए [जे] फार्म नोड्स, और सी [के] किनारे की लागत इन नोड्स को जोड़ने, या शायद कुछ बुलियन सैट समस्या ... कि सभी नीचे जा रहा है लगता है गलत ट्रैक पूरी तरह से।

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

अग्रिम धन्यवाद ।

आप ओ (n * 2 ^ n) स्पेस, ओ (एन ^ 2 * N ^ 2) इसे हल करने के लिए सबसेट पर गतिशील प्रोग्रामिंग एल्गोरिथ्म।

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

गणना मूल रूप से है इस समाधान के रूप में एक ही संरचना

आप अपने डीपी विचार के साथ सही रास्ते पर थे अंतर्दृष्टि सिर्फ यही है कि इन सभी आंशिक रास्तों के बाद इष्टतम मार्ग समान है

1335

2135

2315 < / P>

3125

3215

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

> यहाँ कुछ TLE पायथन कोड है जो वर्णित एल्गोरिथ्म लागू करता है, लेकिन पायथन में निरंतर कारक मंदी की वजह से विफल रहता है। मैं सी ++ में बदल चुका हूं और मुझे एसी मिल गया। 

  वैश्विक ए वैश्विक सीए = [] सी = [] डीईफ़ हल (इस्तेमाल किया, अंतिम, कैश): यदि कैश में (इस्तेमाल किया, अंतिम): वापसी कैश [(इस्तेमाल किया, आखिरी)] cur_pos = len (उपयोग किया जाता है) अगर cur_pos == लेन (ए): 0 में एमएन = 1e10 रेंज में आईडीएक्स (लेन (ए)): यदि उपयोग में आईडीए नहीं है: next_used = used.union ([आइडीएक्स]) subcost = समाधान (अगली_उत्पादन, ए [आईडीएक्स], कैश) अतिरिक्त = सी [cur_pos] * abs (अंतिम - ए [idx]) mn = min (mn, subcost + अतिरिक्त) कैश [(उपयोग किया, अंतिम )] = एमएन रिटर्न एमएन टी = इंट (कच्चे_इनपुट ()) में मैं रेंज (टी) में: एन = इंट (कच्चे_इनपुट ()) ए = मैप (इंट, कच्चे_इनपुट ()। विभाजित ()) सी = नक्शा (इंट, रेंज (len (ए))) के लिए (/)>   प्रिंट करें ()। विभाजन ()। कैश = {} प्रिंट मिनट (हल (frozenset ([idx]), ए [idx], कैश)

Comments

Post a Comment

Popular posts from this blog

mysql - BLOB/TEXT column 'value' used in key specification without a key length -

-
I have developed an extension which works up to 1.6 on Magren (I'm trying Enterprise Edition, And I think the community is the same problem, because it is the same code). In my install script, I see the $ installer-> gt; CreateEntityTables ($ this- & gt; getTable ('alphanum / info')); The installation is done until it is not in the _text unit table. It crashed there! It turns out that when I log in to SQL and run it via PHPmyadmin, then this error is: Blob / Text column 'value' is used without the key 'key' . I saw the code there, and this is what is trying to create an index on the value column: -> addIndex ($ this- & gt; getIdxName ($ eavTableName, array ( 'attribute_id array (' attribute_id ',' value ')) - & gt; addIndex ($ this- & gt; getIdxName ($ eavTableName, array (' entity_type_id ' , 'Value')), array ('entity_type_id', 'value')) If there is no if statement is n...
Read more

c# - Using Vici cool Storage with monodroid -

-
Oh, for the moment I am not sure how it is officially supported, but for the success of the people Using Monodroid Vic Cool Storage I am able to leave and compile assemblies in my project, but while trying to use some classes, the errors of time have to be gathered. Especially when trying to connect like the example for Mono Touch string dbName = path. Cobain (environment. Gatefolder path (environment specialfolder personal), "mydb.db3"); // The following line will be called coolestation, where is the database, // to make it if it does not exist, and call a delegate that creates the necessary tables (only when the database file was newly created //) CSConfig.SetDB (DbName, true, () => {CSDatabase.ExecuteNonQuery ("Subscriber Integer Primary Key Attribute, Name Text (50) No, Number, Date First Text (30)");); There is no difference when I try to use the methods of CSConfig and when I cscfif If I try to pass 3 aggregates to STDB (3) then I get the invalid ...
Read more

python - referencing a variable in another function? -

-
I am an experienced TCL developer and write my own processes to help myself. I call it a proc i callVar, print out the value of the variable in a certain format, so I know that it is variable and what is the value "set foo 1; putVar foo" result 'foo = "1" I want to do the same thing in Python, but I can not find the answer :( In TCL I use the up command because when I pass the name of the variable, then I can see the value at the top. . I understand that an advanced light in the dragon There is no mechanism of r, but with its introspection capability, I would think that this is something trivial, but I am not getting the answer anywhere. It seems that this should work: and expanded: def foo (): y = "Hello World" printwor ("y") foo () y = "Hello World " You can, but you should not do so if your code is correct If is needed , then there is something wrong with your design, and you should probably use the dictionar...
Read more