Randomized Algorithm!

হ্যালো! আজকের এই পর্বটি সাজানো হয়েছে Competitive Programming এর একটি কম আলোচিত বিষয় নিয়ে। Randomized Algorithm নিয়ে প্রথম পড়েছিলাম Codeforces এর blog থেকে। এরপর Famous Contestant Errichto এর ইউটিউব ভিডিও গুলো দেখে খুব মুুুুুগ্ধ হয়েছিলাম, বিশেষ করে Randomized Algorithm নিয়ে তার সিরিজটা বেশ ভালো লাগে। তাই নিজের এবং অন্যদের ভবিষ্যৎ প্রয়োজনের কথাগুলো চিন্তা করে এগুলোকে ব্লগ আকারে লিখে রাখার সিদ্ধান্ত নিই।

Problem 1:

Statement: তোমাকে N (1≤N≤105) সংখ্যক বিন্দু দেয়া আছে। এমন একটি সরলরেখার সমীকরণ তোমাকে বের করতে হবে যেন at least N4 টা বিন্দু সেই সরলরেখার উপর থাকে। এটা গ্যারান্টি দেয়া হবে যে এমন একটা সরলরেখা অবশ্যই থাকবে।

 

Solution: একটা Bruteforce Solution হতে পারে এরকমঃ আমরা ধরে নিতে পারি যে পয়েন্টগুলো একটা অ্যারে হিসেবে আমাদের কাছে দেয়া হয়েছে। আমরা প্রতিবার এই অ্যারে থেকে দুইটি করে বিন্দু নিয়ে একটি করে সরলরেখা পেতে পারি এবং check করতে পারি, অবশিষ্ট বিন্দুগুলো থেকে N4 – 2 সংখ্যক বিন্দু এই সরলরেখার উপর রয়েছে কিনা। যদি থাকে, তাহলে আমরা আমাদের সরলরেখা পেয়ে গিয়েছি।

আমাদের এই bruteforce solution টির টাইম কমপ্লেক্সিটি কত হতে পারে? আমরা একটি N2 লুপ চালিয়ে প্রতিবার দু’টি করে বিন্দু বাছাই করে চেক করতে পারি, অবশিষ্ট বিন্দুগুলো থেকে N4 – 2 টি বিন্দু এই সরলেখাটির উপর বিদ্যমান কিনা। এই চেক করার কাজটায় আমাদের আরো একটি O(N) লুপ চালাতে হবে। তাহলে আমাদের overall time complexity দাড়াচ্ছেঃ O(N3)

আমাদের আরো ভালো কিছু খুঁজে বের করতে হবে। মাঝেমধ্যে কিছু প্রবলেমের সমাধান করতে গিয়ে আমরা এমন কিছু সমস্যার সম্মুখীন হই, যেসব থেকে বের হতে তেমন কোনো অ্যালগোরিদিম বা ডাটা স্ট্রাকচার আমাদের সাহায্য করতে পারেনা। এ ধরণের সমস্যাগুলোকে বেশিরভাগ সময়ে Randomized Approach এ সমাধান করতে হয়।

আমরা একটু বুদ্ধিমানের মতো যদি দু’টি বিন্দু pick করতাম,তাহলে পুরো সমস্যাটিকে আমরা O(NK) কমপ্লেক্সিটিতে সমাধান করতে পারতাম। K এর পরিচয় আলোচনার শেষেই বলবো!

আমরা যদি N সংখ্যক বিন্দু থেকে randomly একটি বিন্দু বাছাই করি,তাহলে সেই বিন্দুটির N/4 সংখ্যক পয়েন্টের সেট টিতে থাকার প্রবাবিলিটি কত হতে পারে? তোমার উত্তর যদি হয় 14, তাহলে তুমি ঠিক রাস্তাতেই আছো! ব্যাপারটি এভাবে চিন্তা করলে সহজ হবে। ধরো, আমরা আমাদের N সংখ্যক বিন্দুগুলোকে 2টি সেটে ভাগ করতে পারি, যেখানে একটি সেটে উপাদান থাকবে N4 টি এবং অন্য সেটে থাকবে অবশিষ্ট বিন্দুগুলো। এখানে বলে রাখা ভালো, N4 টি বিন্দু যেই সেটটিতে থাকবে তারা সবাই সরলরৈখিক!

এখন, যদি সেট দুটিতে আমরা ভাগ না করে, বিন্দুগুলো থেকে 1টি বিন্দু randomly বাছাই করতাম, তাহলে সেই বিন্দুটির সরলরৈখিক বিন্দুগুলোর সেটটির থেকে চলে আসার প্রবাবিলিটি হতো 25%! অর্থাৎ , গড়ে প্রতি ৪টি বিন্দুর মধ্যে অন্তত 1টি বিন্দু থাকবে যেটি এই সরলরৈখিক সেট থেকে এসেছে।

