سلام دوست کوئرایی!
در این مطلب، به راه‌حل‌های سوالات مسابقه انتخابی ۴ کدکاپ ۸ می‌پردازیم. اگر در این مسابقه شرکت کرده‌ای و سوال یا ابهامی درباره پاسخ سوالات داری، این بلاگ پست برای شماست.
از آن‌جایی که داده‌ها درست هستند. همیشه برنده‌ی بازی تیمی است که آخرین امتیاز را کسب کرده باشد. پس کافی است از روی آخرین کاراکتر رشته‌ها، برنده را مشخص کنیم.
اگر چند جمله‌ی اول دنباله را بنویسیم، متوجه این الگو می‌شویم که بعد از جمله‌ی اول، یک تناوب ۴ تایی دارد.
همواره برش کیک موازی محور yz است. پس در واقع پاسخ ما یک افراز برای بازه‌ی [0, a] از محور xها را تشکیل می‌دهد. اگر برای هر واحد صحیح مثل [i, i+1] که 0 \leq i \leq a - 1 مجموع حجم شکلات‌هایی که در این بازه قرار می‌گیرند را حساب کنیم، مسئله به یک بعد کاهش پیدا می‌کند. حجم شکلات هر شخص را می‌توان از قبل مشخص کرد. حال کافی است از چپ به راست حرکت کنیم و سهم هر شخص را مشخص کنیم.
نقشه را به این صورت بسازید. بین هر دو شهر یک جاده قرار دهید به جز جفت شهرهایی که باهم در یک مثلث نیامده‌اند. این نقشه k شرط مربوط به مثلث نداشتن را دارد. (چون بین آن‌ها یال نیست.) اما کافی است بررسی کنیم آیا بین m جفت اول مثلث هست یا نه. اگر برای همه این جفت‌ها حداقل یک مثلث وجود داشت، پاسخ مسئله بله است. اما اگر وجود نداشت هیچ گرافی پیدا نمی‌شود که همه‌ی این شرط‌ها را برآورده کند. برای بررسی کردن وجود مثلث بین دو راس می‌توانیم سطرهای ماتریس مجاورت گراف متناظر را در bitset ذخیره کنیم و سپس با تقریباً \frac{n}{64} عملیات تعداد مثلث‌ها را بشماریم.
می‌توانیم روی مقدار k جست‌وجوی دودویی انجام بدهیم. به این ترتیب کافی است چک کنیم آیا می‌توانیم دنباله‌ی مطلوبی با حداکثر k تغییر بسازیم یا خیر. برای این کار برای هر i سعی می‌کنیم دنباله‌ی h_1, h_2, \dots, h_i را صعودی کنیم به طوری که هر عدد حداکثر k واحد تغییر کند. شدنی بودن این کار را می‌توانیم با استفاده از برنامه‌نویسی پویا و حریصانه انجام دهیم.
سپس همین‌کار را برای دنباله‌ی h_{i+1}, \dots, h_n انجام می‌دهیم ولی این بار سعی می‌کنیم دنباله را نزولی کنیم. با استفاده از پاسخ‌ها برای این دو دنباله با پیمایش کردن برای مقدار میانی کوه می‌توانیم شدنی بودن این راه را بررسی کنیم.
از روش برنامه نویسی پویا استفاده می‌کنیم. ابتدا درخت را از راس ۱ ریشه دار می‌کنیم. سپس برای هر راس پیدا می‌کنیم که حداکثر چند چنگک به طول x می‌توان از زیردرخت این راس کند. همچنین به جز این محاسبه می‌کنیم به جز کندن این مقدار چنگک، حداکثر چه بخشی از یک چنکگ را کند که راس بالای زیردرخت متصل باشد و قابل استفاده برای راس‌های بالاتر باشد. این مقدار دو حالت دارد، یا یک مسیر تا ریشه هست مثلا به طول k و یا به شکل یک چنگک است که یکی از سه پایه‌ی آن کوتاه تر است و به جای x مثلا طول k' را دارد.
برای محاسبه‌ی این مقدار برای هر راس، ابتدا این مقادیر را برای فرزندان آن راس پیدا می‌کنیم. سپس برای این که بیشترین تعداد چنگک را با استفاده از فرزندان یک راس بسازیم ابتدا باید فرزندان را براساس تعداد یال‌ای که از چنگک آماده کرده‌اند مرتب کنیم. پس از مرتب کردن فرزندان باید به شکل حریصانه از فرزندی که کمترین تعداد یال از یک چنگک را آماده کرده است شروع کنیم و آن را با راسی جفت کنیم که با هم تشکیل یک چنگک می‌دهند.
توجه کنید که اگر راس سه فرزند داشته باشد که هر کدام یک مسیر به طول x دارند، می‌توان با متصل کردن این سه فرزند یک چنگک ساخت.
جمع‌بندی
در این مطلب تلاش کردیم تا تمامی نکات مربوط به سوالات این بخش از مسابقات را پوشش دهیم. اگر سوال دیگری دارید، حتما آن را در بخش نظرات با ما به اشتراک بگذارید.
باتشکر از «ارشیا سلطانی موخر»، «امین انوری»، «رومینا سحری مقدم»، «مهلا انتظاری» و «علی شفیعی» برای طراحی و تست سوالات کدکاپ ۸ مرحله‌ی انتخابی ۴.
