hints.tex

\begin{Hint}{5.3}
প্রথম অভজারভেশন হলো, দুটো মাস $i$ এবং $j$ তে যদি তুমি ২টি অফার চালু করো (যেখানে $i < j$), তাহলে $i$ আর $j$ এর মধ্যে এমন কোন মাস $k$ থাকতে পারবে না যেটাতে তুমি কোন অফার চালু করোনি (অর্থাৎ, $i < k < j$ হতে পারবে না)। সুতরাং যেই মাসগুলোতে তুমি চালু করবা সেগুলো একটা consecutive রেঞ্জ হবে। ধরো তুমি একটা সিকুয়েন্স ঠিক করেছ $s_0, s_1, \ldots, s_{m-1} \, (m \le n)$, যার মানে হলো প্রথম মাসে তুমি $s_{m-1}$-তম অফারটি চালু করবে, দ্বিতীয় মাসে $s_{m-2}$-তম... $m$-তম মাসে $s_0$-তম অফারটি নিয়েছ, তাহলে এই সিকুয়েন্সের কস্ট হবেঃ
\[
  \sum_{i=0}^{m-1} a_{s_i} - b_{s_i} \cdot \min(k_{s_i}, i)
\]
এইরকম কস্ট ফাংশনে এক্সচেঞ্জ আর্গুমেন্ট অ্যাপ্লাই করতে ঝামেলা হবে, কারণ একটা $\min$ চলে এসেছে। সেজন্য আমরা এক কাজ করতে পারি, যেগুলোর জন্য $k_{s_i} < i$ হবে (অর্থাৎ, তুমি যখন গাড়ি নিয়ে পালিয়ে যাবে, তার আগেই এসব অফারের মেয়াদ শেষ হয়ে যাবে), সেগুলো পুরাপুরি আলাদা করে ফেলা। এদেরকে প্রথম টাইপের অফার বলবো এখন থেকে, আর বাকিগুলোকে দ্বিতীয় টাইপের অফার। এখন আরেকটা অভজারভেশন হলো, আমরা যদি প্রথম টাইপের অফার গুলো সব আগেভাগে নিয়ে ফেলি তাহলে আমাদের কোন লস হবে না। আরেকটা ক্রুশাল বিষয় হলো, এখন আমরা ধরে নিতে পারি প্রথম টাইপের অফার গুলা আমাদের মোট যোগফলে $a_i - b_i \cdot k_i$ কন্ট্রিবিউট করবে, আর এই জিনিসটা পুরাপুরি ইন্ডিপেন্ডেন্ট -- এই অফার কোন মাসে নেয়া হচ্ছে তার উপর নির্ভর করে না। কেন? এমন কি হতে পারে না যে এই অফারটিকে যখন চালু করেছিলাম তার পরে $k_i$ মাস পার হওয়ার আগেই তুমি গাড়ি নিয়ে পালিয়েছ? সেরকম হলে তো এই অফার আরও বেশি কন্ট্রিবিউট করতে পারতো! হতে পারে, কিন্তু যেটা খেয়াল করার বিষয় তা হলো, আমাদেরকে তো ম্যাক্সিমাম কস্ট বের করতে বলেছে। এমন যদি হয়, আমরা যেই ফিক্সড কন্ট্রিবিউশন ধরে নিয়েছি, তার কারণে আসল কস্টের চাইতে ডিপিতে কম অ্যাড হচ্ছে, তাহলে সেই সলিউশনটা অপ্টিমাল হবে না! চিন্তা করে দেখো এটা।

\noindent সুতরাং আমরা বলতে পারিঃ
\begin{gather*}
  \max_{s} \left ( \sum_{i=0}^{m-1} a_{s_i} - b_{s_i} \cdot \min(k_{s_i}, i) \right )\\
  = \max_{p \cap q = \emptyset} \left ( \sum_{i \in p} a_i - b_i \cdot k_i + \sum_{i=0}^{|q|-1} a_{q_i} - b_{q_i} \cdot i \right )
\end{gather*}
এখন আমাদের $q$ এর উপাদান গুলা কিভাবে সাজাতে হবে সেটা চিন্তা করতে হবে। এই কস্ট ফাংশনে এক্সচেঞ্জ আর্গুমেন্ট অ্যাপ্লাই করলে দেখবে উপাদান গুলো $b_i$ এর decreasing অর্ডারে সাজালে সবসময় অপ্টিমাল হবে। এরপর খালি একটা ডিপি লেখা বাকি আমাদের। শুরুতে সবকিছুকে $b_i$ দিয়ে বড় থেকে ছোট অর্ডারে সাজানোর পর বাম থেকে ডানে যাবা, একটা উপাদানের জন্য তিনটা অপশানঃ $p$ তে নিবা, $q$ তে নিবা, কোনটাতেই নিবা না। এছাড়াও, $q$ তে ইতোমধ্যে কয়টা নিয়ে ফেলেছ সেটাও স্টেটে রাখতে হবে।
\end{Hint}