راه‌حل‌های مسابقه‌ شماره‌ ۲۰

سلام!

امیدواریم که از سوال‌ها خوشتان آمده باشد!

با عرض پوزش از تاخیر بوجود آمده در انتشار پاسخ‌ها، این هم از پاسخ‌ها.

بخونید و یاد بگیرید و لذت ببرید 🙂

در صورتی که متوجه راه‌حلی نشدید یا راه‌حلی دیگر برای یک سوال دارید، در بخش نظرات مطرح کنید.

• وسیله کمک آموزشی

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

  کد ++C از علی توسلی

  کد Java از پارسا عالیان

  کد Python 3 از رضا باقی

• کلاس تقویتی

  این سوال با الگویابی به راحتی حل می‌شود، هر چند می‌توان برای آن روابطی بازگشتی نیز نوشت که ساده‌شده‌ی همه‌ی آن‌ها همان جواب بدست آمده از الگویابی است. البته برای درست بودن پاسخ الگویابی اثبات نیز ارائه می‌دهیم.

  با الگویابی به سادگی به دست می‌آید که پاسخ همیشه n-1 است مگر برای n = 2 و n = 1 .

  اثبات: با فرض این‌که n>2 باشد، همیشه کاراکتر کمکی ۱ در نیمکت ۱ و کاراکتر کمکی ۲ در نیمکت n می‌نشینند و نیمکت n - 1 پس از نشستن کاراکتر کمکی ۱ و کاراکتر کمکی ۲ خالی است. فاصله‌ی نیمکت n - 1 تا نزدیک‌ترین نیمکت پر (نیمکت n) بعد از نشستن دو نفر اول صفر است. حال اگر فرض کنیم کسی قبل از کاراکتر کمکی n روی نیمکت n - 1 بنشیند، از آنجایی که با این فرض حتما بیش از یک نیمکت خالی برای انتخاب آن فرد وجود دارد، پس بایستی یا نیمکتی با فاصله‌ی کمتر از نیمکت n-1 تا اولین نیمکت پر وجود داشته باشد (که امکان ندارد، چون کمینه فاصله‌ی دو نیمکت ۰ است)، یا نیمکتی با فاصله‌ی ۰ تا نزدیک‌ترین نیمکت پرش وجود داشته باشد که شماره‌اش از n - 1 بیشتر باشد (که این هم امکان ندارد، تنها نیمکتی که شماره‌اش از n - 1 بیشتر است نیمکت n است که قبلا توسط کاراکتر کمکی ۲ پر شده است). در نتیجه می‌توانیم بگوییم حتما کاراکتر کمکی n روی نیمکت n - 1 می‌نشیند چون مخالف این گزاره طبق اثباتی که کردیم امکان ندارد. در حالت‌های n = 1 و n = 2 هم به ترتیب پاسخ صحیح برابر ۱ و ۲ است.
  کد ++C از علی اسدی

  کد Java از علی سلمانی

  کد Python 3 از علی‌پاشا منتصری

