Divide & Conquer Optimization – DP(ডিপি অপ্টিমাইজেশন)

 

প্রথমেই বলে রাখি, এই টিউটোরিয়ালটা একটু এডভান্সড লেভেলের। তাই ডিপি নিয়ে খেলা করতে মোটামুটি পারদর্শী না হলে এই টিউটোরিয়ালটা স্কিপ করাই ভাল। সাথে Divide and Conquer সম্পর্কেও জানা থাকতে হবে!

 

এবার তাহলে শুরু করা যাক। প্রথমেই কিছু কঠিন কঠিন শর্ত লিখে শুরু করব। 😥 ঘাবড়ে যাওয়ার কোন কারণ নেই, উদাহরণ দিলে আস্তে আস্তে সবটাই পরিষ্কার হয়ে যাবে! আমরা চেষ্টা করব উদাহরণ হিসেবে ২টা প্রব্লেম নিয়ে আলোচনা করার। 🙂

 

এই অপ্টিমাইজেশন ব্যবহার করার জন্যে প্রথমে কিছু শর্ত পূরণ করতে হবেঃ

 

১) dp[i][j] = mink < j {dp[i - 1][k] + C[k][j]}
২) P[i][j]  ≤  P[i][j + 1]

 

১ম শর্তে একটা ডিপি রিকারেন্স লেখা আছে। অর্থাৎ Divide and Conquer অপ্টিমাইজেশন টেকনিক ব্যবহার করার জন্যে ডিপি রিকারেন্সটা এরকম হতে হবে। C[k][j] হচ্ছে একটা কস্ট ভ্যালু / ফাংশন।

 

২য় শর্তে আমরা একটু পরে আসছি। এর আগে আমরা আমাদের প্রথম প্রব্লেমে চলে যাই। প্রব্লেমটা HackerRank এর Guardians of the Lunatics. সামনে যাওয়ার আগে প্রব্লেম স্টেটমেন্টটা একবার পড়ে ফেলো।

 

আশা করি, প্রব্লেম স্টেটমেন্টটা পড়ে ফেলেছো, স্যাম্পল কেসের এক্সপ্লেনেশন দেয়া থাকায় বুঝতেও কোন সমস্যা হওয়ার কথা না। তবু যারা বুঝতে পারো নি, তাদের জন্যে সংক্ষেপে প্রব্লেমটাতে কি করতে বলেছে, সেটা একটু বলে রাখি।

 

প্রব্লেমটাতে L সাইজের একটা অ্যারেকে G ভাগে এমনভাবে ভাগ করতে বলা হয়েছে যাতে R এর ভ্যালু মিনিমাম হয়। R হচ্ছে প্রতিটা ভাগের cost এর যোগফল। প্রতিটা ভাগের cost = (ওই ভাগে মোট ভ্যালুর সংখ্যা X ওই ভ্যালুগুলোর যোগফল)

 

বুঝতেই পারছো, এটা একটা নরমাল পার্টিশন প্রব্লেম। ডিপি রিকারেন্সটা আশা করি লিখে ফেলতে পারার কথা। পরবর্তী অংশে যাওয়ার আগে একবার নিজে চেষ্টা করে দেখো। সবচেয়ে ভাল হয়, তুমি রিকারেন্সটা লিখে সাবমিট দিয়ে দেখো। বড় টেস্টকেসের জন্যে TLE খাবে, কিন্তু ছোট টেস্টকেসগুলো যদি পাস করে, তাহলে বুঝবে তোমার রিকারেন্স ঠিক আছে।

 

আমি নিচে কোডটা দিয়ে দিলামঃ

 

long long int f(int rem, int pos)
{
    if(pos==n)
        return 0;

    long long int &ret = dp[rem][pos];
    if(ret!=-1)
        return ret;

    ret = 99999999999999999;
    for(int k = pos+1; k<=n; k++)
    {
        if(rem>0)
            ret = min(ret, f(rem-1,k) + cost(pos+1,k));
    }
    return ret;
}

 

দেখো তো, রিকারেন্সটা ১ম শর্তের মত লাগছে কিনা?! ১ম শর্তের মত করে রিকারেন্সটা লিখি তাহলেঃ

 

dp[rem][pos] = min(k < n + 1){dp[rem - 1][k] + C[pos+1][k]}

 

১ম শর্তটা তাহলে পূরণ হল। আচ্ছা, এই সল্যুশনটার ভার্ডিক্ট TLE কেন হল? এর কমপ্লেক্সিটি কত বলতে পারবে?

 

ফাংশনের ২টা স্টেট G,L এবং ভিতরে L এর আরেকটা লুপ আছে। অর্থাৎ টাইম কমপ্লেক্সিটি হচ্ছে O(GL2)

 