এবার, আমরা যদি দু’টি বিন্দু বাছাই করতে চাই যারা সরলরৈখিক সেট থেকে আসবে, সেটার প্রবাবিলিটি হবে 14 * 14  = 116

তার মানে, আমরা যদি randomly দু’টি বিন্দু নিই তাহলে সেই বিন্দুগুলোর সরলরৈখিক সেট থেকে না আসার প্রবাবিলিটি হবে 1516.

আচ্ছা। এবার আমরা যদি 116 প্রবাবিলিটিতে দুইটি বিন্দুকে তুলে নিয়ে একটি O(N) লুপ চালিয়ে দেখি যে বাকি বিন্দুগুলো থেকে N4 – 2 টি বিন্দু কি একই সরলরেখার পড়েছে কিনা, তাহলেই আমাদের কাজ হয়ে যাবে। আমরা যদি এই কাজটি একবার করি, তাহলে আমাদের failure probability (FP) দাঁড়াবে 1516. ভিন্ন দুইটি বিন্দু নিয়ে যদি দুইবার এই কাজটি করি, তাহলে আমাদের FP দাঁড়াবে (1516)2. যদি এই কাজটি তিনবার করি,তাহলে আমাদের FP দাঁড়াবে (1516)3. মোট কথা, আমরা যদি এই একই কাজ K সংখ্যক বার করি, তাহলে আমাদের failure probability (FP) দাঁড়াবে (1516)K. (আশা করি K এর সংজ্ঞা পেয়ে গিয়েছো এবার)

এখন K = 500 যদি ধরে নিই, তাহলে (1516)K এর মান আসে 0.0000000000000009 এর চেয়েও কম! তার মানে, মোটামুটি 500 বারের মতো আমরা যদি randomly দু’টি করে বিন্দু বাছাই করে চেক করি যে বাকি বিন্দুগুলোর মধ্য থেকে অন্ততঃপক্ষে N4 – 2 টি বিন্দু বাছাই করা দু’টি বিন্দু দ্বারা গঠিত সরলরেখার উপরে অবস্থান করছে কিনা, তাহলে আমাদের success probability দাঁড়াচ্ছে প্রায় 100%! 😀

তো,Randomized Algorithm এর মাধ্যমে সমস্যাটির সমাধান হয়ে গেলো!

Problem 2:

ধরো, আমি জাজ আর তুমি প্রবলেম সল্ভার। আমার কাছে N (1≤N≤105) সাইজের একটা স্ট্রিং আছে। স্ট্রিং-টায় শুধুমাত্র A,C,T এবং G এই চারটি ক্যারেক্টারই থাকবে! তোমাকে এই N সাইজের স্ট্রিং টা খুঁজে বের করতে হবে। সেজন্যে তুমি আমাকে maximum 2.5x10টি কুয়েরি করতে পারবে। প্রতি কুয়েরিতে তুমি আমাকে একটা করে স্ট্রিং দিয়ে বলবে যে এই স্ট্রিং টি কি আমার কাছে থাকা স্ট্রিং টির কোনো প্রিফিক্স কি না। আমি হ্যা বা না উত্তর দিবো।

Solution: সমাধানে যাওয়ার আগে কিছু উদাহরণ দেখে আসি। ধরো, আমার কাছে যেই স্ট্রিং টি আছে সেটি হচ্ছেঃ ACATG

তুমি প্রথম কুয়েরিতে জিজ্ঞেস করলে, “C কি তোমার স্ট্রিং টির একটি প্রিফিক্স?” আমার উত্তরঃ না।

তারপর জিজ্ঞেস করলে, “T কি তোমার স্ট্রিং টির একটি প্রিফিক্স?” আমার উত্তরঃ না।

তারপর জিজ্ঞেস করলে, “A কি তোমার স্ট্রিং টির একটি প্রিফিক্স?” আমার উত্তরঃ হ্যা।

তুমি আমার কাছে থাকা স্ট্রিং টার প্রথম ক্যারেক্টার জেনে গেলে! এবার তুমি ২য়,৩য় ক্যারেক্টারও জানতে পারবে! একইভাবে তুমি N টা ক্যারেক্টারই বের করে ফেলতে পারবে। এক্ষেত্রে, প্রতিটা ক্যারেক্টার খুঁজে বের করতে তোমাকে worst case এ 4টি কুয়েরি করতে হতে পারে। তাহলে N সংখ্যক ক্যারেক্টার এর জন্যে তোমাকে 4N টা কুয়েরি করতে হবে। কিন্তু আমাদেরকে এই কাজটা 2.5N টা কুয়েরিতেই করতে হবে। কীভাবে improve করা যায়?

