SOS DP | DP Series(Last Episode)

-
শুরুতেই বলে রাখি এই এপিক টপিক আমি শিখেছি এই CF Blog থেকে। 
SOS DP:

SOS(Sum Over Subset) মূলত একটি সংখ্যার সবগুলো সাবমাস্ক এফিসিয়েন্টলি ইটারেট করে। 

  • সাবমাস্ক কি?
        একটি সংখ্যা x এর একটি সাবমাস্ক হবে y যদি x & y = y হয়। 
        সহজ ভাষায় বললে, একটি সংখ্যার kth বিট যদি 0 হয় তবে তার সাবমাস্ক এর kth বিট অবশ্যই 0            হবে এবং যদি সংখ্যাটির kth বিট 1 হয় তবে তার সাবমাস্কের kth বিট 0 অথবা 1 যেকোন কিছু হতে         পারে।
        
        তাহলে, একটি সংখ্যার On bit যদি k টা হয় তবে তার সাবমাস্ক হতে পারে 2^k টা।

এখন ধরে নেই,

S(mask) = {x : x & mask = x}

অর্থাৎ, S(mask) হচ্ছে mask সংখ্যাটির সাবমাস্কের সেট। 

S(mask , i) হচ্ছে মাস্কের এমন সব সাবমাস্কের এর সেট যাদের 0th to ith পজিশনের বিটগুলো শুধু পরিবর্তন হতে পারবে। 

এখন, S এবং সাবমাস্ক এর সংজ্ঞা থেকে আমরা লিখতে পারিঃ

S(mask , i) = S(mask , i-1)                                                       IF  ith bit is OFF
S(mask , i) = S(mask , i-1) U S(mask XOR (1<<i) , i-1)        IF ith bit is ON

অর্থাৎ, mask সংখ্যাটির ith বিট 0 হলে সাবমাস্কের সংজ্ঞা অনুযায়ী এই বিট পরিবর্তন হতে পারবে না যদিও S(mask , i) এ 0th to ith বিট পরিবর্তন করার অনুমতি ছিলো। তাহলে, আমরা লিখতেই পারি যে
S(mask , i) = S(mask , i-1)

আবার, mask সংখ্যাটির ith বিট ১ হলে সাবমাস্কের সংজ্ঞা অনুযায়ী আমরা এই বিট এ ০ অথবা ১ যেকোন কিছু বসাতে পারি। ১ রেখে S(mask , i-1) এবং ১ কে ইনভার্ট করে S(changedMask , i-1) দুটি সেট জেনারেট করলে দুটি সেটের ইউনিয়ন এর মাধ্যমেই আমরা S(mask , i) সেট টি পাবো। 

এখানে, changedMask হচ্ছে mask এর ith বিট কে 0 করে দিলে যে সংখ্যা হয় সেটি। সেটের ডেফিনিশনে যা mask XOR (1<<i) হিসেবে লিখা হয়েছে। 

এখন, S(mask , i) ফাংশন ব্যাবহার করে কিভাবে একটি সংখ্যার সবগুলো সাবমাস্ক জেনারেট হয় দেখে নেইঃ


এখানে, বোল্ড করা বিটগুলো পরিবর্তনযোগ্য নয়। 


এবার একটি প্রব্লেম সলভ করা যাক উদাহরণ হিসেবেঃ


Problem: তোমাকে n সাইজের একটি অ্যারে a দেয়া আছে যেখানে n <= 10^6 এবং a[i] <= 4 * 10^6
অ্যারের প্রতিটি এলিমেন্ট এর জন্য তোমাকে বলতে হবে যে অ্যারে তে অন্য কোন এলিমেন্ট আছে কি না যার সাথে এই এলিমেন্ট কে AND করলে 0 হয়। যদি থাকে তবে, ঐ এলিমেন্ট প্রিন্ট করতে হবে অন্যথায় -1 প্রিন্ট করতে হবে। 
 

Solution: a[i] & ans[i] = 0 মানে কি? 
a[i] এর কোন বিট যদি ১ হয় তবে ans[i] এর Corresponding ঐ বিট অবশ্যই 0 হবে। এবং a[i] এর কোন বিট যদি 0 হয় তবে ans[i] এর Corresponding ঐ বিট 0 অথবা 1যেকোন কিছু হতে পারে। 

তার মানে ans[i] হচ্ছে Invert(a[i]) এর একটি সাবমাস্ক! Invert(a[i]) মানে হচ্ছে a[i] এর ON Bit গুলোকে OFF করে দিবো এবং OFF Bit গুলোকে ON করে দিবো। 

ধরে নেই, b[i] = Invert(a[i])

তাহলে, ans[i] হবে SOS এর মাধ্যমে বের করা b[i] এর এমন একটি সাবমাস্ক যা মূল অ্যারে তে আছে। 


Recursive Code:


এখন, ভালোভাবে প্রব্লেম এর Constraint এর দিকে তাকালে দেখবে আমাদের এই সল্যুশন MLE খাবে! আর অপ্টিমাইজ করারও কোন উপায় দেখতেছি না। 
ইটারেটিভ কোড দেখি কিছু করা যায় কি না। 

Iterative Code:



ইটারেটিভ কোডে দেখতে পাচ্ছি, dp[mask][bitpos] এর ভ্যালু dp[submask(mask)][bitpos-1] এর উপর নির্ভর করতেছে! কোন সংখ্যার submask ঐ সংখ্যার সমান অথবা ছোট। আর bitpos-1 অবশ্যই bitpos এর ছোট! ডিপি অপ্টিমাইজেশনের অতীত পর্বগুলোর কথা মনে আছে কি?

কিভাবে ইটারেটিভ ডিপি তে পজিশন স্টেট এর মেমোরি কমাতে হয় সেটি আমরা এই পর্বে শিখেছিলাম! 



আশা করি, SOS DP সম্পর্কে কিছুটা হলেও আইডিয়া দিতে পেরেছি।

Happy Coding 😊

Comments

Post a Comment

Trending Post

At Coder Educational DP-A | DP Series(Episode-1)

-
কিছু কথাঃ DP Series এ আমি মূলত  At Coder Educational DP  কন্টেস্টের প্রব্লেমগুলো নিয়ে আলোচনা করবো এবং সেই সাথে ডিপি সল্যুশন প্রিন্ট, ডিপি অপটিমাইজেশনসহ আরো কিছু বিষয় নিয়ে আলোচনা করবো।  এই সিরিজ টি পড়া শুরু করার আগে সবার ব্যাসিক ডিপি সম্পর্কে ধারণা থাকা আবশ্যক।  এজন্য  শাফায়েতের ব্লগ  থেকে ডাইনামিক প্রোগ্রামিং এর সবগুলো পর্ব পড়ে নেয়ার জন্য অনুরোধ করছি।  Problem Description  here Problem: প্রব্লেমটিতে বলা হয়েছে, আমাদেরকে n টি পাথর দেয়া থাকবে। এবং প্রতিটি পাথরের উচ্চতা দেয়া থাকবে।  একটি ব্যাঙ শুরুতে ১নম্বর পাথরে আছে। ব্যাঙ টি একঘর অথবা দুইঘর জাম্প করতে পারে। অর্থাৎ, i তম পাথর থেকে i+1 or i+2 তম পাথরে যেতে পারে। ith থেকে jth পাথরে যেতে তাকে দুইটি স্টোনের উচ্চতার পার্থক্যের সমান টাকা খরচ করতে হয়।  বের করতে হবে n তম পাথরে পৌঁছাতে তাকে সর্বনিম্ন কত খরচ করতে হবে?  Recursive Solution: ১) এই প্রব্লেমের জন্য আমাদের কয়টি স্টেট লাগবে? ভালোভাবে লক্ষ্য করলে বুঝবে শুধুমাত্র পজিশন ই স্টেট হিসেবে রাখা যথেষ্ট।  ২) এরপর, প্রতি পজিশন থেকে আমি একবার একঘর জাম্প করে দেখবো কত খরচ হয়। তারপর, যদি সম্ভব হয় দুইঘর
Read more

DP Optimization (Part-1) | DP Series(Episode-15)

-
 এই পর্বে আমরা মূলত ডিপি তে মেমোরি অপ্টিমাইজেশন কিভাবে করে সেটা দেখবো।  প্রব্লেম-১ঃ  এটি সাধারণ একটি ন্যাপস্যাক প্রব্লেম যেখানে তোমাকে n <= 500 টি জিনিস দেয়া থাকবে। ন্যাপস্যাকের সর্বোচ্চ সাইজ 2*10^6, প্রতিটি জিনিসের মূল্য v[i] <= 10^7, প্রতিটি জিনিসের ওজন wt[i] <= 10^7। এমনভাবে ন্যাপস্যাক এ আইটেমগুলো নিতে হবে যাতে সর্বোচ্চ মূল্যের জিনিস নেয়া যায়।  সাধারণ ন্যাপস্যাকের কোডটি দেখতে অনেকটা এরকমঃ  কিন্তু, উপরোল্লিখিত সমস্যার সমাধান না এই সল্যুশন! কারণ তুমি 500*2000000 সাইজের অ্যারে ই ডিক্লেয়ার করতে পারবা না! তার মানে আমাদের মূল সমস্যা হচ্ছে মেমোরি!  উপরের কোডের ১৬ নম্বর লাইনটা ভালো করে দেখো তো। আমি যখন ith to nth আইটেম কনসিডার করে কোন ওয়েট বানাতে চাচ্ছি তখন আমার জানা দরকার (i+1)th to nth আইটেম কনসিডার করে ঐ ওয়েট বানানো যায় সর্বোচ্চ কত লাভে। আমার কিন্তু তখন (i+2)th, (i+3)th,.... এসব সারির ভ্যালুগুলো জানার দরকার পড়ে না!   সবশেষে, আমার জানা দরকার 1st to nth আইটেম কনসিডার করে কোন ওয়েট বানানো যায় সর্বোচ্চ কত লাভে! তাহলে, i যদি জোড় হয় তখন (i+1) হবে বিজোড়। i যদি বিজোড় হয় তখন (i+1) হবে জোড়
Read more