Bappy's Blog

এই পর্ব পড়ার আগে  Range GCD & Point Update  পর্বটি পড়া আবশ্যক।   Problem: এই প্রব্লেমে আমাদের একটি অ্যারে দেয়া থাকবে n সাইজের এবং q সংখ্যক কুয়েরী এন্সার করতে হবে। দুই ধরনের কুয়েরী থাকবে।  1 L R                অ্যারের L থেকে R Index পর্যন্ত সংখ্যাগুলোর GCD বের করতে হবে। 2 L R x              অ্যারের L থেকে R ইনডেক্স পর্যন্ত সংখ্যাগুলোর ভ্যালু x বাড়াতে হবে।  Solution: আমরা জানি,  GCD(a , b) = GCD(a , b-a) = GCD(a-b , b) = GCD(abs(a-b) , a) = GCD(abs(a-b) , b) GCD(a , b , c) = GCD(a , GCD(b , c)) উপরোক্ত দুটি সমীকরণ থেকে লিখতে পারি, GCD(a , b , c) = GCD(a , GCD(b-a , c-b)) অর্থাৎ, GCD(a[l] , a[l+1] , a[l+2] , ... , a[r]) = GCD(a[l] , a[l+1]-a[l] , a[l+2]-a[l+1] , ... , a[r]-a[r-1]) এখন, এই প্রব্লেম এ আমরা দুটি সেগমেন্ট ট্রি ব্যাবহার করবো।  ১) ১ম সেগমেন্ট ট্রি তে আমরা মূল অ্যারের বর্তমান অবস্থা কি সেটার হিসাব রাখবো। অর্থাৎ, মূল অ্যারের কোন ইনডেক্সের ভ্যালু বর্তমানে...

 Problem: এই প্রব্লেমে আমাদের একটি অ্যারে দেয়া থাকবে n সাইজের এবং q সংখ্যক কুয়েরী এন্সার করতে হবে। দুই ধরনের কুয়েরী থাকবে।  1 L R           অ্যারের L to R index পর্যন্ত সংখ্যাগুলোর GCD বের করতে হবে।  2 pos x         অ্যারের pos তম পজিশনের ভ্যালু x বাড়িয়ে দাও।  Solution: সেগমেন্ট ট্রি এর রেঞ্জ কুয়েরী এবং পয়েন্ট আপডেট সম্পর্কে ধারনা থাকলেই এই প্রব্লেম সলভ করা সম্ভব। তাই বিস্তারিত আলোচনা না করে সরাসরি কোডে যাচ্ছিঃ  Suggested problem Happy Coding 

 Problem Description  here এই প্রব্লেমটি আমার তৈরী করা একটি প্রব্লেম যেটি মূলত  Intra CoU Programming Contest 2020  এর জন্য সেট করা। এই প্রব্লেম সলভ করতে যা যা জানা দরকার তা হলোঃ Sparse Table ,  Segment Tree ,  DFS ,  Binary Search প্রব্লেমঃ প্রব্লেমটিতে বলা হয়েছে n সাইজের একটি ট্রি দেয়া থাকবে যার প্রতি নোডে কিছু ফুল আছে। এখন, তোমাকে q টা কুয়েরী এন্সার করতে হবে। কুয়েরী আবার দুই ধরণের হতে পারে। ১) u     v     x           v থেকে u এর দিকে সর্বনিম্ন কয়টা নোড ভিজিট করে কমপক্ষে x সংখ্যক ফুল কালেক্ট করা যায় তা বের করতে হবে যেখানে u হচ্ছে v এর এন্সেস্টর(পূর্বসুরী) । ২) u      y u নোডের ফুল সংখ্যা আপডেট করতে হবে। y পজিটিভ হলে যোগ হবে, নেগেটিভ হলে বিয়োগ।  হিন্টসঃ   ১) স্পার্স টেবিল ডাটা স্ট্রাকচার শিখে থাকলে এখন তুমি একটি ট্রি এর প্রতিটি নোডের জন্য এর kth প্যারেন্ট বের করতে পারবে নিশ্চয়ই! এর জন্য তোমার log(n) কমপ্লেক্সিটি লাগবে।  ২) প্রব্লেমে একটা ব্যাপার লক্ষ্য করেছো কি?...

 এই পর্বে আমরা মূলত ডাটা স্ট্রাকচার ব্যাবহারের মাধ্যমে কিছু কিছু ডিপি প্রব্লেমের কমপ্লেক্সিটি কিভাবে কমিয়ে আনা সম্ভব তা দেখবো।  Problem: মনে কর, তোমাকে একটি n<=10^4 সাইজের অ্যারে দেয়া আছে। এই অ্যারের দীর্ঘতম ক্রমবর্ধমান অনুক্রমের দৈর্ঘ্য বের করতে হবে😛 ইংরেজীতে বললে Longest Increasing Subsequence এর Length বের করতে হবে। তাহলে এই প্রব্লেমের সল্যুশন কি হতে পারে?  Hints: শেষ থেকে শুরুর দিকে প্রত্যেক পজিশনে দাঁড়িয়ে দেখবো এই পজিশনের ভ্যালুটি অবশ্যই নিলে আমি সর্বোচ্চ কত লেন্থ এর LIS বানাতে পারবো। এভাবে সবগুলো রেজাল্ট এর মধ্যে ম্যাক্সিমাম টা এন্সার।  কোডটি হলোঃ  এখন, কী হবে যদি n<=10^5 এবং a[i]<=10^5 হয়?  উপরের সল্যুশন এ ভালো করে লক্ষ্য করলে দেখবে যে, প্রত্যেক পজিশন i তে দাঁড়িয়ে আমরা দেখি i এর ডানে যেসব ভ্যালু আছে a[i] এর সমান অথবা বড় তাদের মধ্যে কার DP এর ভ্যালু সর্বোচ্চ? যেখানে, dp[i] বলতে বোঝায় ith to nth ইনডেক্সের ভ্যালুগুলো কনসিডার করে সর্বোচ্চ কত লেন্থ এর LIS বানানো যায়।  একটু ভালো করে চিন্তা করলে দেখবে ১৫ নম্বর লাইনের ইনার লুপের ক...

