Bappy's Blog

Problem: এই প্রব্লেমে মূলত আমাকে 100 x 100 সাইজের একটি 2D অ্যারে দেয়া থাকবে। আমাকে ঐ অ্যারে তে এমন একটি আয়ত (Rectangle) নির্বাচন করতে হবে যাতে তার সংখ্যাগুলোর যোগফল সর্বোচ্চ হয়। যেমনঃ উপরোক্ত 3 x 5 সাইজের 2D অ্যারের জন্য সম্ভাব্য সকল আয়তের মধ্যে সবুজ চিহ্নিত আয়তের সংখ্যাগুলোর যোগফল সর্বোচ্চ।  Solution: 1D অ্যারে তে  Maximum Sub-Array Sum  বের করতে পারলে এই প্রব্লেমটি O(n^3) কমপ্লেক্সিটি তে সলভ করা সম্ভব।  আমরা একটি আয়ত নির্বাচন এর জন্য তার Upper & Lower Row দুইটি ফিক্স করবো। এরপর, নতুন একটি অ্যারে তৈরী করবো। ঐ অ্যারের i'th Element হবে i'th Column বরাবর Upper Row to Lower Row এর সংখ্যাগুলোর যোগফল। এখন, এই নতুন অ্যারের  Maximum Sub-Array Sum  বের করে এন্সার কে ম্যাক্সিমাইজ করার চেষ্টা করবো। এভাবে, সম্ভাব্য সকল (Upper Row, Lower Row) = (i , j) কম্বিনেশন এর জন্য কাজ করলেই আমরা আমাদের মূল রেজাল্ট পেয়ে যাবো।  কোডটি দেখতে যেমন হবেঃ  Happy Coding

Problem: এই প্রব্লেমে আমাকে একটি অ্যারে দেয়া থাকবে। ঐ অ্যারের এমন একটি সাব-অ্যারে নির্বাচন করতে হবে যার সংখ্যাগুলোর যোগফল সর্বনিম্ন হয়।  Solution: Maximum Sub-Array Sum  এই পর্বটি পড়ে থাকলে এই প্রব্লেম সলভ করা খুবই সহজ। কীভাবে? ১) অ্যারের প্রতিটি সংখ্যার সাথে -১ গুণ করবো। অর্থাৎ, পজিটিভ সংখ্যাগুলোকে নেগেটিভ বানাবো আর নেগেটিভ গুলোকে পজিটিভ।  ২) তারপর, পরিবর্তিত এই অ্যারের  Maximum Sub-Array Sum  ক্যালকুলেট করবো। ৩) প্রাপ্ত রেজাল্ট কে -১ দ্বারা গুণ করবো। কাজ শেষ 😛

