خداروشکر مسابقه‌ی شماره ۴ به خوبی برگزار شد. از تمام کسانی که در مسابقه شرکت کرده‌اند سپاس گزاریم.
راه حل‌های این مسابقه را می‌توانید در ادامه‌ی مطلب ببینید.
پرسش نخست، حدس عدد
راه حل ۱
اعداد ورودی زیرمجموعه ای از مقسوم علیه‌های عدد n است. به ازای تمام اعداد ۱ تا n میتوان مقسوم علیه‌هایش را حساب کرده و بررسی کرد آیا اعداد ورودی زیرمجموعه‌ای از آن است یا خیر.
راه حل ۲
n حتما بر ک.م.م اعداد ورودی بخش پذیر است. با کمک این میتوان مسئله را حل کرد.
پرسش دوم، دیدار دوست
با توجه به ویژگی ناحیه‌های صفرقند، محمدمهدی مجبور است از مرز یک ناحیه عبورکند اگر و تنها اگر یکی داخل این ناحیه باشند و دیگری نباشد.
با کمک این شهود میتوان مسئله را به سادگی حل کرد.
پرسش سوم، محمدمهدی و LIS
لم، اگر i < j و d_i \geq d_j، آنگاه a_i > a_j.
با کمک این لم اگر زیردنباله‌ای نزولی از d_i داشته باشیم، زیردنباله با همین اندیس‌ها در دنباله‌ی اصلی اکیدا نزولی است!
پس اگر بزرگترین زیردنباله‌ی نزولی ورودی x باشد، پاسخ بزرگتر مساوی x است.
حال بیابید دنباله‌ای بسازیم که بزرگترین زیردنباله‌ی نزولی آن x باشد.
i ها را به شیوه‌ی زیر مرتب می‌کنیم: اول آنهایی که d_i] اشان ۱ است، سپس آنهایی که d_i] شان ۲ هست و …، همچنین اگر چند i داشتیم که d_i] آنها یکسان بود را به صورت نزولی مرتب می‌کنیم.
حال اگر در این مرتب سازی جایگاه i را a_i در نظر بگیرید. دنباله‌ی a_1, a_2, ..., a_n چنین دنباله‌ای است!
پرسش چهارم، قتل عام
مسئله امیدریاضی وزن‌هایی که کشته می‌شوند را می‌خواهد.
a_i را امید ریاضی مجموع وزن‌ها اگر اسکل i شروع کننده‌ی قتل عام باشد و s_i را مجموع امیدریاضی فرزندان i تعریف می‌کنیم. مقدار a_i و s_i برای اسکل‌های بی‌بچه صفر است و برای بقیه‌ی اسکل‌ها به سادگی از روی مقادیر بچه‌هایشان قابل ساختن است. به این شیوه که اگر مجموعه بچه‌های i، C_i باشد،
s_i = \sum_{v \in C_i}{a_v}
a_i = \frac{1}{|C_i|} \times \sum_{v \in C_i}{w_v + s_v + s_i-a_v}
است. که با هر کدام از الگوریتم های پیمایش درخت قابل حل است. پاسخ مسئله نیز برابر با a_1 است.
پرسش پنجم، جدول رنگی
یکی از راه‌حل‌های این مسئله 2SAT است. لازمه‌ی فهمیدن راه حل بلد بودن 2SAT و روش‌های آن است.
جدول را گرافی با 2n راس در نظر میگیریم، هر کدام از سطر ها و ستون ها را یک راس از این گراف و یال‌های این گراف یک رنگ و یک شماره دارند. راس سطر i به راس سطر j یالی به رنگ c و شماره‌ی x دارد اگر و تنها اگر رنگ خانه‌ی (i, j) برابر c و شماره‌ی آن x باشد.
حال مسئله به مسئله‌ی مقابل متناظر می‌شود: یک گراف داریم، می‌خواهیم یک تطابق از آن انتخاب کرده، به طوری که با حذف یال‌های تطابق، رنگ‌آمیزی یالی گراف، یک رنگ آمیزی معتبر باشد، یعنی دویال همرنگ به یک راس وصل نباشد. همچنین بزرگترین عدد روی یال‌های تطابق کمینه باشد.
حال بیایید مسئله‌ی جدید را حل کنیم. (تعداد یال‌ها را با E و تعداد راس‌ها را با V نشان می‌دهیم)
می‌توانیم روی بزرگترین عدد یال انتخاب شده باینری سرچ بزنیم، فرض کنید این عدد w است.
حال متغیر‌های x_1, x_2, ..., x_E را در نظر بگیرید. اگر یال i را در تطابق انتخاب کردیم x_i = 1 و در غیر اینصورت x_i = 0 در نظر میگیریم.
اولا اگر راسی بیش از ۳ یال همرنگ داشت، پاسخ برابر No است. اما اگر دو یال مثل g, h داشت که همرنگ بودند، باید حتما یکی انتخاب شود یعنی شرط x_g \lor x_h باید برقرار باشد.
دوما، اگر یال‌های متصل به راسی مانند u، e_1, e_2, ..., e_k باشند، باید مطمئن شویم که هیچ زوج (i, j) که 1 \leq i < j \leq k ای وجود نداشته باشند که x_{e_i} = x_{e_j} = True باشد.
یک راه برای پیاده سازی شروط دوم، اضافه کردن متغیر‌های y_1, y_2, ..., y_k و اطمینان حاصل کردن از اینکه برای هر i \leq j ، x_{e_i} \rightarrow y_j است. برای این ما می‌توانیم برای هر y_i دو شرط زیر را اضافه کنیم: \neg x_{e_i} \lor y_i و \neg y_{i-1} \lor y_i است.
و در اخر بررسی شرط \neg y_i \lor \neg x_{e_{i+1}} برای اینکه مطمئن شویم دویال متصل به یک راس انتخاب نمی‌شوند.
که با این کار تعدا شروط و متغیر‌ها از O(E+V) و بررسی آن با 2SAT و به کمک الگوریتم SCC نیز از O(E+V) است.
پس زمان الگوریتم در کل O(\lg 10^9 \times (E+V)) خواهد بود.
کد‌های پرسش‌ها
پرسشی بود در بخش نظرات بپرسید.
باسپاس و التماس دعا