আমরা তো প্রতিটি ক্যারেক্টার এর ক্ষেত্রে worst case এ চারটি করে কুয়েরি করছি। তো best case টা কেমন হতে পারে? মানে, প্রতি ক্যারেক্টার এর ক্ষেত্রে একদম প্রথম অনুমানটাই যদি সঠিক হয়ে যায়, তাহলে প্রতিটি ক্যারেক্টার আমরা মাত্র একটি কুয়েরি করেই বের করে ফেলতে পারবো! এভাবে পুরো স্ট্রিং টা কে খুঁজে বের করতে আমাদের N টার বেশি কুয়েরি দরকার হবে না!

জাজ বা প্রবলেম সল্ভার, কেউ শুরু থেকেই গ্যারান্টি দিয়ে বলতে পারবে না যে প্রবলেম সল্ভার এর কোড প্রতি কেইসেই worst case বা best case ফেইস করবে। এটা পুরোপুরি নির্ভর করে প্রবলেম সল্ভার তার কোডে 4টা ক্যারেক্টারকে কোন order এ কুয়েরি করতে চাচ্ছে তার উপর!

তো আমরা কি 4N এবং N এর মাঝামাঝি কিছু করতে পারি?

হ্যা, পারি!

আমরা যদি প্রতিবার , প্রতি ক্যারেক্টারের ক্ষেত্রে কুয়েরি করার সময় randomly একটা ক্যারেক্টার পছন্দ করে সেটা জাজের কাছে পাঠিয়ে দিয়ে উত্তর জানতে চাই, তাহলে সেই ক্যারেক্টারটি সঠিক হওয়ার জন্যে গড়ে আমাদের কতগুলো কুয়েরি করতে হবে সেটা বের করে ফেলার চেষ্টা করি!

best case: প্রথম কুয়েরিতেই কেল্লাফতে!

2nd best case: ২য় কুয়েরিতে সঠিক ক্যারেক্টার বের করে ফেললাম!

3rd best case: ৩য় কুয়েরিতে সঠিক ক্যারেক্টার বের করে ফেললাম!

worst case: ৪র্থ কুয়েরিতে সঠিক ক্যারেক্টারটি বের করতে পারলাম।

তাহলে আমরা যদি RANDOMLY একটা করে ক্যারেক্টার পছন্দ করে জাজের কাছে পাঠিয়ে দিই এবং সেটা সঠিক হিসেবে বের হতে হয়, তাহলে গড়ে আমাদের (1+2+3+4)/4 = 2.5 টি কুয়েরি লাগবে! Interesting! 😀

কিন্তু এটা একদম কানায় কানায় আমাদের constraints এর সাথে মিলে যাচ্ছে। আমরা চাইলে একটা improvement করতে পারি। খেয়াল করে দেখো, worst case এর ক্ষেত্রে 4টি কুয়েরি করার কোনো দরকার ছিলো না। ৩টি কুয়েরি করার পরেও যদি জাজ প্রতিবার “না” উত্তর দেয়,তার মানে fourth কুয়েরিতে জাজ অবশ্যই “হ্যা” উত্তর দিবে। তাই, worst case  এ কুয়েরি সংখ্যা ৪টি না হয়ে হবে ৩টি। তাহলে আমাদের গড় কুয়েরি সংখ্যা (প্রতিটি ক্যারেক্টার এর ক্ষেত্রে) দাড়াবেঃ (1+2+3+3)/4 = 2.25. তাহলে, মোট কুয়েরি সংখ্যা হবে 2.25x105

বেশ সহজেই একটা কঠিন সমস্যার সমাধান হয়ে গেল Randomized Algorithm এর মাধ্যমে!

কীভাবে ভালো একটা সিড ব্যবহার করে Random Number জেনারেট করা যায়?

অনেকেই C++ এ rand() ব্যবহার করে Random Number জেনারেট করে। এটা মাথায় রাখা উচিত, rand() এর maximum range 32767.

তাই, সবচেয়ে ভালো উপায় হচ্ছে different কিছু random generator ব্যবহার করা। আমরা C++ এর built in একটা random generator ই ব্যবহার করবো।

Code for Random Generation and Random Shuffle:

#include <chrono>
#include <bits/stdc++.h>

using namespace std;
const int N = 3000000;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); /// MUST ADD

double average_distance(const vector<int> &permutation)
{
    double distance_sum = 0;

    for (int i = 0; i < N; i++)
        distance_sum += abs(permutation[i] - i);

    return distance_sum / N;
}

int getRandom(int L,int R) /// generate random numbers in range [L,R]
{
    return rng()%(R-L+1) + L;
}

int main()
{
    int numb = rng(); /// use rng() to generate random numbers.
    cout << numb << "\n";

    vector<int>permutation(N);

    for (int i = 0; i < N; i++)
        permutation[i] = i;

    shuffle(permutation.begin(), permutation.end(), rng); /// you can random_shuffle a vector with this function.
    cout << average_distance(permutation) << '\n';

    return 0;
}

Random Generation সম্পর্কে বিস্তারিত জানা যাবে এখান থেকে

আগামী সপ্তাহে Part 2 আসবে। 🙂