مساله «عکاسی از گاوها»

تعدادی گاو در یک صف با ترتیبی خاص ایستاده اند. هر گاو یک شناسه متمایز با بقیه دارد. عموجان می‌خواهد از آن ها با همین ترتیب ایستادنشان در صف عکس بگیرد. همین که عموجان می‌خواهد عکس را بگیرد زیر مجموعه‌ای از گاو ها از صف خارج می‌شوند و به ترتیبی دلخواه در مکان های مختلف صف وارد می‌شوند. عموجان از ترتیب به هم ریخته آن‌ها عکس می‌گیرد. سپس دوباره آن‌ها را با همان ترتیب اولیه مرتب می‌کند تا دوباره عکس بگیرد. اما باز تا می‌خواهد عکس بگیرد زیر مجموعه‌ای از گاوها از صف خارج می‌شوند و با ترتیبی دلخواه وارد آن می‌شوند. و باز هم عکسی از ترتیب به هم ریخته گرفته می‌شود. عموجان این کار را ۵ بار انجام داده و حالا پنج عکس از صف‌های به هم ریخته گاوها دارد. می‌دانیم هر گاو در حداکثر یکی از عکس‌ها از صف خارج می‌شود. به شما تعداد گاو ها و پنج جایگشت از شناسه های گاو‌ها داده شده است. شما باید ترتیب اصلی گاوها را چاپ کنید. می دانیم تعداد گاو‌ها از ۲۰،۰۰۰ بیشتر نیست و شناسه هر گاو متمایز و بین ۰ تا ۱۰۰۰،۰۰۰۰،۰۰۰ است.

راه حل

فرض کنید می‌خواهیم بدانیم گاو x در جایگشت اصلی زودتر آمده است یا گاو y. می‌دانیم هرکدام از این دو گاو حداکثر در یکی از جایگشت‌ها جایش را عوض کرده (شرط مساله است). پس دست بالا ۲ در تا از جایگشت‌ها x و y به ترتیبی غیر از ترتیب اصلی‌شان آمده اند. پس همواره ترتیبشان در حداقل ۳ تا از جایگشت ها (بیش از نیمی از جایگشت ها) درست است. نتیجه می‌گیریم گاو x زود تر از گاو y آمده است اگر و تنها اگر در حداقل ۳ تا از جایگشت ها x زود تر از y آمده باشد.

می‌دانیم برای مرتب کردن یک دنباله کافی هست که بتوانیم هر دو عضو آن را با هم مقایسه کنیم. ساده ترین الگوریتم مرتب سازی دنباله Bubble Sort می‌باشد که به O(n^۲) مقایسه نیاز دارد. اما چون طول دنباله ممکن است ۲۰،۰۰۰ باشد این الگوریتم کند است. الگوریتمی مثل Merge Sort با O(n lg n) عمل مقایسه می‌تواند یک دنباله را مرتب کند.

حال روشی ارایه می‌دهیم که دو عضو را در O(lg n) مقایسه کند. برای این کار از داده‌ساختار map استفاده می‌کنیم. با استفاده از map می‌توان هر شناسه را به اندیسش ربط داد. حال در ۵ map اندیس هر عضو را در جایگشتش ذخیره می‌کنیم. با این اطلاعات می‌توانیم دو عضو را در O(lg n) مقایسه کنیم. چون هر عملیات map هزینه زمانی‌اش O(lg n) هست.

با یک الگوریتم مرتب سازی O(n lg n) و یک تابع مقایسه O(lg n) می‌توان مساله را در O(n lg^۲ n) حل کرد. در زبان C++ می‌توانید از تابع sort در کتابخانه algorithm استفاده کنید. این تابع به شما اجازه می‌دهد تا یک دنباله را با تابع مقایسه‌ای که خودتان درست کرده‌اید مرتب کنید.

صورت اصلی سوال - کد نمونه و راه حل - فایل‌های ورودی و خروجی