سلام؛
مسابقه کدکاپ ۸ مرحله‌ی انتخابی ۱ با تلاش‌های «ارشیا سلطانی موخر»، «امین انوری»، «رومینا سحری مقدم»، «مهلا انتظاری» و «فیروزه ابریشمی» طراحی و برگزار شد.
وبینار حل سوال این مسابقه را می‌توانید از آپارات مشاهده کنید.
این مکعب مستطیل را در نظر بگیرید. می‌دانیم اضلاع این مکعب موازی محورهای مختصات هستند. هر کدام از محورهای مختصات را که در نظر بگیرید راس‌های این مستطیل دو عدد مختلف در این محور اتخاذ کرده‌اند. و دو وجه روبه‌رو هم وجود دارند که هر کدام از آن‌ها در این محور عدد یکسانی دارند.
پس با توجه به این موضوع هر کدام از محور های مختصات دقیقاً ۴ راس با عدد یکسان در این محور و ۴ راس دیگر با یک عدد یکسان دیگر در این محور دارند.
با توجه به اینکه مختصات ۷ راس مختلف مکعب را داریم و فقط یکی از راس‌های آن باقی مانده است پس در هر کدام از محور های مختصات ۴ عدد یکسان و ۳ عدد یکسان دیگر وجود دارد. و در این محور مختصات راس گمشده برابر عددی است که سه بار در بقییه راس های تکرار شده است.
پس برای حل این مساله کافی است برای هر کدام از محورهای مختصات عددی را بیابیم که ۳ بار تکرار شده است.
یک قطر در جدول را در نظر بگیرید. فرض کنید در این قطر بیشتر از ۲ فیل از هر کدام از نوع ها داشته باشیم. می‌دانیم اگر بیش از ۲ فیل داشته باشیم حداقل ۲ فیل وجود دارند که از یک نوع هستند. با توجه به اینکه اگر در یک قطر دو فیل با نوع یکسان بگذاریم یکی از آن‌ها دیگری را تهدید می‌کند.
یک روش برای قراردادن این مقدار فیل در جدول این هستش که در فقط در سطرها و ستون‌های اول و آخر جدول قرار دهیم. در سطر اول و ستون اول فیل‌های نوع A و در بقیه نوع B
یکی از اشتباهات متداول در حل این سوال، توجه نکردن به جدول‌های با یک سطر یا یک ستون بود.
در این سوال اگر n کیک و k میهمان داشته باشیم و بخواهیم به هر نفر سهم برابری از کیک‌ها برسد یعنی به هر نفر n/k می رسد .همچنین می‌دانیم اگر در ابتدا یک کیک به مساحت ۱ واحد را به دو قسمت تقسیم کنیم هر کدام مساحت 1/2 دارند و از تقسیم این قطعه کیک‌ها نیز به مساحت 1/4 می‌رسیم و الی آخر . پس سهم هر نفر مجموعی از قطعه کیک‌هایی است به مساحت 1/2 , 1/4 , 1/8 , 1/16 , ... . پس اگر صورت و مخرج کسر n/k را ساده کنیم و به کسر a/b برسیم , باید مخرج کسر عامل اولی جز 2 نداشته باشد . همچنین برای یافتن حداقل تعداد برش های لازم قطعه کیکی را پیدا میکنیم که بیشترین تعداد برش لازم را داشته یعنی مخرج آن بزرگترین مقدار ممکن است که می شود log(b) .
راه‌حل سوال «مشق شب»
این سوال یک راه حل ترکیبیاتی با اردر O(n^3) که به یک یک راه حل با Dynamic programming از مرتبه O(n^2) دارد .
راه اول : O(n^3) ابتدا یک آرایه C تشکیل می‌دهیم که C_i,_j یعنی انتخاب j از i . سپس به ازای تمام اندیس‌های i در آرایه و حالت‌بندی روی تمام حالات k (طول زیرمجموعه) و j (جایگاه عنصر iام در زیرمجموعه‌ای k عضوی jامین عنصر باشد) تعداد حالت‌ها را محاسبه کرده و جمع می‌زنیم .
راه دوم : O(n^2) بعد از محاسبه آرایه C مطابق راه قبل ، به ازای تمام اندیس‌های i و اندازه زیرمجموعه k تعداد حالت هایی که عنصر iام در نیمه اول زیرمجموعه باشد را محاسبه میکنیم . این یعنی حالتی که عنصر i دقیقاً در وسط زیرمجموعه به اندازه k باشد و یا حالاتی که هر یک از عناصر سمت راست i عنصر وسطی زیرمجموعه‌ای به اندازه k باشند و در سمت چپ آن‌ها نیز عنصر iام انتخاب شده باشد. که برای این کار می‌توانیم در آرایه dp مجموع تعداد این حالات برای هر k تا هر عنصر j از سمت راست آرایه تا آنجا را داشته باشیم. در نهایت هر عنصر به این تعداد بار در بخش منفی‌ها و به تعداد مکمل آن یعنی 2^{n-1} بار در سمت مثبت ها آمده است.
راه‌حل سوال «انقلاب»
در این سوال ابتدا باید بدانیم که شرط در خطر تجزیه بودن این است که یک سمت یک یال برشی کاملا در دست شورشیان باشد. این معادل این است که اگر درختی که در آن یال‌های برشی گراف اولیه، یال‌های درخت هستند و مولفه‌های دو همبند گراف، راس های درخت را بکشیم، برگ های درخت نباید کاملا در دست شورشیان باشد. بنابراین درخت را میسازیم و تعداد راس‌های گراف که متناظر برگ‌های درخت هستند را میشماریم. فرض کنید یک برگ x_1 تا راس دارد و برگی دیگر x_2 تا و همین‌طور تا x_k. برای این که کشور در معرض تجزیه نباشد، هیچ کدام از این برگ‌ها نباید تماما به شورشی‌ها تعلق داشته باشد. پس برگ i$م 2^{x_i}-1 حالت دارد. که یعنی تمامی برگ‌ها روی هم (2^{x_1}-1).(2^{x_2}-1).(2^{x_3}-1)...(2^{x_k}-1) حالت دارند. باقی راس‌ها هم فرض کنید m تا هستند. آن‌ها می‌توانند هر حالتی داشته باشند. پس جواب برابر با (2^{x_1}-1).(2^{x_2}-1).(2^{x_3}-1)...(2^{x_k}-1).2^m است.
در این سوال راه حل گریدی برای هر k خاص کار می‌کند. به این صورت که از پل اول شروع میکنیم به گذاشتن تخته‌ها و سعی میکنیم اول هر تخته را جایی بگذاریم که تخته‌ی قبل تمام شده است. در صورتی که با این کار زیر تخته کمتر از k پایه‌ی پل بود، مجبور هستیم شروع تخته را عقب تر ببریم. ولی توجه کنید که در این حالت شروع تخته دقیقاً روی یکی از پایه های بتنی خواهد بود. پس تمامی پایه‌های بتنی را به سمت عقب برسی کرده و اولین پایه‌ی بتنی که بتوان روی آن تخته را گذاشت را انتخاب کرده و تخته را از آن جا می‌گذاریم.
روش گفته شده با وجود درست بودن، کند است. برای افزایش سرعت باید به نکات زیر توجه کنیم. اول این که مجموع تعداد تخته‌های جوبی به ازای تمامی kها حداکثر \mathcal{O}(n\log(n)) است. این به این دلیل است که برای یک k در صورتی که تخته گذاری ممکن باید حداکثر \frac{2n}{k} تخته نیاز است. چرا که هر پایه‌ی پل حداکثر زیر ۲ پایه‌ی بتنی خواهد بود. همچنین هر تخته در زیر خود حداقل k پایه دارد.
بنابراین اگر بتوانیم تخته‌ها را سریع بگذاریم کد سریع خواهد بود. بنابراین هنگامی که می‌خواهیم برسی کنیم و ببینیم زیر یک تخته چند پایه است با اردر \mathcal{O}(\log(n)) این کار را با استفاده از دو باینری سرچ روی آرایه‌ی از پیش مرتب شده‌ی جایگاه ستون‌ها انجام می‌دهیم. برای این که به سرعت بدانیم که تخته‌ی چوبی باید تا کدام پایه عقب بیاید، ابتدا برای هر پایه محاسبه میکنیم که اگر یک تخته چوب بر از این پایه شروع کنیم در زیرش چند پایه‌ی بتنی قرار خواهد گرفت. با محاسبه‌ی این اعداد، برای این که مشخص شود چه مقداری باید به عقب برویم، کافی است که اولین پایه‌ای که عددی بیشتر مساوی k دارد را پیدا کنیم. این کار را ما با استفاده از segment tree انجام دادیم.
