سلام دوست کوئرایی!
در این مطلب، به راه‌حل‌های سوالات مسابقه انتخابی ۶ کدکاپ ۸ می‌پردازیم. اگر در این مسابقه شرکت کرده‌ای و سوال یا ابهامی درباره پاسخ سوالات داری، این بلاگ پست برای شماست.
در این مطلب تلاش کردیم تا تمامی نکات مربوط به سوالات این بخش از مسابقات را پوشش دهیم. اگر سوال دیگری دارید، حتما آن را در بخش نظرات با ما به اشتراک بگذارید.
همانطور که از روی شکل مشخص است، عدد مقابل ۱، ۶ و عدد مقابل ۲، ۵ و عدد مقابل ۳، ۴ است. پس با قرار دادن حداکثر ۶ شرط می‌توانیم خروجی مورد نظر را چاپ کنیم.
همچنین می‌توانیم یک لیست به طول ۶ تعریف کنیم و عدد iام این لیست برابر عدد مقابل i باشد، سپس بعد از دریافت n عدد nام این لیست را چاپ کنیم.
چالش. آیا بدون استفاده از شرط (if) یا لیست (array) می‌توانستیم سوال را حل کنیم؟
ابتدا یک عدد گذاری ارائه می‌دهیم که با آن می‌توانیم همه‌ی nهای کمتر یا مساوی ۳۱ را نشان دهیم.
0, 1, 2, 4, 5, 6
\\
1, 2, 3, 7, 8, 9
این عدد گذاری همه‌ی ارقام ۱ تا ۹ را دارد. پس برای نمایش آن‌ها مشکلی نیست.
برای نمایش ۱۰ تا ۱۲ و ۱۴ تا ۱۶ رقم دهگان را از تاس دوم و رقم یکان را از تاس اول بر می‌داریم. برای نمایش ۱۳ و ۱۷ تا ۱۹ رقم دهگان را از تاس اول و رقم یکان را از تاس دوم بر می‌داریم. بنابراین برای نمایش اعداد ۱۰ تا ۱۹ مشکلی نیست.
برای نمایش ۲۰ تا ۲۲ و ۲۴ تا ۲۶ رقم دهگان را از تاس دوم و رقم یکان را از تاس اول بر می‌داریم. برای نمایش ۲۳ و ۲۷ تا ۲۸ رقم دهگان را از تاس اول و رقم یکان را از تاس دوم بر می‌داریم. بنابراین برای نمایش اعداد ۲۰ تا ۲۹ مشکلی نیست.
برای نمایش ۳۰ تا ۳۲ رقم دهگان را از تاس دوم و رقم یکان را از تاس اول بر می‌داریم.
حال می‌خواهیم ثابت کنیم نمی‌توان روشی ارائه داد که اعداد ۱ تا ۳۳ را نمایش دهد. به برهان خلف فرض کنید چنین عدد گذاری موجود باشد. در این صورت برای نمایش اعداد ۳۳، ۲۲، ۱۱ باید روی هر دو تاس ارقام ۱، ۲ و ۳ ظاهر شده باشد. بنابراین در مجموع روی این دو تاس ۶ جایگاه خالی می‌ماند که باید ارقام ۰، ۴، ۵، ۶، ۷، ۸ و ۹ را روی آن‌ها قرار داد تا هر رقم حداقل یکبار ظاهر شود ولی تعداد این ارقام ۷تا است و این کار شدنی نیست.
بنابراین چنین عدد گذاری وجود دارد اگر و تنها اگر n \leq 32 و عدد گذاری بالا برای همه‌ی $n$های گفته شده کارآمد است.
چالش. اگر مسئله به k تاس و نمایش اعداد حداکثر k رقمی تغییر کند، پاسخ چیست؟
همانطور که از شکل‌های نمونه قابل مشاهده است. نقطه‌های دستگیری را به دو نیمه‌ی سمت راست و چپ تقسیم می‌کنیم و تعداد آن‌ها را می‌شماریم.
نقاط سمت راست. اگر دزد در نقطه‌ی (0, d) باشد، d - 1 نقطه بالاتر و پایین‌تر آن می‌تواند محل دستگیری باشد. یعنی یک ستون شامل 2d - 3 نقطه داریم و ستون‌های سمت راست هر کدام یک نقطه از بالا و پایین آن‌ها کم میشود، پس ستون بعدی 2d - 5 و به همین ترتیب ستون iام 2d - 1 - 2i نقطه دستگیری دارد. تعداد آن‌ها برابر است با:
\sum_{i = 1}^{d - 1} (2d-1-2i) =
\\
(2d - 1)(d - 1) - 2 \sum_{i = 1}^{d-1}i =
\\
(2d - 1)(d - 1) - 2 \times \frac{d(d - 1)}{2} =
\\
(2d - 1)(d-1) - d(d - 1) =
\\
(2d - 1 - d)(d - 1) = (d - 1)^2
برای نقاط سمت چپ. اگر ستون سمت چپ را نگاه کنیم، مشابه قبل 2d - 5 نقطه در آن ستون وجود دارد، امام در این نیمه از تعداد ستون‌ها ۶ تا ۶ تا کم میشود پس تعداد نقاط برابر است با:
\sum_{i = 1}^{\lfloor\frac{2d + 1}{6}\rfloor} (2d + 1 - 6i) =
\\
\lfloor\frac{2d + 1}{6}\rfloor (2d + 1) - 6 \times \sum_{i=1}^{\lfloor\frac{2d + 1}{6}\rfloor}i =
\\
\lfloor\frac{2d + 1}{6}\rfloor (2d + 1) - 3 \times \lfloor\frac{2d + 1}{6}\rfloor \times (\lfloor\frac{2d + 1}{6}\rfloor + 1) =
\\
\lfloor\frac{2d + 1}{6}\rfloor (2d - 2 - 3 \times \lfloor\frac{2d + 1}{6}\rfloor)حال از جمع کردن این دو عدد به پاسخ مسئله می‌رسیم. توجه کنید این روابط برای d \geq 2 کار می‌کند و برای d = 1 باید جداگانه محاسبه کنیم.
چالش. اگر حرکت دزد و پلیس پیوسته بود و سرعت پلیس ثابت و برابر ۲ و سرعت دزد ثابت و برابر ۱ بود، آنگاه مساحت نقاطی که دزد در آن دستگیر میشود چقدر است؟
مسئله در واقع این است که یک درخت (نقشه استان‌ها) داریم، می‌خواهیم روی هر راس آن یک عدد طبیعی (تعداد سکه‌ها) بنویسیم به طوری که هیچ دو راس مجاوری عدد یکسانی نداشته باشند.
این درخت را از راس ۱ آویزان (ریشه‌دار) می‌کنیم. برای هر راس مثل v، مقدار dp[v][i] برابر کمترین تعداد سکه لازم برای زیردرخت v به طوری که روی راس v دقیقاً i سکه قرار بگیرد چقدر است.
به راحتی می‌توانیم dp[v][i] را از روی فرزندان راس v برزورسانی کنیم. کافی است برای هر راس کمینه dp[v][i] و کمینه‌ی دوم را نگه‌داریم و سپس از روی این دو مقدار رنگ روی فرزندان را مشخص کنیم.
به این ترتیب اگر در جواب بهینه حداکثر از c رنگ استفاده شده باشد، پاسخ این مسئله از مرتبه‌ی زمانی O(nc) خواهد بود.
در یک رنگ آمیزی بهینه، اگر برای یک راس رنگ c را قرار دهیم باید همه‌ی رنگ‌های ۱ تا c - 1 در راس‌های مجاور آن آمده باشند. از آن‌جایی که درخت دور ندارد می‌توانیم نتیجه بگیریم همین شرط برای همان راس‌های مجاور هم باید برقرار باشد.
پس اگر N_c برابر کمترین تعداد راس لازم برای اینکه مجبور باشیم روی ریشه عدد c قرار دهیم، آنگاه داریم:
N_c \geq N_{c - 1} + N_{c - 2} + \dots + N_{1} + 1بنابراین c \leq \log n است. بنابراین راه‌حل ارائه شده از مرتبه‌ی O(n.\log n) است.
چالش. آیا می‌توان یک راه‌حل از مرتبه‌ی O(n) برای حل این مسئله ارائه داد؟
ابتدا همه‌ی زیربازه‌ها را روی آرایه داده شده می‌نشنایم و به ترتیب از ۱ به n حرکت می‌کنیم. در هر مرحله به همه‌ی سوالاتی که روی l آن‌ها رسیدیم پاسخ می‌دهیم و بعد از رد شدن از یک عدد در آرایه آن را حذف می‌کنیم. در واقع با این کار می‌توانیم فرض کنیم همه‌ی سوالات به‌جای یک زیربازه درباره‌ی پیشوندی از آرایه $a$ سوال می‌پرسند.
امتیاز عدد k به بازه‌هایی می‌رسد که r آن‌ها در یک بازه‌ی بین cl_kامین تکرار و cr_kامین تکرار عدد k آمده باشد. پس ابتدا برای همه‌ی اعداد ۱ تا m در یک آرایه خالی تمام بازه‌هایی که باعث خوشحالی آن‌ها می‌شوند را زیاد می‌کنیم. حال برای جواب دادن یک سوال، کافی است به عدد rام از آرایه‌ی جدید ساخته شده نگاه کنیم.
توجه کنید برای حذف کردن یک عدد، تعداد آن‌ها یک واحد کم میشود، پس خوشحالی بازه‌ی فعلی باید یک واحد کاهش پیدا کند و خوشحالی بازه‌ی بعدی مربوط به آن عدد یک واحد افزایش یابد. اگر برای هر عدد مثل k، مقدار next_k را از قبل پیش پردازش کنیم این محاسبات از O(1) خواهد بود.
باتوجه به این نیازمندی‌ها می‌توانیم از Fenwick Tree یا Segment Tree استفاده کنیم تا این بازه‌ها را کم و زیاد کنیم یا مقدار یک عدد را بپرسیم.
در کل این مسئله از مرتبه زمانی O(n + m \log n + q \log n) حل شد.
در ابتدا نقاطی را که یا سر یک سیبل یا ته یک سیبل هستند را بر اساس زاویه‌ی آن‌ها به سارا مرتب می‌کنیم. با این کار هر سیبل تبدیل به یک بازه روی دایره‌ی زاویه‌ها میشود که عباس باید به آن شلیک کند. برای پیدا کردن حداقل تعداد شلیک مورد نیاز به روش تقریبا حریصانه عمل می‌کنیم.
توجه کنید که اگر ما بدانیم که مثلا باید در جهت x شلیک کنیم، شلیک بعدی (در جهت ساعت گرد) خوب است در دور ترین جایی باشد (در جهت ساعت گرد) که ممکن است. یعنی از بین تمام بازه‌هایی که با شلیک به x سوراخ نمی‌شوند آن بازه‌ای که انتهایش دورتر است را باید انتخاب کنیم و به سر دورتر آن شلیک کنیم. بنابراین برای هر نقطه مثل x میدانیم اگر به این نقطه شلیک کنیم، شلیک بعدی کجا خواهد بود. این مقدار را برای تمامی نقاط پیدا می‌کنیم. آن را next^0_x بنامید. حال next^i_x را نقطه‌ای تعریف می‌کنیم که بعد از 2^i شلیک اگر به نقطه‌ی x شلیک کرده باشیم، به آن می‌رسیم. با محاسبه‌ی next^i_x برای تمام نقاط و i های بین صفر تا ۲۰ می‌توانیم به سرعت برای هر نقطه محاسبه کنیم که اگر از این نقطه شروع به شلیک کنیم برای سوراخ کردن تمام بازه‌ها به چند شلیک نیاز داریم.
باتشکر از «ارشیا سلطانی موخر»، «امین انوری»، «رومینا سحری مقدم»، «مهلا انتظاری» و «علی شفیعی» برای طراحی و تست سوالات کدکاپ ۸ مرحله‌ی انتخابی ۶.
