جواب سوال

سلام

جواب سوال های الگوریتمی که هفته ی پیش گذاشتیم آماده کردیم. اگه سوالی رو حل نکردید بعد از این که راه حلش رو خوندید سعی کنید خودتون کدش رو بزنید و بعد کد ما رو بخونید.

1- در واقع برای حل این سوال اگر عدد حاج سعید یکی از مقسوم علیه های عدد پویا باشد، پویا برنده است و در غیر این صورت حاج سعید. حال اگرd(x) را مساوی تعداد مقسوم علیه هایxتعریف کنیم ، بنابراین جواب مساله می شود.d(n)/10^9پس در واقع الان بایدd(n)را درO(sqrt(n))حساب کنیم . برای این فرض کنیدn=a*b که(aدر این صورتaاست (چرا؟).پس اگر ما مقسوم علیه های کوچکتر از n را در ((O(sqrt(n حساب کنیم. سایر مقسوم علیه ها هم پیدا می شوند.

کد سوال

      2- برای حل این سوال از برنامه ریزی پویا استفاده می کنیم.

Win[i][j][k]: بازی را کهi دسته ی سمت چپ تا حالا دست نخورده باشند و سپس یک دسته باjسنگریزه داشته باشد و بعد از آن یک دسته باkسنگریزه در نظر بگیرید. حالWin[i][j][k]یک است اگر نفر اول ببرد و در غیر این صورت صفر است.

حال بعد از این تعریف برای بروزرسانی کردن می توانید 3 مجموعه ی زیر را در نظر بگیرید.        

A={Win[i][j][1] , Win[i][j][2], … , Win[i][j][k-1]}

B={Win[i][1][k], Win[i][2][k], … , Win[i][j-1][k]}

C={Win[i-1][a[i]][j], Win[i-1][a[i]][k]}

حال اگر همه ی اعضای A ,B, C یک بود،Win[i][j][k]=0ودر غیر این صورت یک. (چرا؟). 

نکته : با استفاده از ارایه ی کمکی زمان الگوریتم را بهO(n^3)قابل کاهش است.

کد سوال

3-   3- ابتدا تعاریف زیر را در نظر بگیرید :

تورنمنت : به هر گراف جهت داری که بین هر دو راسش دقیقا یک یال جهت دار باشد ، می گوییم.

پادشاه : در گراف جهت دار به راس هایی که به تمامی راس های دیگر با فاصله حداکثر دو مسیر دارند ، پادشاه می گوییم.

لم : هر تورنمنت حداقل یک پادشاه دارد.

اثبات : ثابت می کنیم در یک تورنمت راس با درجه ی خروجی بیشینه پادشاه است. راسvرا راس با این خاصیت در نظر بگیرید. حال سایر راس ها را به دو دسته یAوBتقسیم کنید که دسته یAراس هایی هستند که از راسvبه آنها یال وارد شده است و دسته یBراس هایی که از آنها بهvیال وارد شده است. واضح است که چون گرافمان تورنمنت است هر راس جزvیا درAاست یا درB. حال یک راس ازBمانندuرا در نظر بگیرید. اگر راسی مثلwوجود داشت که  (w->u)پس مسیر(v->w->u)یک مسیر به طول دو ازvبهuاست. اگر هیچ راسی مثلwنباشد در این صورت یعنیu به همه ی اعضایAیال خروجی داشته است و چون یال(u->v)را هم داریم پس درجه ی خروجیuحداقل یکی بیشتر ازvاست که این با فرض ما در تناقض است. پسvبه هر راس ازBمسیری به طول دو و به هر راس ازAمسیری به طول یک دارد . پس حکم اثبات شد.

حال به حل مساله ی اصلی می پردازیم. صورت گرافی مساله می شود:

« در یک تورنمنت تمامی راس هایی را بیابید که به همه ی راس های دیگر مسیر دارند.»

حال می دانیم که گراف یک پادشاه دارد آن را پیدا می کنیم. سپس یال های گراف را بر عکس میکنیم و روی آن پادشاه dfsمیزنیم. مجموعه ی راس هایی که درdfsبه آنها رسیده ایم همان راس های خواسته شده ی مساله اند (چرا؟).

کد سوال

      4- برای راحتی کار به مربع های داخل دایره سیاه و به بقیه سفید می گوییم.

حال ما برای این که تعداد خانه های سیاه جدول را بشماریم می توانیم تعداد خانه های سیاه هر سطر را حساب کنیم و سپس حاصل جمع را چاپ  کنیم. اگر بتوانیم تعدد خانه های سیاه هر سطر را درO(n*log(n))حل کنیم با توجه به این کهnسطر داریم پیچیدگی کل مسالهO(n^2*log(n))می شود که همان چیزی است که مساله می خواهد.

بنابراین از این به بعد روی تعداد خانه های یک سطر خاص متمرکز می شویم.

دایره یiام را در نظر بگیرید. اگر چپ ترین و راست ترین خانه ی این سطر که توسط این دایره سیاه شده اند را به ترتیبL[i]  وR[i]بگیریم.(ستون ها را با 1 تاnاز چپ به راست شماره گذاری کنید.) واضح است که تمامی خانه های بینL[i]وR[i]نیز سیاه می شوند. حال اگر اکنون به هر دایره بازه ی[L[i],R[i]]را نسبت دهیم باید تعداد اعداد داخل کل اینnبازه را به دست آوریم.

برای این ، بازه ها را به صورت اجتماع این بازه ها را ، به صورت چند بازه ی بدون اشتراک حساب می کنیم و سپس اندازه ی بازه های جدید به دست آمده را با هم جمع می کنیم تا به عدد مطلوب برسیم.

حال برای این که اجتماع اینnبازه را به صورت تعدادی بازه ی بدون اشتراک بنویسیم به صورت زیر عمل میکنیم:

بازه ها را بر حسب ابتدای شان مرتب میکنیم. سپس از ابتدا روی بازه ها شروع به حرکت می کنیم. فرض کنید الان روی بازه یiام هستیم و اجتماعi-1بازه ی قبلی به درستی حساب شده اند. حال اگر بازه یiرا در نظر بگیرید این بازه فقط می تواند روی آخرین بازه ی اجتماعi-1بازه ی اول تغییر ایجاد کند. در این صورت اگر انتها ی آخرین بازه قبل از شروع بازه یiبود ، اجتماعiبازه ی اول میشود اجتماعi-1بازه ی اول و بازه یi. در غیر این صورت بازه ی آخر اجتماعi-1بازه را به روز رسانی میکنیم.

کد سوال(در کد برای جلوگیری از پیچیدگی ، مرکز دایره ها روی مراکز مربع ها در نظر گرفته شده اند.)