এবার আমরা একটা এই রিকারেন্সের একটা চিত্র দেখবঃ

 

1.png

 

অর্থাৎ dp[i][j] এর প্রত্যেকটা ইন্ডেক্সের ভ্যালুর জন্যে dp[i-1][j] এর প্রত্যেকটা ভ্যালু দরকার হচ্ছে। এই লুপটার কারণেই টাইম কমপ্লেক্সিটি অনেক বেড়ে যাচ্ছে! Divide and Conquer optimization এ আমরা এই লুপটাই বাদ দিব, তবে সেজন্যে ২য় শর্তটাও পূরণ হতে হবে।

 

২য় শর্তটা ছিল P[i][j] ≤ P[i][j + 1]. এখানে P[i][j] তে এমন একটা ইন্ডেক্স k রাখা হচ্ছে, যার জন্যে dp[i][j] এর অপ্টিমাল এন্সার পাওয়া যাচ্ছে। কিন্তু শর্ত অনুযায়ী, এই ফাংশনটিকে monotonic function(non-decreasing / non-increasing) হতে হবে। মানে কি?! আচ্ছা, আরেকটা চিত্র দিয়ে বোঝানোর চেষ্টা করছিঃ

 

2.png

 

এখানে ০তম(০-বেইজড) ইন্ডেক্সের জন্যে অপ্টিমাল এন্সার পাওয়া যাচ্ছে ২য় ইন্ডেক্সে, ১ম ইন্ডেক্সের জন্যে ৪র্থ ইন্ডেক্সে, ২য়,৩য় উভয় ইন্ডেক্সের জন্যে ৫ম ইন্ডেক্সে। অর্থাৎ এখানে P[i][j] ≤ P[i][j + 1] শর্ত পূরণ হচ্ছে। অর্থাৎ এখানে টেকনিকটা ব্যবহার করা যাবে।

 

3.png

 

এই ক্ষেত্রে কিন্তু ব্যবহার করা যাবে না, নিশ্চয়ই বুঝতে পারছো কেন! কারণ ১ম ইনডেক্সের(অবশ্যই ০-বেইজড) জন্যে অপ্টিমাল এন্সার পাওয়া গেল ৪র্থ ইন্ডেক্সে, অথচ ২য় ইনডেক্সের জন্যে পাওয়া গেল ৩য় ইন্ডেক্সে। অর্থাৎ ২য় শর্ত পূরণ করল না!

 

কঠিন লাগছে কি?! 😕 শর্তগুলো না বুঝে থাকলে এই পর্যন্ত আরেকবার পড়ো! শর্তগুলো না বুঝলে কিন্তু সামনের অংশটুকু বুঝতে পারবে না!

 

এবার চলো, কিভাবে Divide and Conquer টেকনিকটা এখানে ব্যবহার করতে হবে, সেটা দেখি!

 

আচ্ছা বলো তো, ৩য় ইন্ডেক্সের জন্যে অপ্টিমাল এন্সার যদি আমরা ৫ম ইন্ডেক্সে পাই, তাহলে ১ম ইন্ডেক্সের জন্যে অপ্টিমাল এন্সার কোথায় পাব?

 

বুঝতে পারছো না কোথায়?! আচ্ছা, আরেকটা চিত্র দেখাচ্ছি!

 

4.png

 

এবার নিশ্চয়ই বুঝতে পেরেছো! ২য় শর্ত অনুযায়ী, ১ম ইন্ডেক্সের অপ্টিমাল এন্সার কখনোই ৫ম ইন্ডেক্সের পরে থাকতে পারবে না! তাহলে আমরা কেন শুধু শুধু dp[i][j] এর প্রত্যেকটা ইন্ডেক্সের জন্যে বারবার dp[i-1][j] এর প্রতিটা ইন্ডেক্সে বোকার মত ঘুরপাক(লুপ) খাব?! আমাদের তো এর আগের ইন্ডেক্সগুলো দেখলেই কাজ হয়ে যাচ্ছে!

 

মনে হয় এতক্ষণে বুঝে গেছো, কিভাবে Divide and Conquer ব্যবহার করব আমরা! [L,R] এর মাঝের ভ্যালুর জন্যে আমরা অপ্টিমাল ইন্ডেক্স বের করব, ফলে আমাদের পুরো অ্যারেটা ২ভাগে ভাগ হয়ে গেল। ২ ভাগের জন্যে আমরা ২ ভাগে আলাদা আলাদাভাবে সার্চ করব। সার্চ করার সময় বারবার ২ভাগে ভাগ করতে থাকলেই এন্সার পেয়ে যাব। বাকিটুকু আর নাইবা বললাম, Divide and Conquer কিভাবে কাজ করে, সেটা তো তোমরা জানোই! কোডটা আগে নিজে নিজে লিখে ফেলার চেষ্টা করো, নাহলে আমি তো আছিই!

 

