No Expectations!

প্রত্যাশিত মান (এক্সপেক্টেড ভ্যালু) সম্পর্কে জানতে এই আর্টিকেলটি পড়তে পার ।

সাবটাস্ক 1:
প্রথমে, মগগুলির ধারণক্ষমতার এ্যারেকে নন-ডিক্রিজিং ভাবে সর্ট করি । এখন, আমরা যদি কোনো কাস্টমারকে $i^{th}$ মগ দেই, তাহলে ভবিষ্যতের কাস্টমারদের জন্য কেবলমাত্র $[i + 1, n]$ রেঞ্জের ভ্যালিড মগগুলি ব্যবহার করতে পারব । $1^{st}$ কাস্টমারের জন্য কোনো মগ $i$ বাছাই করার সম্ভাবনা অবশ্যই $\frac{1}{n}$ । এখন, ধরা যাক, জগে বর্তমানে পানি আছে $c$ লিটার এবং আমরা কাস্টমারকে $i^{th}$ মগ দিব । সুতরাং, বর্তমান স্টেট থেকে শেষ স্টেটগুলো পর্যন্ত কাস্টমারকে যতবার সার্ভ করা যাবে, তার প্রত্যাশিত মান হল:

$E(i,c) = 1 + \frac{1}{(r-l+1)} \times (E(l, c-a_i) + E(l+1, c-a_i) + … + E(r, c-a_i))$,

যেখানে $l$ হল সবচেয়ে বামের ইনডেক্স যাতে $a_i < a_l\leq c-a_i$ এবং $r$ হল সবচেয়ে ডানের ইনডেক্স যাতে $a_i < a_r \leq c-a_i$ । $E(i, c)$ ফাইনাল স্টেট হলে $E(i,c) = 1$ ।

উপরের রিলেশন থেকে আমরা সহজেই একটি ডাইনামিক প্রোগ্রামিং সমাধান তৈরি করতে পারি ।
সাবটাস্ক 1 এর সলিউশনঃ https://ideone.com/9eZgDh
কমপ্লেক্সিটিঃ $O(n^2\times c)$

সাবটাস্ক 2:
সাবটাস্ক 2 এর জন্য আমাদের সাবটাস্ক 1 এর আইডিয়া অপটিমাইজ করতে হবে । উপরের রিলেশন থেকে আমরা দেখতে পাচ্ছি যে একটি স্টেট $E(i, c)$ থেকে আমরা শুধুমাত্র $c-a_i$ লিটার পানি নিয়ে পরবর্তী স্টেটগুলোয় যেতে পারি । আমরা যদি $c-a_i$ লিটার পানি নিয়ে যাওয়া পরবর্তী স্টেটগুলোর সংখ্যা এবং প্রত্যাশিত মানগুলির যোগফল জানি, তবে আমরা সহজেই $E(i, c)$ বের করতে পারব । ধরা যাক, $k$ লিটার পানি নিয়ে পরবর্তী স্টেটগুলোতে গেলে $cnt_k$ আমাদের কাঙ্ক্ষিত সংখ্যা এবং $sum_k$ আমাদের কাঙ্ক্ষিত প্রত্যাশিত মানগুলির যোগফল। তাহলে আমরা লিখতে পারি,

$E(i,c) = 1 + \frac{1}{cnt_{c-a_i}} \times sum_{c-a_i}$

$cnt_k$ এবং $sum_k$, $n^{th}$ ইনডেক্স থেকে $1^{st}$ ইনডেক্সে ইটারেট করতে করতে গণনা করা যাবে । আমাদের একই ক্যাপাসিটির মগগুলো একসাথে প্রক্রিয়া করতে হবে যাতে একই ক্যাপাসিটির মগগুলো পরবর্তী স্টেট হিসাবে বিবেচ্য না হয় । আরও ভাল করে বুঝতে সলিউশন দেখ ।

সলিউশন: https://ideone.com/Nog7Jm
কমলেক্সিটি: $O(n\times c)$