خانه توسعهدهنده با کوئرا | توسعهدهنده مسابقات و رویدادها پاسخ سوالات مسابقه ۲۶ الگوریتمی
پاسخ سوالات مسابقه ۲۶ الگوریتمی

خب بدون مقدمه میریم سراغ سوال ها :
برای سوال ام ، ai×bi بار نفس ها گرفته می شود. پس پاسخ برابر است با ∑i=1nai×bi.
کد ++C از سایین اعلا
کد Mono C# از محمد احسان شعبانی
برنامه را شبیه سازی می کنیم و خط به خط آن را اجرا می کنیم. چون ورودی های دستور goto ثابت هستند اگر یک دستور را دو بار ببینیم هیچ وقت برنامه تمام نمی شود. پس هر خطی که میبینیم را مارک می کنیم و اگر به خط مارک شده ای دوباره رسیدیم ، −1 چاپ می کنیم. اگر هم که برنامه تمام شد مقادیر cout را در انتها چاپ می کنیم.
پیچیدگی زمانی O(n)
امید ریاضی تعداد اعداد متفاوت برابر است با جمع احتمال این که عدد x روی سردر شاز نصب شود به ازای همه x های ممکن. از O(n2) می توانیم x هایی که احتمالشان 0 نیست(جمع حداقل یک بازه هستند) را بدست آوریم. حال به ازای یک عدد x می خواهیم احتمال این که x وجود داشته باشد را بدست آوریم. dpa را برابر تعداد حالت ساخته نشدن x در a تای اول دنباله در نظر می گیریم. dpa=∑b=0a−1dpb به شرطی که جمع بازه (b,a] برابر x نباشد.پس اگر به ازای x تعداد بازه هایی که جمعشان x است را cnt بنامیم آنگاه می توان dp را از O(n+cnt) می توان محاسبه کرد.احتمال حضور x هم می شود −2n−1dpn 1 . پیچیدگی زمانی O(n3)
ابتدا حلی با O(n2) را بررسی می کنیم.باید گرافی بسازیم که به ازای هر رابطه مثل عمو اگر b عموی a بود آنگاه از a به b یالی جهت دار قرار داشته باشد که روی آن واژه عمو نوشته شده است. حالا جهت یال های گراف را برعکس می کنیم.کوتاه ترین مسیر از b به a را در نظر بگیرید(و در صورتیکه چند کوتاه ترین مسیر بود مسیری که از لحاظ لغت نامه ای ماکسیمم است را در نظر بگیرید).جواب مسئله رشته متناظر با این مسیر است!(در انتها توضیح می دهیم که چطور می توان یک کوتاه ترین مسیر با شرط بزرگترین بودن از لحاظ ترتیب لغت نامه ای را یافت).
حالا برای اینکه تعداد یال های گراف را کم کنیم از ایده اضافه کردن راس استفاده می کنیم. به این صورت که اگر بخواهیم مجموعه راس های A را به مجموعه راس های B وصل کنیم و روی همه یال ها رشته s را بنویسیم آنگاه به جای اینکار یک راس جدید اضافه کرده و همه A را به راس جدید و راس جدید را به همه B وصل میکنیم و روی راس جدید رشته s را می نویسیم(این عملیات fA,B,s نامگذاری می کنیم) . توجه کنید که در این گراف جدید رشته ها روی راس ها نوشته می شوند نه یال ها!
برای ساختن رابطه های پدر به ازای هر راس مثل u باید fA,B,pedar را اجرا کنیم:
A=u B=par1u,par2uساختن رابطه های پسر مشابه پدر انجام می شود.
برای ساختن رابطه های برادر به ازای هر راس مثل u باید fA,B,baradar را اجرا کنیم:
A=B=sonsuبرای ساختن رابطه های عمو به ازای هر راس مثل u باید fA,B,amoo را اجرا کنیم:
B=sonsu A=sonssonsuتعداد راس های گراف O(n) است.با توجه به اینکه ∑usonsu تعداد رابطه های پدر و پسری را می شمارد و ∑usonssonsu تعداد رابطه های پدر و پدربزرگی را می شمارد و هر کس حداکثر ۲ پدر و ۴ پدر بزرگ دارد میتوان نتیجه گرفت تعداد یالهای گراف ساخته شده هم O(n) است.
حالا تنها کافی است بتوانیم یک کوتاه ترین مسیر در این گراف پیدا کنیم (چون هر رابطه از طی کردن دو یال شکل می گیرد طول این کوتاه ترین مسیر ۲ برابر کوتاه ترین رابطه است) که رشته متناظر آن (که روی راس ها رشته نوشتیم و رشته متناظر به راس های اصلی پوچ است) از لحاظ ترتیب لغت نامه ای ماکسیمم باشد! همچنین توجه کنید که یال ها برعکس شده اند و کوتاه ترین مسیر از b را می خواهیم.
این کار را با کمک الگوریتم bfs با کمی تغییر انجام میدهیم. بدون توجه به رشته روی راس ها bfs را با شروع از راس b اجرا می کنیم.حالا گراف ما لایه بندی شده است.تنها یال هایی که بین لایه های متوالی هستند را نگه دارید و بقیه را دور بریزید زیرا برای به دست آوردن کوتاه ترین مسیر لازم و کافی است که تنها از این یال ها استفاده کنیم.به ازای هر راس مثل u رشته ماکسیممی که می توان با طی کردن مسیری از ریشه به آن راس ساخت را Su بنامید.هدف این نیست که Su ها را به دست آوریم بلکه این است که بفهمیم برای ساختن Su راس قبل از u در مسیر که بوده است.( که در لایه قبلی است) زیرا اگر این را بفهمیم می توانیم مسیر مورد نظر را بسازیم.
برای این کار تنها لازم است به ازای هر راس مثل u عددی مثل rank محاسبه کنیم که نشان می دهد اگر لایه مربوط به u را در نظر بگیریم رشته Su از لحاظ بزرگی چندمین رشته در این لایه است.(و اگر Si=Sj بود آنگاه ranki=rankj). حالا اگر rank راس های لایه قبلی را داشته باشیم به ازای هر راس مثل u در لایه فعلی می توان به دست آورد که راس قبل از آن باید چه کسی باشد.( یکی راسی که rank آن بیشینه است).پس تنها کافی است بتوانیم با داشتن rank های لایه قبلی rank های لایه جدید را بسازیم!به ازای هر راس مثل u در لایه فعلی بین تمام راس هایی لایه قبلی که به u یال دارند راسی مثل y را بیابید که ranky ماکسیمم باشد.حالا به ازای تمام راس های لایه جدید مثل u قرار دهید:
valu=pair<ranky,stringu>اگر val مربوط به تمام راس های لایه جدید را مرتب کنید می توان از روی آن rank های لایه جدید را به دست آورد. پس راه حل ما O(n∗log(n)) می باشد.قابل ذکر است که به راحتی می توان حل بالا را O(n) کرد
ابتدا صورت سوال را دقیق تر بیان می کنیم.یک جایگشت n تایی داریم. m تا جایگشت دیگر هم داریم که مجموع اندازه های آنها را با σ ( بخوانید سیگما) نشان می دهیم.یه یک بازه از جایگشت اصلی خوب می گوییم اگر فشرده شده اعداد آن برابر با یکی از m جایگشت باشد.حالا ما باید تعداد راه های افراز جایگشت اصلی به بازه های خوب را بگوییم.
ادعا می کنیم تعداد طول های مختلف در m جایگشتمان از O(σ) است.که در اینصورت می توان نتیجه گرفت تعداد بازه های خوب از O(nσ) است.حالا اگر بتوانیم تمام بازه های خوب را شناسایی کنیم می توانیم به راحتی جواب را به دست بیاریم.(کافیست dpi را تعداد افراز i عضو اول جایگشت اصلی به بازه های خوب تعریف کنیم و جواب dpn است). برای شناسایی بازه های خوب دو الگوریتم می دهیم. الگوریتم اول از O(n MaxLen lg(n)) کار می کند(MaxLen ماکسیمم طول در آن m جایگشت است) و الگوریتم دوم از O((σ+(nm))×lg(n))کار می کند.سپس با ترکیب این دو الگوریتم مساله از O(nσlg(n)) حل می شود.(کافیست آن m جایگشت را به دو دسته با طول کمتر از σو بیشتر از آن تقسیم کنید و بازه های خوبی که هر دسته می سازد را محاسبه کنیم).
الگوریتم اول:
قبل از شروع به این تبدیل جایگشتی توجه کنید:
فرض کنید جایگشت k عضوی p را داریم و این تبدیل به ما آرایه k تایی a را میدهد که :
ai تعداد اندیس های j≤ i که aj≤ ai
به این فرم از نمایش جایگشت فرم عجیب می گوییم.می توان ثابت کرد بین جایگشت های k تایی p به آرایه های k تایی a که (1≤ ai≤ i) تناظر یک به یک برقرار است پس هر جایگشت یک فرم عجیب دارد و هر فرم عجیب معادل یک جایگشت است!
حالا توجه کنید که هر آرایه با اعداد متمایز هم یک فرم عجیب دارد.(دقیقا مشابه بالا تعریف می شود).
حالا توجه کنید که فشرده آرایه a برابر با جایگشت p می شود اگر و فقط اگر فرم عجیب آن دو برابر باشد.
حالا کل m جایگشت را به فرم عجیب در بیاورید(این کار از O(σlg(n)) با داده ساختاری مثل درخت فنویک ممکن است).سپس آنها را در ترای بریزید.حالا به ازای هر نقطه شروع از جایگشت اصلی می خواهیم چک کنیم که هر کدام از بازه های [i,i+MaxLen) خوب هستند یا نه.برای اینکار از i شروع می کنیم و پیمایش را شروع می کنیم.فرض مرحله قبل فرم عجیب بازه [i,i+k) را ساخته ایم و مکان آن رشته را در ترای پیدا کرده ایم.در این مرحله باید فرم عجیب را گسترش دهیم و آنرا برای بازه [i,i+k+1) بسازیم(از ویژگی های خوب فرم عجیب این است که اگر بخواهیم به ته آرایه k عضوی عدد اضافه کنیم دیگر k عضو اول فرم عجیب تغییری نمی کنند). و مکان رشته جدید را در ترای پیدا کنیم(کافیست از مکان قبلی یالی را طی کنیم که عدد روی آن همان عددی است که به ته فرم عجیب اضافه کردیم).
اگر روی راس های مربوط به m فرم عجیب(به صورت کامل نه یک پریفیکس از آنها)علامت بگذاریم می توانیم بازه های خوب با شروع از i را تشخیص دهیم(هر وقت به یک راس علامت دار رسیدیم یعنی بازه مان خوب است).
از آنجایی که از هر نقطه شروع کافیست MaxLen تا جلو برویم و هر مرحله جلو رفتن به اندازه O(lg(n))برایمان هزینه دارد(کار کردن با فنویک) پس با این الگوریتم می توان بازه های خوب را از O(n MaxLen lg(n)) پیدا کرد.
الگوریتم دوم:
به ازای هر کدام از m جایگشت چک می کنیم که با چه بازه هایی از جایگشت اصلی مطابقت دارد.
به جایگشت اصلی A و به جایگشتی که می خواهیم مکان های منطبق شدنش بر جایگشت اصلی را بیابیم B می گوییم.
مشابه الگوریتم KMP برای تطابق رشته ها کار می کنیم.تعریف کنید fi بزرگترین طول کمتر از i باشد که فشرده B1...fi همان فشرده Bi−fi+1...i باشد.توجه کنید که برای اینکه این برقرار باشد باید فشرده B1...fi−1 همان فشرده Bi−fi+1...i−1 باشد و همچنین تعداد اعداد کمتر مساوی Bi در [i−fi+1,i) برابر با تعداد اعداد کمتر مساوی Bfi در [1,fi)باشد(می توان با کمک فنویک این را چک کرد).
پس می توان f ها را به شیوه KMP به دست آورد.
همچنین matchi را تعریف می کنیم ماکسیمم مقداری که فشرده Ai−matchi+1...i همان فشرده B1...matchi باشد.مشابه بالا و با توجه به شیوه کار KMP می توان match ها را هم به دست آورد که اینکار از O((∣A∣+∣B∣)lg(∣A∣+∣B∣)) انجام می شود(و در نهایت مکان هایی که matchi=∣B∣ است را می خواهیم).
ادعا می کنیم به ازای هر عدد اول p عددی مثل g وجود دارد که g1...gp−1 تمام باقی مانده های ممکن به پیمانه p را تولید می کنند.
به چنین g هایی ریشه اولیه p می گوییم(در انتها روش به دست اوردن ریشه اولیه را توضیح می دهیم).
حالا فرض کنید g را یافته ایم.به ازای هر عدد بین 1 تا p−1 به دست آورید که معادل چه توانی از g است این مقدار را برای عدد x با logx نشان میدهیم.
حالا توجه کنید که
logx∗y≡logx+logymodp−1
حالا اگر به جای هر عدد log اش را در نظر بگیریم عملیات ضرب در پیمانه p به جمع در پیمانه p−1 تبدیل می شود!
پس اگر جمع تمام زیر مجموعه های ممکن از logai ها در پیمانه p−1 را به دست آوریم آنگاه تمام logans ها را به دست اوردیم که ans ها جواب های ممکن هستند.
برای حساب کردن جمع تمام زیرمجموعه های ممکن از کافیست به شیوه الگوریتم کوله پشتی کار کنیم اما با این تفاوت که می توان این کار را با بیت ست هم انجام داد! یعنی فرض کنید dp بیت ستی باشد که بیت i ام آن ۱ است اگر بتوان مجموعه ای با جمع i داشت.(اول کار dp0=1) حالا بعد از اضافه کردن عدد x به آرایه مقدار جدید dp برابر با dp∣(dp<<(p−1−x)) می شود پس در نهایت الگوریتم ما از O(32np) کار می کند.
روش به دست اوردن ریشه اولیه:
ابتدا توجه کنید که اگر d کوچکترین عددی باشد کهxd≡1 modp آنگاه تمام اعداد x0...xd−1 متمایزند(در غیر اینصورت d ما مینیمم نیست).از این موضوع نتیجه می شود که xy=xy mod d پس اگر قرار باشد که xy≡1modp آنگاه باید d∣y.
از طرفی طبق قضیه فرما می دانیم که xp−1≡1modp همچنین طبق تعریف و مطالب بالا عدد x ریشه اولیه است اگر و فقط اگر d=p−1.
توجه کنید که d∣p−1.حالا اگر d=p−1 باید عامل اولی در p−1 مثل q وجود داشته باشد که d∣qp−1 و در نتیجه xqp−1≡1modp .
پس می توان برای تمام عداد ۱ تا p−1 را چک کرد که می توانند ریشه اولیه باشند یا نه(و این فرایند چک کردن با O(lg(p)) بار به توان رساندن همراه است). پس می توان این کار را از O(g×lg(p)2) انجام داد.
آرایه را در یک درخت دودویی متوازن میریزیم . ( مانند AVL Tree ) . یک کپی از درخت می گیریم و بازه[l,r] کپی را از درخت جدا می کنیم (این کار از O(h) قابل انجام است). سپس درخت اصلی را از مکان k به دو قسمت تقسیم می کنیم و قسمت [l,r] درخت قبلی را در فاصله k و k+1 اضافه می کنیم.فقط نباید درخت را واقعا کپی بگیریم زیرا زمان اجرایی کد به صورت نمایی زیاد میشود.صرفا باید در هر مرحله تغییرات درخت قبلی نسبت به درخت های جدید را ذخیره کنیم و هیچوقت به دادههای درختهای قبلی دست نزنیم. اگر این کار را کنیم قسمت های تکراری درخت حافظه اضافه نمیگیرند.
پیچیدگی زمانی O(q×lg(Nq))