پاسخ سوالات مسابقه ۲۶ الگوریتمی

خب بدون مقدمه میریم سراغ سوال ها :

سوال نفس‌گیر:‌

برای سوال ام ، a_i \times b_i بار نفس ها گرفته می شود. پس پاسخ برابر است با \sum_{i=1}^{n} a_i \times b_i .

کد ++C از سایین اعلا

کد Python 3 از علی کاویانی

کد Java از معصومه ابراهیمی

کد Mono C# از محمد احسان شعبانی

مسئله هالت:

برنامه را شبیه سازی می کنیم و خط به خط آن را اجرا می کنیم. چون ورودی های دستور goto ثابت هستند اگر یک دستور را دو بار ببینیم هیچ وقت برنامه تمام نمی شود. پس هر خطی که میبینیم را مارک می کنیم و اگر به خط مارک شده ای دوباره رسیدیم ، -1 چاپ می کنیم. اگر هم که برنامه تمام شد مقادیر cout را در انتها چاپ می کنیم.

پیچیدگی زمانی O(n)

خستگان:

امید ریاضی تعداد اعداد متفاوت برابر است با جمع احتمال این که عدد x روی سردر شاز نصب شود به ازای همه x های ممکن. از O(n^2) می توانیم x هایی که احتمالشان 0 نیست(جمع حداقل یک بازه هستند) را بدست آوریم. حال به ازای یک عدد x می خواهیم احتمال این که x وجود داشته باشد را بدست آوریم. dp_a را برابر تعداد حالت ساخته نشدن x در a تای اول دنباله در نظر می گیریم. dp_a = \sum_{b=0}^{a-1} dp_b به شرطی که جمع بازه (b,a] برابر x نباشد.پس اگر به ازای x تعداد بازه هایی که جمعشان x است را cnt بنامیم آنگاه می توان dp را از O(n+cnt) می توان محاسبه کرد.احتمال حضور x هم می شود - \frac{dp_n}{2^{n-1}} 1 . پیچیدگی زمانی O(n^3)

ارتباطات فامیلی:

ابتدا حلی با O(n^2) را بررسی می کنیم.باید گرافی بسازیم که به ازای هر رابطه مثل عمو اگر b عموی a بود آنگاه از a به b یالی جهت دار قرار داشته باشد که روی آن واژه عمو نوشته شده است. حالا جهت یال های گراف را برعکس می کنیم.کوتاه ترین مسیر از b به a را در نظر بگیرید(و در صورتیکه چند کوتاه ترین مسیر بود مسیری که از لحاظ لغت نامه ای ماکسیمم است را در نظر بگیرید).جواب مسئله رشته متناظر با این مسیر است!(در انتها توضیح می دهیم که چطور می توان یک کوتاه ترین مسیر با شرط بزرگترین بودن از لحاظ ترتیب لغت نامه ای را یافت).

حالا برای اینکه تعداد یال های گراف را کم کنیم از ایده اضافه کردن راس استفاده می کنیم. به این صورت که اگر بخواهیم مجموعه راس های A را به مجموعه راس های B وصل کنیم و روی همه یال ها رشته s را بنویسیم آنگاه به جای اینکار یک راس جدید اضافه کرده و همه A را به راس جدید و راس جدید را به همه ‌B وصل میکنیم و روی راس جدید رشته s را می نویسیم(این عملیات f_{A,B,s} نامگذاری می کنیم) . توجه کنید که در این گراف جدید رشته ها روی راس ها نوشته می شوند نه یال ها!

برای ساختن رابطه های پدر به ازای هر راس مثل u باید f_{A,B,pedar} را اجرا کنیم:

A={u} B={par1_u,par2_u}

ساختن رابطه های پسر مشابه پدر انجام می شود.

برای ساختن رابطه های برادر به ازای هر راس مثل u باید f_{A,B,baradar} را اجرا کنیم:

A=B=sons_u

برای ساختن رابطه های عمو به ازای هر راس مثل u باید f_{A,B,amoo} را اجرا کنیم:

B={sons_u} A={sons_{sons_u}}

تعداد راس های گراف O(n) است.با توجه به اینکه \sum_{u}^{} sons_u تعداد رابطه های پدر و پسری را می شمارد و \sum_{u}^{} sons_{sons_u} تعداد رابطه های پدر و پدربزرگی را می شمارد و هر کس حداکثر ۲ پدر و ۴ پدر بزرگ دارد می‌توان نتیجه گرفت تعداد یال‌های گراف ساخته شده هم O(n) است.

حالا تنها کافی است بتوانیم یک کوتاه ترین مسیر در این گراف پیدا کنیم (‌چون هر رابطه از طی کردن دو یال شکل می گیرد طول این کوتاه ترین مسیر ۲ برابر کوتاه ترین رابطه است) که رشته متناظر آن (که روی راس ها رشته نوشتیم و رشته متناظر به راس های اصلی پوچ است) از لحاظ ترتیب لغت نامه ای ماکسیمم باشد! همچنین توجه کنید که یال ها برعکس شده اند و کوتاه ترین مسیر از b را می خواهیم.

