راه‌حل‌های مسابقه الگوریتمی ACM-ICPC Challenge

راه‌حل‌های سؤالات مسابقه الگوریتمی ACM-ICPC Challenge در ادامه توضیح داده شدند. در صورتی که متوجه راه‌حلی نشدید، می‌تونید در بخش نظرات، سؤالات و ابهام‌های خودتون رو مطرح کنید. اگه راه‌حل دیگه‌ای برای سؤالات دارید، خوشحال می‌شیم که راه‌حلتون رو در بخش نظرات با ما و دوستانتون به اشتراک بذارید.

گروه خونی

جواب سؤال $valid$ است اگر به ازای هر ماده ($A$ یا $B$ یا $+$) در گروه خونی فرزند‌، آن در حداقل یکی از والدین باشد. نوعی از پیاده‌سازی تمیز و سریع آن است که به هر گروه خونی یک عدد ۳ بیتی نسبت دهیم که بیت‌های آن به ترتیب نشان دهند که ماده $A$ و $B$ و $+$ در گروه خونی هست یا نه. حال اگر عدد متناظر با گروه خونی پدر, مادر و فرزند به ترتیب $dad$ و $mom$ و $son$ باشد، داریم:

پیچیدگی زمانی: $\mathcal{O}(t)$

---

مامور مخفی

حداقل درصد مأمور مخفی‌ها:
برای حالت $n=1$ که بدیهی است. اگر دو طرح با درصدهای $x$ و $y$ داشته باشیم آنگاه پاسخ مشخصا برابر $\max(0,x+y-100)$ است. حال اگر $n$ طرح داشته باشیم. می‌توانیم جواب را برای $n-1$ طرح اول حساب کنیم(آن را $ans_{pre}$ در نظر می‌گیریم.) و جواب مشابهاً برابر $max(0,ans_{pre}+p_n-100)$ است. بنابرین جواب برابر است با

حداکثر درصد مأمور مخفی‌ها:
ثابت می‌کنیم پاسخ این بخش برابر کمینه اعداد است.(آن را $m$ در نظر بگیرید.) مشخصاً پاسخ از $m$ بیشتر نمی‌تواند باشد چرا که یک طرح $m$ درصد موافق داشته‌است. همچنین ممکن است $m$ درصد افراد به همه طرح‌ها رای مثبت داده باشند.

پیچیدگی زمانی: $\mathcal{O}(n)$

---

شیر تو شیر

فرض کنید می‌خواهیم جواب را برای $i$ محاسبه کنیم. می‌دانیم شیر ظروف $i+1, i+2, \dots, n$ به طور یکسان بین ظروف $1,2,\dots,i$ توزیع شده‌است. پس داریم:

برای محاسبه $\sum_{k = i+1}^n{a_k}$ نیز (آن را $S_i$ بنامید.) داریم:

پیچیدگی زمانی: $\mathcal{O}(n)$

---

کاغذ دیواری

اگر ستونی شامل دو پریز باشد آنگاه می‌توانیم سمت چپ و راست آن را جداگانه حل کنیم. پس در ادامه راه فرض می‌کنیم ستونی دو پریز ندارد و نیز اگر دیوار بدون پریز باشد جواب مسلماً ۱ است.

حال ادعا می‌کنیم به کاغذ دیواری با عرض ۲ نیاز نداریم, فرض کنید که کاغذ دیواری $2 \times k$ مفید باشد. توجه کنید یک طرف آن حداقل پریز قرار دارد. (در غیر اینصورت یا کلا پریز نداریم و یا کاغذ دیواری مد نظر می‌توانست $2 \times (k+1)$ باشد.) و می‌دانیم در ستونی که پریز هست یک خانه خالی هم هست که توسط کاغذ دیواری به ابعاد $1 \times l$ پوشانده شده. پس می‌توانستیم بدون تغییر کلیت کار بجای $2 \times k$ از $1 \times k$ و بجای $1 \times l$ از $1 \times (l+k)$ استفاده کنیم.

بنابرین تنها از پریزهای $1 \times u$ استفاده می‌کنیم و با این فرض کافی است تعداد قسمت‌هایی که پریزها روی هر سطر درست کرده‌اند را با هم جمع کنیم.

پیچیدگی زمانی: ($K = \sum k_i$)

---

موج مکزیکی

به موجی $k$-مکزیکی گوییم که افراد در بلوک‌های $k$ تایی ایستاده یا نشسته باشند. همچنین $ans_k$ برابر طول بلندترین زیردنباله موج $k$-مکزیکی است. طبق صورت مسئله جواب برابر