• میان‌ترم هندسه

  پس از حرکت‌دادن مهره توسط هر یک از دو بازیکن، زوجیت فاصله‌ی دو مهره تغییر می‌کند. این یعنی همیشه پس از حرکت دادن مهره توسط کاراکتر کمکی ۱، زوجیت فاصله‌ی دو مهره مقدار ثابت X و نیز همیشه پس از حرکت دادن مهره توسط کاراکتر کمکی ۲، زوجیت فاصله‌ی دو مهره ثابت Y است.

  با بررسی ساده‌ای متوجه می‌شویم فاصله‌ی دو مهره باید ۰ باشد تا بازی تمام شود و یک نفر برنده داشته باشیم، چرا؟ چون در صورت سوال تضمین شده است که با حرکت دادن ۱ مهره (بدون حضور مهره‌ی دیگر در صفحه) می‌توان از هر دایره‌ی صفحه به هر دایره‌ی دیگری از آن رسید، از این گزاره می‌توان نتیجه گرفت، هر دایره حداقل به یک دایره‌ی دیگر متصل است و برای این‌که یک مهره نتواند حرکت کند بایستی تنها دایره‌ی همسایه‌ی یکی از دایره‌هایی که فقط یک همسایه دارد، پر باشد.

  مقادیر ثابت X  و Y در طول مسئله تغییری نمی‌کنند و از روی آرایش ابتدایی مهره‌ها در صفحه می‌توان آن‌ها را بدست آورد، چیزی که در بالا فهمیدیم هم این است که اگر بازی استراتژی برد داشته باشد (اثبات خواهیم کرد چرا حتما استراتژی برد دارد) فاصله‌ی دو مهره در حرکت پایانی بازی ۰ است. به عبارت دیگر زوجیت فاصله‌ی دو مهره در حرکت پایانی، زوج است. پس اگر بازی استراتژی برد داشته باشد، اگر X زوج باشد، کاراکتر کمکی ۱ استراتژی برد دارد و اگر Y زوج باشد، کاراکتر کمکی ۲ استراتژی برد دارد.

  چرا بازی حتما استراتژی برد دارد؟ باید مطمئن باشیم کسی که نمی‌تواند بازی را ببرد، نمی‌تواند کاری کند که بازی را نبازد. اگر کسی که راهبرد دارد به سمت کسی که راهبرد ندارد برود و به او نزدیک شود تا جایی که او را در یک دایره با ۱ همسایه گیر بیاندازد، بازی را می‌برد. چرا این‌کار همیشه ممکن است؟ زمانی که نوبت کسی که راهبرد دارد می‌رسد تا مهره‌اش را حرکت دهد، حتما می‌تواند مهره‌اش را به سمت مهره‌ی حریف تکان دهد، چون زوجیت فاصله‌ی دو نفر فرد است و این یعنی ۰ نیست. تنها چیزی که می‌ماند و اثبات نکردیم این است که چرا بازی تا ابد ادامه پیدا نمی‌کند که برای درک آن نیاز است کمی نظریه گراف بدانید. اگر کنجکاو هستید درباره‌ی نظریه‌ی گراف مطالعات بیشتری داشته باشید، پیشنهاد می‌کنیم به اینجا مراجعه کنید.

  برای یافتن فاصله‌ی بین دو مهره در ابتدا، از یکی از دو الگوریتم معمول جستجوی عمق‌اول و جستجوی سطح‌اول استفاده‌ می‌کنیم.

  کد ++C از آرش محمودیان بیدگلی

  کد Java از محمد مقدسی

  کد Python 3 از علی‌ صفری

• پایان‌ترم هندسه

  برای محاسبه‌ی پاسخ از برنامه‌نویسی پویا بهره می‌گیریم. متغیری به نام ans را برای محاسبه‌ی پاسخ مسئله در صورتی که برگه‌های i تا n را بجای کل برگه‌ها داشته باشیم در نظر می‌گیریم. اگر ans=0 باشد به معنی این است که بازی با نتیجه‌ی مساوی پایان خواهد یافت، اگر ans>0 باشد یعنی کاراکتر کمکی ۱ بازی را می‌برد و اگر ans<0 باشد یعنی کاراکتر کمکی ۲ بازی را می‌برد و \left |ans \right | نشان‌دهنده‌ی بیشینه اختلاف تضمین شده برای فردی است که استراتژی برد دارد.

  محاسبه‌ی ans وقتی i=n  است ساده است. از i=n-1 به بعد اگر برگه‌ی i را نفر اول انتخاب کند، در این‌صورت نفر دوم می‌تواند به اندازه‌ی ans امتیاز بگیرد پس می‌توانیم ans جدید را با توجه به امتیاز جدید دو نفر حساب کنیم. اگر برگه‌ی i را نفر اول انتخاب نکند، پس باید قبل از این برگه‌، برگه‌ی دیگری را انتخاب کرده باشد که به اندازه‌ی ans اختلاف امتیاز ایجاد می‌کند. پس پاسخ را برای هر دو حالت موجود می‌توانیم به دست بیاوریم، هر کدام از این دو حالت که برای کاراکتر کمکی ۱ بهتر بود را انتخاب می‌کنیم و ans جدید را در هر مرحله تولید می‌کنیم. در حالت i=1 متغیر ans برابر پاسخ مسئله است.

