ট্রি : IN-OUT DP

আজকে আমরা খুবই সুন্দর একটা জিনিস শিখতে চলেছি, যা দিয়ে ট্রি এর খুবই সুন্দর কিছু প্রব্লেম সলভ করা যায়। টেকনিকটার নাম In – Out DP. বেশি কথা না বাড়িয়ে, সরাসরি প্রব্লেমে চলে যাই। 🙂    তোমাকে একটা ট্রি দেয়া আছে, আর রুট নোড বলে দেয়া আছে। বলতে হবে, এই ট্রি এর উচ্চতা(Height) কত? Height বলতে … More ট্রি : IN-OUT DP

প্রব্লেম অ্যানালাইসিস – সেগমেন্ট ট্রি

  প্রথমেই বলে রাখি, এটা সেগমেন্ট ট্রি এর টিউটোরিয়াল না, অর্থাৎ এখানে সেগমেন্ট ট্রি কি, কি কাজ করে, কিভাবে করে, কিভাবে কোড লিখতে হয়, কিছুই বলা হবে না! কারণ সেগমেন্ট ট্রি নিয়ে বাংলা এবং ইংরেজি উভয় ভাষায়ই অনেক ভাল ভাল টিউটোরিয়াল আছে। তাই যদি সেগমেন্ট ট্রি সম্পর্কে না জেনে থাকো, তবে এই ব্লগপোস্ট পড়ার আগে … More প্রব্লেম অ্যানালাইসিস – সেগমেন্ট ট্রি

পলিসি বেইজড ডাটা স্ট্রাকচার (PBDS)

আচ্ছা, তোমরা নিশ্চয়ই C++ STL এর set (সেট) ব্যবহার করেছো বিভিন্নসময়। তাহলে নিশ্চয়ই কখন সেট ব্যবহার করা হয়, সেটাও জানা থাকার কথা। সেটের মূল দুটো বৈশিষ্ট্য হচ্ছেঃ সেটের ভিতরে কোন উপাদান (element) ১ বারের বেশি থাকে না, এবং সেটের ভিতরে উপাদানগুলো সবসময় সর্টেড অবস্থায় থাকে। অর্থাৎ তুমি যদি একে একে ৫, ২, ৬, ৪, ২, ৭ … More পলিসি বেইজড ডাটা স্ট্রাকচার (PBDS)

LightOj Dp – পর্ব ১

ডায়নামিক প্রোগ্রামিং ভাল করে শেখার জন্যে প্র্যাকটিসের কোন বিকল্প নেই। আর প্র্যাকটিসের জন্যে বেশিরভাগ সময় LightOj এর প্রব্লেমগুলো রিকমেন্ড করা হয়। মোট ১০৬টা ডিপি প্রব্লেম আছে এই অনলাইন জাজে এবং প্রত্যেকটাই তোমাকে নতুন নতুন কিছু শিখতে সাহায্য করবে। প্রব্লেমগুলো একে একে করতে থাকলেই দেখবে, তোমার ডিপি প্রব্লেম সলভ করার স্কিল আস্তে আস্তে বাড়ছে। কিন্তু লাইটওজের … More LightOj Dp – পর্ব ১

Divide & Conquer Optimization – DP(ডিপি অপ্টিমাইজেশন)

  প্রথমেই বলে রাখি, এই টিউটোরিয়ালটা একটু এডভান্সড লেভেলের। তাই ডিপি নিয়ে খেলা করতে মোটামুটি পারদর্শী না হলে এই টিউটোরিয়ালটা স্কিপ করাই ভাল। সাথে Divide and Conquer সম্পর্কেও জানা থাকতে হবে!   এবার তাহলে শুরু করা যাক। প্রথমেই কিছু কঠিন কঠিন শর্ত লিখে শুরু করব। 😥 ঘাবড়ে যাওয়ার কোন কারণ নেই, উদাহরণ দিলে আস্তে আস্তে … More Divide & Conquer Optimization – DP(ডিপি অপ্টিমাইজেশন)

আহো-কোরাসিক(Aho-Corasick) অ্যালগোরিদম

