مساله «طولانی‌ترین دنباله»

شما باید طول بلند‌ترین دنباله از اعداد حقیقی را پیدا کنید که مجموعه‌ای از شرط‌ها را ارضا می‌کند.

یک آرایه C از اعداد صحیح ناصفر به شما داده می‌شود. هر عضو C یکی از شرط‌ها را تعیین می‌کند.

اگر C_i مثبت بود مجموع هر C_i عضو متوالی از دنباله باید مثبت باشد.

اگر C_i منفی بود مجموع هر -C_i عضو متوالی از دنباله باید منفی باشد.

طول بلندترین دنباله‌ای را حساب کنید که همه‌ی این شرایط را دارد. اگر طول دنباله محدودیتی ندارد طولش را -۱ در نظر بگیرید.

می‌دانیم تعداد اعضای C از ۵۰ بیشتر نیست و هر عضو C بین -۱۰۰۰ و ۱۰۰۰ است و با صفر فرق می کند.

راه حل

فرض کنید دنباله ای به طول k با شرایط مساله یافته باشیم. آنگاه حتما دنباله ای به طول k-۱ با شرایط مساله وجود دارد (عضو آخرش را حذف می‌کنیم). پس اگر بتوان برای هر x تشخیص داد که آیا دنباله‌ای به طول x با شرایط مساله یافت می‌شود و همچنین کران بالایی برای جواب پیدا کرد می‌توان با Binary Search بیشترین مقدار ممکن x را که چنین دنباله‌ای وجود داشته باشد به دست آورد.

یافتن کران بالا برای جواب
اگر تمام اعداد آرایه C مثبت باشند یا همه منفی، طول دنباله جواب محدودیتی ندارد. در غیر این صورت فرض می‌کنیم در آرایه‌ی C عدد مثبت n و عدد منفی -m را داشته باشیم. واضح است که طول دنباله جواب از nm کمتر است. زیرا اگر دنباله را به دسته‌های nتایی متوالی افراز کنیم مجموع کل اعداد مثبت می‌شود (چون مجموع هر دسته مثبت است) و اگر دنباله را به دسته‌های mتایی متوالی افراز کنیم مجموع کل اعداد منفی می‌شود و به تناقض می‌رسیم. حال می‌خواهیم ثابت کنیم که طول دنباله جواب از n+m-۱ کمتر است. ایده اثبات را با یک مثال نشان می‌دهم. فرض کنید n = ۴ و m = ۳. حال جدول زیر را درنظر بگیرید.

a۱	a۲	a۳	a۴
a۲	a۳	a۴	a۵
a۳	a۴	a۵	a۶

مجموع اعداد هر سطر مثبت است و نتیجه می‌گیریم مجموع اعداد کل جدول مثبت است. همچنین مجموع اعداد هر ستون منفی است که نتیجه می‌دهد مجموع اعداد جدول منفی است. پس به تناقض می‌رسیم. همین روش اثبات با می‌توان برای m و n های دیگر به کار گرفت. حال با توجه به محدودیت‌های ورودی می‌دانیم طول دنباله جواب اگر بی‌نهایت نباشد از ۱۹۹۸ بیشتر نیست.

آیا دنباله ای به طول k با شرایط مساله وجود دارد؟

شرط‌هایی که داریم همگی روی علامت حاصل جمع تعدادی عضو متوالی است. برای مثال داریم a_i+a_i+۱+...+a_j > ۰. حال دنباله s را بر روی a تعریف می‌کنیم. به‌طوری که s_۰ = ۰ و s_i = s_i-۱ + a_i. به عبارتی دیگر s_i برابر با مجموع i عضو اول a است. حال به جای a_i+a_i+۱+...+a_j از معادلش یعنی s_j-s_i-۱ استفاده می‌کنیم. این‌گونه هر شرط تبدیل به مقایسه دو مقدار از s می‌شود. برای مثال در شرط a_i+a_i+۱+...+a_j > ۰ نتیجه می‌گیریم s_j > s_i-۱.

هر s_i را راسی از گراف و هر شرط را یالی از عدد کوچکتر به بزرگتر در نظر می‌گیریم. اگر در این گراف جهت‌دار دور وجود داشته‌ باشد به تناقض می‌رسیم، یعنی چنین دنباله ای به طول k وجود ندارد. در غیر این صورت چون گراف دور ندارد یک  DAG (گراف جهت دار بدون دور) است. با مرتب سازی توپولوژیکی ترتیبی از رئوس به دست می‌آوریم. به راس ها طبق همین ترتیب اعداد ۰ تا k را نسبت می‌دهیم. این مقدار s همه شرط ها را ارضا می‌کند. در نهایت می‌توان دنباله a را از روی s به دست آورد.

پس نتیجه می‌گیریم اگر گراف دور نداشته باشد دنباله‌ای به طول k وجود دارد.

محاسبه بیشترین مقدار ممکن برای k

تابع f(k) را در نظر بگیرید. این تابع ۱ است اگر دنباله ای به طول k با شرایط مساله وجود داشته باشد، در غیر این صورت صفر است. می‌دانیم اگر f(x) = ۱ آنگاه f(x-۱) = ۱. پس تابع f نزولی است و می‌توان با Binary Search بیشترین مقدار k را بین ۱ تا ۱۹۹۸ پیدا کرد که f(k) = ۱.

لینک سوال اصلی