تبلیغات
الف مثل المپیاد - ترجمه متون یوساکو
در این درگه که گه گه که که و که که شود ناگه/مشو غره به امروزت که از فردا نه ای آگه
درباره وبلاگ

آرشیو

طبقه بندی

آخرین پستها

پیوندها

پیوندهای روزانه

صفحات جانبی

نویسندگان

آمار وبلاگ


1.

جست و جوی کامل:

ایده:

جست و جوی کامل با توجه به اصل :" ساده ترین راه احمقانه رو انتخاب کن " استفاده می شه ! وقتی در مسابقه ای زمان اجرای برنامه اونقدر هست که جست و جوی کامل به جواب برسه اونو استفاده می کنیم ! اگر چه راه بهتری وجود داشته باشه !

این روش باید اولین راه حلی باشه که شما بهش فکر می کنید ! اگر این کار در زمان و حافظه ای که در اختیار شما قرار داده می شه کار می کنه ازش استفاده کنید ! چون معمولا نوشتن برنامش و اصلاحش راحت تره و وقت کمتری می گیره و می تونید وقتتونو بیشتر صرف سوالای سخت تر کنید !

وقتی سوالی که حل می کنید کلا کمتر از دو میلیون حالت داره تک تک اونا رو چک کنید و ببینید اون حالت جوابه یا نه!

 

توجه! توجه !

بعضی وقتا معلوم نیست که دارید از این روش استفاده می کنید

 سوال:لامپ های مهمونی IOI98 

به شما n لامپ داده می شه و 4 کلید ! کلید اول حالت همه ی لامپ ها رو تغییر می ده !کلید دوم لامپ های زوج،کلید سوم لامپ های فرد و کلید آخر 3*k+1 یعنی 1 4 7 10 ....

به شما تعداد لامپ ها n و تعداد کلید هایی که تا الان فشار داده شده(حد اکثر 10000 تا ) و حالت بعضی لامپ ها (مثلا لامپ 7 خاموشه ) در خروجی شما باید تمام حالت هایی که ممکن بود لامپ ها باشن رو چاپ کنید !

برای هر بار زدن یک دکمه 4 حالت داریم ! پس در کل 4 به توان 10000 حالت داریم ( یه چیزی حدود10 به توان 6020) پس از جست و جوی کامل نمی شه استفاده کرد !

حالا توجه کنید که ترتیب زدن کلید ها اصلا تاثیری در حالت پایانی نداره و این باعث می شه حالت هایی که بخوایم چک کنیم بشه حدودا 10 به توان 16 ! ولی این هم هنوز زیاده برای جست و جوی کامل !

حالا به این هم توجه کنید که دوبار زدن یک دکمه مثل اینه که اصلا نزنیمش و تاثیری در کار ما نمی ذاره ! حالتی که برای هر کلید لازمه چک کنید اینه که یه دکمه رو یه بار بزنیم یا کلا نزنیم ! پس کلا تعداد حالت های ممکن که لازمه چک بشه 2 به توان 4 می شه 16 حالت ! مطمئنا می شه با جست و جوی کامل به جواب رسید !

سوال 3:ساعت ها IOI94

9 تا ساعت داریم که به صورت یک جدول 3*3 کنار هم قرار دارن و هرکدوم یکی از ساعت های 3 6 9 12 رو نشون می ده !هدف اینه به حالتی برسیم که همه 12 رو نشون بده ! در هر حرکت هم می تونیم یکی از 9 کلید رو بزنیم ! هر کلید هم تعدادی از ساعت ها رو 90 درجه ی ساعت گرد جلو می بره !

با کمترین تعداد حرکت به حالت مطلوب (همه 12 ) برسید !

بدیهی ترین راه اینه که اول چک کنیم آیا راه حلی با 1 حرکت وجود داره؟ اگه نداشت بعد 2 ! اگه نه ....تا وقتی به جواب برسیم ! اگه k حرکت انجام داده باشیم برای جواب 9به توان k حالت رو چک می کنیم ! از اونجا که ممکنه k بزرگ باشه این کار خیلی وقت می بره و جواب نمی ده !

باز هم توجه کنید ترتیب زدن دکمه ها تاثیری نداره این باعث می شه زمان اجرامون به k به توان 9 کاهش پیدا کنه !ولی باز هم این زمان کافی نیست !

