راه‌حل‌های مسابقه بُل‌تات – الگوریتمی

سلام!
در این پست به توضیح راه‌حل‌های سوالات مسابقه بل‌تات می‌پردازیم.

سوال سپیده

از آن‌جایی که پس از هر m مرحله، به ورودی‌های همه‌ی درب‌ها دقیقا یکی اضافه می‌شود، پاسخ برابر با سقف تقسیم n بر m می‌باشد.
کد راه‌حل

سوال سلام سلام خداحافظ

برای حل این سوال صرفا لازم است تا موارد گفته‌شده در صورت سوال را اجرا کنید و سلام و یا خداحافظ‌های گفته‌شده را چاپ کنید.

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

سوال چارپک

ادعا می‌کنیم اگر همواره چهار نفری که در لحظه‌ی فعلی بیشینه تعداد غذا را می‌خواهند (اگر چهار نفر وجود نداشتند کل افراد را می‌فرستیم)، داخل صف بفرستیم، با کمترین تعداد پک می‌توان کل افراد را سیر کرد. برای اثبات این ادعا، از برهان خلف استفاده می‌کنیم. فرض کنید این‌گونه نباشد و روشی وجود داشته باشد که در یک مرحله چهار نفر ماکسیمم را داخل صف نفرستد و پاسخ کمتر به دست آورد.

حال یکی از نفرات که بیشینه تعداد غذا را می‌خواهد و در این مرحله نیامده است را x بنامید و یکی از نفرات غیر بیشینه‌ای که در این مرحله آمده است را y بنامید. همچنین اولین مرحله‌ای پس از این حرکت که x داخل صف رفته است را k بنامید. اکنون اگر بگوییم که x در مرحله‌ی فعلی بیاید و y در مرحله kام بیاید و بقیه حرکات بدون تغییر باقی بمانند، پاسخ فعلی بیشتر نمی‌شود و تعداد پک‌ها ثابت باقی می‌ماند. پس به تناقض رسیدیم چون پس از تعدادی جابه‌جایی به شکل بالا به الگوریتم اولیه خود می‌رسیم. بنابراین الگوریتم گفته‌شده بهینه است.

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

روش اول:

کار گفته‌شده در بالا را شبیه‌سازی می‌کنیم به این صورت که یک آرایه سه‌تایی ذخیره می‌کنیم که هر عضو آن مشخص می‌کند که چند آدم هستند که به آن مقدار غذا می‌خواهند. حال در هر مرحله بررسی می‌کنیم که ۴ عضو بیشینه چه مقداری دارند و آن‌ها را کم می‌کنیم و آرایه ۳تایی را آپدیت می‌کنیم.

روش دوم:

جمع تعداد غذاهای مورد نیاز افراد را s و ماکسیمم تعداد غذاهای مورد نیاز را m می‌نامیم. همچنین k را برابر سقف تقسیم s بر ۴ قرار می‌دهیم و ادعا می‌کنیم که پاسخ برابر با ماکسیمم m و k است.

می‌دانیم حداقل به m پک برای سیر کردن افراد نیاز داریم چون از هر پک حداکثر یک غذا به هر نفر می‌رسد. پس اگر بتوانیم در همه‌ی مراحل به غیر از بار آخر ۴ نفر را داخل صف بفرستیم، پاسخ ما درست است. حال فرض کنیم شرایط فوق برقرار نباشد.

اولین مرحله‌ای پیش از مرحله آخر را در نظر بگیرید که نتوانیم در آن چهار نفر را داخل صف بفرستیم (در واقع در این مرحله حداکثر سه گرسنه داریم).

اکنون نفری را در نظر بگیرید که ماکسیمم تعداد غذا را می‌خواهد. اگر این نفر سه غذا بخواهد نتیجه می‌شود که از ابتدا همواره همین تعداد نفرات وجود داشته‌اند و تاکنون هیچ کسی سیر نشده است (زیرا در غیر این صورت طبق الگوریتم در مرحله‌ی قبلی باید به جای سیر کردن فرد دیگری، یک غذا به نفر موردنظر می‌دادیم). حال پاسخ برابر با m خواهد بود که درست است.

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

کد راه‌حل اول
کد راه‌حل دوم

سوال خسته تر از امید خودشه

برای حل این سوال گرافی با 2n+9 راس با شرایط زیر می‌سازیم.

به ازای هر کدام از حروف رشته و همچنین هر کدام از حروف الفبا یک راس در نظر می‌گیریم. n – 1 راس دیگر نیز در گراف قرار می‌دهیم.

حال راس iام از n – 1 راس اضافه را به رئوس متناظر حرف i ام و i + 1 ام رشته متصل می‌کنیم. همچنین به ازای هر حرف الفبا، راس متناظر آن را به رئوس متناظر تمام جایگاه‌هایی در رشته وصل می‌کنیم که دارای این حرف می‌باشند.

حال در گراف فعلی هر کدام از حرکات مسئله (رفتن به یک حرف مجاور و رفتن به یک حرف برابر) را می‌توان با پیمودن دقیقا دو یال انجام داد و با یک یال هم نمی‌توان این کار را کرد. بنابر این در گراف فعلی اگر فاصله راس متناظر حرف اول رشته و راس متناظر حرف آخر رشته را k در نظر بگیریم، پاسخ مسئله برابر k / 2 می‌باشد. برای پیدا کردن کوتاه‌ترین فاصله هم می‌توان از الگوریتم bfs استفاده‌کرد. (برای پیداکردن اطلاعات بیشتر در مورد این الگوریتم می‌توانید به این‌جا مراجعه کنید.)

