راه حل سوال‌های First Source Challenge

راه حل‌های First Source Challenge!

ببخشید که یکم دیر شد.

سوال ۱ (Joos) :

در صورتی که جواب “Yes” باشد اندیسی وجود دارد مثل i که با شروع از کاراکتر i-ام روی دایره و طی کردن |p| (طول رشته‌ی مهرداد) کاراکتر رشته‌ی حاصل با رشته‌ی مهرداد برابر شود در صورتی که جواب “No” باشد هیچ اندیسی وجود ندارد که شرط بالا را داشته باشد.

پس کافیست برای هر اندیس i ، |p| کاراکتر طی کنیم و اگر رشته‌ای که دیدیم با رشته‌ی مهرداد برابر شد “Yes” خروجی دهیم.

اردر زمانی : O(|s||p|)

لینک راه حل سی پلاس پلاس

سوال ۲ (economize!) :

ابتدا تمام زمان‌هایی که در سوال داده شده است را به ثانیه تبدیل می‌کنیم (برای مثال 03:01:02 می‌شود ثانیه‌ی ۱۰۸۶۲)

بعد ارایه‌ای نگه می‌داریم که مقادیر آن ابتدا ۰ است و طول آرایه ۸۶۴۰۰ (یک روز ۸۶۴۰۰ ثانیه است!) و اگر از ثانیه t تا t+1 برق وجود نداشت خانه‌ی t ام آن را ۱ می‌کنیم یعنی این آرایه اگر در بازه زمانی (t,t+1] برق بود خانه‌ی t ام آن ۰ و در غیر این صورت ۱ است.)

برای هر بازه زمانی که برق نیست روی خانه‌های آرایه حرکت می‌کنیم و در صورتی که اندیس آن خانه در این بازه بود آن خانه را ۱ می‌کنیم

در نهایت کافیست ۹۰۰ ثانیه (=۱۵ دقیقه) برق داشته باشیم یعنی ۹۰۰ خانه‌ی پشت سر هم آرایه ۰ باشن که می‌توانیم برای هر اندیس آرایه تا ۹۰۰ خانه قبلش را چک کنیم که ۰ باشد.

اردر زمانی : O(86400k + 86400\times900)

لینک راه حل سی پلاس پلاس

سوال ۳ (Gheyme) :

اگر k بیشتر از ۳ باشد جواب ۰ است!

اثبات : فرض کنید حداقل ۴ عدد انتخاب کردید که ویژگی مساله را دارند. (ب.م.م هر دو اختلافی ۱ است.)

فرض کنید ۴ تا از این اعداد a > b > c > d باشند.

سه اختلاف  a-b,a-c,b-c را در نظر بگیرید. a-c = (a-b)+(b-c) حداقل یکی از این ۳ اختلاف زوج است چون اگر (b-c) و (a-b) هر دو فرد باشنید جمع آن‌ها زوج می‌شود و a-c زوج می‌شود.

بدون از دست دادن کلیت مساله فرض کنید b-c زوج است حالا b را در نظر نگیرید . ۳ عدد a > c > d را در نظر بگیرید مثل بالا می‌شود گفت حداقل یک اختلاف وجود دارد که زوج است و چون b در ۳ عدد بالا نیست ب.م.م این اختلاف و b-c حداقل ۲ است. (چون هر دو زوج هستند.)

برای k=1 جواب می‌شود n ( چون تنهای یک عدد می‌توانیم انتخاب کنیم که n حالت دارد و هیچ اختلافی وجود ندارد)

برای k=2 می‌شود n*(n-1)/2 چون هر دو عددی را انتخاب کنیم یک اختلاف وجود دارد و شرط مساله برقرار است)

برای k=3 :

(x,y) = gcd(x,y)

فرض کنید ۳ عدد انتخاب شده a,b,c باشند و a > b > c

(x,y) = (x,y+x)

در نتیجه:

( a-b , b-c )

