راه‌حل‌ها و نتایج مسابقه مقدماتی کدکاپ ۳

سلام.

مسابقه مقدماتی کدکاپ هم به پایان رسید و امیدواریم برای شما راضی‌کننده بوده‌باشد.

بابت تأخیر در انتشار این پست عذرخواهی می‌کنیم. این تأخیر بخاطر کشف تقلب مسابقه بود؛ تعداد کمی از تیم‌ها تقلب کرده بودند ولی تک تک موردهای مشکوک از جهات مختلف بررسی شدند تا حقی ضایع نشود.

 

تیم‌های زیر برنده جوایز شدند:

تیم اول ـ ۴۸۱۵۱۶۲۳۴۲ ـ برنده ۲ تی‌شرت کوئرا + ۲ ماگ کوئرا +‌ ۲ هلیکوپتر کنترل از راه دور

تیم دوم ـ Monsters ـ برنده ۲ تی‌شرت کوئرا + ۲ ماگ کوئرا +‌ ۲ اسپیکر گلدان هوشمند (Smart Music Flowerpot)

تیم سوم ـ کام شاد ـ برنده ۲ تی‌شرت کوئرا + ۲ ماگ کوئرا

تیم دهم ـ asdf – برنده ۲ تی‌شرت کوئرا + ۲ ماگ کوئرا

تیم بیست و ششم ـ thinker – برنده ۲ تی‌شرت کوئرا + ۲ ماگ کوئرا

تیم شصت و نهم ـ relentless logic – برنده ۲ تی‌شرت کوئرا + ۲ ماگ کوئرا

 

جایزه ویژه ـ تو کدکاپ ـ برنده ۲ تی‌شرت کوئرا + ۲ ماگ کوئرا +‌ ۲ اسپیکر گلدان هوشمند (Smart Music Flowerpot)

این تیم سوال‌های مسابقه را به ترتیب با زبان‌های JavaScript , Python 2 , Ruby , Python 3 , Java , C , CPP حل کرده بود.

 

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

سوال اول  ـ مشق امشب باقر

کافیست چک کنیم که اعداد ورودی بیشتر از صفر و همچنین دارای مجموع ۱۸۰ باشند.

کد  Haskell از تیم Pneumonoultramicroscopicsilicovolcanoconiosis

کد  Perl از تیم mina

کد  JavaScript از تیم توکدکاپ

کد Python 3 از تیم Nioh

سوال دوم ـ خب باقر سرما خورده

کافیست به ازای هر پنج حرف متوالی از هر رشته چک کنید که این پنج حرف “HAFEZ” یا “MOLANA” هستند یا خیر.

کد C++

کد  Swift از تیم Qwerty

کد  PHP از تیم ته دیگ

کد Python 3 از تیم Scorpion

 

سوال سوم ـ  باقر خسته‌ست ولی بی‌فرهنگ نه

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

کد Java

کد  Python 2 از تیم SBAY

کد  C Sharp Mono از تیم RikiCoders

کد Python 3

 

سوال چهارم ـ باقر مخالف است

برای این سوال ما عدد n رقمی داده‌شده را به شکل یک دنباله n عضوی نگاه می‌کنیم.

فرض کنیم تمام دنباله‌هایی که با این  n عدد می‌توان نوشت را به ترتیب لغت‌نامه‌ای(Lexicographic) مرتب کرده‌ایم.

حال مسئله به این تبدیل شد که با گرفتن یک دنباله، دنباله بعدی آن را در صورت وجود چاپ کنیم.

برای اینکار در زبان  C++ تابعی آماده وجود دارد که البته این تابع برای زبان‌های دیگر مانند پایتون هم موجود است.

کد C++

کد  Python 3 از تیم FORK

 

سوال پنجم ـ باقر حال نداره ولی پول داره

ایده اصلی این سوال، برنامه‌نویسی پویا است.

DP[pos][need] را اینگونه تعریف می‌کنیم‌: جواب بهینه برای حالتی که بخواهیم مجموع مساحت  need را با pos تا کاشی اول بسازیم.

با کمی بررسی متوجه می‌شویم که DP[pos][need]  برابر مینیمم عبارت:

DP[pos - 1][need - i * i] + (a[i] - i)^2

به ازای i های از صفر تا ۱۰۰ است به شرطی که  i \times i \le need .

در واقع  i را طول کاشی آخر است که آن را تثبیت می‌کنیم و به سراغ کاشی های قبلی می‌رویم.

در کل پیچیدگی زمانی برابر شد با:  O(n \times m \times max(a_i))

کد  Java

کد  C++ با رویکرد ممویزد

 

سوال ششم ـ نمی‌شه که همه کارها رو باقر بکنه

جایگشتی که معلم به باقر می‌دهد را با A نشان می‌دهیم.

نکته اینست که پس از حذف کردن، دنباله جواب نهایی ما عدد تکراری ندارد چون از ابتدا A عدد تکراری نداشته است.

حال هر عددی از ۱ تا n  دنباله‌های باقر موجود نبود را ستونش را حذف می‌کنیم.

در طول این حذف کردن‌ها ممکن است بازهم اعدادی به طور کلی از دنباله‌های باقر حذف شوند که ستون آن‌ها را هم حذف می‌کنیم و به همین روال ادامه می‌دهیم تا متوقف شویم.

واضح است که عمل بالا پایان پذیر است چون هر ستون تنها یکبار می‌تواند حذف شود و ستون‌ها محدود هستند.

