راه حل های مسابقه شماره ۲۳

سلام!
در این بلاگ راه‌حل سوالات مسابقه شماره ۲۳ رو به‌ صورت فشرده بیان می‌کنیم!

سوال خواب پوپک:

کافی است مقسوم علیه‌های دو عدد a و b را فیکس کرده و اگر مجموعشان از x کمتر بود آن حالت را به جواب اضافه کنیم.

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

کد راه حل

سوال کادوی پوپک‌پسند:

در این سوال جواب بهینه در صورتی است که a=1 باشد پس کافی‌است صفر‌های پشت عدد را حذف کنیم.

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

کد راه حل

سوال دنباله تورج پسند:

با توجه به اینکه اختلاف هر دو عضو مجاور در دنباله کمتر‌ مساوی d است و عوض اول دنباله نیز کمتر مساوی d است، پس عضو i ام دنباله نیز کمتر مساوی i*d می‌باشد!

dp[i][j] را به این صورت تعریف میکنیم: تعداد دنباله‌های به طول i که آخرین عضو آن برابر j باشد.
بنابراین حداکثر مقدار j در دامنه dp ها، d*k است، بنابراین تعداد حالات dp برابر با k^2*d است .

برای محاسبه هر حالت از dp ، در O(1) ، کافی است Partial Sum از dp های سطر قبلی داشته باشیم .

پیچیدگی زمانی: O(k^2d)

کد راه حل

سوال انتقام توک:

یک dsu نگه می‌داریم به طوری که به ازای هر نفر xor خودش با پدرش در dsu را داریم در ابتدا پدر هر کس خودش است و xor هر کس با خودش 0 است.

در اینصورت می‌توان xor هر کس تا ریشه را داشت چون xor هر کس با پدرش را داریم روی مسیر آن راس تا ریشه اش حرکت می‌کنیم و همه این اعداد را ( xor هر کس با پدرش) با هم xor می‌کنیم و آن را w بنامیم، w برابر xor آن راس و ریشه‌اش است چون:

اگر مسیر v_0,v_1,...,v_k باشد:

w=(a_{v_0}\oplus a_{v_1})\oplus (a_{v_1}\oplus a_{v_2})\oplus...\oplus (a_{v_{k-1}}\oplus a_{v_k})=a_{v_0}\oplus a_{v_1}

و xor هر دو راس هم که با هم در یک مولفه باشند مثل u,v را که ریشه اشان s است را به صورت زیر داریم:

a_u\oplus a_v=(a_u\oplus a_s)+(a_v\oplus a_s)

پس اگر از هر مولفه یک عدد را فیکس کنیم بقیه به صورت یکتا در می‌آیند، پس اگر تعداد مولفه ها f باشد (که f را با dsu داریم) جواب برابر است با: ans=(2^{31})^f

هر شرط که اضافه می شود به شکل u,v,k است:

اگر u,v در یک مولفه بودند: در این صورت a_u\oplus a_v را داریم اگر برابر k نبود این شرط یک تناقض است پس از این به بعد تعداد حالت‌ها برابر 0 است.

اگر u,v در یک مولفه نبودند: در اینصورت هیچ وقت به تناقض نمی رسیم چون تا قبل از این هیچ شرطی بین این دو مولفه نبوده و حداقل یک حالت هست به این صورت که a_u=0 , a_v=k باشد و بقیه یکتا طبق چیزی که قبلا گفته شد در می‌آیند و شرط جدید نیز برقرار است پس کافیست این دو مولفه را در dsu مرج کنیم.
اگر ریشه‌هایشان به ترتیب s,t بودند در اینصورت :

a_s\oplus a_t=(a_u\oplus a_v)+(a_u\oplus a_s)+(a_v\oplus a_t)

پس می‌توانیم در dsu بین دو راس  s,t یال بگذاریم.

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

