راه‌حل‌های سؤالات مسابقه الگوریتمی ACM-ICPC Challenge در ادامه توضیح داده شدند. در صورتی که متوجه راه‌حلی نشدید، می‌تونید در بخش نظرات، سؤالات و ابهام‌های خودتون رو مطرح کنید. اگه راه‌حل دیگه‌ای برای سؤالات دارید، خوشحال می‌شیم که راه‌حلتون رو در بخش نظرات با ما و دوستانتون به اشتراک بذارید.
جواب سؤال valid است اگر به ازای هر ماده (A یا B یا +) در گروه خونی فرزند، آن در حداقل یکی از والدین باشد. نوعی از پیاده‌سازی تمیز و سریع آن است که به هر گروه خونی یک عدد ۳ بیتی نسبت دهیم که بیت‌های آن به ترتیب نشان دهند که ماده A و B و + در گروه خونی هست یا نه. حال اگر عدد متناظر با گروه خونی پدر, مادر و فرزند به ترتیب dad و mom و son باشد، داریم:
((mom \lor dad) \land son == son) \Leftrightarrow valid
پیچیدگی زمانی: \mathcal{O}(t)
حداقل درصد مأمور مخفی‌ها:
برای حالت n=1 که بدیهی است. اگر دو طرح با درصدهای x و y داشته باشیم آنگاه پاسخ مشخصا برابر \max(0,x+y-100) است. حال اگر n طرح داشته باشیم. می‌توانیم جواب را برای n-1 طرح اول حساب کنیم(آن را ans_{pre} در نظر می‌گیریم.) و جواب مشابهاً برابر max(0,ans_{pre}+p_n-100) است. بنابرین جواب برابر است با
\max(0, \sum_{i=1}^n{p_i} - (n-1) \times 100)حداکثر درصد مأمور مخفی‌ها:
ثابت می‌کنیم پاسخ این بخش برابر کمینه اعداد است.(آن را m در نظر بگیرید.) مشخصاً پاسخ از m بیشتر نمی‌تواند باشد چرا که یک طرح m درصد موافق داشته‌است. همچنین ممکن است m درصد افراد به همه طرح‌ها رای مثبت داده باشند.
پیچیدگی زمانی: \mathcal{O}(n)
فرض کنید می‌خواهیم جواب را برای i محاسبه کنیم. می‌دانیم شیر ظروف i+1, i+2, \dots, n به طور یکسان بین ظروف 1,2,\dots,i توزیع شده‌است. پس داریم:
ans_i = \frac{\sum_{k = i+1}^n{a_k}}{i} + a_iبرای محاسبه \sum_{k = i+1}^n{a_k} نیز (آن را S_i بنامید.) داریم:
S_n = 0, \space S_i = S_{i+1}+a_{i+1} (i < n)پیچیدگی زمانی: \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-مکزیکی است. طبق صورت مسئله جواب برابر
\max(ans_1, ans_2, \dots, ans_n)
است. برای محاسبه 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} بلوک دارد.
همچنین مشابه تحلیل مرتبه الگوریتم غربال اعداد اول داریم:
\sum_{i=1}^n{\mathcal{O}(\frac{n}{i})} = \mathcal{O}(n\log(n))پیچیدگی زمانی: ( N = \sum n_i)
قصد داریم سؤالی کلی‌تر را حل کنیم. آرایه‌ای از اعداد داریم و هر مرحله یک عنصر عوض می‌شود. حال بزرگترین جمع زیربازه‌ای از آرایه چقدر است؟ برای تبدیل سؤالات هم به هم کافی است در خانه‌های آبی -a_i و در خانه‌های قرمز a_i قرار دهیم.
برای حل سؤال از الگوریتم درخت-بازه‌ای (segment-tree) استفاده می‌کنیم و برای هر گره در درخت ۴ چیز نگه می‌داریم: جمع کل, جمع بزرگترین زیر بازه, جمع بزرگترین پیشوند و جمع بزرگترین پسوند. (آن‌ها را به ترتیب با sum ، max_{all} ، max_{pre} و max_{suf} نشان می‌دهیم.) حال برای ادغام دو گره متوالی L و R داریم:
sum = L_{sum}+R_{sum}
\\
max_{all} = \max(L_{max_{all}}, R_{max_{all}}, L_{max_{suf}}+R_{max_{pre}})
\\
max_{pre} = \max(L_{max_{pre}}, L_{sum}+R_{max_{pre}})
\\
max_{suf} = \max(R_{max_{suf}}, R_{sum}+L_{max_{suf}})برای عوض کردن یک خانه کافی است همه بازه‌های شامل آن خانه را به‌روزرسانی کنیم و مقدار 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 قرار می‌دهیم.
نحوه به دست آمدن این دو متغیر چنین است:
L_{v,0} = R_{v,0} = v
\\
L_{v,h} = max_{element}(\{ L_{u,h-1} | u \in N(v), R_{u,h-1} < v \})
\\
R_{v,h} = min_{element}(\{ R_{u,h-1} | u \in N(v), L_{u,h-1} > v \})همچنین توجه کنید که اگر h > \log n آنگاه درخت کامل دودویی از هیچ راسی به ارتفاع h وجود ندارد.
در نهایت پاسخ مسئله مشخصاً
max_{element}(\{ 2^{h+1}-1 | 1 \le v \le n, L_{v,h} > 0\}خواهد بود. (توجه کنید درخت دودویی کامل به ارتفاع h، 2^{h+1}-1 راس دارد.)
پیچیدگی زمانی: \mathcal{O}(n \times \log n)
امیدورام راه‌حل‌ها مفید بوده باشه. اگر پیشنهاد یا سؤالی داشتین، حتما در نظرات مطرح بفرمایید.