این کار را با کمک الگوریتم bfs با کمی تغییر انجام می‌دهیم. بدون توجه به رشته روی راس ها bfs را با شروع از راس b اجرا می کنیم.حالا گراف ما لایه بندی شده است.تنها یال هایی که بین لایه های متوالی هستند را نگه دارید و بقیه را دور بریزید زیرا برای به دست آوردن کوتاه ترین مسیر لازم و کافی است که تنها از این یال ها استفاده کنیم.به ازای هر راس مثل u رشته ماکسیممی که می توان با طی کردن مسیری از ریشه به آن راس ساخت را S_u بنامید.هدف این نیست که S_u ها را به دست آوریم بلکه این است که بفهمیم برای ساختن S_u راس قبل از u در مسیر که بوده است.( که در لایه قبلی است) زیرا اگر این را بفهمیم می توانیم مسیر مورد نظر را بسازیم.

برای این کار تنها لازم است به ازای هر راس مثل u عددی مثل rank محاسبه کنیم که نشان می دهد اگر لایه مربوط به u را در نظر بگیریم رشته S_u از لحاظ بزرگی چندمین رشته در این لایه است.(‌و اگر S_i=S_j بود آنگاه rank_i=rank_j). حالا اگر rank راس های لایه قبلی را داشته باشیم به ازای هر راس مثل u در لایه فعلی می توان به دست آورد که راس قبل از آن باید چه کسی باشد.( یکی راسی که rank آن بیشینه است).پس تنها کافی است بتوانیم با داشتن rank های لایه قبلی rank های لایه جدید را بسازیم!به ازای هر راس مثل u در لایه فعلی بین تمام راس هایی لایه قبلی که به u یال دارند راسی مثل y را بیابید که rank_y ماکسیمم باشد.حالا به ازای تمام راس های لایه جدید مثل u قرار دهید:

val_u = pair<rank_y,string_u>

اگر val مربوط به تمام راس های لایه جدید را مرتب کنید می توان از روی آن rank های لایه جدید را به دست آورد. پس راه حل ما O(n*log(n)) می باشد.قابل ذکر است که به راحتی می توان حل بالا را O(n) کرد

رمز جایگشت

ابتدا صورت سوال را دقیق تر بیان می کنیم.یک جایگشت n تایی داریم. m تا جایگشت دیگر هم داریم که مجموع اندازه های آنها را با \sigma ( بخوانید سیگما) نشان می دهیم.یه یک بازه از جایگشت اصلی خوب می گوییم اگر فشرده شده اعداد آن برابر با یکی از m جایگشت باشد.حالا ما باید تعداد راه های افراز جایگشت اصلی به بازه های خوب را بگوییم.
ادعا می کنیم تعداد طول های مختلف در m جایگشتمان از O(\sqrt{\sigma}) است.که در اینصورت می توان نتیجه گرفت تعداد بازه های خوب از O(n \sqrt{\sigma}) است.حالا اگر بتوانیم تمام بازه های خوب را شناسایی کنیم می توانیم به راحتی جواب را به دست بیاریم.(کافیست dp_i را تعداد افراز i عضو اول جایگشت اصلی به بازه های خوب تعریف کنیم و جواب dp_n است‌). برای شناسایی بازه های خوب دو الگوریتم می دهیم. الگوریتم اول از O(n\ MaxLen\ lg(n)) کار می کند(MaxLen ماکسیمم طول در آن m جایگشت است) و الگوریتم دوم از O((\sigma+(nm))\times lg(n)) کار می کند.سپس با ترکیب این دو الگوریتم مساله از O(n \sqrt{\sigma} lg(n) ) حل می شود.(کافیست آن m جایگشت را به دو دسته با طول کمتر از \sqrt{\sigma} و بیشتر از آن تقسیم کنید و بازه های خوبی که هر دسته می سازد را محاسبه کنیم).

الگوریتم اول:

قبل از شروع به این تبدیل جایگشتی توجه کنید:
فرض کنید جایگشت k عضوی p را داریم و این تبدیل به ما آرایه k تایی a را میدهد که :

a_i تعداد اندیس های j \leq\ i که a_j \leq\ a_i
به این فرم از نمایش جایگشت فرم عجیب می گوییم.می توان ثابت کرد بین جایگشت های k تایی p به آرایه های k تایی a که ( 1 \leq\ a_i \leq\ i ) تناظر یک به یک برقرار است پس هر جایگشت یک فرم عجیب دارد و هر فرم عجیب معادل یک جایگشت است!

