পলিসি বেইজড ডাটা স্ট্রাকচার (PBDS)

আচ্ছা, তোমরা নিশ্চয়ই C++ STL এর set (সেট) ব্যবহার করেছো বিভিন্নসময়। তাহলে নিশ্চয়ই কখন সেট ব্যবহার করা হয়, সেটাও জানা থাকার কথা। সেটের মূল দুটো বৈশিষ্ট্য হচ্ছেঃ সেটের ভিতরে কোন উপাদান (element) ১ বারের বেশি থাকে না, এবং সেটের ভিতরে উপাদানগুলো সবসময় সর্টেড অবস্থায় থাকে। অর্থাৎ তুমি যদি একে একে ৫, ২, ৬, ৪, ২, ৭ সংখ্যাগুলো একে একে সেটে ঢোকাও, তাহলে প্রতিবার ঢোকানোর পরে সেটের অবস্থা হবে এরকমঃ

 

২ ৫
২ ৫ ৬
২ ৪ ৫ ৬
২ ৪ ৫ ৬
২ ৪ ৫ ৬ ৭

 

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

 

কি এই যুগান্তকারী ডাটা স্ট্রাকচার?! 😮 এর নাম অর্ডার স্ট্যাটিস্টিক্স ট্রি (Order Statistics Tree)

 

প্রথমেই দুটো হেডার ফাইল ইনক্লুড করে ফেলিঃ
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>

 

এরপর নেমস্পেসঃ
using namespace __gnu_pbds;

 

এবার চলো ডাটা স্ট্রাকচারটা লিখে ফেলিঃ
template <typename T>  using orderedSet =
   tree<T, null_type, less<T>,
   rb_tree_tag, tree_order_statistics_node_update>;

 

এখানে ২টা জিনিস খেয়াল করতে হবে। প্রথমটা হচ্ছে, typename T. এখানে তুমি সেটের মত করেই যে টাইপের এলিমেন্ট রাখতে চাও, সেটা রাখতে পারবে। আর less<T> হচ্ছে কম্পেয়ার ফাংশন। এখানে less দিয়ে বুঝিয়েছে যে, এই কন্টেইনারে এলিমেন্টগুলো ছোট থেকে বড় হিসেবে সর্টেড থাকবে। তুমি যদি এখানে greater লেখো, তাহলে এলিমেন্টগুলো বড় থেকে ছোট হিসেবে সর্টেড থাকবে। আমাদের কাজ মোটামুটি শেষ। এখন আমরা যেকোন orderedSet ডিক্লেয়ার করতে পারব।

 

কিভাবে ডিক্লেয়ার করতে হয়?! একদম সেটের মতই!
orderedSet os;

 

int এর পরিবর্তে string, pair, struct যা খুশি তাই রাখতে পারবে। চাইলে অপারেটর ওভারলোডিং এর মাধ্যমে এলিমেন্টগুলো কিভাবে সর্টেড থাকবে সেটাও ঠিক করে দিতে পারবে। সবকিছুই একদম নরমাল সেটের মত কাজ করবে!

 

সেটের মতই insert, erase এই ফাংশনগুলোও কাজ করবে। iterator দিয়ে iterate ও করতে পারবে। তাহলে পার্থক্যটা কি?! পার্থক্য হচ্ছে, এর আরও দুটি ফাংশন আছে – find_by_order(), order_of_key()

 

আর এখানেই ঘটে আসল ম্যাজিক।

 

find_by_order(k) – ফাংশনটি kth ordered element এর একটা পয়েন্টার রিটার্ন করে। অর্থাৎ তুমি চাইলেই kth ইন্ডেক্সে কি আছে, সেটা জেনে ফেলতে পারছো!
order_of_key(x) – ফাংশনটি x এলিমেন্টটা কোন পজিশনে আছে সেটা বলে দেয়।

 

