পলিসি বেইজড ডাটা স্ট্রাকচার (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 মানুষটা এই স্টেপে বের হয়ে যাবে।

 

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

 

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

 

#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)