حالا توجه کنید که هر آرایه با اعداد متمایز هم یک فرم عجیب دارد.(دقیقا مشابه بالا تعریف می شود).
حالا توجه کنید که فشرده آرایه a برابر با جایگشت p می شود اگر و فقط اگر فرم عجیب آن دو برابر باشد.
حالا کل m جایگشت را به فرم عجیب در بیاورید(این کار از O(\sigma 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 برای تطابق رشته ها کار می کنیم.تعریف کنید f_i بزرگترین طول کمتر از i باشد که فشرده B_{1...f_i} همان فشرده B_{i-f_i+1...i} باشد.توجه کنید که برای اینکه این برقرار باشد باید فشرده B_{1...f_i-1} همان فشرده B_{i-f_i+1...i-1} باشد و همچنین تعداد اعداد کمتر مساوی B_i در [i -f_i+1,i) برابر با تعداد اعداد کمتر مساوی B_{f_i} در [1,f_i) باشد(می توان با کمک فنویک این را چک کرد).
پس می توان f ها را به شیوه KMP به دست آورد.
همچنین match_i را تعریف می کنیم ماکسیمم مقداری که فشرده A_{i-match_i+1...i} همان فشرده B_{1...match_i} باشد.مشابه بالا و با توجه به شیوه کار KMP می توان match ها را هم به دست آورد که اینکار از O((|A|+|B|)lg(|A|+|B|)) انجام می شود(و در نهایت مکان هایی که match_i = |B| است را می خواهیم).

سوالات ترکیبی:

ادعا می کنیم به ازای هر عدد اول p عددی مثل g وجود دارد که g^1...g^{p-1} تمام باقی مانده های ممکن به پیمانه p را تولید می کنند.
به چنین g هایی ریشه اولیه p می گوییم(در انتها روش به دست اوردن ریشه اولیه را توضیح می دهیم).
حالا فرض کنید g را یافته ایم.به ازای هر عدد بین 1 تا p-1 به دست آورید که معادل چه توانی از g است این مقدار را برای عدد x با log_x نشان می‌دهیم.
حالا توجه کنید که
log_{x*y} \equiv log_x+log_y \mod p-1

حالا اگر به جای هر عدد log اش را در نظر بگیریم عملیات ضرب در پیمانه p به جمع در پیمانه p-1 تبدیل می شود!
پس اگر جمع تمام زیر مجموعه های ممکن از log_{a_i} ها در پیمانه p-1 را به دست آوریم آنگاه تمام log_{ans} ها را به دست اوردیم که ans ها جواب های ممکن هستند.
برای حساب کردن جمع تمام زیرمجموعه های ممکن از کافیست به شیوه الگوریتم کوله پشتی کار کنیم اما با این تفاوت که می توان این کار را با بیت ست هم انجام داد! یعنی فرض کنید dp بیت ستی باشد که بیت i ام آن ۱ است اگر بتوان مجموعه ای با جمع i داشت.(اول کار dp_0=1) حالا بعد از اضافه کردن عدد x به آرایه مقدار جدید dp برابر با dp | (dp << (p-1-x) ) می شود پس در نهایت الگوریتم ما از O(\frac{np}{32}) کار می کند.
روش به دست اوردن ریشه اولیه:
ابتدا توجه کنید که اگر d کوچکترین عددی باشد که x^d \equiv 1\ mod p آنگاه تمام اعداد x^0 ... x^{d-1} متمایزند(در غیر اینصورت d ما مینیمم نیست).از این موضوع نتیجه می شود که x^y = x^{y\ mod\ d} پس اگر قرار باشد که x^y \equiv 1 \mod p آنگاه باید d|y.
از طرفی طبق قضیه فرما می دانیم که x^{p-1} \equiv 1 \mod p همچنین طبق تعریف و مطالب بالا عدد x ریشه اولیه است اگر و فقط اگر d=p-1.
توجه کنید که d|p-1.حالا اگر d\neq p-1 باید عامل اولی در p-1 مثل q وجود داشته باشد که d \mid \frac{p-1}{q} و در نتیجه x^{\frac{p-1}{q}} \equiv 1 \mod p .
پس می توان برای تمام عداد ۱ تا p-1 را چک کرد که می توانند ریشه اولیه باشند یا نه(و این فرایند چک کردن با O(lg(p)) بار به توان رساندن همراه است). پس می توان این کار را از O(g\times lg(p)^2) انجام داد.

کپی پیست:

آرایه را در یک درخت دودویی متوازن میریزیم . ( مانند AVL\ Tree ) . یک کپی از درخت می گیریم و بازه [l,r] کپی را از درخت جدا می کنیم (‌این کار از O(h) قابل انجام است). سپس درخت اصلی را از مکان k به دو قسمت تقسیم می کنیم و قسمت [l,r] درخت قبلی را در فاصله k و k+1 اضافه می کنیم.فقط نباید درخت را واقعا کپی بگیریم زیرا زمان اجرایی کد به صورت نمایی زیاد میشود.صرفا باید در هر مرحله تغییرات درخت قبلی نسبت به درخت های جدید را ذخیره کنیم و هیچوقت به داده‌های درخت‌های قبلی دست نزنیم. اگر این کار را کنیم قسمت های تکراری درخت حافظه اضافه نمی‌گیرند.

پیچیدگی زمانی O(q\times lg(N_q))