এই সমস্যায়, আমাদের একটি বিটোনিক সিকোয়েন্স এবং Q প্রশ্ন দেওয়া হয়। প্রতিটি প্রশ্নের একটি পূর্ণসংখ্যা x আছে। আমাদের কাজ হল প্রতিটি প্রশ্নের পরে পূর্ণসংখ্যা সন্নিবেশ করার পরে বিটোনিক সিকোয়েন্সের দৈর্ঘ্য প্রিন্ট করা। এবং শেষে বিটোনিক সিকোয়েন্স প্রিন্ট করুন।
সমস্যা বর্ণনা - এখানে, আমাদের একটি বাইটোনিক সিকোয়েন্স দেওয়া হয়েছে। এবং Q প্রশ্ন রয়েছে, প্রতিটিতে একটি পূর্ণসংখ্যা রয়েছে যা ক্রমটিতে যোগ করতে হবে। আমরা প্রতিটি ক্যোয়ারী থেকে সিকোয়েন্সে উপাদান যোগ করব এবং তারপর বিটোনিক সিকোয়েন্সের দৈর্ঘ্য ফিরিয়ে দেব। সমস্ত ক্যোয়ারী শেষ হওয়ার পর, আমরা বিটোনিক সিকোয়েন্স প্রিন্ট করব।
বাইটোনিক সিকোয়েন্স একটি বিশেষ ধরনের ক্রম, যা একটি বিন্দু পর্যন্ত বৃদ্ধি পায় (যাকে বিটোনিক পয়েন্ট বলা হয়) এবং তারপর হ্রাস পায়।
উদাহরণ − 1, 5, 6, 8, 9, 7, 5, 2
সমস্যাটি আরও ভালভাবে বোঝার জন্য একটি উদাহরণ নেওয়া যাক,
ইনপুট
bseq = {1, 4, 6, 5, 2, 1}
Q = 2
Query = {5, 6 } আউটপুট
7 7
{1, 4, 5, 6, 5, 2, 1 } ব্যাখ্যা
প্রথম ক্যোয়ারীটির জন্য, সন্নিবেশ করাতে হবে মানটি হল 5 যা ক্রমবর্ধমান অংশে ঢোকানো যেতে পারে তৈরি করা ক্রম {1, 4, 5, 6, 5, 2, 1 }, দৈর্ঘ্য 7৷
প্রথম প্রশ্নের জন্য, সন্নিবেশ করাতে হবে মান হল 6 যা ঢোকানো যাবে না কারণ 6 হল সর্বাধিক মান৷ সুতরাং, 6 ঢোকানো হবে না।
চূড়ান্ত ক্রম {1, 4, 5, 6, 5, 2, 1 } দৈর্ঘ্য 7.
এই সমস্যার সমাধান করতে, আমাদের বাইটোনিক সিকোয়েন্সটিকে দুটি সেটে বিভক্ত করতে হবে, একটি সিকোয়েন্সের অংশকে সর্বোচ্চ মান পর্যন্ত বাড়ানোর জন্য। অনুক্রমের ক্রমহ্রাসমান অংশের জন্য অন্যটি৷
৷এখন, প্রতিটি উপাদান সন্নিবেশ করার জন্য নিম্নলিখিত ক্ষেত্রে হতে পারে -
কেস 1 (যদি উপাদানটি সর্বোচ্চ থেকে বড় হয়) − ক্রমবর্ধমান সিরিজের শেষে উপাদান যোগ করুন, এবং সর্বোচ্চ আপডেট করুন।
কেস 2 − যদি উপাদানটি সর্বোচ্চ থেকে কম হয়, উপাদানটির উপলব্ধতার জন্য প্রথমে ক্রমবর্ধমান সেটটি চেক-ইন করুন, যদি এর সমান কোনো উপাদান উপলব্ধ না হয় তাহলে সন্নিবেশ করুন৷ অন্যথায়, হ্রাসকারী সেটে অনুসন্ধান করুন এবং সম্ভব হলে যোগ করুন।
কেস 3 (যদি উপাদানটি সর্বাধিকের সমান হয় বা মান বৃদ্ধি এবং হ্রাস উভয় সেটে উপলব্ধ হয়) - উপাদান যোগ করা যাবে না ছেড়ে দিন।
প্রতিটি ক্যোয়ারী অপারেশনের পর, আমরা উভয় সেটের দৈর্ঘ্য যোগ করে বিটোনিক সিকোয়েন্সের সেটটি খুঁজে পাব,
length(bseq) = length(incSet) + length(decSet)
সমস্ত ক্যোয়ারী সম্পন্ন হওয়ার পর, theincSet প্রিন্ট করে বিটোনিক সিকোয়েন্স প্রিন্ট করুন এবং তারপর decSet প্রিন্ট করুন।
আমাদের সমাধানের কাজ চিত্রিত করার জন্য প্রোগ্রাম -
উদাহরণ
#include <bits/stdc++.h>
using namespace std;
void calcBitonicSeqLenth(int bSeq[], int n, int query[], int Q){
int maxVal = INT_MIN;
for (int i = 0; i < n; i++)
maxVal = max(maxVal, bSeq[i]);
set <int> incSet, decSet;
incSet.insert(bSeq[0]);
decSet.insert(bSeq[n - 1]);
for (int i = 1; i < n; i++)
if (bSeq[i] > bSeq[i - 1])
incSet.insert(bSeq[i]);
for (int i = n - 2; i >= 0; i--)
if (bSeq[i] > bSeq[i + 1])
decSet.insert(bSeq[i]);
decSet.erase(decSet.find(maxVal));
for (int i = 0; i < Q; i++) {
if (maxVal <= query[i]) {
maxVal = query[i];
incSet.insert(query[i]);
}
else {
if (incSet.find(query[i]) == incSet.end())
incSet.insert(query[i]);
else
decSet.insert(query[i]);
}
int length = incSet.size() + decSet.size();
cout<<"For query "<<(i+1)<<": The length of Bitonic Sequence is "<<length<<endl;
}
cout<<"The Bitonic Sequence at the end of all queries is : ";
set<int>::iterator it;
for (it = incSet.begin(); it != incSet.end(); it++)
cout<<(*it)<<" ";
set<int>::reverse_iterator revIt;
for (revIt = decSet.rbegin(); revIt != decSet.rend(); revIt++)
cout<<(*revIt)<<" ";
}
int main(){
int bSeq[] = { 1, 4, 6, 5, 2, 1 };
int n = sizeof(bSeq) / sizeof(bSeq[0]);
int Q = 2;
int query[] = { 6, 5 };
calcBitonicSeqLenth(bSeq, n, query, Q);
return 0;
} আউটপুট
For query 1: The length of Bitonic Sequence is 6 For query 2: The length of Bitonic Sequence is 7 The Bitonic Sequence at the end of all queries is : 1 4 5 6 5 2 1