سوال توک و صمد :‌
گرافی جدید بسازید و بین راس های i,j ، یالی با وزن A_{i,j} قرار دهید، اکنون در این گراف به کمک Floyd طول کوتاه‌ترین مسیر از i به j راحساب کرده و B_{i,j} بنامید، چنانچه ماتریس های A,B مساوی نباشند، نمی‌توان طوری تونل‌ها را ساخت که شرایط برقرار باشد ، اثبات امر نیز واضح است فرض کنید برای یک i,j خاص B_{i,j}<A_{i,j} باشد، مسیری که طی کردیم در گراف جدید که طولش B_{i,j} شده را در نظربگیرید، در گراف اصلی نیز دقیقا با طی کردن همان کوتاه‌ترین مسیر‌ها می‌توانیم با مسیری به طول B_{i,j} از i به j برسیم، پس A_{i,j} نمی‌تواند طول کوتاه‌ترین مسیر باشد! برای شمردن تعداد یال‌های کمینه لازم برای ساخت چنین گرافی نیز به این شکل عمل می‌کنیم، برای هر جفت i,j :
یال i,j را می‌گذاریم اگر و تنها اگر هیچ k ای نامساوی i,j وجود نداشته باشد که A_{i,j}=A_{i,k}+A_{k,j} ، واضح است که یال‌هایی که می‌سازیم قطعا لازم هستند چرا که بدون آنها نمی‌توان مسیری بین i,j با وزن A_{i,j} طی کرد!

اکنون نشان می‌دهیم با همین یال‌ها که ساخته‌ایم نیز می‌توان بین هر دو راسی با مسیری به طول  A_{i,j} رسید، یه شکل استقرایی روی طول مسیر‌ها حکم را نشان می‌دهیم، فرض کنید بین i,j یالی نمی‌گذاریم پس k ای وجود داشته است که A_{i,j}=A_{i,k}+A_{k,j} ، پس چون A_{i,j}>A_{i,k},A_{k,j} پس طبق استقرا، کوتاه‌ترین مسیر بین i,k و k,j با طول‌های دلخواه وجود دارد، پس کوتاه‌ترین مسیری بین i,j با طول موردنظر یافت می‌شود!

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

کد راه حل

سوال نقشه حمله:

کمترین ضعف یک نقشه [sqrt(n-1)] است.(منظور از  [x] بزرگترین عدد صحیح کوچکتر یا مساوی  از x است.)

فرض کنید بخواهیم ضعف نقشه کمتر از d باشد، یک مستطیل d*n از بالای مربع‌مان را در نظر بگیرید قرار دهید a=[n/d] ، واضح است که باید در a مربع d*d در هر کدام اقلا یک سرباز قرار دهیم.
پس چون کلا این سرباز‌ها را باید در d سطر قرار دهیم و هیچ دو سربازی در یک سطر نیستند، پس باید a<=d باشد.

n = a * d + r (0 <= r < d) a <= d n <= d * d + r < d * (d + 1) d >= sqrt(n - 1)

محاسبات انجام شده نشان می‌دهد که ضعف نقشه نمی‌تواند کمتر [sqrt(n-1)-1] باشد ، اکنون باید نشان دهیم که خود [sqrt(n-1)-1] نیز نمی‌تواند باشد .

