प्वाइंटर इस चुनौतीपूर्ण गतिशील प्रोग्रामिंग कार्य

Question

मैं पेग ऑनलाइन न्यायाधीश में एक समस्या पर अटक गया है हल करने के लिए, डोमिनोज, जिसे आप यहां प्राप्त कर सकते हैं कहा जाता है:

http://wcipeg.com/problem/domino

संक्षिप्त विवरण:

हमें क्षैतिज रूप से व्यवस्थित विभिन्न ऊंचाई और स्थानों के साथ डोमिनोज़ की एक सूची दी गई है। ऊंचाई एच के साथ स्थिति x पर एक डोमिनोज़, एक बार दाईं ओर धक्का दिया जाता है, सभी डोमिनोज़ को पदों x + 1, x + 2, ..., x + h दाएं तरफ भी दस्तक देगा। इसके विपरीत, बाईं ओर धक्का दिया गया एक ही डोमिनोज़ सभी डोमिनोज़ को पदों x-1, x-2, ..., x-h बाईं ओर स्थित करेगा।

सभी डोमिनोज़ को कम करने के लिए हम कितने धक्का दे सकते हैं?

उदाहरण:

   | 
    |   | 
| | | | | | 
1 2 3 4 5 6 7 8 

उत्तर है। स्थान 1 पर डोमिनोज़ को दाएं स्थान पर, बाईं ओर स्थान 8 पर डोमिनोज़ दबाएं।

प्रतिबंध:

इनपुट एक एकल पूर्णांक एन ≤ 100,000 के साथ शुरू होता है, डोमिनो की संख्या, पूर्णांक एन जोड़े के बाद। पूर्णांक की प्रत्येक जोड़ी एक डोमिनोज़ के स्थान और ऊंचाई का प्रतिनिधित्व करती है। (1 ≤ स्थान ≤ 1,000,000,000, 1 ≤ ऊंचाई ≤ 1,000,000,000) कोई भी दो डोमिनोज़ में एक ही स्थान पर होंगे।

मेमोरी सीमा: 64MB

समय सीमा: 1.00s

नोट: परीक्षण डेटा के 60% है एन 5000.

≤ वहाँ एक जानवर बल समाधान जो समस्या का हल है केवल 60% इनपुट के लिए।

ऐसा लगता है कि सबसे बड़ा इनपुट आकार के लिए एसी प्राप्त करने के लिए गतिशील प्रोग्रामिंग का उपयोग करके एक सबक्वाड्रैटिक, या यहां तक ​​कि रैखिक समाधान होना चाहिए।

किसी भी संकेत की सराहना की जाएगी।

लेखक, जो मैं काफी नहीं समझ सकता है, के मामले में यह उपयोगी है से एक संकेत है:

(एन) एक पुनरावर्ती समारोह च करें कि चाल की न्यूनतम # तख्ता पलट करने के लिए आवश्यक देता है पहले एन डोमिनोज़।

अब आप f (n) से f के पिछले मानों से कैसे संबंधित हैं? डोमिनोज़ # एन में दो विकल्प हैं: बाईं ओर जाएं (जिस स्थिति में यह अन्य डोमिनोज़ को ऊपर छोड़ देता है) या दाएं (जिस स्थिति में इसके बाईं ओर एक और डोमिनोज़ इसे ऊपर छोड़ देता है)। वहां से काम कर रहे आज़माएं।

धन्यवाद!

Answer 1

यहाँ एक O(N log N) समाधान है:

1. के यह पता लगाने की गणना करने के लिए कैसे वाम-पंथी डोमिनो गिर जाता है कि अगर हम बाईं ओर i-th डोमिनो धक्का है क्या करते हैं (के निरूपित L[i] के रूप में है)। पहला विचार जो किसी के दिमाग में आता है वह सरल सिमुलेशन को चलाने के लिए है। लेकिन यह रास्ता बहुत धीमा होगा। मेरा दावा है कि जब हम बाएं से दाएं होते हैं तो हम केवल "रोचक" डोमिनोज़ इंडेक्स का ढेर बनाए रख सकते हैं। इसके लिए छद्म कोड इस तरह दिखता है:

   s = Empty stack of dominos 
   for i = 0 .. n - 1 
       while we can knock s.top() domino by pushing the i-th to the left 
        s.pop() 
       the s.top() is the rightmost domino we cannot hit 
       (if s is empty, we can hit all of them) 
       s.push(i-th domino) 
   

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

2. हम R[i] की गणना कर सकते हैं (यदि हम i-th डोमिनोज़ को दाईं ओर धक्का देते हैं तो हम कितनी दूर जा सकते हैं) उसी तरह रैखिक समय में।

3. अब हम जानते हैं कि क्या होता है यदि हम किसी भी दिशा में किसी भी डोमिनोज़ को धक्का देना चुनते हैं। ठंडा!

