المپدیا

فرض کنید جایگشت $P$ را به پیمان بدهیم و پاسخ $x$ از او دریافت کنیم. در صورتی که دو عضو اول $P$ را جابجا کنیم و دوباره بپرسیم، بسته به اعدادی که در دو جایگاه اول هستند، چه پاسخ‌های متفاوتی بر حسب $x$ می‌توانیم دریافت کنیم؟

آیا می‌توانیم با $k$ پرسش به جایگشتی برسیم که مطمئنیم یکی از اعداد ۱ تا $k$ در جای درست قرار گرفته‌اند؟

برای رسیدن به خواسته‌ی راهنمایی ۲، تمام جایگشت‌های دوری ۱ تا $k$ را در $k$ جایگاه ابتدایی قرار دهید. حال کدام را انتخاب کنیم تا مطمئن شویم حتما در جایگاهی با جایگشت پنهان اشتراک دارد؟

پاسخ راهنمایی ۳: جایگشتی که بزرگ‌ترین پاسخ پیمان را بابت آن دریافت کرده باشیم.

حال با راهنمایی (۱) به جایگاهی دست پیدا کنید که مطمئن باشیم عدد آن سر جایش است.

آیا می‌توان در $O(k)$ فهمید که از میان اعداد ۱ تا $k$ هیچ یک در جایگاه‌های ۱ تا $k$ قرار ندارند؟

جایگشت پنهان را با بازه‌های $\sqrt{n}$ تایی افراز کنید. این بازه‌ها را $I_1, I_2, ..., I_r$ در نظر گیرید.

فرض کنید بخواهیم جایگاه اعداد ۱ تا $\sqrt{n}$ را بیابیم. چطور این کار را در $O(n)$ انجام دهیم؟

اعداد ۱ تا $\sqrt{n}$ را در نظر بگیرید. می‌توان در $O(\sqrt{n})$ تشخیص داد آیا عددی از میان آن‌ها در $I_1$ قرار دارد یا خیر. اگر قرار داشت چه کنیم؟ اگر قرار نداشت چطور؟

پاسخ سوالات راهنمایی ۴: اگر قرار داشت، می‌توانیم دوباره عمل را تکرار کنیم. اگر نداشت به سراغ $I_2$ برویم.

اگر الگوریتم ارائه شده برای اعداد ۱ تا $\sqrt{n}$ را در نظر بگیرید، در $O(n)$ جایگاه تمام آن‌ها را یافته‌ایم. حال چند دسته عدد داریم که فرایند مذکور را در مورد آن‌ها تکرار کنیم؟