Processing math: 51%

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:آزمون های اینترنتی ۸۹ تا ۹۱:سوال ۵۲

Function

تابع ‎F‎ با تابع ‎G‎ همگام است اگر و فقط اگر به ازای هر ‎1xn‎ ،F(G(x))‎ با ‎G(F(x))‎ برابر باشد‎.‎

تابع ‎F‎ از تابع ‎G‎ کوچک‌تر است اگر و فقط اگر عدد ‎1in‎ وجود داشته باشد به طوری که: ‎

  • F(i)<G(i)
  • F(j)=G(j)‎ به ازای هر ‎1j<i

به شما تابع یک به یک و پوشای ‎F‎ از ‎{1,2,3,,n}{1,2,3,,n}‎ داده شده است، شما باید کوچک‌ترین تابع ‎G‎ همگام با ‎F‎ به دست آورید‎.‎

ورودی

در سطر اول‌وردی عدد ‎1n2×105‎ آمده است‎.‎

در سطر بعدی اعداد ‎F(1)‎ ، ‎F(2)‎ تا ‎F(n)‎ به ترتیب آمده‌اند.

خروجی

در تنها سطر‌‌‌‌ خروجی ‎n‎ عدد ‎G(1)‎ تا ‎G(n)‎ را چاپ نمایید.

محدودیت‌ها

  • محدودیت زمان: ۴ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
10
1 2 3 4 5 6 7 8 9 10
‎‎1 1 1 1 1 1 1 1 1 1‎‎
10
2 3 4 5 6 7 8 1 9 10‎
‎1 2 3 4 5 6 7 8 9 9

پاسخ

تابع ‎F‎ تابعی یک‌به‌یک و پوشا است. بنابراین یک جایگشت از اعداد ‎1‎ تا ‎n‎ است. فرض کنید که اعداد ‎a0‎، ‎a1‎، ‎‎ ، ‎ak1 شماره رئوس یکی از دورهای گراف جایگشت تابع ‎F‎ باشد. فرض کنید که ‎G‎ به شکلی تعریف شده باشد که ‎a0‎ را به ‎b0‎ نگاشت کند و ‎b0‎ در جایگشت ‎F‎ در دوری به طول ‎p‎ قرار داشته باشد.

