Magic In Grid

-

এই পর্বে আমরা খুবই ইন্টারেস্টিং একটি বিষয় নিয়ে আলোচনা করবো। 


মনে করো, তোমাকে একটি  n * m সাইজের গ্রীড দেয়া আছে। গ্রীডের প্রতিটি সেল এর ভ্যালু,

 grid[i][j] = i+j

তাহলে, একটি ৩ * ৩ সাইজের গ্রীড দেখতে যেমন হবেঃ 


একটি মজার বিষয় লক্ষ্য করেছো কী? কোন একটি সেলের ভ্যালু যদি জোড় হয় তবে তার এডজাসেন্ট সেলগুলোর ভ্যালু বিজোড়। আর কোন সেলের ভ্যালু যদি বিজোড় হয় তবে তার এডজাসেন্ট সেলের ভ্যালু জোড়। এখানে দুটি সেল তখনই এডজাসেন্ট বিবেচ্য হবে যখন তারা একটি সাইড শেয়ার করে। 

গ্রীডের এই প্রোপার্টি টা খুবই সিম্পল। কিন্তু, আমরা অনেকেই হয়তো খেয়াল করি নি এর আগে। আর এটি কতোটা গুরুত্বপূর্ণ প্রোপার্টি তা এই প্রব্লেম সলভ করতে গিয়ে অনুধাবন করেছি 😛


হ্যাপি কোডিং 😊

Comments

Post a Comment

Trending Post

STL পরিচিতি । পর্ব - ০১

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

Knapsack-3 | DP Series(Episode-6)

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

Shortest distance between two point in a grid when you can move all 8 sides from a position

-
একটি 2D গ্রিডে এক পজিশন থেকে অন্য পজিশনের ক্ষুদ্রতম দূরত্ব বের করতে হবে যখন বর্তমান পজিশন থেকে সম্ভাব্য সকল দিকে(৮ দিকে) মুভ দেয়া যায়। এমন প্রব্লেম দেখলে অনেকেই এক দেখাতে সল্যুশন বলে দিবে যে একটা 2D BFS চালিয়ে বের করে নিলাম সিম্পল। কিন্তু এই প্রব্লেম টি যখন অন্য কোন প্রব্লেম এর সাবটাস্ক হিসেবে আসবে তখন MLE অথবা TLE খাওয়ার সম্ভাবনা প্রবল। এক্ষেত্রে এই প্রব্লেম টি O(1) কমপ্লেক্সিটি তে সলভ করা সম্ভব। আর সেটি হলো P1 (x1,y1)  থেকে p2(x2,y2) বিন্ধুর ক্ষুদ্রতম দূরত্ব হচ্ছে distance = max( abs(x1-x2) , abs(y1-y2) )
Read more