ولی باز هم چون هر دکمه ای 4 بار زده بشه اصلا زده نشه سنگین تریم پس می شه بگیم هر دکمه آخرش 3 بار زده می شه ! پس در کل 4 به توان 9 حالت داریم ! که در کل می شه 262072 حالت که می شه 10000000 حالت رو تو یه ثانیه چک کرد !با این طرز فکر چک کردن همه حالت ها کافیه !

سوالات نمونه :

 دوشیدن شیر گاو ها :  usaco مسابقات   1996

برنامه ی دوشیده شدن گاو ها به شما داده می شه ( مثلا گاو دار اول از زمان 300 تا 1000 گاو ها رو می دوشه و گاو دار 2 از 700 تا 1200 ) از شما خواسته شده :

1)      طولانی ترین فاصله زمانی رو پیدا کنید که در هر لحظه از اون حد اقل یه گاو دوشیده می شده

2)      طولانی ترین فاصله زمانی که در اون هیچ گاوی دوشیده نشده

 

 گاو های حرفه ای و پسر عمو های حرفه ایشون usaco فاینال مسابقات 1995:

یه عدد حرفه ایه اگه م.م.ع اش(مجموع مقسوم علیه هاش) بشه خودش مثلا 28=1+2+4+7+14

یه مجموعه هم حرفه ایه اگه م.م.ع اولی بشه دومی ! م.م.ع دومی بشه سومی ! و.... م.م.ع آخری بشه اولی !

 

حالا به هر گاو جان (یه گاودار) یه عدد داره ! اعداد هم از (1 تا 32000) ان ! یه گاو حرفه ایه اگه عددش حرفه ای باشه ! یه گروه از گاو ها هم پسر عمو های حرفه ای حساب می شن اگه مجموعه ی عدداشون یه مجموعه ی حرفه ای باشه !

از شما خواسته شدا تمام گاو های حرفه ای و تمام مجموعه پسر عموهای گاو حرفه ای رو چاپ کنید !

نسخه ی انگلیسی متن


2.

الگوریتم حریصانه(گیریدی)

مثال: تعمیر طویله 1999 usaco مسابقه عمومه بهاره

یک طویله طولانی که اتاق اتاقه داریم که جلوی بعضی اتاقاش نیاز به تعمیر داره و باید با تخته پوشونده بشه . شما مجازید که حد اکثر از n 1<=n>=50 تخته که هر کدوم ممکنه جلوی یه تعداد دلخواه از اتاقای مجاورو پوشش بده استفاده کنید

با این تخته ها طوری همه ی اتاقایی که لازمه رو پوشش بدید که کمترین تعداد اتاق پوشش داده شده باشن!یعنی یه سری از اتاقا می خوان پوشش داده بشن یه سریا نمی خوایم پوشش داده بشن ! چی کار کنیم که با حد اکثر مصرف اون تعداد چوب اونایی که می خوایم پوشش ندیم ولی پوششون دادیم حد اقل بشن و همه ی اونایی هم که می خوایم پوشش داده بشن پوشش داده شده باشن !

 

ایده:

ایده ی اصلی الگوریتم های حریصانه اینه که جواب برای سوالای بزرگتر رو از روی جوابای مثالای کوچیک تر پیدا کنیم ! بر خلاف بقیه ی الگوریتم ها همیشه الگوریتم حریصانه بهترین جوابی رو که پیدا می کنه در طی الگوریتم نگه می داره ! یعنی مثلا برای این که جواب برای n=5 رو پیدا کنیم اول جواب برای n=4 رو پیدا می کنیم و از روی اون به جواب n=5 می رسیم

الگوریتم های حریصانه معمولا خیلی سریع اند ! یعنی معمولا یه چیزی بین خطی تا درجه دوم اند و معمولا خیلی حافظه هم نمی خوان ! متاسفانه همیشه درست کار نمی کنند ! اما اگه برای سوالی الگوریتم حریصانه درست باشه کد زدنش راحت و اجراشم هم سریعه !

مسائل:

معمولا دو مساله ی پایه ای در الگوریتم های حریصانه وجود داره

طرز ساخت :

