راه‌حل‌های سؤالات مسابقه الگوریتمی خداحافظ ۱۴۰۱ در ادامه توضیح داده شدند. در صورتی که متوجه راه‌حلی نشدید، می‌تونید در بخش نظرات، سؤالات و ابهام‌های خودتون رو مطرح کنید. اگه راه‌حل دیگه‌ای برای سؤالات دارید، خوشحال می‌شیم که راه‌حلتون رو در بخش نظرات با ما و دوستانتون به اشتراک بذارید. در نهایت تشکر می‌کنم از «شایان چشم‌جهان» عزیز، بابت همکاری در نوشتن راه‌حل‌های سوالات این مسابقه.
ابتدا ادعا می‌کنیم اگر n=1 باشد، پاسخ برابر ۲ است. این موضوع واضح است زیرا در زمان دیدن عروسک اول هر دوی دارا و سارا جیغ خواهند کشید، پس تعداد جیغ‌ها قطعا ۲ است.
در صورتی که n \ge 2 باشد، ادعا می‌کنیم پاسخ مسئله همیشه ۳ خواهد بود. ابتدا ثابت می‌کنیم حداقل ۳ جیغ را خواهیم داشت. می‌دانیم که بعد از دیدن عروسک اول هم دارا و هم سارا جیغ خواهند کشید. حال دو حالت داریم، اگر عروسک دوم کوچکتر از عروسک اول باشد، سارا جیغ می‌کشد. اگر عروسک دوم بزرگتر از عروسک اول باشد، دارا جیغ می‌کشد. پس در هر صورت یکی از آنها بعد از آمدن عروسک دوم جیغ خواهد کشید و حداقل سه جیغ را خواهیم کشید.
حال برای آنکه نشان دهیم جواب بیش از ۳ نیست، مثالی ارائه می‌دهیم که دارا و سارا دقیقاً ۳ بار در مجموع جیغ می‌کشند. کافی است در ابتدا عروسک شماره ۱، سپس عروسک شماره n و سپس مابقی عروسک‌ها به ترتیبی دلخواه بیایند. در اینصورت دقیقاً دو جیغ بعد از دیدن عروسک اول و یک جیغ بعد از دیدن عروسک دوم خواهیم داشت و بعد از دیدن عروسک‌های بعدی هیچ جیغی وجود نخواهد داشت.
در نتیجه برای n>1 پاسخ مسئله برابر ۳ است.
پیچیدگی زمانی: \mathcal{O}(1)
به یک بازه از کارت‌ها بلوک می‌گوییم اگر همه کارت‌ها وضعیت مشابه داشته باشند و بازه از هیچ طرفی قابل گسترش نباشد (ماکسیمال باشد). مثلاً 0110111000 از ۵ بلوک تشکیل شده است.
حال ادعا می‌کنیم پاسخ برابر تعداد بلوک‌های به پشت است. مشخصاً چون هر بلوک یک بازه هست پس می‌توانیم یکی یکی بلوک‌های پشت را برگردانیم تا همه کارت‌ها رو شوند. از طرفی توجه کنید با یک حرکت تعداد بلوک‌های پشت حداکثر یکی کم می‌شود پس ادعا ثابت می‌شود.
پیچیدگی زمانی: \mathcal{O}(T \times CountCards)
اولین نکته در حل این مسئله این است که قطعاً فایل با بیشترین حجم مربوط به پایانترم است. دلیل این موضوع این است که محتوای همه‌ی فایل‌های دیگر زیرمجموعه‌ی پایانترم هستند، در نتیجه امکان ندارد حجم آنها از حجم پایانترم بیشتر باشد.
در نتیجه حجم فایل پایانترم را می‌دانیم. فرض کنید حجم این فایل A و مجموع حجم مابقی فایل‌ها B است. می‌دانیم A (که همان حجم فایل پایانترم است) برابر با مجموع حجم تمام جلسات کلاس است. همینطور B برابر با مجموع حجم تمام جلسات کلاس و فایل میان‌ترم است. در نتیجه حجم فایل میان‌ترم برابر با B-A است.
در نتیجه حجم پایانترم برابر با پر حجم‌ترین فایل ورودی، و حجم میان‌ترم برابر مجموع حجم بقیه‌ی فایل‌ها منهای آن فایل است.
پیچیدگی زمانی: \mathcal{O}(n)
ابتدا مساله را برای یک شرکت حل می‌کنیم و نیز بدون از دست دادن کلیت مساله فرض می‌کنیم n \le m حال:
اگر n = 1 باشد پاسخ مساله 4 \times 3 ^ {m-1} است چرا که اگر پنجره‌ها را به ترتیب از چپ به راست رنگ آمیزی کنیم آنگاه پنجره اول ۴ حالت و بقیه ۳ حالت دارند.
در غیر این صورت یا جدول (نما را به صورت جدول در نظر بگیرید) سطری رنگ می‌شود و یا ستونی. می‌گوییم جدول سطری رنگ شده اگر سطرهای فرد تنها از دو رنگ مشخص رنگ شده باشند. ستونی رنگ شدن هم مشابه تعریف می‌شود.
اثبات: فرض کنید جدول سطری رنگ نشده باشد پس با کمی استدلال مشخص می‌شود ۳ خانه کنار هم یافت می‌شود که رنگ‌های متمایزی دارند. فرض کنید رنگ‌ها از چپ به راست ۱ و ۲ و ۳ باشند در این صورت ستون‌های بالا و پایین آن یکتا به صورت زیر مشخص می‌شوند:
1 2 3
\\
3 4 1
\\
1 2 3
\\
3 4 1
و باز با کمی استدلال می‌توانید نتیجه بگیرید اگر سطری رنگ نشده باشد پس ستونی رنگ شده.
حال اگر جدول سطری رنگ شده باشد پاسخ $6 \times 2^n$ خواهد بود چرا که انتخاب رنگ‌های سطر اول ۶ حالت و اینکه اولین خانه هر سطر چه رنگی باشد ۲ حالت دارد.
پس جواب برابر است با تعداد رنگ آمیزی‌های سطری به علاوه تعداد رنگ آمیزی‌های ستونی منهای تعداد رنگ آمیزی‌هایی که هم سطری و هم ستونی هستند.
توجه کنید تعداد رنگ آمیزی‌هایی که هم سطری و هم ستونی هستند ۲۴ است.
حال برای پاسخ دادن به تست‌های مختلف کافی است یک بار برای هر 1 \le x \le N مقدار 3^x و 2^x را محاسبه کنید.
پیچیدگی زمانی: \mathcal{O}(N + T)
برای اینکه اعدادی که در کیسه iام هستند را داشته باشیم کافی است از دو آرایه کمکی add و del استفاده کنیم. توجه کنید هر خانه آرایه‌ها خودش لیست است.
یک عملیات با l\space r\space x داده شده را در نظر بگیرید. به لیست‌های add[l] و rem[r+1] عدد x را اضافه می‌کنیم. حال اگر اعداد کیسه iام G_i در نظر بگیریم آنگاه:
G_i = G_{i-1}+add[i]-rem[i]برای حل سوال از دو داده ساختار استفاده می‌کنیم. یک داده ساختار که اعدادی که نداریم را نگه می‌دارد و داده ساختاری دیگر که اعدادی که اضافه داریم یعنی بیش از یکی از آن داریم را نگه می‌دارد. برای پاسخ سوال ابتدا جواب را برای گونی ۱ حساب می‌کنیم سپس ۲ و… جواب همیشه کمترین عضو داده ساختار اولیست.
باید در هر دو داده ساختار در زمان خوبی (مثل \mathcal{O}(\log N) ) بتوانیم یک عضو حذف کنیم و یا یک عضو اضافه کنیم و یا وجود یک عضو را برسی کنیم. در داده ساختار اول باید قابلیت گرفتن کمینه اعضا هم داده باشیم. برای اینکار می‌توان از segment tree , red-black tree و Trie استفاده کرد.
توجه: در C++ داده ساختار set نوعی red-black tree است.
پیچیدگی زمانی: \mathcal{O}(N \log N)
به تعدادی خانه که هر دو تایی از آنها (در صورت وجود فیل در آنها) همدیگر را تهدید کنند و نیز ماکسیمال باشند (یعنی نتوان خانه‌ای به مجموعه مد نظر با حفظ خاصیت اضافه کرد) بلوک می‌گوییم. و نیز می‌دانیم نوع بلوک موجود است. یکی بلوک اصلی که موازی خانه‌های قطر اصلی است و یکی بلوک فرعی که موازی خانه‌های قطر فرعی است. مثلاً جدول زیر را در نظر بگیرید:
123\#
\\
4\#23
\\
54\#2
\\
654\#
خانه‌های هم شماره در یک بلوک هستند. توجه کنید هر خانه‌ی خالی متعلق به دقیقاً دو بلوک است یک بلوک فرعی و یک بلوک اصلی.
حال جدول را به گراف دو بخشی مدل می‌کنیم که بلوک‌ها همان راس‌ها هستند و خانه‌های خالی همان یال‌ها که دو بلوک را به هم وصل می‌کنند.
بزرگترین تطابق گراف همان جوب مساله است.
اولاً اگر در یال‌های بیشینه تطابق فیل‌ها را بگذاریم هیچ دو فیلی همدیگر را تهدید نمی‌کنند چون هیچ دو یالی سر مشترک ندارند. همچنین هر چیدمانی از فیل‌ها که معتبر باشد نیز مشخصاً متناظر با یک تطابق است.
پیچیدگی زمانی: \mathcal{O}(n \times m + (n \times m)^2)
برای یافتن بیشینه تطابق ما از الگوریتم kuhn استفاده کردیم. الگوریتم‌های سریع‌تر هم وجود دارد که نیازی به استفاده آنها در این سوال نیست.
مقدار dp[i] را به اینصورت تعریف می‌کنیم که برابر است با تعداد حالات رنگ‌آمیزی تمام نقاط صحیح که مضربی از i باشند، به طوریکه مابقی نقاط محور مختصات رنگ نشوند. واضح است که طبق این تعریف پاسخ مسئله برابر با dp[1] خواهد بود. همینطور cnt[i] را تعداد رنگ‌هایی که دوره تناوبشان i است تعریف می‌کنیم.
حال مقادیر dp را از آخر به اول بدست می‌آوریم. فرض کنیم می‌خواهیم مقدار dp[x] را بدست آوریم. قطعا فقط می‌توانیم از رنگ‌هایی استفاده کنیم که دوره تناوبشان مضربی از x باشد. یک حالت آن است که نقاط را با یک رنگ با دوره تناوب x رنگ کنیم، در اینصورت از یک رنگ استفاده می‌کنیم و تمامی نقاط پوشش داده می‌شوند. تعداد این حالات cnt[x] است.
حالت دیگر آن است که فقط از رنگ‌هایی استفاده کنیم که دوره تناوبشان مضربی از x و بزرگتر از خود x است. اگر ب.م.م این اعداد را d.x در نظر بگیریم، d نباید برابر با ۱ باشد، زیرا در آن صورت از آنجا که بیش از یک رنگ داریم، طبق لم بزو به تناقض خواهیم رسید (یعنی یک نقطه باید دو رنگ مختلف داشته باشد). اگر d را فیکس کنیم می‌توانیم بگوییم که تعداد حالت برای این d خاص برابر با dp[dx]^d خواهد بود، زیرا نقاط به d دسته مستقل تقسیم می‌شوند که هر کدام از این دسته‌ها dp[dx] حالت دارند.
با توجه به این موضوع، برای محاسبه‌ی dp[x] از شمول و عدم شمول استفاده می‌کنیم. برای تمام اعداد اول مانند p مقدار dp[px]^p را جمع می‌زنیم. با این کار، برای مثال حالتی که ب.م.م 6x باشد هم در زمانی که p=2 قرار داده شده و هم زمانی که p=3 است محاسبه شده است، پس باید کم شود. در نتیجه به صورت کلی به این شکل عمل می‌کنیم که به ازای تمام اعداد square free (یعنی اعدادی که در تجزیه‌شان از هر عامل اولی حداکثر یکی دارند) مانند d مقدار dp[d.x]^d را بدست می‌آوریم. در صورتی که تعداد عوامل d فرد باشد این مقدار را به جواب اضافه می‌کنیم، در صورتی که تعداد عوامل d زوج باشد این مقدار را از جواب کم می‌کنیم.
به این صورت مقادیر dp بدست می‌آیند و حاصل نهایی ما مقدار dp[1] خواهد بود.
پیچیدگی زمانی: \mathcal{O}(N + L \log ^2 L)
یک خط را خوب می‌گوییم اگر نیمه از نقاط یک طرف آن باشند. ثابت می‌کنیم به ازای هر خط خوب یک خط عالی وجود دارد که نقاط را به همان شکل تقسیم می‌کند و بر دو نقطه نیز مماس است(و حتی می‌توان اضافه کرد آن دو نقطه در یک سمت خط هم نیستند.)
خطی خوب را در نظر بگیرید. اگر هیچ نقطه‌ای بر آن مماس نبود (خط و نقطه را مماس فرض می‌کنیم اگر فاصله آنها بسیار کوچک باشد.) خط را با برداری دلخواه(ناموازی با خط) آنقدر انتقال می‌دهیم تا با نقطه‌ای مماس شود. حال خط را حول آن نقطه آنقدر دوران می‌دهیم تا مماس بر نقطه‌ای دیگر شود.
تعداد خطوط عالی محدود است و با برسی هر دو نقطه از صفحه می‌توان آنها را پیدا کرد. حال با توجه به توضیحات بالا می‌توانیم برسی کنیم که کدام دو خط عالی پاسخ مساله ما هستند.
پیچیدگی زمانی: \mathcal{O}(T \times N^3)
