مسابقه الگوریتمی شماره ۴۳ + راه‌حل‌ها

سلام!

خب بدون مقدمه بریم سراغ توضیحات مسابقه الگوریتمی شماره ۴۳. این مسابقه شامل ۷ سؤال الگوریتمی هست که قراره توانایی حل مسئله‌ی شما رو به چالش بکشن. حل سؤالات به تکنولوژی خاصی نیاز نداره و با هر زبانی که دوست داشته باشید، می‌تونید کد بزنید. ترتیب سؤالات تقریباً از ساده به سخت هست، اما پیشنهاد می‌کنیم همه سؤالات رو بخونید و سعی کنید حلشون کنید.

طراحی این مسابقه توسط محمد حسینی و پارسا هاشمی خرسند انجام شده است.

نکات مهم

• حل سؤالات این مسابقه بر روی امتیاز کوئرایی شما تأثیر داره.
• زمان برگزاری مسابقه، سه‌شنبه ۲۴ خرداد ساعت ۲۰:۰۵ دقیقه هست و شما ۲ ساعت و ۳۰ دقیقه زمان دارید تا به سؤالات پاسخ بدید.

ثبت‌نام این مسابقه در صفحه مسابقه الگوریتمی شماره ۴۳ انجام می‌شه و تا ۲۴ام خرداد برای ثبت‌نام فرصت دارید.

منتظرتون هستیم 🙂

پی‌نوشت: راه‌حل‌های مسابقه

شکلات

باید بررسی کنیم که عدد n به عدد k بخش‌پذیر هست یا نه. در واقع باید بررسی کنیم که باقی‌مانده‌ی n بر k صفر می‌شود یا نه.

عدالت پارسا

ابتدا مسئله را برای سطرها حل می‌کنیم. از آنجایی که می‌خواهیم اختلاف بین کمترین و بیشترین تعداد قند در یک سطر از چایی‌ها کمینه شود و هم‌زمان جمع همه‌ی قند‌ها در این n چایی برابر با k شود، باید تا جای ممکن k قند را در n چایی به‌صورت مساوی پخش کنیم. اگر k بر n بخش‌پذیر باشد، در هر چایی k / n قند می‌ریزیم. در غیر این صورت k \% n تا از چایی‌ها یک قند بیشتر خواهند داشت. هر جایگشتی از این تقسیم‌بندی قابل‌قبول است.

اگر برای هر سطر از راه‌حل بالا استفاده کنیم، این که در هر سطر از این n سطر، از چه جایگشتی استفاده شود حائز اهمیت است. چون شرایط مسئله در هر ستون هم باید برقرار باشد. یک راه‌حل برای مسئله این است که برای سطر اول، جایگشتی را در نظر بگیریم که همه‌ی چایی‌هایی که یک قند بیشتر از بقیه دارند، اول به‌ترتیب چیده شده‌ باشند و بقیه‌ی چایی‌ها به‌دنبال آن‌ها. حال برای سطر دوم، جایگشت سطر اول را یک واحد شیفت چرخشی می‌دهیم. برای سطر سوم، جایگشت سطر دوم را یک واحد شیفت چرخشی می‌دهیم و به همین ترتیب برای سطر‌های بعدی نیز همین کار را انجام می‌دهیم.

انتقام به سبک محمد

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

سودی که از خرید شکلات قهوه‌ای به دست می‌آوریم برابر با A - (a + i \times X) است که در آن i تعداد دفعاتی است که قبلاً از این نوع شکلات خریداری کرده‌ایم. سودی که از خرید شکلات سفید به دست می‌آوریم برابر با B - (b + j \times Y) است که در آن j تعداد دفعاتی است که قبلاً از این نوع شکلات خریداری کرده‌ایم. در صورتی که شکلات‌های جادویی تمام نشده باشند، سودی که از خرید آن به دست می‌آوریم برابر با C - c می‌باشد.

آلیس افسرده می‌شود

برای شمارش تعداد پرانتز‌گذاری‌های معتبر به طول k از برنامه‌نویسی پویا استفاده می‌کنیم. یک بُعد برای پیمایش رشته نیاز داریم. یک بُعد نیز برای طول رشته‌ی انتخاب‌شده. همچنین چون هم از پرانتز استفاده می‌کنیم هم از براکت، نمی‌توانیم تعداد پرانتز‌های بازِ باقی‌مانده را یک بُعد در نظر بگیریم. بلکه باید استک پرانتز و براکت‌های باز‌شده را داشته باشیم. چون k حداکثر ۱۶ است، می‌توانیم از bitmask برای ذخیره‌سازی این استک در یک بُعد از حافظه‌ی dp استفاده کنیم.

