Bappy's Blog

 এই পর্বে আমরা মূলত ডাটা স্ট্রাকচার ব্যাবহারের মাধ্যমে কিছু কিছু ডিপি প্রব্লেমের কমপ্লেক্সিটি কিভাবে কমিয়ে আনা সম্ভব তা দেখবো।  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 বানানো যায়।  একটু ভালো করে চিন্তা করলে দেখবে ১৫ নম্বর লাইনের ইনার লুপের কাজ আমরা সেগমেন্ট ট্রি এর একটি কুয়ে

 এই পর্বে আমরা মূলত প্রিফিক্স সাম এর মাধ্যমে ডিপির টাইম কমপ্লেক্সিটি অপটিমাইজেশন দেখবো। যা অনেক ডিপি প্রব্লেমেই কাজে লাগতে পারে।  প্রব্লেমঃ একটি 1*n আকারের গ্রীডের প্রতি সেলে কিছু ভ্যালু a[i] আছে। একটি সেল i থেকে a[i] দূরত্বের মধ্যে সামনে অথবা পিছনের কোন সেলে জাম্প দেয়া যায়। বলতে হবে সেল 1 থেকে সেল n এ এক্সেক্টলি k সংখ্যক জাম্প দিয়ে কতভাবে যাওয়া যায়? প্রথমেই এই প্রব্লেমের যে সল্যুশন আমাদের মাথায় আসে তা অনেকটা এরকমঃ  এখন, n<=10^4, k<=10^4 হলে উপরোক্ত সল্যুশন আর কাজ করবে না! এখন, ১২ এবং ১৫ নম্বর লাইনের ফর লুপ এর দিকে ভালো করে লক্ষ্য কর।  লক্ষ্য করলে বুঝবে যে এই লুপ দুইটির কাজ আমরা প্রিফিক্স সাম ক্যালকুলেট করে O(1)  কমপ্লেক্সিটি তে করতে পারি। তখন কোডটি দেখতে এরকম হবেঃ  এখন, উপরের সল্যুশন এ আমাদের মেমোরি লাগে প্রায় ৩৮১ মেগাবাইট। অর্থাৎ, MLE খাওয়ার সম্ভাবনা খুবই বেশি।  আগের দুইটি পর্ব পড়ে থাকলে নিজে নিজে এই সল্যুশনটিকে মেমোরি অপ্টিমাইজ করার চেষ্টা কর।  মেমোরি অপ্টিমাইজ করার পর সল্যুশনটা দেখতে এরকম হবেঃ  Next Episode Happy Coding😀

গত পর্বের মতো এই পর্বেও আমরা মেমোরি অপ্টিমাইজেশন দেখবো।  প্রব্লেমঃ মনে করি, আমাকে একটি n * m গ্রীড দেয়া আছে যেখানে n<=10^4 এবং m<=10^4। গ্রীডের প্রতিটি সেলে দুই ধরণের ক্যারেক্টার থাকতে পারে। '.' মানে ফাঁকা সেল এবং '#' মানে দেয়াল। গ্রীডের (1,1) সেল থেকে গ্রীডের (n,m) সেলে যাওয়ার মোট কয়টি পাথ আছে তা বের করতে হবে। প্রতিটি সেল থেকে আমি নিচে অথবা ডানে মুভ দিতে পারবো।  এন্সার খুব বড় হতে পারে তাই এন্সার কে 10^9 + 7 দ্বারা মড করতে হবে।  এই প্রব্লেমটি দেখা মাত্রই আমাদের মাথায় যে সল্যুশন আসে তা দেখতে অনেকটা এরকমঃ  একটু হিসেব করলেই দেখতে পাবা এই কোডে আমার মেমোরি লাগে প্রায় ৫৭২ মেগাবাইট!!! যদি প্রব্লেমে এর কম মেমোরি দেয় তাহলেই আমার এই সল্যুশন আর কাজ করবে না! তার মানে আমাকে মেমোরি আরো অপ্টিমাইজ করতে হবে।  এখন, কোডের ২৪ এবং ২৫ নম্বর লাইন যদি দেখো তাহলে দেখবে আমাকে বর্তমান সারির ডিপি ভ্যালু নির্ণয়ের জন্য আগের সারির ডিপি ভ্যালু জানতে হবে। অর্থাৎ, ith সারির জন্য শুধু (i-1)th সারির ভ্যালু জানাই যথেষ্ট। (i-2)th, (i-3)th,....এসব সারি আমার আর কোন কাজে লাগবে না।  এখন, আগের পর্বটি পড়ে থ

 এই পর্বে আমরা মূলত ডিপি তে মেমোরি অপ্টিমাইজেশন কিভাবে করে সেটা দেখবো।  প্রব্লেম-১ঃ  এটি সাধারণ একটি ন্যাপস্যাক প্রব্লেম যেখানে তোমাকে 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) হবে জোড়

