سلام!
امیدواریم که از سوال‌ها خوشتان آمده باشد!
متاسفانه پس از انتشار راه حل‌های مسابقات قبلی، شاهد بودیم که تعدادی از افراد کدهای گذاشته شده را برای سوال‌های سخت ارسال می‌کردند و خودشان لزوماً برای آن زحمتی نمی‌کشیدند. از این رو تصمیم گرفتیم که از این به بعد، برای سوال‌های انتهایی مسابقه تنها راه حل تشریحی قرار بدیم و کد نمونه را در بلاگ نگذاریم.
در صورتی که راه‌حل دیگری برای سوال‌ها دارید در بخش نظرات با ما در میان بگذارید!
کد Python 3 از علی‌پاشا منتصری
کد ++C از کیوان رضایی
کد Java از محمد محمودی
کد #C از محمد هادی هادوی
می‌توان شماره‌های روی دایره را از ۰ تا n - 1 در نظر گرفت. در این صورت، حرکت روی ترامپ‌لین‌ها به این صورت می‌شود که از ترامپ‌لین شماره i به ترامپ‌لین شماره 2i \mod n جهش می‌کنیم. این یعنی پس از شروع از ترامپ‌لین i، ترامپ‌لین‌های 2i \mod n، 4i \mod n، 8i \mod n و … را می‌بینیم. پس همه‌ی ترامپ‌لین‌های به شکل 2^ki \mod n که k عددی طبیعی است را می‌بینیم.
حال مسئله به این تبدیل می‌شود که چه تعداد i بین ۰ تا n-1 وجود دارد که ضربدر توانی از ۲، ضریبی از n بشود. پس یعنی این عدد باید به تمام مقسوم‌علیه‌های فرد n بخش‌پذیر باشد. ک.م.م. همه‌ی این مقسوم‌علیه‌های فرد برابر بزرگ‌ترین مقسوم‌علیه فرد n است؛ پس i شروع باید ضریبی از بزرگ‌ترین مقسوم‌علیه فرد n باشد. این بزرگ‌ترین مقسوم‌علیه فرد n را با k نشان می‌دهیم. تعداد این i های شروع برابر است با \frac n k که برابر بزرگ‌ترین توانی از ۲ است که n به آن بخش‌پذیر است. پس کافیست این بزرگ‌ترین توان را خروجی دهیم.
زمان اجرای این راه حل O(\log n) است. (با فرض ثابت بودن زمان اجرای عمل‌گرهای تقسیم و باقی‌مانده)
کد ++C از محمد صانعیان
کد Python 3 از علی شاه علی
کد Java از پویان علی‌پناهی
تعریف می‌کنیم dp_{i, j, k} یعنی پاسخ مسئله با این فرض‌ها:
- تنها i نفر اول از افراد با بزرگ‌ترین درجه وجود دارند.
- طوری می‌خواهیم تغییرات را اعمال کنیم که از بین این i نفر، j نفر انتهایی همگی به آقای بی‌خطر رای دهند.
- حداکثر k تغییر مجاز است.
نکته‌ی سوال این این که اگر j نفر پشت سر هم از افراد با بالاترین درجه به آقای بی‌خطر رای بدهند و نفر j+1 ام نیز به رای دهندگان اضافه شود، در مجموع این درجه و دیگر درجات j + 1 نفر به رای‌دهندگان به آقای بی‌خطر اضافه می‌شود.
می‌توان با نکته‌ی بالا به سادگی مقدار dp_{i, j, k} را بوسیله‌ی مقادیر با i کوچک‌تر بدست آورد؛ برای جزییات آن می‌توانید به کد زیر مراجعه کنید.
زمان اجرای این راه حل O(n^2k) است.
راه حل ++C از مجید گروسی
راه حل Java از پویان علی‌پناهی (این راه حل کمی با راه توضیح داده شده متفاوت است)
تعریف می‌کنیم f(i): حداقل تعداد ضربه برای از بین بردن همه‌ی سوسک‌ها وقتی در ابتدا تنها یک سوسک از نژاد i داریم.
برای مقدار f(i) می‌توان چنین رابطه‌ای نوشت:
f(i) = min(a_i, b_i + \sum_{x \in S(i)} f(x))
که S(i) مجموعه‌ی نژادهاییست که پس از کشتن سوسک با نژاد i با b_i ضربه بوجود می‌آیند.
مشکل محاسبه‌ی این مقدار این‌جاست که در رابطه‌ی بازگشتی آن دور وجود دارد و ترتیب بدست آوردن این مقادیر مشخص نیست. یک نکته‌ی کلیدی برای حل این مشکل این است که مقادیر a_i و b_i همگی اعدادی مثبت هستند. نژادی با کمترین مقدار a_i را در نظر بگیرید؛ برای این نژاد i داریم f(i) = a_i. پس از بدست آوردن مقدار f(x)، می‌توانیم به ازای هر i که x \in S_i، ابتدا x را از S_i حذف کنیم و سپس مقدار f(x) را به b_i اضافه کنیم؛ مانند این که بگوییم اگر سوسک از نژاد i را با b_i کشتیم، باید حتماً مقدار f(x) برای کشتن سوسک از نژاد x خرج کنیم. اگر پس از این حرکت S_i تهی شد، می‌توانیم مقدار a_i را با b_i جایگزین کنیم در صورتی که b_i < a_i.
پس می‌توانیم پروسه‌ی گفته شده را همین‌طور ادامه دهیم؛ نژادی با کمترین مقدار a_i را انتخاب کنیم و مقدار f(i) را مشخص کنیم و تغییرات لازم برای مقادیر مربوطه برای دیگر نژادها را اعمال کنیم و دوباره نژادی با کمترین مقدار a_i را انتخاب کنیم و …
برای پیاده سازی بخش بروزرسانی اعداد و گرفتن کوچکترین عدد، می‌توان از داده ساختارهای مناسب (مانند درخت‌های دودویی خود-متوازن) استفاده کرد که زمان اجرای کل راه حل O((n + \sum r_i) \log n) بشود.
مسئله به ما جدولی از اعداد می‌دهد از ما می‌خواهد مسیری از خانه‌های با اعداد مثبت با بیشترین سود ممکن انتخاب کنیم. سود یک مسیر تعریف می‌شود برابر مجموع ارزش خانه‌های مسیر و طول مسیر. طول مسیر بصورت منهتنی محاسبه می‌شود. عدد خانه‌ی در سطر i و ستون j راh_{i, j} می‌نامیم و ارزش خانه در سطر i و ستون j را c_{i, j}.
برای بدست آوردن بهترین مسیر از برنامه‌نویسی پویا استفاده می‌کنیم. dp_x (که x یکی از خانه‌های جدول است) را تعریف می‌کنیم بیشترین سودی که می‌توانیم با شروع از خانه‌ی x در مسیر مد نظر ببریم. برای مقدار dp_x داریم:
dp_x = c_x + \max_{h_y > h_x} dp_y + dist(x, y)
که dist(x, y) برابر فاصله‌ی بین دو خانه‌ی x و y است. در صورتی که بخواهیم مقادیر dp را این‌چنین بدست آوریم، زمان اجرای برنامه O((n \times m)^2) می‌شود که بسیار بیش‌تر از زمانیست که محدودیت زمانی سوال اجازه بدهد.
برای تسریع بدست آوردن مقادیر dp، از خاصیت فاصله‌ی منهتنی استفاده می‌کنیم. فرض کنید سطرها از پایین به بالا و ستون‌ها از چپ به راست شماره گذاری شده‌اند. مسیر منهتنی بین دو خانه در جدول ۴ حالت دارد: بالا-راست، بالا-چپ، پایین-راست و پایین-چپ. برای هریک از این انواع می‌توان یک رابطه‌ی ریاضی که از روی آن فاصله بدست می‌آید را نوشت:
dist_{UR}((i, j),\ (i', j')=(i' + j') +(-i - j)
dist_{UL}((i, j),\ (i', j')=(i' - j') +(-i + j)
dist_{DR}((i, j),\ (i', j')=(-i' + j')+(i - j)
dist_{DL}((i, j),\ (i', j')=(-i' - j')+(i + j)
طور جذابی در فواصل منهتنی داریم:
dist(a, b) =
\max(distUR(a, b),\ distUL(a, b),\ distDR(a, b),\ distDL(a, b))
هم‌چنین با توجه به روابط ریاضی نوشته شده، هریک از چهار حالت dist از دو بخش (مقدار مبدأ) و (مقدار مقصد) تشکیل شده است که مجزا از هم هستند؛ از این رو یافتن بزرگ‌ترین مقدار آن‌ها کار سختی نیست. برای مثال برای حالت بالا-راست داریم:
\max_{(i, j),\ (i', j')} dist_{UR}((i, j),\ (i', j')) =
\max_{(i, j)} (i + j) + \max_{(i', j')} (-i' - j')
برای تاثیر dp مقصد نیز کافیست در مقدار مقصد، عدد dp آن را نیز جمع کنیم.
پس می‌توانیم برای پر کردن مقدار dp_{i, j}، چهار عدد نگه داریم، هریک برای یک حالت از جهت حرکت، که شامل مقدار مربوط به مبداأهای (i', j') است که h_{i', j'} > h_{i, j}. در این حالت پس از مرتب کردن خانه‌ها به ترتیب مقادیر h، زمان اجرای راه حل O(n \times m).
برای حل این مسئله باید ابتدا درک مناسبی از مسئله پیدا کرد. مسئله پیدا کردن خوشه‌ای از گراف است که مجموع ارزش راس‌هایش بیشینه است. این مسئله در حالت کلی NP-Hard است؛ اما شرایط مسئله اینجا بسیار خاص است. گراف مسئله‌ی ما اجتماع دو خوشه‌ی راس مجزا است که تعدادی یال به آن اضافه شده است. یعنی گراف مکمل گراف ما دو بخشی است!
حال مسئله را در گراف مکمل بررسی می‌کنیم. بدنبال یافتن یک مجموعه مستقل هستیم که مجموع اعداد رئوسش بیشینه باشد. اگر عدد روی همه‌ی رأس‌ها برابر بود، مسئله برابر بزرگ‌ترین مجموعه‌ی مستقل در یک گراف دوبخشی بود که بوسیله‌ی الگوریتم یافتن بزرگ‌ترین تطابق، قابل حل است. حال که روی هر راس عددی طبیعی نوشته شده گرافی جدید می‌سازیم.در این گراف هر راس u از گراف ابتدایی را با یک دسته راس جایگزین می‌کنیم که به تعداد عدد روی راس u راس، در دسته وجود داشته باشد. مجموعه‌ی همسایه‌های هریک از رئوس دسته را برابر اجتماع دسته‌های همسایه‌های راس ابتدایی قرار می‌دهیم. حال مسئله در گراف جدید همان یافتن بزرگ‌ترین مجموعه‌ی مستقل است. می‌توان دید که در این گراف اگر یکی از رئوس از یک دسته در بزرگ‌ترین مجموعه‌ی مستقل ظاهر شود، حتماً کل رئوس آن دسته در این مجموعه موجود هستند. پس پاسخ مسئله‌ی ابتدایی با پاسخ در این گراف برابر است. الگوریتم یافتن بزرگ‌ترین تطابق در گراف دوبخشی هر بار یک مسیر افزایشی پیدا می‌کند و تطابق را یکی افزایش می‌دهد. اکنون که در گراف رئوسی بسیار مشابه وجود دارند، می‌توان تعداد زیادی از این مسیر‌ها را هم‌زمان یافت و در گراف اعمال کرد؛ به این شکل راه حل ما تبدیل به حل مسئله‌ی شار بیشینه می‌شود. به این صورت که دو راس source و sink به گراف ابتدایی اضافه می‌کنیم و از source به هریک از رئوس یک دسته یک یال به وزن عدد آن رأس می‌گذاریم. هم‌چنین از هر رأس از دسته‌ی دیگر به sink یک یال با وزن عددش قرار می‌دهیم. سپس بین هر دو راس از دو دسته‌ی مخالف که در گراف به یکدیگر یال دارند (دقت کنید که این گراف مکمل گراف ورودی است؛ این یعنی در گراف ورودی مسئله‌ی ابتدایی این دو راس به هم یال ندارند.) یک یال به وزن بی‌نهایت قرار می‌دهیم. با یافتن شار بیشینه در این گراف، می‌توانیم بزرگ‌ترین تطابق و در نتیجه بزرگ‌ترین مجموعه‌ی مستقل در گراف باز شده (دسته‌ها) را بدست آورد که از روی آن پاسخ مسئله قابل محاسبه است.