4. उत्तर की गणना करने के लिए गतिशील प्रोग्रामिंग का उपयोग करें। f(i) हमें कम से कम क्रियाओं की आवश्यकता होने दें ताकि सभी डोमिनोज़ i-th तक विशेष रूप से खटखटाए जाएं और शेष अभी भी छूटे रहें। संक्रमण काफी प्राकृतिक हैं: हम या तो डोमिनोज़ को बाएं या दाएं ओर धक्का देते हैं। पूर्व मामले में हम एक संक्रमण f(j) + 1 -> f(i) बनाते हैं, जहां L[i] - 1 <= j < i। बाद के मामले में संक्रमण f(i - 1) + 1 -> f(R[i]) है। यह समाधान सही है क्योंकि यह प्रत्येक डोमिनोज़ के लिए सभी संभावित कार्यों की कोशिश करता है।

5. इस भाग को कुशल बनाने के लिए कैसे? हमें दो परिचालनों का समर्थन करने की आवश्यकता है: एक बिंदु में मूल्य अपडेट करना और न्यूनतम सीमा में होना। एक सेगमेंट पेड़ उन्हें O(log N) में संभाल सकता है। यह हमें O(N log N) समाधान देता है।

इस समाधान बहुत कठिन लगता है, तो आपको पहले कोशिश करते हैं और लागू एक सरल एक कर सकते हैं: बस सिमुलेशन गणना करने के लिए चलाने के L[i] और R[i] और फिर गतिशील प्रोग्रामिंग (एक खंड पेड़ के बिना) परिभाषा के द्वारा सरणी गणना करने के लिए इस समस्या में इन चीजों का क्या मतलब है (वास्तव में 60 अंक प्राप्त करना चाहिए) की वास्तव में अच्छी समझ प्राप्त करें। एक बार जब आप इसे पूरा कर लेंगे, तो आप पूर्ण समाधान प्राप्त करने के लिए स्टैक और सेगमेंट ट्री ऑप्टिमाइज़ेशन लागू कर सकते हैं।

मामले विवरण में से कुछ स्पष्ट नहीं कर रहे में, मैं एक सही समाधान के एक कार्यान्वयन प्रदान ताकि आप उन्हें वहाँ देख सकते हैं:

#include <bits/stdc++.h> 

using namespace std; 

typedef pair<int, int> pii; 

vector<int> calcLeft(const vector<pii>& xs) { 
    int n = xs.size(); 
    vector<int> res(n, 1); 
    vector<int> prev; 
    for (int i = 0; i < xs.size(); i++) { 
     while (prev.size() > 0 && xs[prev.back()].first >= xs[i].first - xs[i].second) 
      prev.pop_back(); 
     if (prev.size() > 0) 
      res[i] = prev.back() + 2;   
     prev.push_back(i); 
    } 
    return res; 
} 

vector<int> calcRight(vector<pii> xs) { 
    int n = xs.size(); 
    for (int i = 0; i < xs.size(); i++) 
     xs[i].first = -xs[i].first; 
    reverse(xs.begin(), xs.end()); 
    vector<int> l = calcLeft(xs); 
    reverse(l.begin(), l.end()); 
    for (int i = 0; i < l.size(); i++) 
     l[i] = n + 1 - l[i]; 
    return l; 
} 

const int INF = (int) 1e9; 

struct Tree { 

    vector<int> t; 
    int size; 

    Tree(int size): size(size) { 
     t.assign(4 * size + 10, INF); 
    } 

    void put(int i, int tl, int tr, int pos, int val) { 
     t[i] = min(t[i], val); 
     if (tl == tr) 
      return; 
     int m = (tl + tr)/2; 
     if (pos <= m) 
      put(2 * i + 1, tl, m, pos, val); 
     else 
      put(2 * i + 2, m + 1, tr, pos, val); 
    } 

    void put(int pos, int val) { 
     put(0, 0, size - 1, pos, val); 
    } 

    int get(int i, int tl, int tr, int l, int r) { 
     if (l == tl && r == tr) 
      return t[i]; 
     int m = (tl + tr)/2; 
     int minL = INF; 
     int minR = INF; 
     if (l <= m) 
      minL = get(2 * i + 1, tl, m, l, min(r, m)); 
     if (r > m) 
      minR = get(2 * i + 2, m + 1, tr, max(m + 1, l), r); 
     return min(minL, minR); 
    } 

    int get(int l, int r) { 
     return get(0, 0, size - 1, l, r); 
    } 
}; 

int getCover(vector<int> l, vector<int> r) { 
    int n = l.size(); 
    Tree tree(n + 1); 
    tree.put(0, 0); 
    for (int i = 0; i < n; i++) { 
     int x = i + 1; 
     int low = l[i]; 
     int high = r[i]; 
     int cur = tree.get(x - 1, x - 1); 
     int newVal = tree.get(low - 1, x - 1); 
     tree.put(x, newVal + 1); 
     tree.put(high, cur + 1); 
    } 
    return tree.get(n, n); 
} 