এই পর্বে আমি কোডশেফ এর এক্সপেক্টেড ভ্যালুর টিউটোরিয়াল টির কিছু প্রব্লেম নিজের মতো করে সমাধান করার চেষ্টা করেছি।    হ্যাপি কোডিং 😊

এই পর্বটি পড়ার আগে  বিটসেট   সম্পর্কে ভালো আইডিয়া থাকা জরুরী।    Problem:  একটি গ্রাফ দেয়া থাকবে n < = 2000 ভার্টেক্স এবং m < = (n*(n-1))/2 এজ এর। গ্রাফটিতে কয়টি ত্রিভুজ আছে? অর্থাৎ, এমন কয়টি ভার্টেক্স সেট {u,v,w} আছে যেখানে u-v, v-w, w-u এজ দ্বারা কানেক্টেড।  Solution: গ্রাফের প্রতিটি ভার্টেক্স এর এডজাসেন্সি লিস্ট টাকে বিটসেট দিয়ে রিপ্রেজেন্ট করতে হবে। অর্থাৎ, প্রতিটি নোডের জন্য একটি করে বিটসেট ডিক্লেয়ার করতে হবে। সেই নোডের সাথে যেসব নোড কানেক্টেড তার সেসব পজিশন এর বিট অন করে দিবো। এরপর, n^2 লুপ চালিয়ে দেখবো প্রতি জোড়া কানেক্টেড নোড (u,v) এর জন্য তাদের বিটসেটে কমন কয়টি পজিশন এর বিট অন আছে যেখানে u<v ।  অর্থাৎ, ঐ কমন নোডগুলো এদের উভয়ের সাথে কানেক্টেড। এবং কানেক্টেড হয়ে ত্রিভুজ উৎপন্ন করেছে। এই সংখ্যা এন্সার এর সাথে যোগ করবো। ভালোভাবে লক্ষ্য করলে দেখবে যে, এই পদ্ধতিতে প্রতিটি ত্রিভুজ ৩বার করে গণনা হয়। তাই এন্সার কে ৩ দ্বারা ভাগ দিলেই কাজ শেষ!  এবার কোড দেখা যাকঃ 

Problem Description  here Solution: এই প্রব্লেমের সলুশ্যন নিয়ে বিস্তারিত আলোচনা করা হবে না😛 এই প্রব্লেমটি মূলত  Knapsack-2  এবং  Knapsack-3  এর সমন্বিত আইডিয়া দিয়ে সলভ করা সম্ভব!  আর  Knapsack-3  বুঝতে হলে  Bitset  বুঝতে হবে।  উপরোক্ত পর্বগুলো দেখার পরও সলভ করা সম্ভব না হলে সলুশ্যন দেখতে পারো।  হ্যাপি কোডিং😊

 এই পর্বটি পড়ার পূর্বে   বিটসেট    সম্পর্কে ভালোভাবে জানতে হবে।  Problem:  মনে কর, তোমাকে n<=1000 টি কয়েন দেয়া আছে যাদের ভ্যালু coin[i]<=100000। বলতে হবে এই কয়েনগুলো ব্যাবহার করে 1 to 10^5 পর্যন্ত কয়টি ভিন্ন ভিন্ন ভ্যালু বানানো যায়?  Solution: মনে করি, আমার কয়েন গুলোর সেট হচ্ছে, {১ , ৩ , ৬}। ১ থেকে ১০ পর্যন্ত কয়টি ভিন্ন ভিন্ন ভ্যালু বানানো যায় সেটি বের করতে হবে।  ১)  আমরা একটি বিটসেট অ্যারে নিবো 11 সাইজের। যার প্রতিটি ইনডেক্স এ 0 থাকবে প্রাথমিক অবস্থায়। ২) এখন শুরুতে ধরে নিবো কয়েনগুলো দ্বারা আমি ০ ভ্যালু বানাতে পারবো। তাহলে bset = 00000000001 ৩) এখন, আমার প্রথম কয়েন ১ টাকার। অর্থাৎ, ইতোপূর্বে আমি যতো যতো টাকার ভ্যালু বানাতে পেরেছি তাদের সবার সাথে ১ যোগ করলে যে নতুন ভ্যালুগুলো পাবো সেগুলোও বানানো সম্ভব।  ইতোপূর্বে আমি ০ টাকা বানাতে পেরেছি। অর্থাৎ, নতুন করে ১টাকা বানাতে পারবো।  এখন পর্যন্ত বানাতে পেরেছি {১ , ০}  এখন, আমার ২য় কয়েন ৩ টাকার। অর্থাৎ, ইতোপূর্বে আমি যতো যতো টাকার ভ্যালু বানাতে পেরেছি তাদের সবার সাথে ৩ যোগ করলে যে নতুন ভ্যালুগুলো পাবো সেগুলোও বানানো সম্ভব। অর্থাৎ, নতুন কর

