Codeforces Round 262(Problem C)

প্রবলেমঃ

beaver নামের এক বালকের প্রিয় বিষয় informatics। এই বালক তার informatics শিক্ষকের জন্মদিনে শিক্ষককে উপহার দিতে চায়। এই কারণে সে n টি ফুল লাগায়। কয়দিন পর খেয়াল করল যে, ফুলের বেড়ে উঠা বন্ধ হয়ে গিয়েছে। এদিকে জন্মদিনের বাকি দিন।

তাই সে একটা solution এ আসল। সে এক ধরণের বিশেষ পানি দেয়া শুরু করল, যা কিনা একদিনে contiguous ফুলে দেয়া যায়। আর এতে এই w contiguous ফুলের উচ্চতা এক বেড়ে যায়। এভাবে সে m দিন দিতে পারবে। আমাকে সবচেয়ে কম উচ্চতার ফুলটির উচ্চতা as large as possible বানাতে হবে।

যদি ইনপুট এমন হয়ঃ

2 5 1
5 8

উত্তর হবে 9, যেখানে n=2, m=5, w=1। আর {5,8} হল বেড়ে উঠা বন্ধ হয়ে যাওয়ার পর ফুলগুলোর উচ্চতা। আমি একটি করে contiguous ফুলে special পানি দিতে পারব। আমি প্রথম ফুলে চারদিনে চারবার পানি দিব, আর দ্বিতীয় ফুলে পঞ্চমদিন একবার। তাতে মিনিমাম উচ্চতার ফুলের উচ্চতা সর্বোচ্চ হয়। এক্ষেত্রে দু’টি ফুলের উচ্চতাই ৯।

আমি চাইলে প্রথম ফুলেই পাচদিনে পাচবার পানি দিয়ে উচ্চতা ১০ করে বাকিটিকে আট রেখে দিতে পারতাম। কিন্তু তাতে মিনিমাম ফুলের উচ্চতা হয় আট, যা optimal নয়। তাই এভাবে পানি দিব না।

প্রবলেম লিঙ্কঃ C. Present

কিভাবে করব?

আমি answer খুজব বাইনারি সার্চ দিয়ে। বাইনারি সার্চ দিয়ে একটা ভ্যালু নিব, চেক করব, এটা পসিবল answer হতে পারে কিনা। এরপর সে অনুযায়ী lo/hi আপডেট করব।

while(~scanf("%I64d%I64d%I64d",&n,&m,&w))
 {
     mn=2e15;
     sm=cnt=0;
     fg=1;
     fr(i,1,n)
     {
         scanf("%I64d",&a[i]);
         mn=min(mn,a[i]);
     }
     i64 lo=mn,hi=1e15,ans;
     while(lo<=hi)
     {
         mid=(lo+hi)/2;
         if(can(mid,m))
         {
             lo=mid+1;
             ans=mid;
         }
         else
             hi=mid-1;
     }
     printf("%I64d\n",ans);
 }

এখানে fr(i,1,n) দেখে ভয় বা অবাক হওয়ার কিছু নেই… 😛 । এটা আগে ডিফাইন করা আছে, যে পার্টটা এখানে দেখানো হয়নি। ডিফাইন করা পার্টটা মোটামুটি এমনঃ

#define fr(i,a,b) for(i=a;i<=b;i++)

তাই, যখন আমি fr(i,1,n) লিখছি, তখন আসলে 1 থেকে n পর্যন্ত একটি লুপ চালাচ্ছি। এখন বলি, কোডে কি করেছিঃ

কোডে প্রথমে lo আর hi সেট করেছি। এখানে lo হল answer সর্বনিম্ন কত হতে পারে, আর hi হল answer সর্বোচ্চ কত হতে পারে। এখন, answer সর্বনিম্ন হতে পারে যে array টা দেয়া আছে, তার element দের মিনিমাম ভ্যালু। আর answer সর্বোচ্চ হতে পারে (10^9+10^5)। এত ক্যালকুলেশন না করে আমি 10^15 hi ভ্যালু সেট করেছি।

binary search এর মাধ্যমে প্রতিবার mid ভ্যালু নিয়ে can() ফাংশনে যাচ্ছি, আর চেক করছি এটাকে আমার answer বানানো যায় কিনা। যদি বানানো যায়, তাহলে দেখছি, এই answer থেকে বেশি কোন answer পাওয়া যায় কিনা। তাই তখন lo এর ভ্যালু বাড়িয়ে দিয়েছি। এখন দেখি, can() ফাংশনে কি হচ্ছে।

bool can(i64 x,i64 rest)
{
    i64 i;
    fr(i,1,n)
    res[i]=0;

    fr(i,1,n)
    {
        res[i]+=res[i-1];
        i64 need=x-a[i]-res[i];
        if(need>0)
        {
            rest-=need;
            res[i]+=need;
            if(i+w<=n)
            res[i+w]-=need;
        }
        if(rest<0)
            return 0;
    }
    return 1;
}

can() ফাংশনে চেক করা হয়, x কি আমার solution কিনা। যদি x solution হয়, তাহলে আমি আমি এমন একটি array বানাতে পারব, যার minimum element হল x। res[] এর কাজ কি ? এই array টি i ইনডেক্সে কত ভ্যালু যোগ করছি, তা রাখে। আর need হল, x বানাতে আমার কত প্রয়োজন। কোন একটি ফুলে (i তম) পানি দেয়ার প্রয়োজন হওয়ার অর্থ w contiguous ফুলে পানি দেয়া। কিন্তু (w+i তম) ফুলটি পানি পাবে না। তাই তার উচ্চতাও বাড়বে না। এই কারণে ঐ ফুলটির ক্ষেত্রে আমি res[] এর ভ্যালু need পরিমাণ কমিয়ে রেখেছি। যেহেতু res[] cumulative sum রাখে, তাই (i+w)তম ফুলের ক্ষেত্রে res[] ক্যালকুলেশনের সময় এটি 0 হয়ে যায়, যার অর্থ i তম ফুলে পানি দেয়ার affect (i+w)তম ফুলে পড়েনি।

rest যদি কখনো 0 অপেক্ষা ছোট হয়, তার অর্থ কি ? তার অর্থ হল, আমি x কে answer বানাতে হলে m(যেটা can() ফাংশনে rest) থেকে বেশি দিন পানি দিতে হবে। কিন্তু তা সম্ভব নয়, তাই, 0 রিটার্ন করছি। এর অর্থ, আমি x কে আমার answer বানাতে পারব না। আমাকে আরো ছোট value খুজতে হবে।

কারো কোন প্রবলেম থাকলে, খাতা কলমে স্কেচ করে দেখতে পারো। আর যদি এরপরও প্রবলেম থাকলে reply option তো আছেই…… 🙂

2 thoughts on “Codeforces Round 262(Problem C)

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s