• نمرات شرم‌آور

  آرایه‌ای از نوع عدد به نام t را این‌گونه تعریف می‌کنیم: اگر iامین عدد اول p باشد، آن‌گاه تعداد نمراتی که بر p بخش‌پذیرند را در t[i] ذخیره می‌کنیم.

  آرایه‌ای از نوع عدد به نام b را این‌گونه تعریف می‌کنیم: اگر iامین عدد اول p باشد، آن‌گاه تعداد نمراتی که اگر آن‌ها را یکی زیاد کنیم بر p بخش‌پذیر می‌شوند را در b[i] ذخیره می‌کنیم.

  تمام اعداد اول ۱ تا 10^6 را به کمک غربال اراتستن بدست می‌آوریم، سپس مقادیر t و b را به ازای اعداد اول بدست‌ آمده حساب می‌کنیم. با توجه به t و b که به دست آوردیم می‌توان بدست آورد کمینه هزینه برای تبدیل لیست نمرات به لیست نمرات جدید طوری که ب.م.م نمرات جدید بر p بخش‌پذیر باشد چقدر است.

  پاسخ مسئله برابر است با کمینه هزینه از بین هزینه‌ی حالتی که لیست جدید تهی باشد، و تمامی کمینه هزینه‌های بدست آمده.

• شهریور خونین

  درخت را از راس ۱ آن، ریشه‌دار می‌کنیم. در ادامه هرجا از P_i صحبت کردیم، منظور احتمال زنده ماندن کاراکتر اصلی ۱ در راس i است.

  به ازای هر راس v (به‌ جز راس ۱) اگر پدرش را u در نظر بگیریم، می‌توان P_v را بر حسب P_u نوشت. P_v=a.P_u+b (توجه کنید P_v بر حسب P_u خطی است، پس حتما چنین a و bای وجود دارند.)

  حال که احتمال زنده‌ ماندن کاراکتر اصلی ۱ در هر راس را بر حسب احتمال زنده‌ ماندن او در راس پدرش نوشتیم می‌توانیم کار محاسبه را بطور بازگشتی آغاز کنیم. اگر یک راس فرزندی داشته باشد ابتدا نیاز است احتمال زنده‌ ماندن را برای آن حساب کنیم و اگر یک راس فرزندی نداشته باشد (برگ باشد) در صورتی که در این راس کسی کمین کرده باشد P_v=0.P_u+0 را داریم و اگر کسی در این راس کمین نکرده باشد،‌ P_v=0.P_u+1 را داریم.

  اگر فرزند iام راس v را c_i بنامیم، داریم: \Large P_v=\frac{(\sum_{i=1}^{deg_v} P_{c_i}) + P_u}{deg_v}

  با استفاده از رابطه‌ی بالا، در حین انجام عمل بازگشتی P_{c_i}ها را با a.P_v+b جایگزین می‌کنیم که به ما رابطه‌ای برحسب P_v و P_u می‌دهد.

  در آخر با توجه به این‌که برای تمام فرزندان راس ۱، احتمال را برحسب خود راس ۱ داریم، پس با حل دستگاه ۱ معادله ۱ مجهول، می‌توانیم احتمال زنده ماندن در خود راس ۱ را نیز بدست آوریم.

• ثانیه‌های آخر

  dp[i][j][k] را تعریف می‌کنیم: طول بلندترین مسیر با شروع از راس i در زیردرخت 2^jامین پدر i به طوری که از kامین فرزند i نگذریم. واضح است چگونه از روی dp می‌توان پاسخ مسئله را بدست آورد.

  برای بدست‌آوردن مقادیر dp مانند پر کردن مقادیر dp در الگوریتم تارجان برای پیداکردن پایین‌ترین جد مشترک عمل می‌کنیم.

• انتقام پدر

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

  لم: در یک مولفه‌ی دوهمبند به ازای هر دو راس و یال، گذری بین دو راس هست که از یال مذکور بگذرد.

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

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

  حال سوال را بازنویسی می‌کنیم: در گراف H هر راس یک عدد دارد. عدد رئوس در ابتدا نشان‌دهنده‌ی تعداد رئوس زیرگراف متناظر با راس در G است. در هر بار عمل سفت‌سازی یا یک یال قرمز می‌شود یا یک راس. مجموعه‌ای از رئوس با بیشترین وزن (منظور از وزن در اینجا مجموع اعداد رئوس مجموعه است) را می‌خواهیم که بین هر دو راس آن یا مسیر نباشد، یا مسیری بدون یال و راس قرمز باشد.

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

  پیچیدگی زمانی راه حل: O(m+n \log n)

  پیچیدگی حافظه‌ی راه حل: O(n \log (n+m))