= ( a-b , (b-c) + (a-b) )

= ( a-b , a-c )

و

( a-b , b-c )

= ( (a-b) + (b-c) , b-c )

= ( a-c , b-c)

پس در صورتی که (a-b,b-c) = 1 باشد آنگاه  ( a-b , a-c ) = ( a-c , b-c ) = 1 می‌شود و شرایط مساله برقرار می‌شود پس کافیست تعداد اعدادی مثل a > b > c را بشماریم که (a-b,b-c) = 1 شود.

فرض کنید مقدار a-b و b-c را تعیین کردیم ( کمتر از ۲۰۰۰ * ۲۰۰۰ حالت دارد چون اعداد تا ۲۰۰۰ هستند.)

حالا چون سه عدد به صورت a > b > c هستند . b می‌تواند هر عددی در بازه‌ی [a-b, n-(b-c)] باشد. (البته باید بزرگتر از ۱ و کمتر از n هم باشد) پس تعداد حالت‌هایی که b می‌تواند داشته باشد max(0,n-(a-b)-(b-c)) است  و اگر b را تعیین کنیم مقادیر a و c یکتا درمی‌آیند.

اردر زمانی : O(n^2\times log(n))

لینک راه حل سی پلاس پلاس 

سوال ۴ (Tavalbao) :

فرض کن هر راس را رقم‌هایش را جدا می‌کنیم و راس‌های جدیدی برای آن‌ها می‌سازیم و پشت سر هم به هم وصل می‌کنیم.

برای مثال اگر عددمان ۱۴۲۴ است ۴ راس می‌سازیم و عدد روی راس‌ها را به ترتیب ۱، ۴، ۲ و ۴ می‌گذاریم. و راس اول را به راس دوم، راس دوم را به راس سوم و راس سوم را به راس چهارم وصل می‌کنیم ( 1 -> 4 -> 2 -> 4).

حالا اگر یالی از راس v به u وجود داشت از اخرین رقم v به اولین رقم u وصل می‌کنیم (مثلا اگر دو عددمان ۱۲ و ۳۴ باشد و ۱۲ به ۳۴ یال داشته باشد به این شکل می‌شود  1 -> 2 -> 3 -> 4)

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

