راه‌حل‌های مسابقه انتخابی ۲ کدکاپ ۸

سلام دوست کوئرایی!

در این مطلب، به راه‌حل‌های سوالات مسابقه انتخابی ۲ کدکاپ ۸ می‌پردازیم. اگر در این مسابقه شرکت کرده‌ای و سوال یا ابهامی درباره پاسخ سوالات داری، این بلاگ پست برای شماست.

خمیدگی مار

کافی است شماره‌ی سطر و ستونی که سر مار در آن قرار دارد را نگه‌دارید. به این ترتیب می‌توانید با توجه به رشته‌ی ورودی، خانه‌ی بعدی که سر مار در آن قرار دارد را به صورت یکتا مشخص کنید.

به‌طور دقیق‌تر اگر سر مار در خانه‌ی (r, c) از جدول باشد. وضعیت اولیه r = 2 و c = 1 است.

• اگر حرکت بعدی F باشد به خانه‌ی (r, c + 1) می‌رود.
• اگر حرکت بعدی L باشد به خانه‌ی (r - 1, c + 1) می‌رود.
• اگر حرکت بعدی R باشد به خانه‌ی (r + 1, c + 1) می‌رود.

برای بررسی حالت‌های DEATH کافیست بررسی کنید مقدار r برابر ۱ یا ۲ باشد. همچنین همزمان با تغییر مقدارهای (r, c) می‌توانید خانه‌هایی که در سر مار در آن قرار می‌گیرد را به 1 تبدیل کنید و بقیه‌ی خانه‌ها را 0 بگذارید.

به این ترتیب می‌توانید پاسخ مسئله را به درستی بدست آوردید.

درخت بلند

ایده حل این سوال به این شکل است که ابتدا یک درخت رندوم که دنباله درجاتش همان دنباله درجات داده شده باشد می‌سازیم و از یک راس به عنوان ریشه آویزان می‌کنیم.

سپس برای ریشه فرزندی از آن را که بلندترین ارتفاع این زیر درخت مسیری در زیر درخت آن فرزند است را در نظر می‌گیریم.

چون این زیر درخت، درخت است می‌دانیم دارای راسی با درجه ۱ (برگ) است. اگر راس ریشه فعلی شامل فرزند غیربرگ دیگری بود، این فرزند و آن برگ در زیر درخت فرزند دیگر را جابه‌جا می‌کنیم. و این کار را آن‌قدر تکرار می‌کنیم تا راس ریشه فعلی تنها یک فرزند غیر برگ داشته باشد.

حالا به آن فرزند غیر برگ ریشه می‌رویم و همین کار را برای آن زیر درخت که این راس ریشه جدید آن است انجام می‌دهیم و آن قدر این کار را تکرار می‌کنیم تا به راسی برسیم که دیگر فرزند غیر برگی نداشته باشد.

با انجام متناهی بار این عمل می‌بینیم که درخت ما شکل خاصی دارد و آن این است که راس‌هایی که روی بلندترین مسیر درخت یا همان ارتفاع آن (با ریشه نامعلوم) نیستند، همگی برگ هستند.

پس جواب مسئله می‌شود تعداد راس‌هایی که برگ نیستند (راس های داخلی مسیر) + ۲ (راس اول و آخر مسیر که برگ هستند).

قطار یا پیاده

ایده‌ی حل این سوال الگوریتم حریصانه است. ما می‌توانیم اثبات کنیم که در هر ایستگاه قطار باید از بین افراد موجود آن L نفری که مقصدشان دورتر است سوال قطار باشند و باقی افراد پیاده شوند. از بین افراد موجود هم منظور افرادی هست که یا با قطار به این ایستگاه آمده‌اند یا مسیرشان از این ایستگاه شروع می‌شود.

برای پیاده سازی این الگوریتم با مرتبه زمانی مناسب، قطار را با یک multiset مدل سازی می‌کنیم. این multiset در ابتدا خالی هست و ما در ایستگاه ابتدا شماره‌ی ایستگاه‌های مقصد‌ افرادی که می‌خواهند در این ایستگاه مسیر خود را شروع کنند را به multiset اضافه می‌کنیم و افرادی را می‌خواهند در این ایستگاه پیاده شوند را از multiset حذف می‌کنیم. سپس تا وقتی اندازه‌ی multiset بیشتر از L است، کوچک‌ترین عدد آن را حذف می‌کنیم. این عدد نشان دهنده‌ی این است که یک فرد به مقصد خود نرسیده‌است. بنابراین شماره‌ی ایستگاه فعلی را از شماره‌ی ایستگاه مقصد فرد کم می‌کنیم و این عدد را به جواب اضافه می‌کنیم.

برای اثبات درستی الگوریتم، تصور کنید که دو فرد وجود دارند که می‌خواهند از یک ایستگاه به جلو بروند. مثلاً قطار در ایستگاه ۵ است و یکی می‌خواهد به ایستگاه ۸ برود و دیگری به ایستگاه ۱۰. ما اگر بخواهیم حداکثر یکی از آن‌ها را سوار کنیم، کدام را باید سوار کنیم؟
جواب فردیست که می‌خواهد به ۱۰ برود، چراکه اگر فرد ۸ را سوار کنیم و او را در مکانی در مسیر پیاده کنیم که اگر فرد ۱۰ را هم سوار کرده بودیم، می‌توانستیم او را در همان‌جا پیاده کنیم و تفاوتی در مجموع میزان پیاده روی ایجاد نمی‌شد. به طور دقیق‌تر اگر فرد ۸ را در ایستگاه a پیاده کنیم، مجموع پیاده روی این دو نفر (10-5)+(8-a) است و اگر فرد ۱۰ را سوار می‌کردیم این مقدار برابر با (8-5)+(10-a) است که با هم برابر هستند.