این دور را با اعداد ‎b0‎, ‎b1‎, ‎‎ , ‎bp1‎ نشان می‌دهیم. (ممکن است این دور همان دور ‎a0‎و ‎a1‎و ‎‎ و ‎ap1‎ باشد‎(.‎

تابع ‎F‎ تابعی یک‌به‌یک و پوشا است. بنابراین یک جایگشت از اعداد ‎1‎ تا ‎n‎ است. فرض کنید که اعداد ‎a0‎و ‎a1‎و ‎‎ و ‎ak1‎ شماره رئوس یکی از دورهای گراف جایگشت تابع ‎F‎ باشد. فرض کنید که ‎G‎ به شکلی تعریف شده باشد که ‎a0‎ را به ‎b0‎ نگاشت کند و ‎b0‎ در جایگشت ‎F‎ در دوری به طول ‎p‎ قرار داشته باشد. این دور را با اعداد ‎b0‎, ‎b1‎و ‎‎ و ‎bp1‎ نشان می دهیم. (ممکن است این دور همان دور ‎a0‎و ‎a1‎و ‎‎ و ‎ap1‎ باشد‎(.‎ ‎ f(g(a_0 ) )= g(f(a_0 ) ) \Rightarrow f(b_0 )= g(a_1 ) \Rightarrow b_1=g(a_1)

بنابراین تابع ‎G‎ باید ‎a_1‎ را هم به ‎b_1‎ نگاشت کند و همین طور می توان نشان داد که به ازای هر ‎1 \leq i \leq k‎، رابطه‌ی زیر برقرار است‎:‎ ‎ g(a_i)= b_{(i \mod p)} ‎ بنابراین برای اینکه تابع ‎G‎، هر رأس از گراف جایگشت را فقط به یک رأس دیگر نگاشت می کند (خاصیت تابع)، باید ‎k‎ بر ‎p‎ بخشپذیر باشد. پس درواقع تابع ‎G‎ باید به این شکل باشد که رئوس هر دور از گراف جایگشت را که مثلا اندازه‌اش ‎k‎ می باشد به دوری دیگر از جایگشت که مثلا اندازه‌اش ‎p‎ است نگاشت می کند به طوری که حتما ‎K‎ بر ‎p‎ بخشپذیر است. به سادگی می توان نشان داد که این شرط کافی هم هست تا تابع ‎G‎ با تابع ‎F‎ همگام باشد‎.‎

مثلا ‎G‎ می تواند هر دور از گراف جایگشت ‎F‎ را به خودش ببرد به این شکل که تابع ‎G‎ تابع همانی باشد. اما ما کوچک‌ترین تابع ‎G‎ همگام با ‎F‎ را می‌خواهیم. برای مینیمم کردن تابع ‎G‎ باید هر دور گراف جایگشت ‎F‎ را مستقلا مینیمم کنیم. برای این کار کافیست به ازای هر دور در این گراف مثل ‎C‎ که اندازه‌اش ‎k‎ می‌باشد، دوری مثل ‎C’‎ با اندازه‌ی ‎p‎ پیدا کنیم که اولا ‎k‎ بر ‎p‎ بخشپذیر باشد و دوما شماره کوچک‌ترین رأس در دور ‎C’‎ مینیمم باشد. سپس رأس با مینیمم شماره در دور ‎C‎ مثل ‎u‎ را به رأس با مینیمم شماره در رأس ‎C’‎ مثل ‎v‎ نگاشت می‌کنیم و بقیه‌ی رئوس را به ترتیب دوری به هم نگاشت می‌کنیم.

برای یافتن دور ‎C’‎ و رأس ‎u‎ می‌توان از الگوریتمی شبیه غربال اراتستن استفاده کرد. به این طریق که به ازای هر دور در گراف که طولش ‎k‎ و مینیمم رأس در آن ‎u‎ است، در یک آرایه‌ی ‎n‎ تایی به اسم ‎best‎ تمام مقادیر ‎k‎ و ‎2 \times k‎ و‎3 \times k‎ و ‎\cdots‎ را با مقدار ‎u‎ بروزرسانی می‌کنیم. سپس برای اینکه برای دور ‎C‎ با طول ‎p‎ دور بهینه‌ی ‎C’‎ را بیابیم، با استفاده از مقدار ‎best[p]‎، رأس مناسب ‎u‎ را پیدا می کنیم‎.

پیچیدگی

یافتن دورهای گراف جایگشت ‎F‎ با ‎O(n)‎ بوسیله‌ی الگورتمی مثل ‎DFS‎ امکان‌پذیر است. سپس با روشی شبیه غربال اراتستن آرایه best‎ را مقداردهی می‌کنیم. نکته‌ی قابل توجه در این مرحله این است که برای اینکه پیچیدگی زمانی این قسمت از ‎O(n \log n)‎ شود، باید در ابتدا به ازای هر ‎1 \leq i \leq n‎، دور بهینه به طول ‎i‎ را پیدا کنیم و سپس از روی best[i]‎ مقادیر best[2i] و best[3i] و ‎\cdots‎ را بروزرسانی کنیم. بعد از بروزرسانی آرایه‌ی ‎best‎، به ازای هر دور ‎F‎ با ‎O(d)‎ که ‎d‎ تعداد رئوس این دور باشد، می توان مقادیر ‎G‎ برای رئوس این دور را به‌دست آورد که در مجموع از ‎O(n)‎ زمان می‌برد‎.‎ بنابراین در کل از ‎O(n \log n)‎ می‌توان کوچک‌ترین تابع همگام با ‎F‎ را پیدا کرد‎.‎


ابزار صفحه