فرض کنید [ok[k][v یعنی آیا می‌شود با شروع از راس v و طی کردن دقیقا k  رقم به راسی رسید که رقم اخر است. اگر می‌شد این مقدار ۱ و گرنه ۰ است  این مقدار را با برنامه نویسی پویا به راحتی می‌توانید به دست بیاورید.

حالا فرض کنید وکتوری داریم به اسم v که در آن یک سری راس وجود دارد که ویژگی‌های زیر را دارند:

• در ابتدا فرض کنید تمام راس‌‌هایی مثل x را که عددشان ۹ است و رقم اول هستند و ok[k][x] = ۱ است را ریخیتیم اگر وکتور خالی بود همین کار را برای عدد ۸ می‌کنیم سپس ۷ و … تا زمانی که وکتور خالی نباشد و دیگر ادامه نمی‌دهیم. چون راس‌های وکتور رقم اول هستند و ok[k][x]=1 پس با شروع از آن راس‌ها می‌توانیم به یک عدد برسیم که اولین رقمش ماکسیمم باشد پس قطعا جواب اصلی با شروع از یکی از همین راس‌ها است.
• فرض کنید تا الان عددی که ساختیم t رقمی است و تمام راس‌هایی که ممکن است پایان این عدد t رقمی ماکسیمم باشند در وکتور هستند با استفاده از ok می‌توانیم بفهمیم رقم بعدی ما چه عددی است و فرض کنید این رقم a است. تمام راس‌هایی مثل y که همسایه راس‌های وکتورمان هستند و رقمشان برابر a است و ok[k-t-1][y]=۱ را در وکتور می‌ریزیم و راس‌های قبلی را پاک می‌کنیم. بدیهی است که جواب با ادامه دادن این راس‌ها به دست می‌آید و رقم t+1 آن برابر a است.

اردر زمانی :   O((n+m)k)

سوال ۵ (Diversity) :

اگر تعداد جاده‌های جادویی k باشد. گرافی جدید می‌سازیم با دو به توان k به علاوه n راس که n راس متناظر با راس‌های گراف اصلی و بقیه‌ی راس‌ها متناظر حالت‌‌هایی است که یال‌ها می‌توانند داشته باشند و هر راس از n راس متنظار با گراف  را به حالت‌هایی وصل می‌کنیم که راس متنظار آن در گراف اصلی در آن حالت درجه فرد باشد.

خروجی‌ای که مساله می‌خواهد گشتی در این گراف است که همه‌ی یال‌ها را طی کند و مینیمم طول را داشته باشد.

اگر k = 0 :  اگر راس‌های درجه ۰ را در نظر نگیرید گراف ستاره است.

اگر k \ge 2 : هر راس از n راس متناظر با گراف اصلی، درجه زوج است چون درجه‌ی هر راس در دقیقا ۲ به توان k-1 (اگر این راس حداقل یک یال جادویی به آن وصل بود) یا 0 (اگر هیچ یال جادویی ای به آن وصل نبود و درجه زوج بود) و یا ۲ به توان k (اگر هیچ یال جادویی ای به آن وصل نبود و درجه فرد بود) حالت فرد است.

و هر راس متناظر با حالتی از یال‌ها هم درجه زوج است چون در هر گرافی زوج راس درجه فرد داریم.

پس گراف تور اویلری دارد.

اگر k =1 : اگر همه‌ی راس‌ها زوج بود که تور اویلری داریم در غیر این صورت دقیقا ۲ راس درجه فرد دارد چون هر راس متنظار با حالت یال‌های جادویی که زوج یال دارد و تنها ۲ راس که دو سر یال جادویی هستند ممکن است درجه ۱ باشند و بقیه راس‌ها یا درجه ۰ یا درجه ۲ هستند(چون کلا ۲حالت داریم)

پس صرفا کافی است کوتاه ترین مسیر بین این دو راس را در نظر بگیریم (طول این مسیر ۲ یا ۴ است.) و بین هر دو راس متوالی مسیر یال جدیدی اضافه کنیم و این طوری درجه‌ی همه راس‌ها زوج می‌شود و گراف تور اویلری دارد.

سوال ۶ (Nano-ants) :

با توجه به اینکه q \le n^2-n  پس یالی وجود دارد که تا اخر کوئری‌ها حداکثر n سوراخ روی آن ایجاد شود. بدون از دست دادن کلیت مساله فرض کنید اولین یال (۰) این ویژگی را دارد.

با توجه به این موضوع اگر از نقطه ای شروع به پاترول زدن بکنیم و n^2 مرحله طی کنیم به دور می‌رسیم یعنی از مرحله n^2 به بعد از هر یال، راس مشخصی را می‌بینیم چون یال اول حداکثر n سوراخ دارد پس در n^2 مرحله سوراخی را دوبار می‌بینیم و از آن به بعد به دور می‌خوریم.

فرض کنید next(i) یعنی اگر از i امین سوراخ یال ۰ شروع به حرکت کنیم بعد از طی کردن n مرحله به چه سوراخی در یال ۰ می رسیم .

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

حالا برای جواب دادن کوئری نوع دوم کافیست مورچه را به یال ۰ برسانیم و سپس با n بار استفاده از next می‌فهمیم در کدام سوراخ یال ۰ است که مسیری که طی می‌کند ثابت می‌شود و اگر نیاز است که k مرحله دیگر حرکت کنیم می‌توانیم k\ mod\ n مرحله حرکت کنیم چون اگر الان روی i-امین سوراخ یال ۰ هستیم بعد از n مرحله به همین سوراخ بر می‌گردیم.

اردر زمانی : O(q\times n\times log(n) )