راه حل‌های مسابقه‌ی Snapp Challenge

سلام!

امیدواریم که از سوال‌ها خوشتون اومده باشه!

در کنار راه حل‌های سه سوال اول، کد افرادی که در مسابقه در زبان‌های خودشان زودترین ارسال درست را داشته‌اند نیز آمده‌است.

در صورتی که راه‌حل دیگری برای سوال‌ها دارید در بخش نظرات با ما در میان بگذارید.

• اسنپ در شکرستان

  برای این سوال کافی بود یک آرایه دو بعدی مانند  A بگیرید که خانه  A_{i,j} از آن هزینه سفر از شهر  i به شهر  j باشد.

  سپس به ازای هر درخواست که از ما هزینه سفر از  x بع  y را خواسته بود،  A_{x,y} را به جواب نهایی اضافه می‌کردیم و سرآخر جواب نهایی را چاپ میکردیم.

کد Go از میلاد رضایی

کد  ++C از پوریا براتی

• بیکاری در دربار

  ابتدا باید سه بخش معادله‌ی a + b = c، یعنی a,b,c را در رشته‌هایی دریافت و ذخیره کنیم. حال فرض کنید بجای رشته‌ای که شامل کاراکتر # می‌شود، متغیر مجهول x قرار دارد. مقدار x را می‌توان بصورت یکتا مشخص کرد؛ با حل یک معادله – یک مجهول موجود در ورودی. حال با داشتن مقدار x، باید ۲ مورد را بررسی کنیم:

•  مقدار x همانطور که در صورت سوال گفته شده، نامنفی باشد.
•  مقدار بدست آمده با ورودی منطبق باشد.

برای بررسی انطباق، باید پیشوند و پسوندی از رشته‌ی ورودی که # آن‌ها را از هم جدا کرده، پیشوند و پسوند عدد مقدار x باشند؛ این را می‌توان با بررسی کاراکتر به کاراکتر این پیشوند و پسوند با پیشوند و پسوند متناظر در x انجام داد. البته زبان‌هایی مثل Python  و Java کتابخانه‌های مشخصی دارند که انطباق را می‌توان با آن‌ها ساده‌تر بررسی کرد.

کد ++C از ایمان غلامی

کد Python از محمد استادمحمدی

کد Java از محمدعرفان غلامیان

کد #C از آرین الف ب

• تقلب ممنوع!

  با کمی دقت می‌توان فهمید که به ازای هر رشته فقط p حرف اول و q حرف آخر آن مهم هستند و باقی حروف یک رشته تاثیری در جواب نهایی نخواهند داشت.

  پس بیایید به ازای هر کلمه شانس یک رشته جدید بوجود بیاوریم به اینصورت که p حرف اول یک کلمه شانس را به q حرف آخر آن بچسبانیم (مثلاً به ازای کلمه word ، p=2 و q=3 کلمه‌ی جدید woord را خواهیم داشت).

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

  تحلیل زمانی:

  حذف رشته های تکراری را می‌توان با O(n ^ 2) انجام داد به این صورت که هر ۲ رشته را مقایسه کنیم . اما بهتر است به دلیل تعداد بالای رشته ها از داده ساختار درخت متوازن استفاده کرده و کار مقایسه را با O(n log n) انجام دهیم.

  کد پایتون از مرتضی زند
  کد جاوا از مجید اسماعیلی
  کد ++C از آرمین فلاح

