توضیح راه حل های مسابقه شماره یک Quera به همراه کدهای صحیح را در ادامه مطلب می‌بینید. در صورتی که اشتباهی مشاهده کردید در بخش نظرات با ما در میان بگذارید.
برای حل این سوال کافیست به ازای هر اسم داده‌شده، تعداد حروف متمایزش را بدست آوریم. میتوانیم برای هر کلمه w و حرف c، تعداد تکرار c در w را بدست آوریم و تعداد حروف متمایز w را برابر تعداد حرف‌های با حداقل ۱ تکرار قرار دهیم.
کد
با توجه به شرایط گفته‌شده در صورت سوال، متوجه میشویم که به ازای هریک از حروف L, F, T, D در کلمه‌ی گفته شده، ۲ حالت برای کلمه‌ی مدنظر کریم وجود دارد؛ برای T ممکن است مدنظرش K یا T باشد، برای D حروف D یا G، برای L حروف L یا R و برای F حروف F یا R. پس پاسخ مسئله برابر دو به توان تعداد حروف مبهم در کلمه است.
کد
به ازای عدد x، تعداد مظنونینی که در لحظه‌ی x در پارک حضور داشتند را f(x) مینامیم که در زمان اجرای O(n) قابل محاسبه است. این مسئله مقدار کمینه و بیشینه‌ی f(x) به ازای L \le x \le R را از ما میخواهد.
نمودار تابع f از L تا R را در نظر بگیرید. مقدار این تابع تنها در نقاطی تغییر میکند که یا برابر r_i یا برابر l_i به ازای یک مظنون هستند و در بین آن‌ها مقدار ثابتی دارد؛ پس مقدار کمینه یا بیشینه‌ی این تابع در یکی از نقاط l_i, r_i, L, R, r_i + \epsilon, l_i - \epsilon (به ازای \epsilon برابر یک عدد بسیار کوچک) وجود دارد که تعداد این نقاط O(n) است. کافیست مقدار f را در این نقاط بدست آورده و کمینه و بیشینه مقدار بدست آمده را خروجی دهیم. زمان اجرای این راه حل O(n^2) است. میتوان این زمان اجرا را به O(n\log n) کاهش داد؛ اما برای محدودیت‌های سوال نیازی به اینکار نیست.
این کد با زمان اجرای O(n\log n) و این کد با زمان اجرای O(n^2) به ترتیب توسط ایمان غلامی و امیرمحمد قاسمی هنگام مسابقه نوشته‌شدند.
در این سوال گرافی n راسی به دور دایره داریم و میخواهیم یک مسیر همیلتونی مسطح از آن پیدا کنیم. (یعنی مسیری که از همه رئوس بگذرد و هیچ دو یالش باهم تقاطع نداشته باشند.)
پیدا کردن یک مسیر همیلتونی و پیدا کردن یک زیرگراف بزرگ مسطح در یک گراف، هردو در دسته مسائل سخت (NP-Hard) هستند و هنوز راه‌حلی چندجمله‌ای برای آنان پیدا نشده است. اما شرط دور دایره بودن تاثیر به‌سزایی روی سوال دارد.
نکته اصلی اینکه رئوس دور دایره چیده شده‌اند این است که میتوان ثابت کرد که رئوس هر پیشوندی از یک مسیر همیلتونی مسطح، در دور دایره بصورت بازه‌ای پشت سر هم آمده‌اند. یعنی کمانی دور دایره وجود دارد که تنها شامل این راس‌ها میشود.
برای اثبات این لم از استقرا استفاده میکنیم. فرض استقرا را قوی میکنیم: i راس ابتدایی مسیر همیلتونی مسطح دور دایره بصورت بازه‌ای پشت سر هم قرار دارند که iمین راس این مسیر یکی از دو راس انتهایی آن بازه است. این فرض برای پیشوند تک راسی مسیر برقرار است. با فرض برقراری برای پیشوند i راسی که i < n، میخواهیم ثابت کنیم که لم گفته شده برای پیشوند i+1 راسی نیز برقرار است. بدون کاهش فرض مسئله، فرض میکنیم i راس اول مسیر دور دایره روی کمان بین راس 1 و راس i بصورت ساعتگرد آمده اند و شماره‌ی iمین راس مسیر برابر i است. یال بعدی در مسیر، کمان ساعتگرد i تا n را دوبخش مجزا میکند و ادامه‌ی مسیر در تنها یکی از آن‌ها میسر خواهد بود؛ وگرنه مسیر انتخاب شده مسطح باقی نمیماند. پس چون مسیر همیلتونی است یکی از این دوبخش باید تهی باشد پس راس بعدی مسیر یا راس شماره n است و یا راس شماره i+1 که در هر دو حالت فرض مسئله برای i+1 راس اول نیز برقرار خواهد ماند. \blacksquare
برای حل مسئله از برنامه‌نویسی پویا استفاده میکنیم. dp_{i, j, dir} را تعریف میکنیم: اگر میتوان مسیری در گراف یافت که رئوس آن راس‌های کمان i تا j در جهت dir (ساعتگرد یا پادساعتگرد) دور دایره باشند و راس انتهایی آن j باشد، مقدار dp_{i, j, dir} برابر true است وگرنه false. میتوان مشابه اثبات لم گفته شده، مقادیر این آرایه را بدست آورد. زمان اجرای این راه‌حل O(n^2) است.
کد این راه‌حل که توسط محمد‌هادی حجت هنگام مسابقه نوشته‌شده است.
در علوم کامپیوتر، کلاسی از الگوریتم‌ها تعریف میشود بنام one-pass algorithms. این الگوریتم‌ها برای حل مسائلی بکار میروند که در آن‌ها اندازه‌ی ورودی بسیار بزرگ است، بطوری که معمولاً نمیتوان ورودی را نگه داشت و باید با یکبار خواندن ورودی، پاسخ مسئله را یافت. در سوال دورگیری باید الگوریتمی one-pass برای محاسبه‌ی مساحت یک شکل طراحی میکردید. در حالت کلی این کار ممکن نیست اما شکل خاص ورودی این سوال ارائه‌ی الگوریتم one-pass را ممکن کرده است.
ابتدا فرض میکنیم که شکل را میتوانیم نگهداریم. “الگوریتم بند کفش” یا “قاعده‌ی مساحت گاوس”، روش معمول برای محاسبه‌ی مساحت یک شکل بسته و بدون سوراخ است. توضیحات بیشتر این الگوریتم را میتوانید در اینجا بخوانید. با دقت به این الگوریتم، میبینیم که لزومی ندارد که ما کل شکل را داشته باشیم و اگر خط‌های دور شکل را به ترتیب ساعتگرد بیابیم، براحتی میتوان حافظه راه حل را به O(1) کاهش داد. یافتن دورگیری خطی شکل نیز بوسیله‌ی دورگیری توصیف شده در سوال بصورت one-pass امکان‌پذیر است. دقت کنید که کد پیدا کردن دورگیری خطی شامل جزییات بسیاری است.
کد