মনে কর, তোমাকে একটা অ্যারে a[n] দেয়া আছে যেখানে n<=1e5 এবং a[i]<=1e7।  এরপর তোমাকে q<=1e5 টা কুয়েরী এন্সার করতে হবে। প্রতি কুয়েরী তে একটি সংখ্যা x দিবে। তোমাকে বলতে হবে এই সংখ্যাটি অ্যারে তে আছে কি না?  এখন এই সমস্যাটির একটি O(n) কমপ্লেক্সিটির সমাধান করতে বলা হলে তুমি কিভাবে করবে?  এখন, প্রব্লেমের সবকিছু ঠিক রেখে যদি a[i]<=1e9 করে দেয়া হয় তাহলে কী হবে? তোমার সলুশ্যনের মেমোরি কমপ্লেক্সিটি অনেক বেশি হয়ে যাবে। কারণ, প্রতিটি সংখ্যার জন্য তুমি ২বাইট = ১৬ বিট করে মেমোরি নিচ্ছো।  এখন, এরকম একটা বুলিয়ান অ্যারের পরিবর্তে আমরা বিটসেট ব্যাবহার করতে পারি। আসলে বিটসেটও একটি বুলিয়ান অ্যারে ই। কিন্তু সে প্রতিটি পজিশনের জন্য ১৬ বিট ব্যাবহার না করে মাত্র ১ বিট ব্যাবহার করবে!!!  তার মানে তোমার উপরোক্ত কোড এর মেমোরি কমপ্লেক্সিটি ১৬ গুণ কমানো সম্ভব!!!  বিটসেট ব্যাবহার করলে কোড টি নিচের কোডের মতোই হবে।  এই ছিলো বিটসেটের পরিচয় পর্ব।  এখন দেখবো বিটসেটের কিছু এপ্লিকেশন। হ্যাপি কোডিং😊

Problem: একজন চোর একটি ঘরে ঢুকে দেখলো সেখানে n<=100 ধরণের পণ্য আছে। প্রতি প্রকারের পণ্যের সংখ্যা সর্বোচ্চ cnt[i]<=1000 এবং প্রতি প্রকারের একটি পণ্যের ওজন wt[i]<=1000 এবং প্রতিটি পণ্য চুরি করলে সর্বোচ্চ লাভ profit[i]<=10000। এখন, ঐ চোরের কাছে থাকা ব্যাগে সর্বোচ্চ 10000 KG ওজনের পণ্য নেয়া গেলে চোর সর্বোচ্চ কত লাভ করতে পারবো?  Solution: মনে কর, ১টি পণ্যের সংখ্যা ১০ ইউনিট এবং প্রতি ইউনিটের দাম ৩টাকা করে। আমার অপ্টিমাল এন্সারে সেই পণ্যটি ০, ১, ২, ৩, ৪, ৫, ৬, ৭, ৮, ৯ অথবা ১০ বার থাকতে পারে। এবং এর জন্য আমার লাভ হবে যথাক্রমে ০, ৩, ৬, ৯, ১২, ১৫, ১৮, ২১, ২৪, ২৭ অথবা ৩০ টাকা।  এখন, আমি যদি ঐ প্রকারের পণ্যের ১ ইউনিট নিয়ে একটি কম্বো প্যাক, ২ ইউনিট নিয়ে একটি কম্বো প্যাক, ৪ ইউনিট নিয়ে একটি কম্বো প্যাক এবং ৩ ইউনিট নিয়ে একটি কম্বো প্যাক বানিয়ে নেই তাহলে আমি ঐ প্রকারের ১০ টি পণ্যের পরিবর্তে নতুন ৪ প্রকারের পণ্য পাবো যারা প্রত্যেকে ১ ইউনিট করে আছে। এবং এই চার প্রকারের পণ্যের দাম যথাক্রমে ৩, ৬, ১২, ৯ টাকা। এখন ভালো করে লক্ষ্য করলে দেখবে যে এই চারটি পণ্যের সাবসেট দ্বারা আমি ০, ৩, ৬, ৯, ১২, ১৫,

Problem Description  here Problem: একটি ঘরে n<=100 টি পণ্য আছে যাদের প্রতিটির দাম Price[i]<=1000 এবং ওজন wt[i]<=1e9। এখন, একজন চোর একটি ব্যাগ নিয়ে সেই ঘরে চুরির উদ্দ্যেশ্যে প্রবেশ করলো যার ধারণ ক্ষমতা capacity<=1e12। বলতে হবে সর্বোচ্চ কত টাকার পণ্য সে চুরি করতে পারবে?  Solution: সাধারণত, ন্যাপস্যাক প্রব্লেমে আমরা পজিশন এবং ক্যাপাসিটি কে স্টেট ধরে লাভের অংক ম্যাক্সিমাইজ করি (বিস্তারিত) । কিন্তু, এই প্রব্লেমে ক্যাপাসিটি অনেক বেশি থাকায় তা স্টেট হিসেবে ধরা যাবে না।  একটু ভালোভাবে লক্ষ্য করলে দেখবে ক্যাপাসিটি বেশি হলেও পণ্যের সর্বমোট দাম(<= 1e5)। তাহলে, এখন আমি দুটি স্টেট নিয়ে কাজ করতে পারি। স্টেট-১ঃ পজিশন স্টেট-২ঃ সর্বমোট লাভ  অর্থাৎ, প্রতি পজিশন i তে দাঁড়িয়ে i to n পর্যন্ত কত কম ওজনের পণ্য নিয়ে এক্সেক্টলি x পরিমাণ লাভ করা যায় এটা বের করাই আমার কাজ।  সবশেষে, দেখবো আমার ব্যাগের ক্যাপাসিটির সমান বা কম ওজনের পণ্য নিয়ে সর্বোচ্চ কতটাকা লাভ করা যায়।  Recursive Solution: Iterative Solution: Suggested Problem Next Episode Happy Coding

একটি সংখ্যা x কে ০ না হওয়া পর্যন্ত সর্বোচ্চ কতবার অন্য একটি পজিটিভ সংখ্যা(যা ঐ সংখ্যার সমান অথবা ছোট) দ্বারা মড করা যায়?  মনে করি, x = 16 এখন, x কে কোন সংখ্যা দ্বারা ভাগ করলে ভাগশেষ সব থেকে বড় হয়? 9 দ্বারা।  তাহলে, x = 16%9 = 7 এখন, x কে কোন সংখ্যা দ্বারা ভাগ করলে ভাগশেষ সব থেকে বড় হয়? 4 দ্বারা। তাহলে, x = 7%4 = 3 এখন, x কে কোন সংখ্যা দ্বারা ভাগ করলে ভাগশেষ সব থেকে বড় হয়? 2 দ্বারা। তাহলে, x = 3%2 = 1 এখন, x কে কোন সংখ্যা দ্বারা ভাগ করলে ভাগশেষ সব থেকে বড় হয়? 1 দ্বারা। তাহলে, x = 1%1 = 0 ভালোভাবে লক্ষ্য করলে দেখবে যে, প্রতি মডেই সংখ্যাটি অর্ধেক এর থেকেও ছোট হয়ে যাচ্ছে!  তার মানে, একটি সংখ্যাকে ০ না হওয়া পর্যন্ত আমি সর্বোচ্চ Log(X) বার ভাগ করতে পারি! বলে রাখা ভালো এখানে Log এর বেইস ২। এই অবজার্বেশন অনেক সময় বিভিন্ন প্রব্লেমের সাবপ্রব্লেম সলভ করা সহজ করে দেয়।  Happy Coding😀