Bappy's Blog

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

এই প্রব্লেমে আমাদের L দৈর্ঘ্য এবং W প্রস্থের একটা পেপার দেয়া থাকবে। এই পেপারের চার কোণা থেকে X^2 ক্ষেত্রফল বিশিষ্ট চারটি বর্গ ক্ষেত্র কেটে নিতে হবে যাতে অবশিষ্ট পেপার দিয়ে সর্বোচ্চ আয়তনের একটি ঢাকনাবিহীন বক্স বানানো যায়। এই প্রব্লেমের সল্যুশন নিয়ে চিন্তা করার আগে অন্য একটা প্রব্লেম নিয়ে চিন্তা করা যাক।  মনে কর, তোমাকে একটি সংখ্যা X দেয়া আছে। X কে এমন দুটি সংখ্যার যোগফল হিসেবে প্রকাশ করতে হবে যাদের গুণফল সর্বোচ্চ হয়। এক্ষেত্রে ১০=৫+৫ গুণফল ২৫। ১১=৫+৬ গুণফল ৩০।  এই প্রব্লেমেও তোমাকে একইভাবে আয়তন ম্যাক্সিমাইজ করতে হবে। আর তুমি জানো VOLUME = LENGTH * WIDTH * HEIGHT তোমাকে দৈর্ঘ্য প্রস্থ দেয়া থাকবে। উচ্চতা X এর এমন একটি মান বের করতে হবে যাতে আয়তন সর্বোচ্চ হয়। বুঝতেই পারছো উচ্চতা বাড়লে দৈর্ঘ্য , প্রস্থ কমবে।  আগের প্রব্লেম টা বুঝতে পারলে বুঝতেই পারছো এই প্রব্লেমে উচ্চতা X এর ভ্যালু বাড়ার সাথে সাথে একটি নির্দিষ্ট সময় পর্যন্ত আয়তন বাড়বে। এরপর আবার আয়তন কমতে শুরু করবে। অর্থাৎ , গ্রাফটি হবে এমনঃ  আর এই কাজটি তুমি খুব সহজেই টার্নারী সার্চ দিয়ে করতে পারো।...

এই প্রব্লেমের টিউটরিয়াল পড়ার আগে নিজে নিজে ট্রাই কর। মজার ব্যাপার হলো আমি এই প্রব্লেম এর প্রথম যে কোড টা করেছিলাম সেটা ছিলো প্রায় ৪০০ লাইনের একটা কোড। যদিও পরে অনেক অপটিমাইজ সল্যুশন ঘাটার পর যা যা অবজার্ব করেছি সেটাই লিখছি। ১। প্রথমে স্ট্রিং টা কে দুইভাগে ভাগ করে ২য় ভাগ টা ১ম ভাগ দ্বারা রিপ্লেস করে এটা কে প্যালিন্ড্রোম বানাও। মানে ১২৩৪৫ থাকলে সেটা হয়ে যাবে ১২৩২১। এবার যে স্ট্রিং টা পাবা সেটা যদি আগের স্ট্রিং থেকে বড় হয় তবে সেটাই এন্সার। ২। আর যদি না হয়! তবে মিড ভ্যালু থেকে ০ ইন্ডেক্সের দিকে রওনা হও -_- । ৯ এর ছোট কোন ডিজিট পেলেই সেটা এক ইনক্রিমেন্ট করে ব্রেক করে লুপ থেকে বেরিয়ে যাও। আর এর আগে যতো ৯ পাবে সব ০ বানিয়ে দিবে। ৩। এখন মনে কর তুমি ৯ এর ছোট কোন ডিজিট ই পাও নি! তার মানে প্রথম ডিজিট ০। সেক্ষেত্রে তোমাকে স্ট্রিং এর শুরুতে একটা এক্সট্রা ডিজিট ১ যোগ করতে হবে। ৪। এরপর বর্তমান স্ট্রিং টার ক্ষেত্রে আবার স্টেপ ১ এপ্লাই কর। তবে এটাই হবে এন্সার। HAPPY CODING -_-