int main() { 
    ios_base::sync_with_stdio(0); 
    int n; 
    cin >> n; 
    vector<pii> xs(n); 
    for (int i = 0; i < n; i++) 
     cin >> xs[i].first >> xs[i].second; 
    sort(xs.begin(), xs.end()); 
    vector<int> l = calcLeft(xs); 
    vector<int> r = calcRight(xs); 
    cout << getCover(l, r) << endl; 
    return 0; 
} 

Answer 2

आप एक 2 डी सरणी जहां प्रत्येक कोशिका प्रत्येक डोमिनोज़ द्वारा एक जोड़ी (एल, आर) है, जो विशेष स्थिति

प्रारंभिक स्थिति में निरूपित किया जाता धक्का द्वारा गिरा डोमिनो को दर्शाता है (बाएं, दाएं) धारण बनाने की जाएगी:

1  2  3  4  5  6  7  8 
<0, 2> <1, 1> <2, 0> <0, 0> <0, 1> <1, 0> <0, 0> <2, 0> 

इसके साथ आप एक ऐसा कदम बनाकर सरणी को कम करने के लिए नहीं चाहते हैं जो आपकी सरणी को < 0, 0> जोड़े तक कम कर देता है। इस मामले आर नई सरणी के एल

को एल आर 1, 3 या 8 चलती 1 के लिए में:

1  2  3  4  5  6  7  8 
<0, 0> <0, 0> <0, 0> <0, 0> <0, 1> <1, 0> <0, 0> <2, 0> 

हम केवल 1 ले जाएँ एल से 8, छोड़ दिया है, इसलिए नई सरणी:

1  2  3  4  5  6  7  8 
<0, 0> <0, 0> <0, 0> <0, 0> <0, 0> <0, 0> <0, 0> <0, 0> 

हम में से एक 2 डी सरणी देते:

1  2  3  4  5  6  7  8 
<0, 0> <0, 0> <0, 0> <0, 0> <0, 1> <1, 0> <0, 0> <2, 0> // initial 
<0, 0> <0, 0> <0, 0> <0, 0> <0, 1> <1, 0> <0, 0> <2, 0> // pushed 1 to R 
<0, 0> <0, 0> <0, 0> <0, 0> <0, 0> <0, 0> <0, 0> <0, 0> // pushed 8 to L 

सभी कोशिकाओं के बाद से कर रहे हैं अब < 0, 0>, हम उस यकीन है अल मैं dominoes गिर गया और कोई भी रहता है।

Answer 3

यह समस्या segtree

बिना हे (एन) में हल किया जा सकता

क्रैस्केविच के अनुसार, हमें L[i] - 1 से i - 1 तक की सीमा में न्यूनतम खोजना होगा। हम रोचक स्थिति और उसके डीपी मान की एक सूची रख सकते हैं, जिसमें दोनों पदों और डीपी मान आरोही क्रम में हैं।

जब हम सीमा से न्यूनतम पूछताछ करना चाहते हैं, तो हम आसानी से पीछे की सूची को स्कैन कर सकते हैं और सीमा के भीतर मौजूद सबसे छोटे रोचक बिंदु को ढूंढ सकते हैं।

के बाद हम dp[x] अद्यतन, हम वापस पॉप जाएगा सूची जो dp[x] से अधिक डीपी महत्व है (चूँकि उनका अब कोई दिलचस्प हैं) में सभी बिंदुओं और एक नया दिलचस्प बात के रूप में सूची में (x, dp[x]) जोड़ें।

यह रैखिक समय में चलता है।

int getCover(vector<int> l, vector<int> r) { 
    int n = l.size(); 
    vector<int> dp(n + 1, INF); 
    dp[0] = 0; 
    vector<pii> st; 
    st.emplace_back(0, 0); 
    for (int i = 0; i < n; i++) { 
     int x = i + 1; 
     int low = l[i]; 
     int high = r[i]; 
     int cur = dp[i]; 
     while (st.size() > 1) { 
      pii second_last = st[st.size() - 2]; 
      // if the 2nd last point is within range 
      // then the last point will no longer be interesting 
      if (second_last.first >= low - 1) { 
       // remove the last point 
       st.pop_back(); 
      } else { 
       // the 2nd last point is out of range 
       break; 
      } 
     } 
     dp[x] = min(st.back().second + 1, dp[x]); 
     // continue to pop all the points that are no longer interesting. 
     while (!st.empty() && st.back().second >= dp[x]) { 
      st.pop_back(); 
     } 
     // insert new interesting point 
     st.emplace_back(x, dp[x]); 
     dp[high] = min(dp[high], cur + 1); 
    } 
    return dp[n]; 
}