کد راه‌حل

سوال عصرانه ی پر هزینه

این مسئله راه های مختلفی دارد که هرکدام به ازای تست‌های مختلف عملکردهای مختلفی دارند و در زیر به توضیح آن‌ها می‌پردازیم.

الگوریتم اول: الگوریتم First Fit که خروجی آن حداکثر دو برابر جواب بهینه است (اطلاعات بیشتر در مورد این الگوریتم در این لینک وجود دارد)

حالت کلی این الگوریتم به این صورت است که در ابتدا ترتیب جسم ها(محموله های پفک) را به صورت تصادفی عوض میکنیم، و پس از آن لیستی از جعبه ها (کامیون ها) را در نظر میگیریم، و به ترتیب هر جسم را وارد اولین جعبه ای که در آن میتوان این جسم را گذاشت قرار میدهیم. پیاده سازی این الگوریتم به همین صورت دارای پیچیدگی O(n*n) است ( در واقع اگر جواب را برابر ans در نظر بگیریم حداکثر ans*n عملیات انجام میدهیم( و در عمل هم مقدار زمان زیادی طول میکشد تا این الگوریتم جواب مطلوبی را تولید کند.

برای رفع این مشکل میتوانیم در نظر بگیریم که جعبه ها از لحاظ مقدار فضای خالی 21 حالت بیشتر ندارند و در هر مرحله تنها مقدار فضای خالی آنها اهمیت دارد. پس میتوانیم اندیس خانه هایی که مقدار فضای خالی یکسانی دارند را در یک set بریزیم. حال از هر set، تنها بزرگ ترین اندیس موجود در آن میتواند به عنوان کاندید برای اولین جعبه ای که در آن میتوان این جسم را گذاشت باشد، پس تنها کافیست همین جعبه ها را چک کنیم. این پیاده سازی دارای پیچیدگی (O(21*n*logn است. که با محدودیت های ورودی و زمانی گفته شده مشکلی ایجاد نمیکند. ولی همچنان با توجه به محدود بودن زمان اجرای برنامه نمیتوان این الگوریتم را دفعات زیادی اجرا کرد (با عوض کردن ترتیب جسم ها به صورت تصادفی) و بهترین نتیجه را نمایش داد. پیاده سازی ما برای این الگوریتم نمره ی 158 از 500 را میگرفت.

الگوریتم دوم (الگوریتم اصلی): یک جعبه را در نظر بگیرید، وزن اجسام درون آن بدون در نظر گرفتن ترتیب تعداد کمی حالت میتواند داشته باشد (2429 حالت). و میتوان گفت بعضی از این جعبه ها از برخی دیگر بهتر هستند. برای مثال جعبه ای که مجموع وزن اجسام درون آن بیشتر است به نظر میرسد جعبه ی بهتری است.

یا به طور مثال حالتی که در جعبه دو جسم با وزن 10 داشته باشیم بهتر از جعبه ای است که دو جسم با وزن 5 و یک جسم با وزن 10 داشته باشیم. زیرا در حالت اول دو جسم با وزن 5 برای جعبه های دیگر باقی میماند و در حالت دوم یک جسم با وزن 10، که به وضوح میتوان گفت حالت اول بهتر یا مساوی حالت دوم است چون میتوانیم دو جسم با وزن 5 را یک جسم با وزن 10 در نظر بگیریم.

پس اگر در پاسخ نهایی ما از جعبه هایی که بهتر هستند بیشتر داشته باشیم، در نهایت جواب بهتری خواهیم داشت.

حال کافیست ما بتوانیم ترتیب خوبی برای جعبه ها داشته باشیم، اگر ترتیب مطلوبی پیدا کنیم. میتوانیم تا میتوانیم جعبه های بهتری بسازیم و بعد سراغ حالات دیگر ساختن جعبه ها برویم.

برای پیدا کردن یک ترتیب خوب از ساختن جعبه ها از شهود و آزمایش و خطا کمک گرفتیم، شهودا میتوان گفت جعبه ای که مجموع وزن اجسام درون آن بیشتر است جعبه ی بهتری است. یا جعبه ای که میانگین وزن اجسام درون آن بیشتر است جعبه ی بهتری است (برای مثال حالت 10،10 را با حالت 10،5،5 مقایسه کردیم) با تست کردن ترتیب های مختلف نمره های مختلفی برای این سوال میتوان گرفت، کد قرار داده شده در انتهای متن که با ارزش گذاری (مجموع توان دو وزن اجسام) / (تعداد اجسام) جعبه ها را مقایسه میکند، نمره ی 450 را از این سوال میگیرد. برای گرفتن نمره ی کامل از این سوال میتوان از الگوریتم اول و چند تابع ارزش گذاری مختلف استفاده کرد و جوابی که بهتر است را خروجی داد. (این کار برای ساختن تست ها استفاده شده است)

پیاده سازی الگوریتم اول
پیاده سازی الگوریتم دوم