راه‌ حل‌های مسابقه شماره ۱۳ Quera

توضیح راه حل های مسابقه شماره ۱۳ Quera به همراه کدهای صحیح را در ادامه مطلب می‌بینید. در صورتی که راه‌حل دیگری برای سوال‌ها دارید در بخش نظرات با ما در میان بگذارید.

• سوال ۱

  بعد از ورودی گرفتن جدول کافی است تعداد کاراکتر های “*” را به عنوان پاسخ مسئله چاپ کنید. چون هر ستاره دقیقاً در یک خانه ی جدول به صورت یک کاراکتر “*” نمایش داده شده. O(n m)

  کد این مسئله به زبان ++C

• سوال ۲

  دو بازه ای را در نظر بگیرید که کوچک ترین r (زود ترین پایان) و بزرگ ترین l (دیر ترین شروع) را داشته باشد. در این صورت این دو بازه هم طبق فرض ما با هم اشتراک دارند. اکنون اشتراک این دو بازه با همه ی بازه ها اشترک دارد!
  چون اگر بازه ای با بازه ی بالا اشتراک نباشد یا در سمت چپ آن قرار دارد که در این صورت r کوچکتری دارد که این با فرض اولیه ما تناقض دارد و یا در سمت راست آن قرار دارد که این بازه l بزرگتری دارد.

  با توجه به اثبات بالا می توان فهمید که اشتراک بازه ها دقیقن بازه ی [l_{max}, r_{min}] که میشه از O(n) اون رو پیدا کرد. بنابراین بازه ی گمشده هم باید با این بازه اشتراک داشته باشد.

  برای شمارش این بازه ها،تعداد بازه هایی که نامطلوب هستند را از تعداد کل بازه ها کم می کنم. بازه هایی نامطلوب هستند که یا در سمت چپ اشتراک همه بازه ها، یا در سمت راست اشتراک همه بازه ها قرار دارد. لذا پاسخ برابر:
  \frac {m \times (m + 1)} 2 - \frac {l_{max} \times (l_{max} - 1)} 2 - \frac {(m - r_{min}) \times (m - r_{min} + 1)} 2

  کد این مسئله به زبان ++C

• سوال ۳

  می دانیم اگر بتوان n خانه را به k بازه با مساحت های برابر افراز کرد حتماً k \mid n (یعنی k مقسوم علیه n است) پس برای هر مقسوم علیه طبیعی n کل قیمت ها را به k تا k تا افراز می کنیم و بررسی می کنیم که آیا مجموع قیمت همه برابر است یا نه. برای محاسبه ی جمع این بازه ها از روش partial sum استفاده می کنیم. و اگر تعداد مقسوم علیه های n برابر d باشد. الگوریتم ما از O(n.lg(n)) پاسخ را بدست می آورد.

  کد این مسئله به زبان ++C

• سوال ۴

  راه حل اول:
  ابتدا همه‌ی گل ها را در آرایه قرار می دهیم سپس از بیشترین اندازه به کمترین اندازه بررسی می کنیم که اگر گل ها را با ارتفاع h برداریم بیشترین تعداد گلی که می توان برداشت تا همه ی گل هایی که بین آن ها قرار دارند ارتفاع بیشتر یا مساوی h داشته باشند.
  برای این کار می توان از ساختمان داده ی set استفاده کرد. به این صورت که بعد از بررسی هر ارتفاعی، همه ی گل های با آن ارتفاع را حذف می کنیم. و اگر موقع بررسی ارتفاع دو گل در بین آن دو گلی در set وجود داشت. این دو گل نمی توانند با هم در دسته گل باشند. به این ترتیب سوال از  O(n.lg(n)) حل می شود.
  کد این مسئله به زبان ++C

  راه حل دوم:
  برای هر گل می خواهیم بدانیم حداکثر به تعداد چند گل می توان سمت چپ رفت که ارتفاع همه ی آن گل ها بیشتر یا مساوی ارتفاع این گل باشد. برای بدست آوردن این تعداد برای هر گل، گل ها را به ترتیب از چپ به راست وارد یک stack می کنیم. و برای هر گلی که وارد stack می کنیم، اگر گلی با ارتفاع کمتر یا مساوی با گل ما در بالای stack وجود داشت آن را حذف می کنیم و سپس گل را به بالای stack اضافه می کنیم. بنابراین برای هر گل می دانیم اولین گلی که ارتفاع کمتر یا مساوی آن را دارد کدام است. و تا آن بازه تعداد گل های هم ارتفاع آن را محاسبه می کنیم. بنابراین چون هر گل یک بار وارد stack شده و یک بار از stack خارج می شود، الگوریتم از O(n) پاسخ را بدست می آورد.
  کد این مسئله به زبان ++C

