راه حل های مسابقه خداحافظ ۹۷

سلام!
راه حل های مسابقه بالاخره منتشر شد!

سوال ۱
برای این سوال راه های زیادی وجود دارد که به دلیل سادگی تنها یک روش را ذکر می کنیم. کافی است برای تولید n کلمه، کلماتی را در نظر بگیریم که با s شروع می‌شوند و بعد از آنها i تا حرف a آمده باشد در حالیکه 0 <= n > i

سوال دو
برای پیاده سازی این سوال، میتوانیم از stack(پشته) استفاده کنیم. به این صورت که رشته را از سمت چپ به راست پیمایش کنیم و در هر نوبت، به ازای کاراکتر = در صورت خالی نبودن stack، عضو بالایی stack را برداریم و به به ازای کاراکتر های غیر =، کارکتر را در بالای استک اضافه کنیم.در آخر اجزای stack، از پایین به بالا به ترتیب اجزای رشته نهایی است.

سوال سه
ابتدا برای هر شخص، یک in و یک out در نظر میگیریم که به ترتیب زمان ورود و خروج به ثانیه است. حال میخواهیم ورود و خروج ها را پیمایش کنیم. از زمان ۰ شروع میکنیم و تا ماکسیمم زمانی که ورود داشته ایم پیش میرویم. میخواهیم به ازای هر زمان، تعداد افراد داخل مهمانی را بدست آوریم. فرض کنید تا ثانیه آی ام را بدست آورده ایم و میخواهیم زمان آی+۱ را بدست آوریم. کافی است تعداد مهمان هایی که در زمان آی + ۱ به تازگی به مهمانی پیوسته اند را به تعداد افراد داخل مهمانی تا زمان آی اضافه کنیم و تعداد افرادی را که در زمان آی+۱ مهمانی را ترک کرده اند از تعداد افراد داخل مهمانی کم کنیم. زیرا هر کسی که در زمان آی+۱ بخواهد در مهمانی باشد یا در زمان آی+۱ له مهمانی آمده که شمرده ایم یا که قبل از آی+۱ آمده که برابر است با کسانی که در زمان  آی هم داخل مهمانی هستند ولی در زمانی بیش از آی+۱ مهمانی را ترک میکنند.

سوال ۴
برای هر عدد بین  ۱ تا w، تعداد زیر درخت هایی که اور اعدادش، ساب‌مسک آن عدد می شود را بدست میاوریم.(تمامی اعداد را در مبنای دو در نظر میگیریم-a ساب مسک b است اگر و تنها اگر  a OR b = b)فرض کنید میخواهیم برای یک عدد دلخواه مثل mask این کار را انجام دهیم.برای این کافی است زیر گراف القایی روی تمام راس هایی را پیدا کنیم که اعداد آن ها، ساب‌مسک mask هستند را پیدا کنیم.OR اعداد هر زیر گراف از زیر گراف ذکر شده، مشخصا ساب‌مسک mask خواهد بود. هم چنین اگر یک زیر گراف از گراف اصلی، OR اعدادش ساب‌مسک mask شود، تک تک اعداد آن زیر گراف هم ساب‌مسک mask هستند.حال تعداد زیر درخت های یک جنگل را هم میتوانیم با o(n) بدست بیاوریم که n تعداد رئوس جنگل است. (چگونه؟) بنابر این با o(nw) می توانیم برای هر عدد مثلmask، زیر درخت هایی با اور سابمسک mask را بدست آوریم. فرض کنید این عدد برای هر mask، در ارایه ای مثل cnt سیو شود. اکنون میخواهیم تعداد زیر درخت هایی با OR مساوی mask را بدست اوریم. فرض کنید این اعداد را در آرایه ای به نام ans نگه داشته ایم. در مورد ans برای عدد mask می توان گفت:ans[mask] = cnt[mask] – sigma (ans[i])که i ساب مسک mask هستند و کوچیکتر اکید از mask.(چرا؟)این دیپی هم میتوان به راحتی به دست آورد. کافی است با شروع از 0، ans را بدست اوریم. برای هر عدد هر بار، روی اعداد کوچکتر از آن فور میزنیم و در صورتی که ساب مسک عدد مورد نظر بودند، ans آنهارا از cnt عدد مورد کم میکنیم. در آخر cnt عدد مورد نظر برابر ans آن است. اردر این کار هم از o(w×w) است.توجه کنید که برای بدست آوردن ans از روی cnt، راه هایی با اردر بهتر نیز وجود دارد؛ از جمله می‌توان به راه w logw اشاره کرد.