একদম প্রথমে যেই উদাহরণটার কথা বলেছিলাম, সেটাই এবার এই ডাটা স্ট্রাকচারে ব্যবহার করি।

 

    orderedSet os;

    os.insert(5);
    os.insert(2);
    os.insert(6);
    os.insert(4);
    os.insert(2);
    os.insert(7);

    cout << *os.find_by_order(0)<<endl; // 2
    cout << *os.find_by_order(1)<<endl; // 4
    cout << *os.find_by_order(2)<<endl; // 5
    cout << *os.find_by_order(3)<<endl; // 6
    cout << *os.find_by_order(4)<<endl; // 7

    cout << os.order_of_key(5) << endl;  // 2
    cout << os.order_of_key(2) << endl;  // 0
    cout << os.order_of_key(6) << endl;  // 3
    cout << os.order_of_key(4) << endl;  // 1
    cout << os.order_of_key(7) << endl;  // 4

 

আউটপুটগুলো কমেন্টে লেখা আছে। আশা করি, আউটপুটগুলো বুঝতে পারছো! হেডার ফাইল, নেমস্পেস ইনক্লুড করে এই কোডটা রান করে দেখো!

 

চলো এবার একটা প্রব্লেম সলভ করে ফেলি। তাহলেই বুঝতে পারবে, এই ফাংশন দুটোর কত শক্তি!

 

1521. War games 2 (TIMUS)

 

এখানে বলেছে, n টা মানুষ একটা সার্কেলের মত করে দাঁড়িয়ে আছে। প্রথমবার k-th মানুষটা বেরিয়ে যাবে সার্কেল থেকে। এরপরেরবার হতে সার্কেলের সব মানুষ না চলে যাওয়া পর্যন্ত এর আগের স্টেপে যেই পজিশনের মানুষটা চলে গেছে, তার ঠিক পরের k-th মানুষটা এই স্টেপে বের হয়ে যাবে।

 

খুবই সহজ মনে হচ্ছে না?! কিন্তু এই ফাংশন দুটো জানা না থাকলে কিন্তু সল্যুশনটা খুব সহজ না। সেগমেন্ট ট্রি অথবা বাইনারী ইন্ডেক্সড ট্রি ব্যবহার করতে হবে। সেক্ষেত্রে কোডও কত বড় হবে, নিশ্চয়ই বুঝতে পারছো! কিন্তু এই ডাটা স্ট্রাকচার জানা থাকলে মেইন ফাংশনের কোড হবে মাত্র ১০-১৫ লাইন। o_O

 

নিজে কয়েকবার চেষ্টা করো, আশা করি পারবে। নিচে আমি সল্যুশন কোড দিয়ে দিলামঃ

 

#include 
#include 
#include 

using namespace std;
using namespace __gnu_pbds;

template  using orderedSet =
    tree<T, null_type, less,
    rb_tree_tag, tree_order_statistics_node_update>;

int main()
{
    int n,k;
    cin >> n >> k;

    orderedSet s;
    orderedSet::iterator it;

    for(int i = 1; i <= n; i++)
        s.insert(i);

    int cur = 0;

    while(n)
    {
        cur = (cur + k - 1) % n;
        it = s.find_by_order(cur);
        cout << *it << endl;
        s.erase(it);
        n--;
    }

    return 0;
}

 

এত্ত সহজ! 😀 হ্যা, এই ডাটা স্ট্রাকচার জানা থাকলে এই টাইপের প্রব্লেম তোমার কাছে ডাল-ভাতের মতই মনে হবে! 😎

 

প্র্যাকটিসের জন্যে আরও কিছু প্রব্লেম দেয়া হলঃ

 

1028. Stars (TIMUS)
1090. In the Army Now (TIMUS)
1439. Battle with You-Know-Who (TIMUS)
Galactic Collegiate Programming Contest (KATTIS)
Advertisements