چطور از جواب کوچکتر به جواب برای بزرگتر برسیم؟ این معمولا یه تابعه برای سوال ! برای مثال بالا چطور از 5 قطعه چوب به جواب واسه 4 قطعه برسیم ؟ فرض کنید بهترین حالت پوشش اتاقا رو با 4 قطعه داریم ! حالا اگه بخوایم ببیینیم بهترین حالت با 5 تا قطعه به دست بیاریم کافیه به این نکته دقت کنید که اگه یکی از اون 4 تا قطعه به 2 قسمت تقسیم بشه به جوابی با 5 قطعه می رسیم ! حالا کی این جواب بهترین جواب ممکن می شه ؟ وقتی که با تقسیم این قطعه به دو قطعه بیشترین حدی که می تونیم از اتاقایی که نمی خوایم پوشش بدیم ولی با 4 قطعه پوششون دادیم رو دیگه پوشش ندیم ! واسه همین کافیه ببینیم طولانی ترین بازه ای که اتاقا رو بی خود پوشش دادیم کجاست ؟ اون یه تیکه رو دیگه پوشش ندیم ! برای همین الگوریتم این میشه : همه ی اتاقا رو اول با یه قطعه ی خیلی بلند پوشش بده ! در هر مرحله بزرگ ترین بازه ی بی خودی رو حذف کن !

آیا جواب می ده ؟

مسابقه ی واقعی برای برنامه نویسا اینه که ببینن آیا الگوریتم حریصانه جواب می ده یا نه ؟ اگه الگوریتم حریصانه برای ورودی های نمونه ی سوال یا حتی اونایی که به ذهنتون می رسه و یا حتی تست های رندوم هم درست جواب بده ولی یکی ! و فقط هم یه ورودی وجود داشته باشه که الگوریتم حریصانه براش جواب نده ، در این صورت تمام ورودی های مسابقه که برنامتون قراره باش چک بشه از اون نوعه !

 

برای مثال بالا : فرض کنید یه وقتایی الگوریتم حریصانه جواب نده ! در این صورت توی جواب بهینه یه تعدادی از اتاقایی که می خوایم پوشیده نشن رو پوشش نداده که طولش ماکزیمم نبوده به جاش بازه ی بزرگتری رو پوشش داده !در این صورت می تونیم بگیم این جواب بهینه نیست چون می تونست به جاش دو سر قطعه کوچیک تره رو به هم وصل کنه ( دو قطعه ی جفتشو بکنه یه قطعه ) به جاش قطعه ی ماکسیمم رو بکنه دو قطعه و پوششش نده و به یه جواب بهتر برسه !

در ضمن اگه توی جواب بهینه دو تا بازه وجود داشته باشه که طول ماکسیمم داشتن ولی یکیشون پوشیده شده بود و یکی شون نشده بود خوب می شه هر کدومو که دلمون خواست برداریم بپوشونیم و اون یکی رو خالی بذاریم ! در جواب فرقی نمی کنه !

برای همین جواب بهینه ای وجود داره که بازه ی ماکسیممی رو که ما انتخاب می کنیم نداشته باشه ! برای همین هر مرحله کار ما درسته پس الگوریتم اینجا درست کار می کنه !

 

نتیجه گیری:

اگه الگوریتم حریصانه درست کار می کنه ازش استفاده کنید ! چون کد زدنش راحته ! راحت دیباگ می شه ! سریع اجرا می شه ! و خیلی هم حافظه نمی گیره ! و در کل راه حل خیلی خوبیه واسه مسابقه ها ! فقط تو لیست بالا تنها چیزی که کمه چیه ؟ درستیه ! چون همیشه درست کار نمی کنه ! اگه درست جواب می ده واسه یه سوالی ازش استفاده کنید ولی فکر نکنید همیشه درسته !

 

مسائل نمونه :

مرتب سازی یه دنباله سه عددی ! ioi 1996

به شما یه دنباله از اعداد 1 و 2 و3 می دن و می خوان با کمترین تعداد ممکن جابه جا کردن این اعداد دنباله رو به ترتیب سعودی مرتب کنید ! جا به جایی یعنی جای دو عدد توی این دنباله رو با هم عوض کنید ( لازم نیست مجاور باشن)

