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

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

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

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

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

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

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

مساله «آرایه قوی»

دنباله a_۱, a_۲, ..., a_n به شما داده شده است. زیردنباله a_L, ..., a_R را از این دنباله در نظر بگیرید. K_s برابر با تعداد بارهایی است که عدد s در این زیر دنباله ظاهر شده است. قدرت عدد s برابر است با K_s.K_s.s. قدرت زیردنباله برابر با مجموع قدرت تمام اعداد طبیعی است (چون تعداد اعداد دنباله محدود است قدرت زیر دنباله نیز محدود است). دنباله a_۱, a_۲, ..., a_n به شما داده می‌شود. شما باید در تعدادی پرسش مقدار L و R را دریافت کنید و قدرت زیردنباله a_L, ..., a_R را چاپ کنید. می‌دانیم تعداد پرسش‌ها و تعداد اعداد دنباله از ۲۰۰،۰۰۰ بیشتر نیست. همچنین هر عضو دنباله بین ۱ تا ۱۰۰۰،۰۰۰ است.

مساله «عکاسی از گاوها»

تعدادی گاو در یک صف با ترتیبی خاص ایستاده اند. هر گاو یک شناسه متمایز با بقیه دارد. عموجان می‌خواهد از آن ها با همین ترتیب ایستادنشان در صف عکس بگیرد. همین که عموجان می‌خواهد عکس را بگیرد زیر مجموعه‌ای از گاو ها از صف خارج می‌شوند و به ترتیبی دلخواه در مکان های مختلف صف وارد می‌شوند. عموجان از ترتیب به هم ریخته آن‌ها عکس می‌گیرد. سپس دوباره آن‌ها را با همان ترتیب اولیه مرتب می‌کند تا دوباره عکس بگیرد. اما باز تا می‌خواهد عکس بگیرد زیر مجموعه‌ای از گاوها از صف خارج می‌شوند و با ترتیبی دلخواه وارد آن می‌شوند. و باز هم عکسی از ترتیب به هم ریخته گرفته می‌شود. عموجان این کار را ۵ بار انجام داده و حالا پنج عکس از صف‌های به هم ریخته گاوها دارد. می‌دانیم هر گاو در حداکثر یکی از عکس‌ها از صف خارج می‌شود. به شما تعداد گاو ها و پنج جایگشت از شناسه های گاو‌ها داده شده است. شما باید ترتیب اصلی گاوها را چاپ کنید. می دانیم تعداد گاو‌ها از ۲۰،۰۰۰ بیشتر نیست و شناسه هر گاو متمایز و بین ۰ تا ۱۰۰۰،۰۰۰۰،۰۰۰ است.