مقدار A=[sqrt(n-1)] تعریف کنید، قرار دهید A% r=n ، می توان به وضوح دید که با صدق کردن شرایط بالا ، قطعا r!=0 است! مربع n*n را به مربع های A*A تقسیم کنید (در نهایت بخشی از مربع که تقسیم نمی‌شود را می توان با سه شکل r*r,(n-r)*r,r*(n-r) نشان داد! در هر یک از مربع های A*A باید اقلا یک سرباز قرار دهیم، بالاترین مربع های A*A را در نظر بگیرید، قطعا در یکی از‌آن‌ها مجبوریم سربازی در سطر اولش قرار دهیم، A*A های پایین این مربع را نیز در نظر بگیرید، در این A*A ها هم، باید سرباز را در سطر اول قرار دهید (وگرنه مربع A*A ساخته می‌شود)، اکنون پایین ترین این مربعات را در نظر بگیرید، در زیر این مربع ، یک شکل r*A داریم که به وضوح در آن نمی‌توانیم سربازی قرار دهیم(چون در همگی ستون‌هایش سرباز داریم) ، در نتیجه مربعی A*A در شکل ایجاد می‌شود! پس این حالت نیز به نتیجه نمی‌رسد!

برای ساخت مثالی که سایز بیشترین مربع A باشد، هم به این شکل عمل می‌کنیم،

t=A+1;

for(int i=1; i<=t; i++){

int j = i;

while(j <= n){

ans.pb(j); //be tartib satr ha ra misazim!

j += t;

}

}

اکنون قسمت اول مساله را حل می‌کنیم!

روی جواب باینری سرچ می‌زنیم حالا باید چک کنیم آیا مربعی به ضلع x داریم که درونش سربازی نباشد.
اگر همچین مربعی وجود داشته باشد حتما مربعی به ضلع x وجود دارد که یا سمت راستش یک سرباز باشد یا سمت چب آن چون:

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

ابتدا مربع‌هایی را چک می کنیم که سمت راست آن ها سربازی باشد و برای سمت چب هم مشابه همین کار را انجام می دهیم.

از سمت چب به راست روی ستون‌ها حرکت می کنیم و در مرحله i ام یک set داریم که در آن p_{i-1},p_{i-2},...,p_{i-x} وجود دارد. مستطیلی که عرض آن x است و از سمت راست به سرباز i ام چسبیده حداکثر طولی که می تواند داشته باشد برابر A-B-1 است که A کوچکترین عضو set است که از p_i بزرگتر است و B بزرگترین عضو set است که از p_i کوچکتر است که این اعداد را می توان با O(nlog n) به وسیله set بدست آورد.مربعی به ضلع x داریم که از طرف راست به این سرباز چسبیده اگر و تنها اگر حداکثر طول مستطیل بیشتر مساوی x باشد.

پیچیدگی زمانی: O(n log^2n)

کد راه حل

سوال فرار از زندان :
برای سهولت در کار فرض کنید، گراف ورودی همبند است!

چنانچه n<=20 باشد، تعداد دور‌های گراف را با محاسبه این dp می‌شماریم.

dp[i][mask] : تعداد مسیر‌های درون گراف، که از مجموعه راس‌های mask استفاده کند، از راس i شروع شود و به راس lowbit(mask) منتهی شود .
برای آپدیت کردن این dp می توان راسی که درون مسیر i به آن وصل می‌شود را فیکس کرد و مقادیر dp را محاسبه کرد .
پس هزینه محاسبه dp از O(2^n*n) است .

سپس برای شمردن تعداد دوره‌ها کافی است برای هر dp[i][mask] ، چنانچه size(mask) بیشتر مساوی ۳ باشد و راس های i و lowbit(mask) به یکدیگر یال داشتند جواب را به اندازه dp اضافه کنیم.
دقت کنید که در این وضعیت هر دور در گراف دقیقا 2 بار شمرده می‌شود ( از طرف ۲ یالی که به راس با اندیس مینیمم متصل می‌شوند) .

چنانچه n>20 باشد، با فرض همبند بودن گراف، یک درخت dfs دلخواه مثل T از گراف را در نظرمی‌گیریم، تعداد backedge ها، m-n+1<=20 است. می‌دانیم هر دور در گراف باید تعدادی از backedge ها را داشته باشد.  اکنون هر زیرمجموعه از backedge ها را در نظر بگیرید، یال‌هایی از درخت که باید در دوری که شامل این backedge هاست بیایند به صورت یکتا معین می‌شوند. اگر یالی مثل e زیر فرد تا backedge باشد، باید بیاید و در غیراین‌صورت نباید بیاید.

برای اثبات این موضوع کافی است T-e را در نظر بگیرید، چون این گراف ۲ مولفه است، و می می‌خواهیم دور انتخاب کنیم، پس باید زوج یال بین دو مولفه باشد . پس وضعیت یال e به شکل یکتا معین می‌شود .
اکنون برای هر زیزمجموعه وضعیت هر یال را تعیین می‌کنیم ،‌کافی است در نهایت یال‌هایی که در دور می‌آیند را در نظر بگیریم و ببینیم این یال‌ها تشکیل دور می‌دهند و جواب را محاسبه کنیم!
اردر این بخش از راه‌حل نیز O(2^{m-n}*n) است!

در نهایت توک از ما خواست در ثنای پوپک این تکه شعر را اضافه کنیم!

سحر ندارد این شب‌تار…  مرا به خاطرت نگه دار!