এই সমস্যায়, আমাদের n সংখ্যক নম্বর সম্বলিত একটি অ্যারে এবং একটি পূর্ণসংখ্যা k দেওয়া আছে। আমাদের কাজ হল এলিমেন্ট মুছে ফেলার দেওয়া নিয়ম মেনে অ্যারের ন্যূনতম সম্ভাব্য আকার খুঁজে বের করা।
সমস্যা বর্ণনা - আমাদের অ্যারেতে এলিমেন্টের সংখ্যা ন্যূনতম করতে হবে। দেওয়া ডিলিশন অপারেশন ব্যবহার করে, একবারে মুছে ফেলা যাবে ৩টি এলিমেন্ট। মুছে ফেলা সম্ভব হবে যদি তিনটি এলিমেন্ট দুটি শর্ত সন্তুষ্ট করে:
- শর্ত ১ - তিনটি এলিমেন্ট সংলগ্ন (adjacent) হতে হবে।
- শর্ত ২ - دوটি নিকটবর্তী এলিমেন্টের পার্থক্য k হবে, অর্থাৎ arr[i+1] = arr[i] + k এবং arr[i+2] = arr[i+1] + k।
উদাহরণ
ইনপুট
{4, 6, 8, 4, 1, 5}, k = 2
আউটপুট
3
ব্যাখ্যা
একটি ডিলিশন অপারেশন সম্ভব, ইন্ডেক্স 0, 1, 2 এর জন্য।
সমাধানের পদ্ধতি
এই সমস্যা কিছুটা জটিল কারণ ইনডায়রেক্ট ডিলিশন অপারেশনও সম্ভব যেগুলো এক ডিলিশন করার পর দেখা যায়। উদাহরণস্বরূপ, একবার 5, 6, 7 ইন্ডেক্সের এলিমেন্ট ডিলিট করলে, নতুন অ্যারেতে 3, 4, 5 ইন্ডেক্সের এলিমেন্টগুলো ডিলিশনের শর্ত সন্তুষ্ট করতে পারে। এই ধরনের ওভারল্যাপিং সাবপ্রব্লেম ওয়ালা সমস্যা ডাইনামিক প্রোগ্রামিং দিয়ে সমাধান করা যায়। এর জন্য আমরা একটি DP[][] ম্যাট্রিক্স মেইনটেইন করব সাবপ্রব্লেমের ফলাফল স্টোর করতে যাতে পরে দরকার पड़লে ব্যবহার করা যায়, এটাকে মেমোইজেশন বলা হয়।
প্রোগ্রাম উদাহরণ
#include <bits/stdc++.h>
using namespace std;
#define MAX 1000
int DP[MAX][MAX];
int calcMinSize(int arr[], int start, int end, int k) {
if (DP[start][end] != -1)
return DP[start][end];
if ((end - start + 1) < 3)
return end - start + 1;
int minSize = 1 + calcMinSize(arr, start + 1, end, k);
for (int i = start + 1; i <= end - 1; i++) {
for (int j = i + 1; j <= end; j++) {
if (arr[i] == (arr[start] + k) && arr[j] == (arr[start] + 2*k)
&& calcMinSize(arr, start + 1, i - 1, k) == 0
&& calcMinSize(arr, i + 1, j - 1, k) == 0) {
minSize = min(minSize, calcMinSize(arr, j + 1, end, k));
}
}
}
return (DP[start][end] = minSize);
}
int main() {
int arr[] = {4, 6, 8, 4, 1, 5 };
int n = sizeof(arr) / sizeof(arr[0]);
int k = 2;
memset(DP, -1, sizeof(DP));
cout << "The minimum possible size of the array after removal is " << calcMinSize(arr, 0, n - 1, k);
return 0;
}
আউটপুট
The minimum possible size of the array after removal is 3