মনে আছে তো, আমার সেই কিপটে বন্ধুটাকে জব্দ করে বুফে খাওয়ার কথাটা! আহহ, সেই স্বাদ এখনও মুখে লেগে আছে! 😉 আর বন্ধুর করুণ মুখটা দেখলে আজও হাসি আটকে রাখতে পারি না। 😄 কিন্তু আমার সেই বন্ধুটাও কোনভাবেই ছাড়ার পাত্র নয়, সে এই টাকা আমার থেকে উঠিয়েই ছাড়বে। তাই এবার সে বাজি লাগল আরেকটা নতুন সমস্যা নিয়ে। প্রায় ১০০০০ শব্দ … More আহো-কোরাসিক(Aho-Corasick) অ্যালগোরিদম

এক্সটেন্ডেড ইউক্লিডীয়ান অ্যালগোরিদম

এই টিউটোরিয়ালটি আসলে ‘একের ভেতর দুই’ টিউটোরিয়াল। কারণ, এক্সটেন্ডেড ইউক্লিডীয়ান অ্যালগোরিদম জানতে হলে ইউক্লিডীয়ান অ্যালগোরিদম কিভাবে কাজ করে সেটাও জানতে হবে। আর আমরা সবাই নিশ্চয়ই জানি, ইউক্লিডীয়ান অ্যালগোরিদম আমরা GCD (Greatest Common Divisor) বের করার কাজে ব্যবহার করি!   বেশি কথা না বাড়িয়ে উদাহরণে চলে যাই! খাতা কলম নিয়ে আমার সাথেই লিখতে বসে যাও, তাহলে … More এক্সটেন্ডেড ইউক্লিডীয়ান অ্যালগোরিদম

KMP অ্যালগোরিদম

আমার এক কিপটে বন্ধু একবার আমার সাথে বাজি ধরল, বলল, তোরা তো সবাই বলিস, আমি কোনদিন খাওয়াই না। আচ্ছা, তুই যদি ‘Lord of the Rings’ বইয়ে কতবার ‘and’ শব্দটা আছে, সেটা আমাকে বলতে পারিস, তাহলে তোকে আমি একদিন রেডিসনে বুফে খাওয়াব!    আমি তো বুফে খাওয়ার লোভে একেবারে আদাজল খেয়ে লেগে পড়লাম!   কিন্তু কিছুক্ষণ … More KMP অ্যালগোরিদম

বিটের মজা, মজার বিট

আমরা যে কম্পিউটার প্রোগ্রামিং করি, হাজার হাজার লাইনের কোড লিখে জটিল, অস্থির সব এপস, সফটওয়্যার, গেমস বানাই 😀 ; গুগল, Bing কিংবা আমাদের দেশের পিপীলিকা অথবা চড়কির মত সার্চ ইঞ্জিন বানাই 😉 সবকিছুর মূলে যে অসাধারণ ক্ষমতাধর জিনিসটি লুকিয়ে আছে তা হল বিট : ০ আর ১. আমরা যে সংখ্যা(int, double, float, long long) এবং … More বিটের মজা, মজার বিট

প্রিম’স অ্যালগোরিদম : মিনিমাম স্প্যানিং ট্রি

ধরো, তোমাকে কোন ব্রডব্যান্ড প্রোভাইডার কোম্পানি একটি দায়িত্ব দিল, কোন একটি এলাকায় তাদের সব কাস্টমারের বাড়িতে সবচেয়ে কম খরচে ব্রডব্যান্ড লাইন বসাতে হবে। কোম্পানির সেন্ট্রাল অফিস থেকে প্রতিটি বাড়ি এবং একটি বাড়ি থেকে অন্য একটি বাড়ির দূরত্ব আলাদা। তার মানে তোমাকে সবচেয়ে কম তার খরচ করে, অর্থাৎ সবচেয়ে কম দূরত্ব অতিক্রম করে সবগুলো বাড়িতে লাইন … More প্রিম’স অ্যালগোরিদম : মিনিমাম স্প্যানিং ট্রি