سلام دوست کوئرایی!
در این مطلب، به راه‌حل‌های سوالات مسابقه انتخابی ۳ کدکاپ ۸ می‌پردازیم. اگر در این مسابقه شرکت کرده‌ای و سوال یا ابهامی درباره پاسخ سوالات داری، این بلاگ پست برای شماست.
اگر n, m \geq 2 باشد هر چهار ضلع مستطیل شهرهای مرزی متفاوتی دارند ولی چون چهار شهر گوشه‌ای مستطیل در دو ضلع در نظر گرفته می‌شوند، یکبار آن‌ها را از حاصل کم میکنیم. بنابراین پاسخ برابر 2n + 2m - 4 است.
در غیر اینصورت شهرهای کدکاپ به صورت یک نوار افقی یا عمودی است. پس همه‌ی شهرهای آن مرزی هستند و پاسخ مسئله برابر اندازه‌ی بزرگ‌ترین ضلع است.
میخواهیم برای هر سکه یک عدد که نشان دهنده‌ی وضعیت آن سکه است در نظر بگیریم که 0 به معنی «تقلبی بودن»، 1 به معنی «اصل بودن» و -1 به معنی «نمی‌دانیم اصل یا تقلبی» است. در ابتدا این عدد برای همه سکه‌ها -1 است.
اگر یکی از این دو نوع سکه وجود نداشته باشد، وضعیت هیچ سکه‌ای مشخص نمی‌شود و باید همه‌ی جدول داده شده = باشد. این تنها حالت ممکن برای not unique است.
اگر یک مقایسه از نوع < یا > داشته باشیم، سکه‌ی سبک‌تر تقلبی و سکه‌ی سنگین‌تر اصل است. پس با یک بار پیمایش کردن همه‌ی داده‌های جدول می‌فهمیم برخی از سکه‌ها اصل و برخی تقلبی هستند.
حال بیایم برای همه‌ی علامت‌های = در صورتی که وضعیت یکی از طرفین تساوی مشخص است، وضعیت طرف دیگر را مشخص کنیم.
اکنون اگر داده‌ها درست باشند، چون حداقل یک سکه‌ی تقلبی و یک سکه‌ی اصل در میان سکه‌ها موجود است، وس وضعیت همه‌ی سکه‌ها مشخص می‌شود. برای درست بودن داده‌ها کافی است از روی همین مقدارها مجددا جدول داده‌ها را بسازیم و بررسی کنیم با ورودی مطابقت دارد یا نه.
در صورت مطابقت پاسخ همان وضعیت بدست آمده می‌شود و در غیر این صورت پاسخ invalid خواهد بود.
می‌دانیم هر میزان شن که داخل ساعت شنی ما باشد، اگر تمام شن در بالای ساعت باشد در M ثانیه به پایین منتقل می‌شود. پس می‌توانیم هر واحد شن را اندازه میزان شن‌ای که در یک ثانیه به پایین منتطق می‌شود در نظر بگیریم. در این صورت می‌توانیم درنظر بگیریم M واحد شن داخل ساعت شنی قرار دارد که در هر ثانیه یک واحد از شن ها کم می‌شود. و میخواهیم هیچ ثانیه ای نباشد که با میزان واحد شن ۰ آن لحظه شروع شود.
در ابتدا اعداد را ورودی می‌گیریم و سپس یک آرایه mark تعریف میکنیم و اگر هر لحظه‌ای مانند x وجود داشت که بتوانیم در آن لحظه ساعت را برگردانیم، mark[x] برابر true قرار می‌دهیم.
میخواهیم بررسی کنیم آیا این اتفاق امکان پذیر است یا خیر. به ازای تمام لحظه ها در بازه‌بسته [0, T] و همچنین تمام مقادیر مختلف میزان شن در بالای ساعت که در بازه‌بسته [0, M] قرار می‌گیرد، محاسبه میکنیم که اگر از لحظه مشخص شده با واحد شن مشخص شده شروع کنیم، آیا می‌توانیم با موفقیت به لحظه T برسیم؟
برای محاسبه گذاره بالا، یک آرایه دو بعدی به نام a در نظر می‌گیریم و میخواهیم در a[i][j] ذخیره کنیم که اگر شروع ما از ابتدای ثانیه i باشد و در ابتدا j واحد شن در بالای ساعت شنی باشد، می‌توانیم با موفقیت به ابتدای ثانیه T برسیم؟ پس مقدار این خانه از جنس boolean است.
برای پر کردن آرایه مورد نظر، از i = T شروع میکنیم. می‌دانیم چون در این لحظه بازی به پایان رسیده و هدف رسیدن به همین لحظه هستش پس به ازای تمام i های ممکن، a[T][i] = true
در ادامه برای پر کردن بقییه آرایه، از ثانیه i = T - 1 تا ۰ به ترتیب تمام مقادیر j را در نظر می‌گیریم و با توجه به اینکه پاسخ برای تمام ثانیه های جلوتر از قبل محاسبه شده و داخل آرایه ذخیره شده، a[i][j] را بدست می‌‍آوریم:
می‌دانیم در ثانیه i، به اندازه j واحد شن در بالای ساعت قرار دارد. اگر در این ثانیه mark[i] برابر false باشد، نمی‌توان ساعت را برگرداند پس تا انتهای این ثانیه یک واحد از شن‌های بالای ساعت کم شده و با این وضعییت وارد ثانیه بعدی می‌شویم. پس اگر مقدار شن ما(j) برابر ۰ باشد، a[i][j] برابر false است و در غیر اینصورت برابر a[i + 1][j - 1].
و اما در صورتی که mark[i] برابر true باشد، می‌توانیم در این لحظه ساعت را برگردانیم که در این صورت در بالای ساعت M - j واحد شن قرار می‌گیرد. پس اگر یکی از a[i + 1][j - 1] یا a[i + 1][M - j - 1] میزان شن مثبت داشته باشد و همچنین برابر true باشد پاسخ a[i][j] نیز true است در غیر این صورت false است.
در نهایت پاسخ ما برابر a[0][M] است.
با توجه به اینکه برای حساب کردن هر خانه از آرایه فقط نیاز به چک کردن تعداد خانه ی جلوتر بوده و تعدا کل خانه‌ها برابر TM است پس پیچیدگی زمانی این الگوریتم نیز TM است. شما می‌توانید با کمی دقت و بهینه‌سازی این الگوریتم را تغییر داده و با پیچیدگی زمانی TN سوال را حل کنید.
یک گراف دو بخشی می‌سازیم. که راس‌های یک بخش اعداد مختلف قد و راس‌های بخش دیگر اعداد مختلف برای وزن است. هر مهمان یک یال در این گراف است. می‌دانیم یال‌های (مهمان‌های) یک مولفه‌ی همبندی می‌توانند با هم صحبت کنند. پس مسئله به این تبدیل می‌شود که حداقل چند یال با این گراف اضافه کنیم تا همبند شود. اگر تعداد مولفه‌های همبندی گراف فعلی c باشد به حداقل c - 1 یال نیاز داریم. می‌توانیم مقدار c را با الگوریتمی مثل DFS برای گراف محاسبه کنیم.
رشته‌ی اصلی را در یک درخت بازه‌ای (segment tree) ذخیره میکنیم به طوری که هر کاراکتر یک برگ در این درخت باشد. حال اگر برای هر راس این درخت، تعداد زیررشته‌های جبری موجود در آن، تعداد زیررشته‌های جبری که پیشوند یا پسوند آن بازه هستند و تعداد زیررشته‌هایی از فقط ارقام یا کاراکترها به صورت پیشوند یا پسوند هستند را حساب کنیم، می‌توانیم این اطلاعات را برای دو بازه‌ی کنار هم ادغام کنیم. این به این معنی است که می‌توانیم بعد از یک تغییر اطلاعات راس‌های درخت بازه‌ای را بروز کنیم و پاسخ سوالات را بدهیم.
اگر جمع یک سطر یا یک ستون عددی صحیح نباشد، به این هدف نمی‌توانیم برسیم. حال ادعا میکنیم برای بقیه‌ی حالت‌ها این کار ممکن است. می‌توانیم فرض کنیم اعداد جدول در بازه‌ی [0, 1) هستند چون با کم یا زیاد کردن یک عدد صحیح از یک خانه تاثیری در جواب مسئله ندارد.
حال یک شبکه‌ی جریان (network flow) از روی جدول بسازید. برای هر سطر یک راس قرار می‌دهیم و از راس چشمه (source) به آن‌ها یالی با ظرفیت مجموع آن سطر می‌گذاریم. همچنین برای هر ستون یک راس قرار می‌دهیم و از آن‌ها یالی به راس چاه (sink) با ظرفیت مجموع آن ستون می‌گذاریم. حال برای هر خانه از جدول در صورتی که عدد ناصفر باشد، یک یال از آن سطر به آن ستون با ظرفیت ۱ قرار می‌دهیم.
این شبکه‌ی جریان دارای یک جریان بیشینه است که مقدار جریان یال‌های چشمه و چاه به ظرفیت داده شده می‌رسد. (کافی است مقدار حقیقی جدول را به‌عنوان جریان در نظر بگیریم.) همچنین چون همه‌ی ظرفیت‌ها عدد صحیح هستند پس یک جریان بیشینه با مقدار جریان‌های صحیح هم وجود دارد.
حال اگر این جریان صحیح بیشینه را با استفاده از مثلاً با الگوریتم Dinitiz بدست بیاوریم و یال‌های با جریان ۱ در جدول را سقف و بقیه را کف در نظر بگیریم به هدفمان می‌رسیم.
جمع‌بندی
در این مطلب تلاش کردیم تا تمامی نکات مربوط به سوالات این بخش از مسابقات را پوشش دهیم. اگر سوال دیگری دارید، حتما آن را در بخش نظرات با ما به اشتراک بگذارید.
باتشکر از «ارشیا سلطانی موخر»، «امین انوری»، «رومینا سحری مقدم» و «علی شفیعی» برای طراحی و تست سوالات کدکاپ ۸ مرحله‌ی انتخابی ۲.