Problem Description   Click Here Topic Of This Problem: Segment Tree with Offline Query n সংখ্যক ভিন্ন ভিন্ন সংখ্যার একটি অ্যারে দেয়া থাকবে এবং q সংখ্যক কুয়েরী দেয়া থাকবে। প্রতি কুয়েরী তে l থেকে r ইনডেক্সের মাঝে এমন কয়টা পেয়ার (ara[i] , ara[j]) আছে যেখানে ara[i] সংখ্যাটি ara[j] এর একটা ডিভিজর। প্রথমে এই প্রব্লেমটাকে একটু জেনারেলাইজ করা যাক, তোমাকে একটা দ্বিমাত্রিক তল দেয়া আছে। এই তলে অনেকগুলো অনুভূমিক রেখা আছে। বের করতে হবে, X অক্ষ বরাবর l to r ইনডেক্সের মাঝে কয়টা রেখা সম্পূর্ণভাবে অবস্থান করে। সল্যুশন আইডিয়াঃ ১) জেনারেলাইজ প্রব্লেম অনুযায়ী, প্রতিটা অনুভূমিক রেখার স্টার্টিং আর এন্ডিং পয়েন্ট আমার জানা লাগবে। এজন্য, ১ থেকে n পর্যন্ত প্রতিটি সংখ্যার জন্য তার মাল্টিপল এর ইনডেক্স বের করবো। যেমন, ২ এর ইনডেক্স যদি x হয় এবং ৪ এর ইনডেক্স যদি y হয় তার মানে অনুভূমিক রেখাটি X অক্ষের সমান্তরালে x থেকে y পর্যন্ত অবস্থিত। এভাবে, প্রতিটি সংখ্যার ইনডেক্স এর জন্য তার মাল্টিপলগুলোর ইনডেক্স গুলো বের করে রাখবো। ২) এবার কুয়েরী ইনপুট নেয়ার সময় একটি পেয়ার এর ভেক্টরে প্রত্যেক প...

See the problem description -  Here প্রব্লেম বুঝে থাকলে প্রথমে ১ টি টেবিল দেখে নেয়া যাকঃ  আমাদের কে একটি অ্যারে দেয়া আছে ara[] = {-3 , -2 , -1 , 1 , 2 , 3} টেবিলের ১ম সারি হলো মূল অ্যারে (উল্লেখ্য অ্যারের সাইজ ৬। মূল অ্যারে টা কে ২বার রিপিট করা হয়েছে সলুশন এর সুবিধার্থে) । ২য় সারি হলো মূল অ্যারের কিউমুলেটিভ সাম যা ০ সাইক্লিক শিফট এর জন্য কাজ করে। এই সারির ১ থেকে ৬ ইন্ডেক্স পর্যন্ত সাম অ্যারের ইলিমেন্ট গুলোর মধ্যে মিনিমাম টা ০ থেকে বড় হলে, ০ সাইক্লিক শিফট শর্ত মেনেছে এন্সার ১ বাড়ানো হবে।  ৩য় সারি হলো ২য় ইলিমেন্ট থেকে বানানো কিউমুলেটিভ সাম। এই সারির ২ থেকে ৭ ইনডেক্স পর্যন্ত সাম অ্যারের ইলিমেন্ট গুলোর মধ্যে মিনিমাম টা ০ থেকে বড় হলে, ১ সাইক্লিক শিফট শর্ত মেনেছে। এন্সার ১ বাড়ানো হবে। (উল্লেখ্য এই সারিতে ১ নম্বর ইনডেক্স এর ঘর খালি রাখা হয়েছে)। এভাবে ৬ সাইজের একটা অ্যারের জন্য ০ থেকে ৫ পর্যন্ত সাইক্লিক শিফট বের করে কয়টা সাইক্লিক শিফট এর মিনিমাম ভ্যালু ০ থেকে বড় সেটাই এই প্রব্লেমে বের করতে বলা হয়েছে।  এখন, এভাবে প্রত্যেক সাইক্লিক শিফট এর জন্য সাম জেনা...