سلام دوست کوئرایی!
در این مطلب، به راه‌حل‌های سوالات مسابقه نهایی کدکاپ ۸ می‌پردازیم. اگر در این مسابقه شرکت کرده‌ای و سوال یا ابهامی درباره پاسخ سوالات داری، این بلاگ پست برای شماست.
با توجه به قوانین راه‌یابی به مرحله فینال که در صورت سؤال ذکر شده‌اند، برای هر تست کیس ورودی کافی است بررسی کنیم که آیا رتبه کل شرکت‌کننده در مسابقه بیشتر از ۴۰ نیست و یا این که حداقل یک مرحله از مسابقه وجود داشته باشد که شرکت‌کننده در آن، شرایط مورد نظر را داشته باشد. این شرایط شامل این است که شرکت‌کننده در استان خود رتبه اول شده باشد، حداقل ۲ سؤال را حل کرده باشد و تعداد شرکت‌کنندگان در آن استان حداقل ۷ نفر باشد.
پیچیدگی زمانی: \mathcal{O}(t)
در بررسی تعداد جاده‌های عمودی و افقی داده شده در ورودی، دو حالت ممکن است وجود داشته باشد:
حالت اول زمانی است که تعداد جاده‌های افقی و عمودی با هم برابر باشند. در این حالت، حداقل یک ثانیه تأخیر رخ خواهد داد زیرا هر گونه تنظیم حرکت‌ها منجر به برخورد دو ماشین می‌شود و در نتیجه یک تأخیر ایجاد می‌گردد.
به عنوان مثال، فرض می‌کنیم که اگر دو ماشین به صورت همزمان به یک تقاطع برسند، اولویت عبور با ماشینی است که از بالا به پایین حرکت می‌کند. در این صورت، ماشین‌های عمودی هرگز تأخیر نخواهند داشت. اما ماشین‌های افقی در طول مسیر خود حداکثر یک بار تأخیر خواهند داشت.
فرض کنید یک ماشین در مسیر افقی دو بار با ماشین‌های عمودی برخورد کند و در نتیجه دو تأخیر داشته باشد. از آنجا که ماشین‌های عمودی بدون تأخیر حرکت می‌کنند، پس از ایجاد تأخیر در اولین تقاطع، به مسیر خود ادامه می‌دهند و دیگر تأخیری ایجاد نمی‌کنند. بنابراین، ماشین‌ها به صورت موازی حداکثر یک تأخیر دارند و در نتیجه مجموع تأخیر‌ها برابر با یک خواهد بود. در این حالت، پاسخ برابر است با n+1 (با فرض اینکه n = m باشد).
در حالت دوم، اگر تعداد جاده‌های افقی و عمودی برابر نباشد و فرض کنیم n < m باشد، مشابه حالت قبل استدلال می‌شود که حداکثر یک تأخیر خواهیم داشت. این تأخیر را می‌توان بر روی ماشین‌های با مسیر کوتاه‌تر اعمال کرد. بنابراین، در این حالت، پاسخ برابر با زمان m خواهد بود.
پیچیدگی زمانی: \mathcal{O}(t)
بر اساس قوانین ذکر شده در صورت سؤال، هر استادی که در هر مکانی بنشیند، باعث ایجاد دو جفت خوشبختی می‌شود.
اگر دو استاد را در یک میز قرار دهیم، تمامی اعضا خوشحال خواهند بود و در نتیجه ۴ جفت خوشبختی ایجاد می‌شود.
حال اگر فرض کنیم n > m (و در غیر این صورت می‌توانیم n و m را با هم جابه‌جا کنیم)، می‌توانیم اعضای کوچکتر را به عنوان اساتید در نظر بگیریم، یعنی هر جا که قرار بگیرند، دو طرف آن‌ها خوشحال خواهند بود. زیرا به دلیل کمتر بودن تعداد اعضای گروه m، می‌توان آن‌ها را به گونه‌ای قرار داد که هیچ‌گاه دو نفر از اعضای گروه m کنار یکدیگر قرار نگیرند.
بنابراین، می‌توانیم تعداد اساتید را به صورت p' = p + m در نظر بگیریم و تعداد جفت‌های خوشحال برابر خواهد بود با 2 \times p'.
در نهایت، باید توجه داشت که اگر مقدار محاسبه‌شده بیش از کل تعداد جفت‌های خوشبختی ممکن باشد (به عنوان مثال، وقتی دو استاد کنار هم قرار بگیرند و دوبار شمرده شوند)، باید پاسخ را با 4 \times T که T تعداد میزها است و برابر با \frac{n + m + p}{4} است، مینیمم بگیریم.
پیچیدگی زمانی: \mathcal{O}(t)
ایده اصلی استفاده از الگوریتم DFS برای پیمایش درخت کدکاپ سیتی و استفاده از برنامه‌ریزی پویا برای پیدا کردن کمترین تعداد سکه‌ای است که تروریست نیاز دارد.
ابتدا درخت کدکاپ‌سیتی را ریشه‌دار می‌کنیم و دو آرایه dp_0 و dp_1 را برای محاسبه‌ی پاسخ تعریف می‌کنیم. در سناریوی بمب‌گذاری که کمترین تعداد سکه مورد نیاز است، سه حالت ممکن برای ترتیب سقوط شهر i و پدر آن (در صورت وجود) در درخت ریشه‌دار شده وجود دارد:
- ابتدا شهر i سقوط کند و سپس پدر آن.
- ابتدا پدر شهر i سقوط کند و سپس شهر i.
- شهر i و پدر آن به طور همزمان سقوط کنند.
هزینه‌ی بمب‌گذاری برای کل زیردرخت i در حالت‌های ۱ و ۳ یکسان است، زیرا سقوط پدر شهر i در این دو حالت تأثیری بر سقوط i ندارد. بنابراین:
عدد ذخیره شده در dp_0[i] را این‌گونه تعریف می‌کنیم: کمترین تعداد سکه‌ای که برای بمب‌گذاری در زیردرخت i نیاز داریم تا این زیردرخت مستقل از بقیه‌ی درخت سقوط کند.
عدد ذخیره شده در dp_1[i] نیز این‌گونه تعریف می‌شود: کمترین تعداد سکه‌ای که برای بمب‌گذاری در زیردرخت i نیاز داریم تا مطمئن باشیم که کل زیردرخت i نیز سقوط خواهد کرد، به‌طوری‌که پدر شهر i قبل از خود شهر i سقوط کند یا نیازی به سقوط شهر i نباشد.
برای محاسبه‌ی dp_0 و dp_1 مقادیر، شهرهایی که به عنوان برگ در درخت ریشه‌دار هستند و همسایه‌ای جز پدر خود ندارند را به عنوان پایه در نظر می‌گیریم و dp_0 و dp_1 را برای این شهرها پر می‌کنیم. سپس از پایین درخت شروع کرده و ابتدا dp_0 و dp_1 را برای تمام فرزندان یک شهر محاسبه کرده و سپس به سراغ محاسبه‌ی این مقادیر برای پدر آن‌ها می‌رویم (با استفاده از الگوریتم DFS).
اگر i یک شهر عادی و غیر برگ باشد و تعداد همسایه‌های آن برابر با adj_i باشد، می‌دانیم که این شهر یا باید بمب‌گذاری شود یا حداقل adj_i - f_i + 1 همسایه‌ی آن بدون نیاز به سقوط شهر i سقوط کنند. همسایه‌های شهر i شامل پدر i و فرزندان آن در درخت کدکاپ‌سیتی هستند.
برای حالت dp_0[i]، باید زیردرخت i به صورت مستقل از پدر i سقوط کند. بنابراین، یا شهر i بمب‌گذاری می‌شود و یا حداقل adj_i - f_i + 1 فرزند شهر i باید به صورت مستقل و قبل از شهر i سقوط کنند.
در صورتی که شهر i بمب‌گذاری شود، در مرحله‌ی اول سقوط خواهد کرد و بر سقوط تمام همسایه‌های آن تأثیر می‌گذارد. در این حالت، dp_0[i] برابر است با مجموع هزینه‌ی بمب‌گذاری در شهر i و dp_0 تمام فرزندان i.
همان‌طور که گفته شد، اگر شهر i در ابتدا بمب‌گذاری نشود، باید حداقل adj_i - f_i + 1 فرزند این شهر مستقل از شهر i سقوط کنند و سایر فرزندان می‌توانند از سقوط شهر i برای سقوط زیردرخت خود استفاده کنند. هر فرزند به اندازه‌ی dp_0[i] یا dp_1[i] سکه برای سقوط زیردرخت خود نیاز دارد. می‌دانیم که تعداد سکه‌ها در dp_1[i] کمتر یا مساوی dp_0[i] است. بنابراین، بهتر است adj_i - f_i + 1 فرزندی که dp_0 - dp_1 کمتری دارند، برای سقوط مستقل از i انتخاب شوند. در این حالت، فرزندان را بر اساس این اختلاف مرتب کرده و مجموع dp_0 در adj_i - f_i + 1 فرزند و dp_1 در سایر فرزندان محاسبه می‌کنیم تا تعداد سکه‌های مورد نیاز برای بمب‌گذاری در این حالت به دست آید.
در نهایت، مقدار dp_0[i] برابر است با تعداد کمتر سکه‌ها در دو حالت گفته شده.
به طور مشابه، مقدار dp_1[i] را به دست می‌آوریم. می‌دانیم که پدر شهر i مستقل از این شهر سقوط خواهد کرد. بنابراین، حداقل adj_i - f_i فرزند شهر i باید سقوط کنند یا خود شهر i بمب‌گذاری شود. مشابه حالت dp_0[i]، می‌توان مقدار این حالات را محاسبه کرد و تعداد کمتر سکه‌ها در این دو حالت را به عنوان مقدار نهایی در نظر گرفت.
در نهایت، پاسخ برابر با dp_0 شهر ریشه‌ی درخت است.
پیچیدگی زمانی: \mathcal{O}(\sum n \log n)
توجه کنید که اگر بیت خاصی از حاصل XOR دو عدد برابر صفر باشد، آن بیت در هر دو عدد یکسان است. از آنجا که حاصل XOR هر دو عدد کنار هم حداکثر ۱۰۰۰ است، در مبنای دو با ۱۰ بیت نمایش داده می‌شود. بنابراین، هر بیتی که ارزش بیشتری داشته باشد یا در تمام اعداد برابر ۱ است و یا در تمام آن‌ها برابر ۰. زیرا این بیت در هر گروهی که سؤال پرسیده شود، برای تمامی اعداد یکسان خواهد بود و در نتیجه در عمل AND آن گروه، مقدار این بیت برای تمام اعداد مشخص می‌شود.
ابتدا با استفاده از XOR اعداد کنار هم، بیت‌های اعداد را دسته‌بندی می‌کنیم. به این صورت که فرض می‌کنیم تمام بیت‌های عدد اول در دسته ۰ قرار دارند. سپس هر عدد دیگری اگر در بیت i با بیت i ام عدد اول برابر باشد، در آن بیت در دسته ۰ قرار می‌گیرد و در غیر این صورت، در دسته ۱. با توجه به مقادیر XOR می‌توان این دسته‌ها را برای بیت‌های اعداد مشخص کرد.
هدف ما این است که بیت‌های ۰ تا ۹ در مبنای دو را برای تمامی اعداد آرایه به دست آوریم. با توجه به اینکه می‌دانیم هر بیت در هر عدد در چه دسته‌ای قرار دارد، کافی است مشخص کنیم که دسته ۰ معادل عدد ۰ است یا ۱؛ دسته ۱ نیز متناظر مشخص می‌شود. در صورتی که AND تعدادی عدد در یک بیت خاص به ما اطلاعاتی بدهد، این بدان معناست که تمام این اعداد در یک دسته هستند؛ وگرنه AND آن‌ها همواره ۰ است و هیچ اطلاعاتی در مورد آن بیت به دست نمی‌آید. اما اگر همه از یک دسته باشند، مقدار آن دسته برابر با بیت نهایی در AND اعداد خواهد بود.
حال فرض کنید dp[x] را داریم. x یک رشته ۱۰ بیتی در مبنای ۳ است، به این شکل که هر بیت می‌تواند ۰، ۱ یا ۲ باشد. هدف این است که در dp[x] بیشترین تعداد اعضای گروهی از اعداد را ذخیره کنیم که تمام اعداد گروه در بیت‌هایی که برابر ۰ هستند، در دسته ۰ قرار گیرند و در بیت‌هایی که برابر ۱ هستند، در دسته ۱. همچنین، اعداد گروه در بیت‌هایی که در x برابر ۲ هستند، می‌توانند در هرکدام از دسته‌های ۰ یا ۱ باشند.
پایه‌های این dp را برای تمام xهایی که هیچ بیت ۲ ندارند، در نظر می‌گیریم. به این صورت که دسته‌بندی بیت‌های هر عدد را به دست می‌آوریم و سپس مقدار x متناظر با آن دسته‌بندی را یکی زیاد می‌کنیم.
برای به‌روزرسانی dp، یکی از بیت‌هایی که برابر ۲ هستند را در نظر می‌گیریم. می‌دانیم بزرگترین گروهی که در بیت‌های ۰ و ۱ در دسته‌های مشخص قرار داشته باشند، ممکن است در بیت ۲ یا در دسته ۰ قرار داشته باشند یا در دسته ۱. در حالت اول می‌توانیم بیت مشخص شده در x را برابر ۰ قرار داده و بزرگترین گروه در این حالت را به دست آوریم. سپس آن بیت را ۱ قرار داده و دوباره بزرگترین گروه را به دست آوریم. مجموع این دو گروه برابر با بزرگترین گروهی است که در بیت‌های ۰ و ۱ در دسته مورد نظر قرار داشته و در بیت‌های ۲ اهمیتی نداشته باشد که در چه دسته‌ای هستند.
پس از به دست آوردن dp[x] برای تمامی xها، مقدار x را طوری تغییر می‌دهیم که بیت‌های ۰ و ۱ برابر ۱ و بیت‌های ۲ برابر ۰ باشند. سپس mask[x'] را با dp[x] به‌روزرسانی کرده و حداکثر مقدار را می‌گیریم. در نهایت، در mask، بزرگترین گروهی را ذخیره می‌کنیم که در آن بیت‌های ۰ اهمیتی نداشته باشند، اما بیت‌های ۱ در یک دسته قرار بگیرند.
در نهایت، دو گروه را انتخاب می‌کنیم که تمامی بیت‌ها را پوشش دهند. بنابراین، به ازای هر mask[x]، گروه مقابل باید بیت‌های مکمل x را پوشش دهد و این دو گروه می‌توانند گروه‌های پرسش ما باشند. در نهایت، مقدار ماکسیمم این دو گروه به عنوان پاسخ نهایی انتخاب می‌شود.
پیچیدگی زمانی: \mathcal{O}(t \times 3^{\log_{2}(\max a_i)})
شرط لازم و کافی برای این که بتوان از رأس v به رأس u و سپس از u به w رسید، بدون اینکه هیچ یالی دوبار یا بیشتر پیموده شود، به ساختار درخت دوهمبند یالی گراف مربوط می‌شود.
علت این امر این است که در یک مؤلفه‌ی دوهمبند یالی، بین هر سه رأس مثل a، b و c، می‌توان مسیرهای یال مجزایی از a به b و از a به c یافت. بنابراین، پس از ساخت درخت دوهمبند یالی گراف، باید تعداد سه‌تایی‌هایی که رأس‌های متناظرشان در درخت روی یک مسیر قرار دارند را شمارش کنیم.
پیچیدگی زمانی: \mathcal{O}(n + m)
ابتدا شرط لازم و کافی برای کامل بودن یک دنباله‌ی دلخواه a به طول n از سکه‌ها را بررسی می‌کنیم. برای این کار، سکه‌های دنباله را بر اساس مقدارشان مرتب کرده و سپس مقدار مجموع پیشوند‌های آرایه را با پیمایش روی آن محاسبه می‌کنیم. فرض کنید که در هر مرحله مقدار مجموع پیشوند را در متغیری به نام sum ذخیره می‌کنیم. مقدار اولیه‌ی sum برابر ۰ است که نشان‌دهنده‌ی مجموع پیشوند به طول صفر است.
در مرحله‌ی iام، مقدار a_i از دنباله‌ی مرتب شده را به sum اضافه می‌کنیم و ادعا می‌کنیم که شرط لازم و کافی برای کامل بودن سکه‌ها این است که در تمام مراحل شرط sum \leq a_i + 1 برقرار باشد.
اگر این شرط برقرار باشد، تا قبل از اضافه کردن a_i می‌توانیم تمام مقادیر از ۰ تا sum را بسازیم و پس از اضافه کردن a_i، با قرار دادن a_i و اضافه کردن هر کدام از مقادیر ۰ تا sum، می‌توانیم تمامی مقادیر از ۰ تا sum + a_i را بسازیم.
اما اگر این شرط برقرار نباشد، یعنی در حداقل یکی از مراحل داشته‌ایم a_i > sum + 1 و نمی‌توانیم مقدار sum + 1 را با این دنباله‌ی سکه‌ها بسازیم و این دنباله کامل نیست. زیرا هر ترکیبی از مقادیر قبلی مجموعی کمتر از sum + 1 دارد، بنابراین باید حداقل یکی از اعضای بعدی دنباله برای ساخت sum + 1 استفاده شود. اما از آنجا که دنباله مرتب شده است، تمامی مقادیر بعدی از sum + 1 بزرگتر هستند و نمی‌توانیم این مقدار را بسازیم.
راه‌حل (O(n \log n + q \log n \log(\max c_i)))
برای این راه‌حل باید از یک ساختمان داده‌ی پایدار (مانند درخت سگمنت پایدار) استفاده کنیم تا بتوانیم مجموع مقادیر یک بازه از آرایه را در زمان‌های مختلف محاسبه کنیم. ابتدا مقادیر آرایه‌ی ورودی (c) را مرتب کرده و در آرایه‌ای به نام s ذخیره می‌کنیم. سپس ساختمان داده‌ی پایدار را با مقادیر ۰ مقداردهی اولیه می‌کنیم و مقادیر مرتب شده‌ی s را به ترتیب در جایگاهشان در آرایه‌ی c اضافه می‌کنیم.
برای پاسخ دادن به پرسش‌ها، می‌خواهیم بررسی کنیم که آیا مانند شرط کامل بودن دنباله که پیش‌تر توضیح داده شد، حالتی وجود دارد که در بازه‌ی ورودی، مقدار c_i > sum + 1 رخ دهد یا نه. برای این کار، از مقدار ۰ برای sum شروع کرده و در هر مرحله sum را با مجموع اعداد کوچکتر یا مساوی sum + 1 در بازه‌ی ورودی جایگزین می‌کنیم. برای یافتن مجموع مقادیر کوچکتر یا مساوی sum + 1، ابتدا با جستجوی دودویی موقعیت بزرگترین عدد کوچکتر یا مساوی sum + 1 را پیدا کرده و آن را p می‌نامیم. سپس مجموع اعداد بازه‌ی ورودی را پس از انجام p امین عملیات محاسبه می‌کنیم.
این فرآیند را تا زمانی ادامه می‌دهیم که یا sum به مقدار مجموع کل بازه تبدیل شود (که در این صورت بازه‌ی سکه‌ها کامل است)، یا اگر در یکی از این مراحل sum دیگر تغییر نکند، به این معنی است که مجموع اعداد کوچکتر یا مساوی sum + 1 در بازه داده شده برابر با sum است و کوچکترین عدد بعدی که هنوز به sum اضافه نشده است، بزرگتر از sum + 1 است و بنابراین این بازه از سکه‌ها کامل نیست.
می‌توان اثبات کرد که تعداد مراحلی که مجموع بازه را به ازای هر پرسش بررسی می‌کنیم از (O(\log(\max c_i))) است.
راه‌حل (O((n+q)(\sqrt{n} \log(\max c_i))))
برای این راه‌حل از یک ساختمان داده‌ی تقسیم‌بندی مجذوری (Sqrt Decomposition) استفاده می‌کنیم که عملیات تغییر مقدار یک خانه را در O(1) و پیدا کردن مجموع یک بازه را در O(\sqrt{n}) انجام می‌دهد. ابتدا مقادیر آرایه‌ی ورودی c را مرتب کرده و تنها مقادیر یکتای آن را در آرایه‌ی s ذخیره می‌کنیم. همچنین، یک آرایه‌ی d به طول n تشکیل می‌دهیم که به ازای هر خانه‌ی آرایه‌ی c، موقعیت مقدار آن در آرایه‌ی s را ذخیره کند.
سپس ساختمان داده‌ی تقسیم‌بندی مجذوری را روی آرایه‌ی s تشکیل می‌دهیم، به طوری که در ابتدا مقدار همه‌ی خانه‌های آن ۰ باشد. حال با استفاده از الگوریتم Mo پرسش‌های ورودی را مرتب کرده و شروع به پیمایش پرسش‌ها می‌کنیم. در تغییرات هنگام تبدیل یک بازه به بازه‌ی دیگر، به ازای خانه‌ای مانند i که اضافه یا حذف می‌شود، مقدار c_i را در خانه‌ی متناظر در ساختمان داده جمع می‌کنیم (و یا اگر خانه حذف شود، آن را کم می‌کنیم). در اینجا هر عملیات تغییر روی ساختمان داده‌ی تقسیم‌بندی مجذوری O(1) زمان می‌برد.
برای پاسخ به هر پرسش، مانند راه‌حل قبلی عمل می‌کنیم و هر بار مجموع خانه‌های کوچکتر یا مساوی sum + 1 را محاسبه می‌کنیم.
مجموعه‌ی همه‌ی نقاط را با P نام‌گذاری می‌کنیم. ابتدا پوش‌محدب P را محاسبه می‌کنیم و مجموعه‌ی نقاطی که روی پوش‌محدب (Convex Hull) قرار می‌گیرند را با C نام گذاری می‌کنیم. محاسبه کردن این مجموعه در زمان \mathcal{O}(n. \log n) شدنی است. برای نقاطی که روی پوش‌محدب نیستند، پاسخ مسئله برابر محیط C است.
حال مجموعه‌ی D را برابر پوش‌محدب P \ C تعریف و محاسبه می‌کنیم. بعد از حذف هر نقطه از C بازه‌ای از محیط D به پاسخ مسئله اضافه می‌شود.
با استفاده از روش دو اشاره‌گر (Two Pointers) این بازه را ابتدا برای یک نقطه از C حساب می‌کنیم (در زمان \mathcal{O}(|D|)) و در نهایت با پیمایش به ترتیب نقاط C و حرکت دادن هر دو اشاره‌گر در مجموع همه‌ی محیط‌ها را از مرتبه‌ی \mathcal{O}(|D| + |C|) بدست می‌آوریم.
پیچیدگی زمانی: \mathcal{O}(n \log n)
باتشکر از «ارشیا سلطانی موخر»، «امین انوری»، «رومینا سحری مقدم»، «مهلا انتظاری»، «فیروزه ابریشمی» ،«محمدرضا محمدزاده اصل»، «سیدسینا صالح‌زاده»، «علی شفیعی» برای طراحی و تست سوالات مرحله نهایی کدکاپ ۸.
