جواب پست قبلی

یا حق

سلام به همه رفقا.

شرمنده به خاطر تاخیر تو پست زدن. این جواب سوال‌های پست قبلیه:

۱- برای اینکه ببینیم چندتا جایگشت رو می‌شه مرتب کرد،‌ تعداد جایگشت‌هایی که از جایگشت مرتب شده می‌شه به اون‌ها رفت رو می‌شماریم. اگه جایگاه‌های 1 تا n رو به عنوان راس و هر کارت رو به عنوان یک یال در نظر بگیریم، به یک گراف می‌رسیم. حالا تو این گراف هر دو راسی که تو یک مولفه باشند رو می‌شه جابجا کرد، بدون اینکه بقیه رئوس رو به هم بریزیم. پس در واقع هر مولفه از این گراف رو می‌تونیم به هر شکلی جایگشت بدیم. پس اگه این گراف k تا مولفه با اندازه‌های a₁تا a_kداشته باشه، جواب مسئله می‌شه:

a₁! * a₂! * ... * a_k!) % 1000007)

بنابراین کافیه با یهDFSاندازه مولفه‌ها رو در بیاریم و عبارت بالا رو محاسبه کنیم.

۲- فرض کنید با تعدادی حرکت دنباله رو مرتب کردیم. عناصری رو در نظر بگیرید که در هیچ مرحله‌ای حرکت داده نشده‌اند. این عناصر باید تشکیل یک زیردنباله‌ی صعودی بدهند. از طرفی اگر یک زیر دنباله‌ی صعودی را در نظر بگیریم، با جابجا کردن بقیه عناصر می‌شه دنباله رو مرتب کرد. پس مساله تبدیل می‌شه به پیدا کردن طولانی‌ترین زیردنباله‌ی صعودی که اختصارا بهش می‌گنLIS. برای این مساله یه راه‌حل داینمایک از (O(n^2 وجود داره که با یه ایده‌ی جالب می‌شه به (O(n * log n کاهشش داد.

می‌خواستم برای این دوتا سوال تست‌دیتا درست کنم ولی وقت نشد. اما توصیه می‌کنم که کدهاشون رو بزنید. راه‌حل ها رو خیلی مختصر توضیح دادم، اگه چیزی رو نفهمیدید تو نظرات بپرسید. (بلاخره باید یه جوری آمار نظرها بالا بره!).

----------------------------------------------------------------------------------

چند وقت پیش تصمیم گرفته بودم که از المپیاد جهانی امسال یه چیزی تو مایه‌های سفرنامه بنویسم و تو شاززز بذارم. الان دو-سه روزه که برگشتیم و وقت نشده کاری بکنم. از طرفی ما باید به زودی این وبلاگ رو بدیم به دست سال پایینی‌ها. برای همین نمی‌دونم وقت بشه که پست دیگه‌ای بزنم یا نه. حالا اگه وقت شد سفرنامه رو بنویسم و اینجا بذارم که خب هیجی(یعنی فعلا در خدمتیم) وگرنه اگه خوبی-بدی دیدید حلال کنید.

فعلا خداحافظ!

(پی نوشت: دمه افطاره. از همه دوستان التماس دعا)