Light OJ-1027 A Dangerous Maze - Tutorial

-

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. -_-

Comments

Post a Comment

Trending Post

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

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

DP Optimization (Part-1) | DP Series(Episode-15)

-
 এই পর্বে আমরা মূলত ডিপি তে মেমোরি অপ্টিমাইজেশন কিভাবে করে সেটা দেখবো।  প্রব্লেম-১ঃ  এটি সাধারণ একটি ন্যাপস্যাক প্রব্লেম যেখানে তোমাকে n <= 500 টি জিনিস দেয়া থাকবে। ন্যাপস্যাকের সর্বোচ্চ সাইজ 2*10^6, প্রতিটি জিনিসের মূল্য v[i] <= 10^7, প্রতিটি জিনিসের ওজন wt[i] <= 10^7। এমনভাবে ন্যাপস্যাক এ আইটেমগুলো নিতে হবে যাতে সর্বোচ্চ মূল্যের জিনিস নেয়া যায়।  সাধারণ ন্যাপস্যাকের কোডটি দেখতে অনেকটা এরকমঃ  কিন্তু, উপরোল্লিখিত সমস্যার সমাধান না এই সল্যুশন! কারণ তুমি 500*2000000 সাইজের অ্যারে ই ডিক্লেয়ার করতে পারবা না! তার মানে আমাদের মূল সমস্যা হচ্ছে মেমোরি!  উপরের কোডের ১৬ নম্বর লাইনটা ভালো করে দেখো তো। আমি যখন ith to nth আইটেম কনসিডার করে কোন ওয়েট বানাতে চাচ্ছি তখন আমার জানা দরকার (i+1)th to nth আইটেম কনসিডার করে ঐ ওয়েট বানানো যায় সর্বোচ্চ কত লাভে। আমার কিন্তু তখন (i+2)th, (i+3)th,.... এসব সারির ভ্যালুগুলো জানার দরকার পড়ে না!   সবশেষে, আমার জানা দরকার 1st to nth আইটেম কনসিডার করে কোন ওয়েট বানানো যায় সর্বোচ্চ কত লাভে! তাহলে, i যদি জোড় হয় তখন (i+1) হবে ...
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