12 thoughts on “পলিসি বেইজড ডাটা স্ট্রাকচার (PBDS)

  1. নিজের ইচ্ছেমত সর্ট করার জন্য আমি সেট এ যে ফাংশনটা ইউজ করতাম সেটা দিয়ে এখানেও করা যাচ্ছে ।

    নিচে কোড দিলাম।

    #include
    #include
    #include

    using namespace std;
    using namespace __gnu_pbds;

    //custom sort for set

    class data {
    public:
    int num, pos;//variables on set
    data() {}
    data(int a, int b) {
    pos = a;
    num = b;
    }
    bool operator z.num;;
    }

    return pos < z.pos;//compare as your wish
    }
    };

    template using orderedSet =
    tree<T, null_type, less,
    rb_tree_tag, tree_order_statistics_node_update>;

    int main()
    {
    orderedSet os;
    data a,b,c;
    a.num=1,a.pos=2;
    b.num=2,b.pos=1;
    c.num=1,c.pos=1;
    os.insert(a);
    os.insert(b);
    os.insert(c);
    cout<<(*os.find_by_order(0)).num<<" "<<(*os.find_by_order(0)).pos<<endl;
    cout<<(*os.find_by_order(1)).num<<" "<<(*os.find_by_order(1)).pos<<endl;
    cout<<(*os.find_by_order(2)).num<<" "<<(*os.find_by_order(2)).pos<<endl;
    }

    কিভাবে সর্ট হবে তা data ক্লাস এর ভিতরেই বলে দেয়া আছে এবং এটা কাজ করছেও , কিন্তু এখানে আমরা ডাটা স্ট্রাকচার লিখার সময় যে less লিখতেছি সেটার তো কোনো কাজ নেই দেখা যাচ্ছে । আবার এটা রিমুভ ও করা যাচ্ছে না। এভাবে করলে হবে ? ??
    এ কোড কিন্তু কাজ করছে ।
    আমার প্রশ্ন হচ্ছে উপরের মত সর্ট করলে কি হবে, নাকি অন্য কোনোভাবে করতে হবে ?উপরেরটা ঠিক হলে less এর কাজ কি ?

    Like

  2. উপরের কোড টা কোন কারনে পেস্ট করতে ঝামেলা করতেছে যাহোক , আমার কমেন্ট এর মূল কথা হল , যদি একটা ক্লাস এর ভেতরেই আমরা কিভাবে সর্ট হবে তা বলে দেই , তাহলে ডাটা স্ট্রাকচার ডিক্লেয়ার করার সময় যে less লিখতেছি তার কোন কাজ আছে , এটা কোন প্রবলেম করবে নাতো?

    Like

  3. আপনি যেটা করছেন, সেটা হচ্ছে অপারেটর ওভারলোডিং, যেটার কথা আমি টিউটোরিয়ালেই বলেছি! আপনি একটু set এর ডকুমেন্টেশন থেকে ঘুরে আসুন (প্রথম লাইনেই যে লিংকটা দেয়া আছে), দেখুন ওখানে একদম শুরুতেই টেমপ্লেট ডিক্লেরেশনে লেখা আছে, “class Compare = less” অর্থাৎ সেট এইভাবে ছোট থেকে বড় হিসেবে কাজ করছে! এরপর আপনি আপনার ইচ্ছেমত অপারেটর ওভারলোড করতে পারেন। ওভারলোডিং এর মানে হচ্ছে, আগে less ফাংশন যেভাবে কাজ করত, সেভাবে করবে না, আপনি যেভাবে চাইছেন, সেভাবে করবে। তার মানে কিন্তু আপনি আসল অপারেটরটাকেই রিমুভ করতে পারবেন না, কারণ ওই জিনিসটাকেই আপনি ওভারলোড করছেন! 🙂

    Like

    1. অনেক ধন্যবাদ । অনেক কিছু বুঝতে পারলাম । আগে না বুঝে অপারেটর ওভারলোডিং করেছি , এখন বুঝতে পারলাম যে এটা আসলে সেট এর কম্পেয়ার টাকে ওভারলোড করে ।

      Like

  4. ভাই াআমার কোডব্লক এ এটা কম্পাইল হচ্ছে না। এটার জন্য কি অন্য কোন কম্পাইলার ব্যাবহার করতে হবে নাকি ভাই?

    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 )

Connecting to %s