است. برای محاسبه $ans_k$ کاملاً حریصانه عمل می‌کنیم. کافی است به ازای هر $i$ که $1 \le i \le n$ موقعیت اولین مکانی از آرایه مانند $a_i$ که $i+2\times k \le a_i \le n+1$ را بدانیم به طوری که زیر دنباله $2k$ تایی شامل $k$ نفر نشسته در ابتدا و سپس $k$ نفر ایستاده در بازه $[i,a_i)$ موجود باشد. توجه کنید $a_i$ ممکن است برای برخی $i$ها وجود نداشته باشد. اگر $a_1$ تعریف شود $ans_k$ حداقل $2k$ است و نیز اگر $a_{a_1}$ تعریف شود آنگاه $ans_k$ حداقل $4k$ است و الی آخر $\dots$ (حالتی که با $k$ نفر ایستاده شروع شود مشابه است.)

اگر بدانیم هر کس چندمین فرد ایستاده (از سمت چپ) است و نیز مکان افراد ایستاده را در لیستی داشته باشیم آنگاه در $\mathcal{O}(1)$ می‌توانیم اولین مکان بعد از $i$ مانند $j$ که زیردنباله به طول $k$ از افراد ایستاده در بازه $[i,j)$ موجود است را پیدا کنیم. پس با کمی جزئیات پیاده‌سازی $a_i$ در $\mathcal{O}(1)$ قابل محاسبه است بنابرین $ans_k$ در زمان $\mathcal{O}(\frac{n}{k})$ قابل یافتن است چرا که $ans_k$ حداکثر $\frac{n}{2\times k}$ بلوک دارد.

همچنین مشابه تحلیل مرتبه الگوریتم غربال اعداد اول داریم:

پیچیدگی زمانی: ( $N = \sum n_i$)

---

نوار مش‌رجب

قصد داریم سؤالی کلی‌تر را حل کنیم. آرایه‌ای از اعداد داریم و هر مرحله یک عنصر عوض می‌شود. حال بزرگترین جمع زیربازه‌ای از آرایه چقدر است؟ برای تبدیل سؤالات هم به هم کافی است در خانه‌های آبی $-a_i$ و در خانه‌های قرمز $a_i$ قرار دهیم.

برای حل سؤال از الگوریتم درخت-بازه‌ای (segment-tree) استفاده می‌کنیم و برای هر گره در درخت ۴ چیز نگه می‌داریم: جمع کل, جمع بزرگترین زیر بازه, جمع بزرگترین پیشوند و جمع بزرگترین پسوند. (آن‌ها را به ترتیب با $sum$ ، $max_{all}$ ، $max_{pre}$ و $max_{suf}$ نشان می‌دهیم.) حال برای ادغام دو گره متوالی $L$ و $R$ داریم:

برای عوض کردن یک خانه کافی است همه بازه‌های شامل آن خانه را به‌روزرسانی کنیم و مقدار $max_{all}$ ریشه درخت هم هر بار پاسخ مسئله است.

پیچیدگی زمانی: $\mathcal{O}(n \times \log n)$

راه دیگر سؤال این است که آرایه را به بازه‌های $T$ تایی تقسیم کنیم و برای هر بازه ۴ مورد گفته شده را نگه داریم. حال برای تغییر یک خانه هزینه زمانی پیچیدگی $T$ دارد و برای پاسخ به بزرگترین جمع زیر بازه چنین عمل می‌کنیم: یا خانه ای که اخیراً قرمز شده جز جواب است یا جواب جواب قبلی هست. اگر خانه قرمز جز بزرگترین بازه باشد. کافی است بزرگترین پیشوند که عضو اول آن خانه جدید باشد و بزرگترین پسوند منتهی به خانه جدید را بدانیم که در زمان $T + \frac{n}{T}$ هر دو قابل محاسبه هستند و پیچیدگی کلی برابر
$\mathcal{O}(n \times (T + \frac{n}{T}))$
است که با جایگذاری $T = \sqrt n$ سؤال حل می‌شود.

---

عملیات سری کا. گ. ب.

برای هر راس در درخت مانند $u$، و ارتفاع $h$، $L_{u,h}$ را برابر بزرگترین مقدار ممکن برای کمینه عدد درخت جست‌وجو دودویی کامل به ارتفاع $h$ و با ریشه $u$ در نظر می‌گیریم. اگر چنین درختی وجود نداشت $L_{u,h}$ را $0$ قرار می‌دهیم. $R_{u,h}$ مشابهاً برابر کمترین مقدار ممکن برای بیشینه عدد درخت با مشخصات گفته شده است. و در صورت وجود نداشتن مقدار آن را $n+1$ قرار می‌دهیم.

نحوه به دست آمدن این دو متغیر چنین است:

همچنین توجه کنید که اگر $h > \log n$ آنگاه درخت کامل دودویی از هیچ راسی به ارتفاع $h$ وجود ندارد.

در نهایت پاسخ مسئله مشخصاً

خواهد بود. (توجه کنید درخت دودویی کامل به ارتفاع $h$، $2^{h+1}-1$ راس دارد.)

پیچیدگی زمانی: $\mathcal{O}(n \times \log n)$

امیدورام راه‌حل‌ها مفید بوده باشه. اگر پیشنهاد یا سؤالی داشتین، حتما در نظرات مطرح بفرمایید.