Problem: আমাকে একটি অ্যারে দেয়া থাকবে। ঐ অ্যারের এমন একটি সাব-অ্যারে নির্বাচন করতে হবে যার সংখ্যাগুলোর যোগফল সর্বোচ্চ হবে।  Solution: এটি খুবই কমন একটি প্রব্লেম যার অনেকগুলো সমাধান সম্ভব। তাই বিস্তারিত না বলে সরাসরি কোডে যাচ্ছি। আশা করি কোড দেখেই বুঝতে পারবেঃ 

 Problem Description  here Problem: এই প্রব্লেমে আমাদেরকে n সংখ্যক ডাইস দেয়া থাকবে। প্রতিটি ডাইসের k সংখ্যক তল থাকে যাদেরকে 1,2,3,....,k দ্বারা সংখ্যায়িত করা হয়। আমি ডাইসগুলো যেকোনভাবে সাজাতে পারি। সাজানোর পর যদি সকল ডাইসের উপরের তলের সংখ্যাগুলোর যোগফল S এর সমান হয় তবে স্কোর হবে উপরের তলের সংখ্যাগুলোর গুণফলের সমান।  এখন, আমাকে যতোগুলো ভ্যালিড ওয়ে তে সাজানো যায় সবগুলোর জন্য স্কোর এর যোগফল হিসেব করতে হবে।   এই প্রব্লেমটি আমার সলভ করা ডিপি অপটিমাইজেশনের অন্যতম মজার একটি প্রব্লেম। এই প্রব্লেম সলভ করার আগে আমি ডিপি অপটিমাইজেশন নিয়ে যে পর্বগুলো লিখেছি সবগুলো পড়ে আসতে হবে। এবং DICE-1 প্রব্লেমটি সলভ করে আসতে হবে।  DP Optimization-1 DP Optimization-2 DP Optimization-3 DP Optimization-4 Light OJ 1145 Solution: ১) Prerequisite গুলো পূরণ করে আসলে দুইটা প্রব্লেম ই সিমিলার মনে হবে শুরুতেই। DICE(I) এর সল্যুশনে প্রথম যে ফাংশনটি লিখেছিলাম আমি ঠিক সেরকম একটি ফাংশন লিখতে পারবা এই প্রব্লেমের জন্য যাতে ছোট Constraint এর জন্য কাজ করে?  আগের প্রব্লেমের সল্যুশনে ২৯ নাম্বার লাইনটি কি ছিলো? dp[i][j]  +=  dp[i][

 Problem Description  here এই প্রব্লেমটি নিয়ে বিস্তারিত আলোচনা করবো না। কারণ ইতোমধ্যেই আমি ডিপি অপটিমাইজেশন এর যে পর্বগুলো লিখেছি সেগুলো যথেষ্ট এই প্রব্লেম সলভ করার জন্য।  DP Optimization-1 DP Optimization-2 DP Optimization-3 DP Optimization-4 তোমার উচিৎ উপরোক্ত পর্বগুলো পড়ে প্রব্লেমটি নিজে নিজে সলভ করার চেষ্টা করা।  এরপরও ব্যার্থ হলে নিচের কোড দেখতে পারো। কোডটিকে ধাপে ধাপে অপটিমাইজ করার চেষ্টা করেছি যাতে ভালোভাবে বুঝতে পারো।  Next Episode Happy Coding😊

 Problem Description  here এই প্রব্লেমটি আমার তৈরী করা একটি প্রব্লেম যেটি মূলত  Intra CoU Programming Contest 2020  এর জন্য সেট করা।  প্রব্লেমঃ প্রব্লেমটিতে বলা হয়েছে একটি n সাইজের ট্রি দেয়া থাকবে। যার প্রতিটি নোডে কিছু ক্যারেক্টার থাকবে। ট্রি এর রুট নোড হচ্ছে ১। বলতে হবে, এই ট্রি এর রুট থেকে লিফ পর্যন্ত এমন কোন পাথ আছে কি না যে পাথ "tareq&shawon" এই স্ট্রিং টা কে সাবসিকুয়েন্স হিসেবে ধারণ করে। যদি এমন পাথ থাকে তবে Lexicographically Smallest পাথটি প্রিন্ট করতে হবে।  সল্যুশনঃ এই প্রব্লেমটির একটি ডিপি সল্যুশন সম্ভব।  ১) যেহেতু, Lexicographically Smallest পাথ বের করতে হবে তাই শুরুতেই প্রতিটি নোড এর জন্য তার এডজাসেন্সি লিস্ট টি Sort করে নিবো।  ২) ডিপি অ্যারের কাজ হবে প্রতিটি নোড থেকে লিফের দিকে যতোগুলো পাথ গেছে তাদের কোন একটি পাথ ধরে এখন পর্যন্ত স্ট্রিং এর যে ক্যারেক্টারগুলো সাবসিকুয়েন্স হিসেবে পেয়েছি সেগুলো ছাড়া বাকি সাফিক্সটুকু সাবসিকুয়েন্স হিসেবে পাওয়া যায় কি না সেটি ক্যালকুলেট করা।  ৩) এরপর, ডিপি অ্যারে ব্যাবহার করে ডিপি সল্যুশন প্রিন্ট করলেই কাজ শেষ!  এরপরও না পারলে ন

 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) কমপ্লেক্সিটি লাগবে।  ২) প্রব্লেমে একটা ব্যাপার লক্ষ্য করেছো কি? u সবসময় v এর এন্সেস্টর! কেন?  DFS ব্যাবহার করে একটি ট্রি এর প্রতিটি নোডের স্টার্ট টাইম আর ফিনিশিং টাইম নিশ্চয়ই

 Problem Description  here Problem: এই প্রব্লেমে আমাকে একটি স্ট্রিং s দেয়া থাকবে এবং একটি পজিটিভ সংখ্যা d দেয়া থাকবে। বলতে হবে স্ট্রিং টির এমন কতটি পারমুটেশন সম্ভব যা d দ্বারা ডিভিজিবল। Solution: ১) Constraint এর দিকে লক্ষ্য করলে দেখবে স্ট্রিং লেন্থ মাত্র ১০। বুঝতেই পারতেছো এটি মূলত বিটমাস্ক ডিপির একটি প্রব্লেম।  ২) এই প্রব্লেমে আমার দুটি স্টেট নেয়া দরকার।       স্টেট-১ঃ এখন পর্যন্ত স্ট্রিং এর কোন কোন পজিশনের ডিজিট টি ব্যাবহার করেছি।     স্টেট-২ঃ এখন পর্যন্ত বানানো সংখ্যাটি কে d দ্বারা মড করলে মড ভ্যালু কত।  এখানে, মড ভ্যালু ক্যালকুলেট করবো কিভাবে? নিজে নিজে চিন্তা কর।  ৩) আমি যদি সবগুলো ডিজিট ব্যাবহার করে ফেলি তাহলে রিকার্শন থামাতে হবে। যদি মড ভ্যালু ০ হয় তার মানে আমার বানানো সংখ্যাটি d দ্বারা বিভাজ্য তাই ১ রিটার্ন করবো। অন্যথায়, ০ রিটার্ন করবো। এটি হবে Base Case।  ৪) সমস্যা কিন্তু এখনো সমাধান হয় নি! কম্বিনেটরিক্স এর সামান্য একটু কাজ বাকি আছে। আশা করি সেটি তুমি নিজেই পারবে।  বিটমাস্ক ডিপি সম্পর্কে ধারণা থাকলে এখন প্রব্লেমটি নিজে নিজে সলভ করার চেষ্টা কর। ব্যার্থ হলে কোড দেখে নিতে পারো।

 Problem Description  here Problem: এই প্রব্লেমে আমাকে nth Fi Binary Number বের করতে হবে। Fi Binary Number হচ্ছে এমন একটি নাম্বার যা শুধু 0 এবং 1 নিয়ে গঠিত এবং সেই নাম্বারে পাশাপাশি দুটি 1 থাকতে পারবে না। কয়েকটি Fi Binary Number হচ্ছেঃ  1, 10, 100, 101, 1000, 1001, 1010, 10000, 10001, 10010, 10100, 10101 Solution:  ১) ভালো করে লক্ষ্য করলে দেখবে যে Fi Binary Number এ      ১ ডিজিট এর সংখ্যা আছে ১ টি      ২ ডিজিট এর সংখ্যা আছে ১ টি      ৩ ডিজিট এর সংখ্যা আছে ২ টি      ৪ ডিজিট এর সংখ্যা আছে ৩ টি      ৫ ডিজিট এর সংখ্যা আছে ৫ টি তার মানে, আমরা একটি ফিবোনাচি সিরিজ পাচ্ছি!!! ২) এখন, আমি চাইলে এমন একটি ফাংশন লিখতে পারি যাকে আমি n প্যারামিটার হিসেবে দিলে সে আমাকে বলে দিবে nth নাম্বার টি কত ডিজিটের নাম্বার এবং ততো ডিজিটের কত তম নাম্বার এটি। অর্থাৎ, আমি যদি n = 12 দিয়ে ফাংশন কে কল দেই, তাহলে সে আমাকে বলবে যে nth নাম্বার টি ৫ টি ডিজিট নিয়ে গঠিত এবং ৫ডিজিটসমৃদ্ধ নাম্বার এর মধ্যে এটি ৫ম। ৩) এবার কতগুলো Fi Binary Number নিয়ে ঘাটাঘাটি করলে দেখবে যে একটি Fi Binary Number অনেকগুলো Fi Binary Number এর সমন