dp[i][j][st] = \text{number of accepted sub-strings of s[i:] with length of 2 * j and stack of st}

برای پرانتز‌باز از بیت 0 و برای براکت‌باز از بیت 1 در bitmask استک استفاده می‌کنیم. همچنین پایان استک را با یک بیت 1 نشان می‌دهیم.

حالت پایه:

dp[|s|][j][st] = \begin{cases}
    1 & j=k/2 \text{ and } st=1\\
    0 & \text{otherwise}
\end{cases}

رابطه‌ی بازگشتی:

dp[i][j][st] = dp[i+1][j][st] +
\begin{cases}
    dp[i+1][j+1][st << 1] & s[i]=( \text{ and } j < k/2\\
    dp[i+1][j+1][(st << 1) + 1] & s[i]=[ \text{ and } j < k/2\\
    dp[i+1][j][st >> 1] & s[i]=) \text{ and } st > 1 \text{ and } st \% 2 = 0\\
    dp[i+1[j][st >> 1] & s[i]=] \text{ and } st > 1 \text{ and } st \% 2 = 1
\end{cases}

جواب نهایی:

dp[0][0][1]

ملکه قرمز

برای حل این سؤال می‌توانیم از روش بازگشتی استفاده کنیم. فرض کنید تابعی داریم که برای یک گراف، خروجی سؤال را برمی‌گرداند. پیاده‌سازی این تابع به این صورت است:

اگر همه‌ی رأس‌های گراف زوج باشند، همه‌ی رأس‌ها را در یک گروه قرار می‌دهیم. در غیر این صورت یک رأس با درجه‌ی فرد داریم، آن را گرفته و یال‌های مجاور‌ش را برعکس می‌کنیم؛ یعنی اگر یال بود بر‌می‌داریم و در غیر این صورت یال می‌گذاریم. حال رأسِ انتخابی را حذف کرده و برای گراف جدیدِ به‌دست‌آمده، دوباره تابع را صدا می‌زنیم. تابع مسئله را به‌صورت بازگشتی حل کرده و جواب را برایمان می‌سازد. توجه کنید که چون در هر مرحله یک رأس را حذف می‌کنیم، در آخر حتماً به یک گراف زوج می‌رسیم.

حال جواب را از تابع می‌گیریم که شامل دو گروهِ تقسیم‌بندیِ رأس‌های گراف است. یکی از این گروه‌ها شامل زوج رأس از رأس‌های مجاور‌ِ رأس‌ حذف‌شده در این مرحله از تابع است. چون درجه‌ی رأسِ حذف‌شده در آن مرحله فرد است، پس رأس گفته‌شده حتماً وجود دارد. آن را به گروه اضافه می‌کنیم و یال‌هایی که عوض کرده بودیم را برعکس می‌کنیم تا گراف به حالت اولیه برگردد. با این کار گرافِ حاصل و دو گروهِ تولید‌شده، همه درون گروهشان زوج مجاور دارند و می‌توانیم گروه‌ها را برای تابع قبلی بفرستیم.

در این الگوریتم چون در هر مرحله ممکن است n^2 یال را عوض کنیم و این کار را به تعداد رأس‌های گراف ممکن است انجام دهیم، در مجموع مسئله با پیچیدگی زمانی O(n^3) حل می‌شود.

ددلاین در واندرلند

برای بررسی اینکه اصلاً امکان رساندن همه‌ی تکالیف تا ددلاین‌های مورد‌نظر وجود دارد یا خیر، کافیست بررسی کنیم که آیا زمان tای وجود دارد که تعداد تکالیفی که باید تا این زمان حل شوند، بیشتر از t باشد یا خیر. اگر چنین tای وجود داشته باشد، در آن صورت امکان رساندن تکالیف وجود ندارد. چون کوشان در هر روز می‌تواند یک تکلیف را انجام دهد. حال برای پیدا کردن جایگشتی با کمترین نابه‌جایی کافیست طبق الگوریتم زیر عمل کنیم:

از t = n تا t = 1 حرکت کرده و سپس در هر مرحله در این روز بزرگترین تکلیفی را انجام می‌دهیم که ددلاینش بزرگتر مساوی t بوده و قبلاً حل نشده باشد.