سوال پنج
صورت سوال این است که اگر جای گردو ها ۱ بگذاریم و بقیه جا ها صفر، تعداد مستطیل هایی را میخواهیم که ایکس اور اعداد داخلش صفر باشد. هم چنین اگر تعداد مستطیل ها با ایکس اور یک را بدانیم، تعداد مستطیل ها با ایکس اور فرد هم بدست می آید. 
ابتدا حالت ساده تری از سوال را حل میکنیم. اگر مستطیل ۱ سطر و m ستون داشته باشد جواب چند است؟
یک مستطیل دلخواه را در نظر بگیرید که شامل بازه بسته‌باز l تا r باشد. ایکس اور اعداد این مستطیل را با (F(l, r نشان میدهیم. میدانیم :(F(l, r) = f(0, r) ^ f(0, l
یعنی ایکس اور مستطیلی را بر حسب ایکس اور دو مستطیل نوشتیم که پریفیکسی از این سطر هستند. حال اگر قرار باشد ایکس اور این مستطیل ۱ شود، باید یکی از دو مستطیل ذکر شده ایکس اوری مساوی ۱ داشته باشد و دیگری صفر. پس اگر تعداد مستطیل های پریفیکسی با ایکس اور ۰، a باشد و تعداد مستطیل های پریفیکسی با ایکس اور ۱، b، آنگاه تعداد زیر مستطیل های این سطر با ایکس اور ۱، a×b خواهد بود.( دقت کنید که یک مستطیل تهی هم داریم که شامل بازه بسته‌باز ۰ تا ۰ است و ایکس اور آن را صفر در نظر گرفته ایم)
حال برای حل سوال اصلی، میخواهیم به ازای هر i و j، تعداد مستطیل های پریفیکسی با ایکس اور های ۰ و ۱ را که خطوط افقی آنها، y=i و y=j است بدست آوریم. برای این کار، یک آرایه در نظر میگیریم که در خانه k ام آن، ایکس اور مستطیل پریفیکسی که خط عمودی راستی‌ش x=k است نوشته شده. حال به ازای i, j این کار را میکنیم. ابتدا فرض میکنیم i کوچکتر یا مساوی j است.۱. اگر i=j بود، فور میزنیم و تمام پریفیکس ها را دستی ست میکنیم. ۲. در غیر این صورت، آرایه مربوط به i و j-1 را در نظر میگیریم. این آرایه را با آرایه مربوط به j, j، نظیر به نظیر ایکس اور میکنیم. یعنی خانه k ام آرایه جدید، ایکس اور خانه های k ام دو آرایه قبلی است . واضح است که نتیجه ایکس اور های مستطیل های پریفیکسی مربوط به i و j خواهد بود.
حال باید تعداد ۱ ها و ۰ های این آرایه را بدست بیاوریم تا تعداد زیر مستطیل های این حالت را بدست آوریم .
به صورت عادی میتوان ایکس اور های ذکر شده را با (o(m انجام داد و باید برای هر سطر، ارایه را نگه داری کنیم که آن هم (o(nm خواهد بود. ولی برای هر i و jدیگری مشخصا نیاز به نگه داری ارایه اش نیست.هم چنین کل عملیات های ما برابر خواهد بود با :O(nm + (nm) * m)که nm * m به دلیل عملیات ایکس اور است و بدست آوردن تعداد ۱ های ارایه.
حال اگر جای این که برای هر سطر یک آرایه بگیریم، یک بیت‌ست بگیریم، عملیات های ایکس اور با اردر m/32 انجام میشود. هم چنین بیت‌ست با اردر m/32 تعداد ۱ ها را هم به ما می دهد. پس کل عملیات های مربوط به ایکس اور و بدست آوردت تعداد ۱ ها و ۰ ها با اردر nm ×m/32 انجام میشود که با لیمیت های سوال، تایم قابل قبولی خواهد داشت.

سوال ۶
به زودی…

سوال هفت
گرافی n راسی می‌سازیم و در آن به ازای هر قرص یک راس می‌گذاریم، همچنین به ازای هر a و b که باید قرص a را قبل قرص b بخوریم، یک یال از راس a به راس b می‌گذاریم، حال در واقع می‌خواهیم یک مرتب‌سازی توپولوژیکال (Topological Sort) روی رئوس‌ ارائه دهیم، به طوری‌که تمام یال‌ها رو به جلو باشند (تعریف مرتب‌سازی توپولوژیکال) و راس iام، در آرایه در مکان l تا r باشد.

حال ابتدا رئوس را بر مبنای مرتب‌سازی توپولوژیکال مرتب می‌کنیم (بدون آنکه به شروط مربوط به جایگاه رئوس توجهی کنیم) به طوری‌که تمام یال‌ها به سمت جلو باشند.

می‌خواهیم به ازای هر راس v بدست بیاوریم آخرین جایی که می‌تواند بیاید کجاست به‌ طوری‌که شرط هیچ کدام از راس‌هایی مانند u که v به u یال دارد خراب نشود، برای این منظور از آخرین راس در مرتب سازی توپوژیکال شروع کرده و به ترتیب تا راس اول می‌رویم، و به هر راس v که رسیدیم، به ازای تمام راس هایی مانند u که به v یال دارند قرار می‌دهیم:

حال دوباره می‌خواهیم یک مرتب‌سازی توپولوژیکال ارائه دهیم، به طوری‌که شروط جایگاه رئوس نیز برقرار باشند.

بدون شک تنها رئوسی مانند i را در این مرتب‌سازی می‌توانیم در ابتدا قرار دهیم، که هیچ ورودی‌ای نداشته باشند و l = 1، تمام رئوس با این خاصیت را به رئوسی که می‌توانند در حال حاضر بیایند در نظر بگیرید. رئوسی نیز که هیچ ورودی ای ندارند را نیز ذخیره می‌کنیم، تا یادمان باشد وقتی به جایگاه رسیدیم، راس را به راس‌هایی که می‌توانند در این جایگاه بیایند اضافه کنیم. (برای مثال در vector مخصوص به x ذخیره می‌کنیم)

حال ادعا می‌کنیم بین تمام رئوسی که می‌توانند در این جایگاه ظاهر شوند، بهتر است راسی مانند را انتخاب کنیم به طوری‌که مقدار کمینه شود، زیرا در بین تمام رئوسی که می‌توانند بیایند، آمدن این راس واجب تر است 🙂 چون محدودیتی بیش‌تر از دیگر راس‌ها دارد. اگر هم در حال حاضر هیچ راسی وجود نداشت که بتواند بیاید، جوابی برای سوال وجود ندارد و را چاپ می‌کنیم و برنامه را خاتمه می‌دهیم.

در آخر راسی که گذاشتیم را از گراف حذف می‌کنیم و درجه‌ی ورودی بقیه راس‌ها را update می‌کنیم، یعنی به ازای تمام رئوسی که این راس به آن‌ها یال دارد، درجه ورودی آن‌ها را یکی کم می‌کنیم، و اگر درجه ورودی راسی مانند در جایگاه صفر شد، اگر بود، راس i را به مجموعه رئوسی که می‌توانند بیایند اضافه می‌کنیم، و در غیر‌اینصورت به vector مخصوص l به راس i را اضافه می‌کنیم.