•  فریاد

  فرض کنید مدل درخواست‌ها به این صورت باشد که ۲ خانه مبدا و مقصد حتما در جزیره‌ها باشند، برای این حالت به راحتی می‌توان مسئله را به گراف مدل کرد به این صورت که جزیره ها راس های گراف‌اند و به ازای ‌۲ جزیره‌ی i و j طول یال بین ۲ راس متناظر این ۲ جزیره برابر کمترین تعداد خانه‌هایی است (جدا از این که این خانه‌ها در دریا باشند یا در خشکی) که لازم است طی شود تا از جزیره‌ی i به جزیره‌ی j‌ رسید.

  حال با استفاده از الگوریتم Floyd–Warshall در زمان O(n^3)کوتاهترین فاصله بین ۲ جزیره i و j را به دست می‌آوریم و آنرا [dis[i][j می‌نامیم، به این صورت که ممکن است از جزیره مبدا تا مقصد از تعدادی جزیره‌ی دیگر هم عبور کنیم،  ادعا می‌کنیم این کوتاه ترین فاصله‌ی به دست آمده برای جابه‌جایی بین ۲ جزیره فقط شامل خانه‌هایی است که در آب قرار دارند (چرا؟).
  حال حالت اصلی مسئله را در نظر بگیرید، به ازای هر درخواست کمترین تعداد خانه‌های داخل آبی که باید از خانه مبدا تا مقصد طی شوند، یا برابر فاصله منهتنی خانه‌ی مبدا تا مقصد است ویا ابتدا از مبدا به یک جزیره می‌رویم و بین تعدادی جزیره جابه‌جا می‌شویم و سپس به مقصد می‌رویم.

  در نتیجه می‌توان جواب هر درخواست بین ۲ خانه‌ی A و B را به صورت زیر محاسبه کرد.

   

  ans = manhattan_distance (A,B);

  For (i=1 -> n )

        For(j=1 -> n)

              ans = min( ans ,  manhattan_distance ( A , island[i] ) + dis[i][j] + manhattan_distance ( island[j] , B ) )

   

  تحلیل زمانی :

  ابتدا با O(n^3) کمینه تعداد خانه های آبی بین هر ۲ جزیره را پیدا میکنیم و سپس به ازای هر درخواست آن را با O(n^2) جواب می‌دهیم پس در نهایت الگوریتم ما از O(n^3 + q \times n ^ 2) است.

• علی خلافه

  طبق توضیحات مسئله اگر شهر شکرستان را به یک گراف مدل کنیم که هر تقاطع راسی در گراف و هر جاده‌ی بین ۲ تقاطع یالی جهتدار بین ۲ راس متناظر در گراف باشد گراف حاصل گرافی جهتدار بدون دور و یا به اصطلاح DAG خواهد بود.

  می‌دانیم که در DAG حتما راسی وجود دارد که درجه ورودی آن صفر است و همچنین راسی وجود دارد که درجه خروجی آن صفر است.

  ابتدا راس‌ها را به ترتیب توپولوژیک مرتب می‌کنیم، حال راسی در گراف را درنظر می‌گیریم که ورودی آن برابر صفر باشد، ادعا می‌کنیم که اگر یال خروجی این راس به همسایه‌ای از آن که در ترتیب  توپولوژیک زودتر از باقی همسایه‌ها آمده را برعکس کنیم باز هم گراف جدید DAG خواهد ماند (چرا؟).

  در نتیجه جواب همیشه یک خواهد بود و برابر یالی است که در توضیح بالا پیدا می‌شود .

  البته می‌توان یال‌های دیگری هم پیدا کرد ولی حتما یه راس از ۲ راس این یال‌ها درجه ورودی صفر یا درجه خروجی صفر دارند.

  تحلیل زمانی:

  به دست آوردن عدد هر راس در ترتیب توپولوژیک را می‌توان با  به انجام‌داد و همچنین پیدا کردن همسایه‌ای که عدد توپولوژیکال آن کمتر است O(n) زمان میگیرد که در کل الگوریتم ما از O(n + e) خواهد بود.

• تبلیغات میدانی

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

  اگر نقطه‌ی چپ‌پایینِ پوستر را با (A, B) نشان دهیم، واضح است که 0 \leq A \leq w - n و 0 \leq B \leq h - m

  به ازای یک پوستر با گوشه‌ی پایین‌چپ (a, b) و گوشه‌ی بالا‌راست (c, d) نیز می‌دانیم که گوشه‌ی پایین‌چپ پوستر پارسا در نقاط مستطیلی با گوشه‌ی پایین چپ (a-n+1,b-m+1) و گوشه‌ی بالا راست (c - 1, d - 1) نمی‌تواند باشد.(شامل محیط آن مستطیل)

  یعنی از تمام نقاط تابلو، تعدادی مستطیل پیدا کردیم که گوشه‌ی پایین چپ پوستر پارسا نمی‌تواند در آن باشد و در سایر نقاط آن تابلو می‌تواند باشد. با استفاده از یک خط جاروب(sweep line) شروع به پیمایش صفحه از چپ به راست می‌کنیم. یک آرایه هم داریم و در زمانی که خط جاروبمان در طول x قرار دارد، در خانه‌ی yام آن نوشته‌ایم نقطه‌ای با مختصات (x, y) در چند تا از مستطیل‌های مذکور آمده است. (به ازای 0 \leq y \leq h - m) خط جاروبمان نیز از طول 0 تا w - n حرکت می‌کند.

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

  اگر در لحظه‌ای از حرکت خط جاروب، خانه‌ای از آرایه برابر صفر شد، یعنی جواب مساله yes است! در غیر این صورت نیز بدیهتا جواب no خواهد بود، چرا که هیچ نقطه‌ی مُجازی برای گوشه‌ی پایین چپ مستطیل نیافته‌ایم.

  اکنون یک سوال دیگر حل می‌کنیم و سپس به سراغ حل مساله‌ی کلّی می‌رویم: «یک خط افقی و یک نقطه داده شده‌اند. نزدیک‌ترین نقطه‌ی خط به آن نقطه را بیابید.» این سوال به آسانی قابل حل است.

  در یک مرحله از حرکت رو به جلوی خط جاروبمان، تعدادی از خانه‌های آرایه صفر هستند و تعدادی نیز مقداری بیشتر از یک دارند. این مقادیر با جلو رفتن خط جاروب، تا قبل از رسیدن به ضلع عمودی یکی از مستطیل‌ها ثابت می‌مانند. وقتی که می‌خواهیم وسط پوسترمان نزدیک‌ترین نقطه به وسط تابلو باشد، می‌توان چنین برداشتی کرد که می‌خواهیم خانه‌ی پایین چپ آن نزدیک ترین نقطه به نقطه‌ی bestAns = (\frac{w - n}{2},\frac{h - m}{2}) باشد.

  فرض کنید ‌bestY =\frac{h - m}{2} ؛ در این صورت واضح است از بین تمام خانه‌های آرایه‌ی خط جاروب که اندیسشان بیشتر از bestY است و برابر صفر است، که پایین‌ترین نقطه از بین آن‌ها، کمترین فاصله با bestAns را دارد. از بین تمام خانه‌هایی با اندیس کمتر از bestY که برابر صفر هستند، بالاترین آن‌ها نیز کمترین فاصله تا bestAns را دارد. (دقّت کنید که تنها در مورد مجموعه‌ی نقاط روی خط جاروب داریم صحبت می‌کنیم)

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

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

  فشرده‌سازی مختصات مستطیل‌ها از O(n.log(n)) است. پیمایش آن‌ها توسط خط جاروب در 2n مرحله انجام می‌شود که در هر مرحله تعدادی کار انجام می‌شود: یک عدد به یک بازه از آرایه اضافه می‌شود (با زمانO(log(n)))، یا این که از بین خانه‌های شامل صفر، نزدیک‌ترین دو خانه به اندیس bestY را بیابیم. (در صورت استفاده از جستجوی دودویی با زمانی از O(log^2(n) و در صورت استفاده از راه دیگر، زمانی از O(log(n))

  پس زمان اجرای الگوریتم از O(n.log^2(n)) یا O(n.log(n)) خواهد بود.

• مضدو

  در این سوال، گرافی همبند با زوج یال به داده شده و ما باید تعدادی گشت زوج یالی بدون یال تکراری بیابیم که هر راس با درجه‌ی فرد، انتهای دقیقاً یکی از این مسیرها باشد.

ابتدا فرض می‌کنیم که فرض زوج یالی بودن این گشت‌ها وجود ندارد!

حال برای اینکه گشت‌هایی که می‌یابیم اشتراک یالی نداشته باشند، می‌توانیم از تور اویلری گراف استفاده کنیم! به این صورت که ابتدا با اضافه کردن یک راس به گراف و متصل کردن آن به تمام رئوس درجه فرد، گراف را اویلری می‌کنیم و سپس تور اویلری را می‌یابیم. هم‌اکنون با حذف مکان‌هایی که رأس اضافه در تور آمده، تور تبدیل به تعدادی مسیر می‌شود که دقیقاً همان مسیرهایی هستند که دنبال‌شان بودیم.

حال حالت کلی مسئله را حل می‌کنیم.

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

از روی گراف ورودی G که n رأس دارد، گراف H را می‌خواهیم طوری بسازیم که:

1. H متشکل از دو بخش A, B باشد که |A| = |B| = n و هر راس از هر بخش H نمایانگر یکی از رئوس G باشد. یعنی هر راس در G متناظر دو راس در H است.
2. هر یال در G دقیقاً متناظر یک یال در H باشد؛ یعنی یال uv در G متناظر یال u'v' در H باشد که یا u' \in A, v' \in B و یا u' \in B, v' \in A و u و v در G، متناظر u' و v' در H باشند.
3. درجه‌ی همه‌ی رئوس B زوج باشد و  راس‌هایی که متناظرشان در G درجه فرد است، در A نیز درجه‌ی فرد داشته باشد.

اگر در این گراف ما راه حل قبلی را اجرا کنیم، همه‌ی گشت‌های بدست آمده زوج یال خواهند داشت و متناظر هر گشت در G نیر وجود دارد.

حال مسئله ساختن چنین گرافیست. برای هر یال uv  ۲ گزینه وجود دارد: یا از u' \in A به v' \in B باشد و یا از u' \in B به v' \in A  باشد. برای اینکه رئوس داخل بخش B درجه‌ی زوجی داشته باشند، یال‌‌ها را بصورت دوتا دوتا به گراف اضافه می‌کنیم طوری که هر زوج یال یک راس مشترک داشته باشند و آن راس را در بخش B در نظر می‌گیریم. یعنی یال‌های G را به مسیرهای ۳ راسی افراز می‌کنیم و دو یال uv, vw را بصورت u'v', v'w' که v' \in B, u', w' \in A اضافه می‌کنیم. پس مسئله تبدیل شد به افراز یال‌های گراف به مسیرهای ۳ راسی.

افراز یال‌های گراف به مسیرهای ۳راسی

می‌توان این کار را با یک dfs بسادگی انجام داد؛ به این صورت که پس از صدا زدن dfs راس v، قرارداد می‌کنیم که یال‌هایی که حداقل یک سرشان در زیردرخت v در درخت dfs هستند به مسیرهای ۳ راسی افراز شده‌اند، مگر وقتی که تعداد این یال‌ها فرد باشد. در این حالت یال از v به پدرش در درخت dfs در افراز تنها می‌ماند. با این قرارداد می‌توان این یال‌ها را در هر مرحله از dfs جفت-جفت کرد تا شرط گفته شده برقرار بماند. چون گراف ورودی زوج یال دارد و همبند است، در نهایت همه‌ی یال‌های گراف به مسیر ۳ راسی افراز می‌شوند.

حال راه حل ما تکمیل شد! پس از افراز یال‌ها به مسیرهای ۳ راسی، گراف گفته شده را می‌سازیم و با یافتن تور اویلری در آن گشت‌های دلخواه‌مان را می‌یابیم.

تحلیل زمانی:

تمامی مراحل راه حل با زمان اجرای O(n+m) می‌توانند پیاده سازی شوند.

راه حل ساده‌تر:

راه حلی ساده‌تر نیز وجود دارد که شرکت‌کنندگان بدست آوردند: ابتدا یال‌ها را به مسیرهای ۳ راسی افراز می‌کنیم، سپس گراف H را از روی گراف‌مان می‌سازیم به این صورت که مجموعه‌ی راس‌های H مانند مجموعه راس‌های G است و هر یال در H بین دو سر یک مسیر ۳ راسی در افراز یالی G قرار دارد. حال مجموعه‌ی راس‌های با درجه فرد در G و H برابر است و در عین حال هر گشتی در H متناظر یک گشت با زوج یال در G است. حال می‌توانید مسئله‌ی ساده (بدون شرط زوج بودن یال‌های گشت‌ها) را برای H حل کنیم و گشت‌ها را در G در نظر بگیریم تا جواب مسئله پیدا شود.