الگوریتم: بعد از مرتب شدن دنباله 3 تا قسمت داره ! قسمتی که فقط 1 اونجاست . قسمتی که فقط 2 اونجاست و قسمتی که فقط 3 اونجاست .  الگوریتم حریصانه میاد هر بار تا جایی که می تونه 1 هایی که تو قسمت 2 باشن با 2 های قسمت 1 ، همچنین 1 های قسمت 3 رو با 3 های قسمت 1 ، 3 های قسمت 2 با 2 های قسمت 3 رو جا به جا می کنه ! تا جایی که دیگه نشه ! در این صورت دو حالت داریم : یا یه سری 1 توی 3 اند یه سری 3 توی 2 و یه سری 2 توی 1 ! یا یه سری 3 توی 1 یه سری 2 توی 3 و یه سری 1 توی 2 ! (برعکس قبلی) که اینا رو هم با هر 2 حرکت 3تاشونو می بریم سر جاشون مثلا واسه حالت اول: هر بار یه 1رو می بریم توی جاش به جاش یه 2 می ره سر جای 1 توی 3 ! بعد جای اون 2 رو با یه 3 عوض می کنیم !

آنالیز:مشخصه هر جابه جایی حد اکثر 2 تا رو سر جاش می ذاره پس قسمت اول الگوریتم بهینه است ! در ترتیب جا به جا کردن ها داخل ترتیب نهایی تاثیری نداره (بلکه محل هایی که عوض می شن مهمه)وقتی هم اون کار انجام شده باشه اینه که با هر 2 جابه جایی 3 عنصر مرتب شن . که اینم در قسمت دومش اجرا می شه !

سکه های دوست ! مثال نقض(با تلخیص خود یوساکو(نه تلخیص ما)):

می خوایم با یه مجموعه از سکه ها ( از هر نوعی بی نهایت داریم) یه مقدار خاص پول رو خورد کنیم. به طوری که از کمترین تعداد سکه استفاده کرده باشیم.در ضمن بین این مجموعه ی سکه حتما 1 سنتی هم هست.

الگوریتم:  هر بار از مقدار باقی مونده ی پول بزرگترین سکه ای رو که می شه باهاش ادامه داد برمی داریم و اون مقدار رو از پول کم می کنیم.

آنالیز(البته از نوع غلطش): مشخصا شما هیچ وقت سکه با ارزش کمتری رو برنمی دارید، این به این معنیه که اگه قرار بود از سکه با ارزش کمتری استفاده کنید تعداد بیشتری سکه استفاده می شد. پس این الگوریتم درست کار می کنه.

شاید هم نه:الگوریتم معمولا کار می کنه. در واقع برای مجموعه سکه های رایج آمریکا(خیلی شبیه قبلنای ایرانه) {1و5و10و25} همیشه درست کار می کنه. اما برای مجموعه های دیگه مثلا {1و5و8و10} و مثلا موقع خورد کردن 13 سنت پول، الگوریتم حریصانه اول یه سکه ی 10 سنتی برمی داره بعد 3 تا 1سنتی یعنی 4 تا سکه کلا . اما می شد با دو سکه یکی 5 و یکی 8 سنتی قضیه رو حل کرد.

مرتب کردن مکان شناسانه(منظور همون توپولوژیکال سورته :دی):

یه سری اشیا داریم که می خوایم توی یه صف بچینیمشون و یه سری قوانین که باید حتما رعایت بشه. قوانین به این شکله که می گه جسم A باید حتما قبل B چیده شده باشه .ترتیبی پیدا کنید که همه ی قوانین برقرار باشه.

الگوریتم: یه گراف بسازید و به ازای هر جسمی یه راس و به ازای هر قانون اگه قراره A قبل B باشه ، یه یال جهت دار از راس A به B وصل کنید. حالا هر بار حریصانه بیاید راسی رو پیدا کنید که درجه ی ورودیش صفره. اونو بذارید توی صف و تمام یال های خروجیش رو پاک کنید. همین کار رو برای اونایی که جسممون الان بشون یال خروجی داشت انجام بدید(یعنی ببینید درجه ی ورودیشون صفره یا نه). اگه الگوریتم جایی راسی با درجه ی ورودی صفر پیدا نکرد ترتیبی که همه ی قوانین رعایت بشه نداریم.

نسخه ی انگلیسی متن: