Bappy's Blog

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

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

আজকের আলোচ্য টপিক ঃ ম্যাপ  মনে করো , তোমাকে তোমার ক্লাসের সকল ছাত্রের কোন বিষয়ে ১০০ তে প্রাপ্ত নাম্বার দেয়া হলো। এখন , তোমাকে বলা হলো ১ থেকে ১০০ পর্যন্ত কোন নাম্বার কতজন ছাত্র পেয়েছে? যারা মোটামুটি প্রব্লেম সলভ করেছো তাদের মাথায় যে সলুশ্যন এসেছে সেটি হলোঃ একটা অ্যারে নিবো ১০১ সাইজের! যেখানে সকল ইনডেক্সের ভ্যালু প্রাথমিকভাবে ০ থাকবে।   প্রত্যেক ছাত্রের নাম্বার পাওয়া মাত্রই অ্যারের ততো তম ইন্ডেক্সের ভ্যালু  ১++ করে দিবো। কাজ শেষ!!! এখন যদি আমি তোমাদেরকে এক আজব স্কুলের নাম বলি যেখানে কোন ছাত্রের নাম্বার নেগেটিভ ও হতে পারে! সেই স্কুলের স্যার রা মার্কস দেয় -১০০ থেকে +১০০ পর্যন্ত। এখন তোমাদের কেউ কেউ হয়তো একটু কনফিউজড! কিন্তু এমন কিছু চালাক প্রোগ্রামার তোমার আশেপাশে আছে যারা এই সমস্যা টি ও অ্যারে দিয়েই সমাধান করে ফেলবে!!! কি পোলাপান রে ভাই! আর তুমি যদি এখনো সমাধান টা না পাও তাহলে এই সমাধান টা তোমার চিন্তা করার জন্যই রেখে দিলাম।  এবার তাহলে আরো হার্ড প্রব্লেম দেয়া যাক। তোমাকে একটা ক্লাসের N জন ছাত্রের নাম দেয়া আছে।  তোমাকে বলতে হবে...

আজকের পর্বে আলোচনার বিষয় 2D ভেক্টর।  আমরা যারা অলরেডি 2D অ্যারের সাথে পরিচিত এই পর্বটি তাদের জন্য। 2D অ্যারে তে আমরা একটা ম্যাট্রিক্স ইনপুট নিতে পারি। একটা 1D  অ্যারে র কোন এলিমেন্ট প্রকাশ করতে একটি ভ্যারিয়েবল প্রয়োজন। 1D অ্যারের ক্ষেত্রে   ara[x]  তার X তম এলিমেন্ট বোঝায়। তেমনি একটা ২D অ্যারে র কোন এলিমেন্ট প্রকাশ করতে দুটি ভ্যারিয়েবল i , j ব্যাবহার হলে ara[i][j] বলতে বোঝায় i তম সারির j তম কলাম এর ভ্যালু।  ধরো, 2     0     7 5     6     9 এই ম্যাট্রিক্স তথা 2D অ্যারে ইনপুট নিতে হবে। তাহলে আমরা কিভাবে নেই?  নিশ্চই এভাবে? এখানে ara[n][m] ডিক্লেয়ার করার মানে হচ্ছে আমার 2D অ্যারে তে n টি সারি আর m টি কলাম থাকবে। আউটার লুপের কাউন্টার ভ্যারিয়েবল অ্যারের সারি নং এবং ইনার লুপের কাউন্টার ভ্যারিয়েবল অ্যারের কলাম নং প্রকাশ করে। এবার আসা যাক এই একই কাজ কিভাবে 2D ভেক্টর দিয়ে করা যায়!   তাহলে আমি কি করলাম এখানে?  প্রথম লাইনে একটা 2D ভেক্টর ডিক্লেয়ার করে ন...

ভেক্টরঃ  ভেক্টর হচ্ছে এক প্রকার ডায়নামিক অ্যারে ।  অর্থাৎ, এটি অটোমেটিক্যালি রিসাইজ হবে যখনই আমরা এখানে কোন ইলিমেন্ট ইনসার্ট কিংবা ইরেজ করবো ।  অ্যারে তে আমরা আগে থেকেই সাইজ ডিক্লেয়ার করে থাকি , কিন্তু ভেক্টর এর কিছু বিশেষ সুবিধা হলো আগে থেকে সাইজ ডিক্লেয়ার করার দরকার হয় না, বর্তমানে কয়টা ইলিমেন্ট আছে তা কোন কাউন্টার ভ্যারিয়েবল ছাড়াই জানা যায় , যে কোন পজিশনে ইলিমেন্ট ইনসার্ট করা যায়,ডিলিট করা যায় ,  খুব সহজে একটা সম্পূর্ণ ভেক্টর অন্য ভেক্টরে ইনসার্ট করা যায়।  কিভাবে ডিক্লেয়ার করবো?  ডাটা ইরেজ করাঃ  ইটারেটর এর মাধ্যমে ডাটা এক্সেস এবং ভেক্টর ক্লিয়ার করাঃ    ভেক্টর সরাসরি অ্যারের মতো করে এক্সেস করা গেলেও অন্যান্য STL এভাবে এক্সেস করা যায় না। সেক্ষেত্রে, ডাটা এক্সেস এর জন্য ইটারেটর এর প্রয়োজন হয় নিচের ছবির মতো করেঃ সরাসরি  n  তম পজিশনে ডাটা ইনসার্ট বা ইরেজ করাঃ   মনে রাখা শ্রেয় যে, এক্ষেত্রে কমপ্লেক্সিটি  O(n) হবে। একটি ভেক্টরের মধ্যে আরেকটি ভেক্টর ইনসার্ট করা , দুটি ভেক্টর...