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:

	#include<bits/stdc++.h>
	using namespace std;
	int Set(int N, int pos) {return N = N | (1<<pos);}
	int Reset(int N, int pos) {return N = N & ~(1<<pos);}
	bool Cheek(int N, int pos) {return (bool)(N & (1<<pos));}
	#define sz 1000009
	int ara[sz],bra[sz],dp[1<<23][23];
	bool fre[5000009],vis[1<<23][23];
	int FuN(int mask,int bitpos) ///Here, bitpos means we can change 0th to bitpos th bit
	{
	if(bitpos == -1){
	if(fre[mask])
	return mask;
	else
	return -1;
	}
	if(vis[mask][bitpos])
	return dp[mask][bitpos];
	int ret1=-1e9 , ret2=-1e9;
	if(Cheek(mask , bitpos)){
	ret1 = FuN(mask , bitpos-1);
	ret2 = FuN(Reset(mask , bitpos) , bitpos-1);
	}
	else
	ret1 = FuN(mask , bitpos-1);
	vis[mask][bitpos] = 1;
	return dp[mask][bitpos] = max(ret1 , ret2);
	}
	void Solve(int t)
	{
	int i,j,k,n,supermask = (1<<22)-1;
	scanf("%d",&n);
	for(i=1 ; i<=n ; i++){
	scanf("%d",&ara[i]);
	fre[ara[i]] = 1;
	bra[i] = ara[i] ^ supermask; ///Invert the array element
	}
	for(i=1 ; i<=n ; i++){
	int ansi = FuN(bra[i] , 22);
	printf("%d ",ansi);
	}
	printf("\n");
	}
	int main()
	{
	Solve(1);
	return 0;
	}

view raw SOS-1.cpp hosted with ❤ by GitHub

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

ইটারেটিভ কোড দেখি কিছু করা যায় কি না। 

Iterative Code:

	#include<bits/stdc++.h>
	using namespace std;
	int Set(int N, int pos) {return N = N | (1<<pos);}
	int Reset(int N, int pos) {return N = N & ~(1<<pos);}
	bool Cheek(int N, int pos) {return (bool)(N & (1<<pos));}
	#define sz 1000009
	int ara[sz],bra[sz],dp[1<<23][23];
	bool fre[5000009],vis[1<<23][23];
	int giveMeValue(int mask,int bitpos)
	{
	if(bitpos >= 0)
	return dp[mask][bitpos];
	else{
	if(fre[mask])
	return mask;
	else
	return -1;
	}
	}
	void FuN()
	{
	for(int mask=0 ; mask < (1<<22) ; mask++){
	for(int bitpos=0 ; bitpos <= 22 ; bitpos++){
	if(Cheek(mask , bitpos))
	dp[mask][bitpos] = max(giveMeValue(mask , bitpos-1) , giveMeValue(Reset(mask , bitpos) , bitpos-1));
	else
	dp[mask][bitpos] = giveMeValue(mask , bitpos-1);
	}
	}
	}
	void Solve(int t)
	{
	int i,j,k,n,supermask = (1<<22)-1;
	scanf("%d",&n);
	for(i=1 ; i<=n ; i++){
	scanf("%d",&ara[i]);
	fre[ara[i]] = 1;
	bra[i] = ara[i] ^ supermask; ///Invert the array element
	}
	FuN();
	for(i=1 ; i<=n ; i++){
	int ansi = dp[bra[i]][22];
	printf("%d ",ansi);
	}
	printf("\n");
	}
	int main()
	{
	Solve(1);
	return 0;
	}

view raw SOS-2.cpp hosted with ❤ by GitHub

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

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

	#include<bits/stdc++.h>
	using namespace std;
	int Set(int N, int pos) {return N = N | (1<<pos);}
	int Reset(int N, int pos) {return N = N & ~(1<<pos);}
	bool Cheek(int N, int pos) {return (bool)(N & (1<<pos));}
	#define sz 1000009
	int supermask = (1<<22)-1 , ara[sz],bra[sz],dp[2][1<<23];
	bool fre[5000009];
	int giveMeValue(int mask,int bitpos)
	{
	if(bitpos >= 0)
	return dp[bitpos & 1][mask];
	else{
	if(fre[mask])
	return mask;
	else
	return -1;
	}
	}
	void FuN()
	{
	for(int bitpos=0 ; bitpos <= 22 ; bitpos++){
	for(int mask=0 ; mask <= supermask ; mask++){
	if(Cheek(mask , bitpos))
	dp[bitpos & 1][mask] = max(giveMeValue(mask , bitpos-1) , giveMeValue(Reset(mask , bitpos) , bitpos-1));
	else
	dp[bitpos & 1][mask] = giveMeValue(mask , bitpos-1);
	}
	}
	}
	void Solve()
	{
	int i,j,k,n;
	scanf("%d",&n);
	for(i=1 ; i<=n ; i++){
	scanf("%d",&ara[i]);
	fre[ara[i]] = 1;
	bra[i] = ara[i] ^ supermask; ///Invert the array element
	}
	FuN();
	for(i=1 ; i<=n ; i++){
	int ansi = giveMeValue(bra[i] , 22);
	printf("%d ",ansi);
	}
	printf("\n");
	}
	int main()
	{
	Solve();
	return 0;
	}

view raw SOS-3.cpp hosted with ❤ by GitHub

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

Happy Coding 😊