در کل پیچیدگی زمانی برابرست با  O(n)

 

سوال هفتم ـ باقر جابه‌جا می‌کند

میتوانیم ساختار جایگشت را مثل یک درخت دودویی در نظر بگیریم. ما هر عضو دنباله مانند  p_i را با راس  i ام درخت متناظر می‌کنیم.

همچنین راس  i ام را به راس های  i \times 2 + 1 و  i \times 2 وصل می‌کنیم و این راس را پدر راس‌های i \times 2 و i \times 2 + 1 می‌نامیم.

به عنوان مثال گراف جایگشت نمونه سوال در ابتدا به صورت زیر خواهد شد:

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

برای راس هایی که فرزند چپ پدرشان هستند از راس ۲  تا راس  n الگوریتم زیر را انجام می‌دهیم‌:

 

راس  i ام را  Right , راس  i + 1 ام را  Left می‌نامیم و راس  i / 2 که پدر این دو راس است را با  par نشان می‌دهیم.

بسته به  Right Left Par  سه حالت زیر پیش می‌آید:

 

حالت اول ـ  Par \le Right و  Par \le Left :

در این حالت هیچ جابه‌جایی برای  Right و  Left که عنصرهای  i و  i + 1 جایگشت هستند نباید انجام شود چون در اینصورت به جواب بهینه‌تری می‌رسیم.

 

حالت دوم ـ   Left \le Right و  Left \le Par :

در این حالت باید  Left که عنصر  i ام است جایش با  i / 2 عوض شود تا به جواب بهینه برسیم و برای اینکه  i در جایگاه پدرش باقی  بماند  i + 1 نباید عوض شود.

 

حالت سوم ـ Right \le Left و  Right \le Par :

این حالت اندکی با حالات بالا تفاوت دارد و پیچیدگی کار را بیشتر می‌کند. مانند بالا چیزی که در این حالت بدیهی است این است که  Right باید در جایگاه پدر قرارا بگیرد. پس تعویض  i + 1 با  i / 2 باید انجام شود.

اما مسئله اینجاست که آیا بین  i و  i / 2 هم تعویضی انجام شود یا خیر؟

اعدادی که در ابتدا روی رئوس    Left  و   Par نوشته شده بودند را به ترتیب   a و  b می‌نامیم. اکنون باید انتخاب کنیم که در جایگشت نهایی،  a در زیر درخت  Left استفاده شود و  b در زیردرخت  Right و یا برعکس. از این جهت همین روش حریصانه‌ای که برای انتخاب اعداد داریم استفاده می‌کنیم را برای ادامه‌ی کار در این زیردرخت‌ها انجام می‌دهیم. به این شکل که بین  a و  b آن عنصری که کوچکتر است اگر به زیر درخت راست پدر برود در در چه ارتفاعی قرار می‌گیرد و اگر به زیر درخت چپ پدر برود در چه ارتفاعی قرار می‌گیرد. مانند الگوریتم   dfs ، طوری زیردرخت را پیمایش می‌کنیم تا جایی که عدد کوچکتر بین   a و   b که از هر دو بچه‌ی یک رأس کوچکتر شود. البته باید به نکات ریزی هنگام پیاده‌سازی توجه شود، مثلاً اگر در یک رأسی بچه‌ی سمت چپ کوچکتر از بچه‌ی سمت راست بود، زیردرخت سمت راست آن بچه نمی‌تواند بین گزینه‌های ما برای گذاشتن عدد باشد.

فرض کنیم درصورتی که به راست برود در ارتفاع h_r و اگر به چپ برود در ارتفاع h_l قرار می‌گیرد.

اگر داشتیم  h_r > h_l ، باید عدد کوچکتر بین a و   b در سمت راست قرار گیرد وگرنه در سمت چپ.

10 دیدگاه در “راه‌حل‌ها و نتایج مسابقه مقدماتی کدکاپ ۳

  1. مصطفی می‌گوید:

    با سلام
    لطفا در خصوص صورت سوال “هفتم ـ باقر جابه‌جا می‌کند” واضح تر توضیحاتی ارائه دهید. متاسفانه سوال را متوجه نمی شویم

  2. محمدامین رییسی می‌گوید:

    یه راهی که برای سوال “نمیشه همه کارها رو باقر بکنه” اینه که ابتدا دنباله ی اولو a و دومی رو b و سومی رو c در نظر بگیرید. یک گراف جهتدار (که خروجی هر راس ۱ است) بدین صورت با جایگشت های a و b متناظر می کنیم که عدد i ام از دنباله ی a تو گراف به عدد i از دنباله ی b یال داشته باشد …
    حالا تمام دورهای دو به دو مجزا رو پیدا کنیم تو این گراف (درجه ی خروجی رئوس یک است پس به سادگی میتوان این کار را کرد) و دوباره تو این لیسته بیایم با دنباله ی c هم یه همچین کاری بکنیم و این بار مجموع طول دورهای دو به دو مجزای گراف را پیدا و n رو ازون کم کنیم :))
    https://paste.ubuntu.com/25672898/

  3. Din0 می‌گوید:

    سلام
    من در مرحله دستگرمی و مقدماتی با یک تیم بودم و الان تیمم رو عوض کردم
    الان میتونم با تیم جدیدم مسابقه بدم

    • امیرحسین می‌گوید:

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

Leave a comment

نشانی ایمیل شما منتشر نخواهد شد. بخش‌های موردنیاز علامت‌گذاری شده‌اند *