میدان روشن

می‌توانیم مسئله را با dp بر روی خانه‌ها حل کنیم. به این صورت که dp[i] را در نظر می‌گیریم حداقل هزینه‌ای که باید داده شود تا خانه اول تا iام روشن شوند و چراغ iام هم روشن باشد. همچنین در ابتدا در نظر می‌گیریم که خانه اول و آخر به یکدیگر متصل نیستند یعنی به جای میدان، تنها یک خیابان مستقیم داشته باشیم.

برای روشن بودن چراغ iام که باید هزینه c[i] پرداخت شود. بعد از آن سه حالت داریم که یا چراغ i-1ام روشن باشد و یا i-2 و یا i-3. پس بین این سه حالت، حالتی را انتخاب می‌کنیم که کمترین هزینه را داشته باشد و از روی آن dp را آپدیت می‌کنیم.

و جواب مسئله برابر می‌شود با مینیمم dp برای این سه حالت.

dp[i] = min(dp[i - 1], dp[i - 2], dp[i - 3]) + c[i]

در نهایت برای بازگشت به مسئله اصلی که در آن خانه‌های اول و آخر به هم متصل بودند با حالت‌بندی روی این که از کدام قسمت اتصال را به هم بزنیم و دوباره به خیابان مستقیم تبدیل کنیم می‌توانیم هزینه مینیمم را بدست آوریم. برای این کار سه حالت شکستن میدان از فاصله بین خانه ۱ام و خانه nام ، خانه ۱ام و خانه ۲ام و همچنین فاصله بین خانه ۲ام و خانه ۳ام را داریم.

حداکثر گچ

اگر تجزیه‌ی n به عوامل اول به صورت

n = {p_1}^{a_1} {p_2}^{a_2} \dots {p_k}^{a_k}

باشد. می‌دانیم جواب مسئله برابر

\frac{(a_1 + a_2 + \dots + a_k)!}{(a_1)!(a_2)! \dots (a_k)!}

است.

حال فرض کنید برای همه‌ عوامل اولی از n که کمتر یا مساوی \sqrt[3]{n} هستند را پیدا کردیم و بر n تقسیم کردیم. مقدار باقی‌مانده در n یکی از سه حالت زیر را دارد. عدد n = p یا n = pq یا n = p^2 که p و q اعدادی اول هستند.

حالت سوم را می‌توان با جذر گرفتن بررسی کرد. چون تنها حالت مربع کامل است. حالت اول را می‌توان با استفاده از روش‌های مختلف مثل «تست اویلر» و… از مرتبه O(log n) بررسی کرد. بنابراین حالت دوم هم قابل شناسایی است، چون تنها حالت باقی‌مانده است.

توجه کنید با بررسی این سه‌حالت می‌توانیم توان‌های تجزیه را تشخیص دهیم ولی لزوماً خود تجزیه را بدست نمی‌آوریم و این کار برای محاسبه‌ی جواب مسئله کافی است.

خروج از سازمان

برای هر راس dp[v][i] را تعریف می‌کنیم. به چند طریق می‌توان از زیردرخت راس v دقیقاً i نفر را خارج کرد به طوری که شرط مسئله برقرار بماند. اگر تعداد راس‌های موجود در زیردرخت راس v را با t(v) نشان دهیم. مقدار i را ۰ تا t(v) محاسبه کنیم کافی است.

برای محاسبه‌ی پاسخ مسئله، یکی یکی کارمندهای v را اضافه می‌کنیم. برای ادغام کردن پاسخ‌های dp[v] با dp[u] که مدیر u برنامه‌نویس v است.

برای این کار مقدار dp[v][i + j] را به اندازه‌ی dp[v][i] \times dp[u][j] افزایش می‌دهیم.

اگر همه‌ی فرزند‌های راس v برابر u_1, u_2, \dots , u_k باشد. زمان محاسبه‌ی dp[v][i] برابر

T(v) = \sum_{1 \leq i \lt j \leq k} t(u_i) t(u_j)

و مرتبه‌ی زمانی کل مسئله برابر \sum T(v) است. این مقدار تقریباً برابر تعداد جفت راس‌های مختلف در درخت است. کافی است برای این تناظر به اولین جد مشترک آن‌ها دقت کنیم که این جفت راس فقط در آن‌جا یکبار شمارش می‌شود. پس با می‌توان با این تناظر نشان دهد این مقدار از O(n^2) است.

جمع‌بندی

در این مطلب تلاش کردیم تا تمامی نکات مربوط به سوالات این بخش از مسابقات را پوشش دهیم. اگر سوال دیگری دارید، حتما آن را در بخش نظرات با ما به اشتراک بگذارید.

باتشکر از «ارشیا سلطانی موخر»، «امین انوری»، «رومینا سحری مقدم» و «علی شفیعی» برای طراحی و تست سوالات کدکاپ ۸ مرحله‌ی انتخابی ۲.