• سوال ۵

  می دانیم p(n) رای هر عدد زیبای n تنها عوامل اول ۲ و ۳ و ۵ و ۷ را دارد. اگر همه ی اعداد که p(n) آنها کمتر از 10^{12} است را بررسی کنیم متوجه می شویم که تعداد این اعداد کم است!
  اکنون dp[x][i][j][k][l] را به این صورت تعریف می کنیم که چند عدد زیبای x رقمی وجود دارد که تجزیه ضرب ارقام آن دارای i عامل ۲، j عامل ۳، k عامل ۵ و l عامل ۷ داشته باشد. برای محاسبه ای این مقادیر ابتدا از x = ۱ شروع می کنیم و حالت بندی می کنیم که اگر رقم آخر چه باشد،p(n) در چه عددی ضرب می شود و از روی مقادیر x – ۱ پاسخ را بدست می آوریم.

  اکنون برای بدست آوردن جواب مساله در یک بازه کافیست اعداد مختلفی که p(n) می تواند باشدمرتب می کنیم. و با استفاده از binary search و partial sum، جواب یک بازه را بدست می آوریم.
  کد این مسئله به زبان ++C

• سوال ۶

  مسئله را با گراف مدل می‌کنیم:

  یک گراف n راسی داریم که m یال بی‌جهت با وزن مثبت رئوس آن را به هم متصل کرده‌اند. علاوه بر این m یال، یک زیرمجموعه از رئوس گراف هستند که بین هر جفت از آن‌ها یک یال بی‌جهت با وزن t وجود دارد که t می‌تواند عددی منفی باشد. مسئله یافتن کوتاه‌ترین مسیر از راس شماره ۱ به راس شماره n در این گراف است.

  مسئله‌ی یافتن کوتاه‌ترین مسیر در یک گراف مسئله‌ی آشنایی است و الگوریتم‌های متعددی برای آن وجود دارد؛ اما هیچ‌یک از این الگوریتم‌ها نمی‌تواند کوتاه‌ترین مسیر در گرافی که تعدادی از یال‌های بی‌جهت آن منفی است را در زمان چند جمله‌ای پیدا کند. ثابت شده‌است که الگوریتم با زمان اجرای چندجمله‌ای برای چنین مسئله‌ای وجود ندارد؛ وگرنه P = NP !! (شاید فکر کنید که این چنین نیست؛ در این صورت امتحان کنید و برای الگوریتم‌تان مثال نقض بیابید!)

  اما گراف ورودی این سوال شرایط ویژه‌ای دارد که با استفاده از آن‌ها، می‌توان کوتاه‌ترین مسیر را در آن یافت. این m یال گراف که همه وزن مثبت دارند را یال‌های معمولی و دیگر یال‌ها با وزن t را یال‌های خاص می‌نامیم و به راس‌های دو سر این یال‌ها رئوس خاص می‌گوییم.

  ابتدا فرض کنیم که مقدار t نمی‌تواند منفی باشد.

  در این حالت مسئله بنظر ساده‌تر می‌آید! چرا که اگر تمام این یال‌ها را بگذاریم، با الگوریتم Dijkstra (یا امثال آن) می‌توان کوتاه‌ترین مسیر را در زمان اجرای O(n^2) یافت. شرایط مسئله‌ی ما ( n \le 1000 و m \le 1000 ) نشان می‌دهند که تعداد یال‌های گراف اولیه خیلی زیاد نیست؛ ولی اگر یال‌های خاص را اضافه کنیم تعداد یال‌ها به نسبت می‌تواند زیاد بشود. تلاش می‌کنیم که راه‌ حلی با زمان اجرای بهتر از O(n^2) ارائه کنیم.

  کوتاه‌ترین مسیر را درنظر می‌گیریم. یا هیچ یال خاصی در این مسیر نیست، که در این حالت راه حل O(n + m \log n) با Dijkstra برای یافتن چنین مسیری وجود دارد. یا تعدادی یال خاص در این مسیر هستند. با توجه به این‌که وزن یال‌های معمولی مثبت است، می‌بینیم که اگر داخل مسیر یک یال خاص آمده باشد و سپس یک یال معمولی، پس از آن در داخل مسیر هیچ یال خاصی پیدا نخواهد شد! زیرا در غیر این صورت می‌توانیم یال‌های معمولی این بین را از مسیر حذف کنیم و با یک یال خاص، از راس انتهایی یال خاص اول به راس انتهایی یال خاص دوم برویم. (چنین یالی وجود دارد زیرا بین هر دو راس خاصی، یک یال خاص وجود دارد.)

  پس یال‌ها و راس‌های خاص همیشه یک بازه‌ی پشت سر هم از مسیر را تشکیل می‌دهند؛ پس می‌توان گفت که راس‌های خاص v و u در این گراف وجود دارند بصورتی که مسیر را می‌توان این‌چنین توصیف کرد: از راس شماره ۱ پس از طی کردن تعدادی یال عادی به راس v می‌رویم، سپس با طی کردن تعدادی یال خاص به راس u می‌رسیم و پس از آن دوباره با طی کردن تعدادی یال عادی به راس شماره n می‌رویم.

  چون فرض کرده‌ایم مقدار t منفی نیست، در توصیف بالا واضح است که به‌صرفه است تنها با یک یال خاص از v به u برویم! پس چون این کوتاه‌ترین مسیر در گراف است، نباید با یال‌های عادی مسیری با وزن کم‌تر از t بین راس‌های v و u یافت شود؛ پس (با توجه به مثبت بودن مقدار t) با اضافه کردن یال با وزن t بین آن دو راس این مسیر باید کوتاه‌ترین مسیر بین راس ۱ و n بشود؛ در نتیجه مسیر از راس شماره ۱ به v و از u به راس شماره n هریک یک کوتاه‌ترین مسیر با استفاده از یال‌های عادی در گراف هستند! پس می‌توانیم تنها یال‌های عادی را در گراف بگذاریم و سپس یک بار کوتاه‌ترین مسیر از هر راس به راس شماره n و یک بار کوتاه‌ترین مسیر از راس شماره ۱ به هر راس را بیابیم و سپس نزدیک‌ترین راس خاص به راس شماره ۱ را v و نزدیک‌ترین راس خاص به راس شماره n را u در نظر بگیریم!

  پس می‌توان در زمان اجرای O(n + m \log n) این مسئله را حل کرد!

  حال فرض می‌کنیم که t می‌تواند مقدار منفی نیز داشته باشد.

  در این حالت هم این نکته که یال‌های خاص دنباله‌ی پشت‌سرهمی از مسیر را تشکیل می‌دهند درست است، اما لزومی ندارد این دنباله حداکثر یک یال داشته باشد. اگر t مقداری منفی داشته باشد طبق اثبات مشابه اثبات گفته‌شده در بخش پیشین، می‌توان نشان داد که در مسیر بهینه باید بین دو راس v و u دقیقا k-1 یال خاص طی شده باشد که k تعداد راس‌های خاص است. (یعنی از راس v شروع کرده و با گذشتن از همه‌ی راس‌های خاص، به راس u می‌رویم.) پس طول کوتاه‌ترین مسیر برابر می‌شود با طول مسیر از راس شماره ۱ به v + طول مسیر از u به راس شماره n + (k-1) \times t. مقدار (k-1) \times t ثابت است؛ پس طول کوتاه‌ترین مسیر این‌چنینی مسیری تنها به طول یال‌های عادی‌اش وابسته است.

  نکته‌ای که مسئله را پیچیده‌تر می‌کند، این است که اکنون لزومی ندارد مسیر از راس شماره ۱ به v یک کوتاه‌ترین مسیر باشد؛ زیرا ممکن است کوتاه‌ترین مسیر از راس شماره ۱ به v و کوتاه‌ترین مسیر از u به راس شماره n اشتراک راسی داشته باشند و اجتماع آن‌ها یک مسیر در گراف نشود!

  پس مسئله یافتن دو راس خاص v و u و دو مسیر راس-مجزا ، یکی از راس شماره ۱ به v و یکی از u به راس شماره n است که مجموع طول دو مسیر کمینه باشد. یک نکته‌ی مثبت در سوال، بی‌جهت بودن یال‌های عادی است! می‌توان مسیر از u به راس شماره n را برعکس در نظر گرفت. پس مسئله یافتن دو راس خاص است و دو مسیر راس مجرا از آن‌ها به دو راس شماره ۱ و n است که مجموع طول مسیرها کمینه شود.

  اینجاست که مسئله به مسئله‌ی شار بیشینه شبیه می‌شود! دو راس s و t به گراف اضافه می‌کنیم و از راس s به تمام راس‌های خاص یک یال جهت‌دار با ظرفیت ۱ می‌گذاریم و از راس شماره ۱ و راس شماره n نیز به راس t یک یال جهت‌دار با ظرفیت ۱ در گراف قرار می‌دهیم. فرض می‌کنیم ظرفیت دیگر یال‌های گراف نیز برابر ۱ است و روی هر راس نیز ظرفیت ۱ می‌گذاریم که حداکثر ۱ شار از آن‌ها بگذرد و هر شار، مسیری مجزا از دیگری باشد. (نحوه‌ی حل مسئله‌ی شار بیشینه با وجود ظرفیت روی رئوس گراف را می‌توانید در اینجا ببینید!) وزن هر یال عادی روی گراف را برابر وزن خودش قرار می‌دهیم و وزن یال‌های اضافه شده را برابر ۰ قرار می‌دهیم. سپس کم‌وزن ترین شاری به اندازه‌ی ۲ در این گراف، دقیقا همان دو مسیر راس مجزایی می‌شود که در جست‌وجوی آن هستیم!

  برای پیاده سازی این الگوریتم باید ۲ بار کوتاه‌ترین مسیر را بدست بیاوریم که بوسیله‌ی الگوریتم bellman-ford یا spfa، در زمان اجرای O(nm) قابل انجام است.

• کد این مسئله به زبان++C