Topic of this problem: Binary Search with "meet in the middle" tricks মিট ইন দ্য মিডল টেকনিক হলো প্রব্লেম টা কে দুইভাগে ভাগ করে সেই দুই ভাগের রেজাল্ট মার্জ করে ফাইনাল রেজাল্ট টা বের করা।  ১। এই প্রব্লেমে কয়েন সংখ্যা মাত্র n = ১৮ টি। প্রত্যেক কয়েন সর্বোচ্চ দুইবার নেয়া যায়।  ২। প্রব্লেম সলভের আইডিয়া হলো কয়েনগুলোকে দুইভাগে ভাগ করে নেবো। এরপর প্রথম ভাগের অল পসিবল সাবসেট এর জন্য যতো ভ্যালু বানানো যায় তা একটি ভেক্টরে পুশ করবো। ৩। এরপর একইভাবে ২য় ভাগের কয়েনগুলোর অল পসিবল সাবসেট এর জন্য যে যে ভ্যালু X বানানো যায় প্রথমভাগে বাইনারী সার্চ চালিয়ে দেখবো  K-X আছে কি না। যদি থাকে তার মানে K ভ্যালু বানানো যাবে এই কয়েনগুলো দিয়ে।  ৪। অল পসিবল সাবসেট জেনারেট করার সময় যেকোন একটা কয়েন আমি চাইলে ০ বার, ১বার অথবা ২ বার নিতে পারি।  অনুরূপ একটি প্রব্লেম হলো      Funny Knapsack মিট ইন দ্য মিডল সম্পর্কে আরো জানতে     Tap The Link -_-

Topic of this problem: Probability,Expected value+DP প্রত্যেক পজিশনে দাঁড়িয়ে পরবর্তী ৬ টি পজিশনের এক্সপেক্টেড ভ্যালু বের করে যোগ করতে হবে। যদি তা  n ছাড়িয়ে যায় তবে সেক্ষেত্রে সেটি বর্তমান পজিশনের এক্সপেক্টেড ভ্যালু কে নির্দেশ করবে। সবশেষে,যোগফল রিটার্ন করে দিতে হবে। এবং সর্বশেষ, বাই ডিফল্ট প্রথম ভ্যালু টা যোগফল এর সাথে যোগ করে সেটাই হবে আউটফুট।  এক্সপেক্টেড ভ্যালু নির্ণয়ঃ Sample Input: 1 8 97 39 75 96 117 67 84 101 Sample Output: Case 1: 350.663889 হ্যাপি কোডিং -_-

Topic of this problem: Probability+Expected Value This is a simple problem that can be solved with expected value. A clarification for 3rd test case can help u to solve this problem if u know a little bit about expected value.  Now, if u don't understand the above calculation then please learn about expected value. Happy Coding. -_-

এই প্রব্লেমটি প্রোবাবিলিটি ও এক্সপেক্টেড ভ্যালু সম্পর্কিত। যদি ঐ পার্টিতে ৪জন লোক উপস্থিত থাকে এবং ৩৬৫ দিনে এক বছর হয়। তাহলে যেকোন ২জনের জন্মদিন একই হওয়ার সম্ভাব্যতা ঃ Now, you can solve this problem according to the clue. Happy Coding -_-

Hints: এই প্রব্লেমে আমাদেরকে শুধুমাত্র প্রত্যেকটা পয়েন্টের  y ভ্যালু নিয়েই কাজ করতে হবে। y অ্যারেটাকে সর্ট করে নিতে হবে। এরপর , DP function এ প্রত্যেক পজিশনে দাঁড়িয়ে w interval এ নেক্সট কোন পজিশন পর্যন্ত ডাস্ট কভার করা যায় ক্যাল্কুলেট করে নিতে হবে( বাইনারী সার্চের সাহায্যে )।  এভাবে, প্রত্যেক পজিশনে দাঁড়িয়ে আমি 1 টি মুভ ব্যাবহার করে সামনে জাম্প করতে পারি অথবা মুভ ব্যাবহার না করে পরবর্তী পজিশনে সুইচ করতে পারি। সবশেষে, ম্যাক্সিমাম রেজাল্ট DP অ্যারে তে স্টোর করতে হবে। Happy Coding -_-

As n<=16, the problem can be solved with bitmask DP with 2 states. State-1 is for the row(Boy). State-2 is now which column(Girl) is free with bitmasking. Go row by row. For every row(Boy), check the all available columns(Girl) one by one and calculate the best result. When all the girls have been taken, then the process will be terminated. Think before you code -_- Happy Coding -_-