void fill(int g, int l, int r, int p1, int p2)
{
    if(l>r)
        return;

    int mid = (l+r)/2;

    p[mid][g] = -1;
    dp[mid][g] = 999999999999999999;

    Rep(i,p1,p2)
    {
        i64 wgt = dp[i][g-1] + cost(i+1,mid);
        if(dp[mid][g] > wgt)
        {
            dp[mid][g] = wgt;
            p[mid][g] = i;
        }
    }

    fill(g, l, mid-1, p1, p[mid][g]);
    fill(g, mid+1, r, p[mid][g], p2);
}

 

কমপ্লেক্সিটিও কিন্তু অনেক কমে গেল। আগে যেই L এর লুপটা ঘুরছিল, সেটা এখন Divide and Conquer এর কারণে logL এ কাজ সারবে। অর্থাৎ পুরো সল্যুশনের কমপ্লেক্সিটি হল O(GLlogL)

 

লেখাটা অনেক বড় হয়ে গেল! তাই ২য় প্রব্লেমটা নিয়ে আর আলোচনা করলাম না, সেক্ষেত্রে রচনা লেখা হয়ে যাবে। 😐  একটু চেষ্টা করলেই প্রব্লেমটা পারার কথা! প্রব্লেমটার লিঙ্ক নিচে দিয়ে দিলামঃ

 

Yet Another Minimization Problem(CF)
Advertisements

7 thoughts on “Divide & Conquer Optimization – DP(ডিপি অপ্টিমাইজেশন)

    1. আসলে এটা নির্ভর করে আপনি কিভাবে cost ফাংশনটা ডিফাইন করছেন। এখানে cost ফাংশনে cummulative sum এর সাথে রেঞ্জ গুণ দেয়া হয়েছে। cummulative sum সম্পর্কে ধারণা থাকলে জানার কথা, যেকোন রেঞ্জ (l,r) এর sum বের করতে হলে sum[r] – sum[l-1] করতে হয়, অর্থাৎ এই ফাংশনটাতে ১-বেইজড ইন্ডেক্স নিয়ে কাজ করলে সুবিধা, যেখানে sum[0] = 0 থাকে। কিন্তু যেহেতু আমার মূল ডিপি ফাংশনটা ০-বেইজড, অর্থাৎ আমি pos = 0 পাস করছি প্রথমে, সেক্ষেত্রে C[0][k] = sum[k] – sum[0-1] হবে, অর্থাৎ sum[-1] এ ভ্যালু খুঁজতে যাবে। এ কারণেই এখানে C[pos+1][k] হয়েছে। আপনি উপরের যে dp function টা লেখা হয়েছে সেটার সাথে কম্পেয়ার করুন। ওখানে কিন্তু cost(pos+1,k) লেখা হয়েছে!

      Like

  1. আপনি যে তিনটা চিত্র দিয়েছেন P[i][j] ≤ P[i][j + 1] বুঝাবার জন্য ,ওখানে চিত্রতে লিখেছেন [i-1][j] and [i][j] , কিন্তু চিত্রটা তো আসলে [i][j] and [i][j+1] এর হবার কথা , তাই না ?
    আমি নতুন শিখছি , কিন্তু এ জিনিসটা বুঝতেছি না । দয়া করে রিপ্লাই দেবেন

    Like

    1. চিত্রগুলোতে dp[i][j] এর ভ্যালু দেখানো হয়েছে! প্রথম চিত্রটা আর রিকারেন্সটা একসাথে দেখুন, dp[i][j] এর ভ্যালু বের করতে dp[i-1][j] এর ভ্যালুগুলো দরকার হচ্ছে!

      P[i][j] এর ডেফিনিশনটা ভাল করে খেয়াল করুন! এখানে dp[i][j] এর অপ্টিমাল এন্সার যেই ইন্ডেক্সে পাওয়া যাচ্ছে, সেই ইন্ডেক্সটা রাখা হচ্ছে। এই ইন্ডেক্সটা কি সেটা জানার জন্যেই তো আমাদের dp table টা জানা প্রয়োজন, তাই না?! চিত্রগুলোতে যেই ডিপি টেবিল দেয়া হয়েছে, সেখানে থেকেই আমরা P[i][j] বের করছি। এখানে, P[1][0] = 2, P[1][1] = 4, P[1][2] = 5, P[1][3] = 5 – এটা monotonically increasing function.

      আশা করি, বুঝতে পেরেছেন!

      Like

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

w

Connecting to %s