تمرین ۳

ددلاین تحویل: ۱۳ خرداد ۲۳:۵۹

ثبت اولویت ویدیوی حلاگر می‌خواهید برای این تمرین ویدیوی حل ضبط کنید، اولویت سوال‌ها را ثبت کنید.

نمایش:

مقدماتی

سوال ۱ — روش‌های نمایش گراف

صورت سوال

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

الف) پیچیدگی حافظه و همچنین پیچیدگی زمانی اضافه کردن یال، بررسی وجود یال بین دو رأس داده‌شده مثل \(u\) و \(v\) و پیدا کردن همسایه‌های یک رأس را وقتی که گراف را با ماتریس مجاورت نمایش می‌دهیم، پیدا کنید.

ب) مشابه الف اما با فرض نمایش گراف با لیست مجاورت، پیچیدگی‌های خواسته‌شده را پیدا کنید.

ج) از نظر شما کدام روش از بین این دو، برای ذخیره‌ی گراف بهتر است؟

سوال ۲ — کوچک‌ترین پوشش رأسی در درخت

صورت سوال

یک درخت با \(n\) رأس داده شده است.

کوچک‌ترین اندازه‌ی مجموعه‌ای از رأس‌ها را پیدا کنید که هر یال درخت حداقل یک سر در این مجموعه داشته باشد.

مرتبه‌ی زمانی مورد انتظار: \(O(n)\)

راهنمایی‌ها

برای هر رأس دو حالت کافی است: آیا خود آن رأس را انتخاب کرده‌ایم یا نه.

راهنمایی

اگر رأس \(v\) انتخاب نشود، همه‌ی فرزندانش باید انتخاب شوند تا یال بین \(v\) و فرزند پوشش داده شود.

اگر \(v\) انتخاب شود، هر فرزند آزاد است انتخاب شود یا نشود.

پاسخ

درخت را ریشه‌دار می‌کنیم.

برای هر رأس \(v\) دو مقدار تعریف می‌کنیم:

\(dp_1[v]\): کمترین جواب در زیر‌درخت \(v\) وقتی \(v\) انتخاب شده است.
\(dp_0[v]\): کمترین جواب در زیر‌درخت \(v\) وقتی \(v\) انتخاب نشده است.

اگر \(v\) انتخاب شود، هر فرزند می‌تواند انتخاب شود یا نشود:

\(dp_1[v] = 1 + \sum \min(dp_0[u], dp_1[u])\)

اگر \(v\) انتخاب نشود، همه‌ی فرزندان باید انتخاب شوند:

\(dp_0[v] = \sum dp_1[u]\)

جواب برابر است با:

\(\min(dp_0[1], dp_1[1])\)

پیچیدگی زمانی \(O(n)\) است.

سوال ۳ — کوچک‌ترین مجموعه‌ی غالب در درخت

صورت سوال

یک درخت با \(n\) رأس داده شده است.

کوچک‌ترین اندازه‌ی مجموعه‌ای از رأس‌ها را پیدا کنید که هر رأس یا خودش در مجموعه باشد، یا حداقل یک همسایه در مجموعه داشته باشد.

مرتبه‌ی زمانی مورد انتظار: \(O(n)\)

راهنمایی‌ها

برای هر رأس فقط انتخاب شدن یا نشدن کافی نیست. باید بدانیم رأس توسط زیر‌درختش پوشش داده شده یا منتظر پدرش است.

راهنمایی

سه حالت نگه دارید:

رأس انتخاب شده است.
رأس انتخاب نشده ولی توسط یکی از فرزندانش پوشش داده شده است.
رأس هنوز پوشش داده نشده و باید توسط پدرش پوشش داده شود.

سوال ۴ — دو‌رنگ‌آمیزی درست گراف

صورت سوال

یک گراف با \(n\) رأس داده شده است.

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

مرتبه‌ی زمانی مورد انتظار: \(O(m+n)\)

راهنمایی‌ها

درخت همبند و بدون دور است. اگر رنگ یک رأس را ثابت کنید، رنگ بقیه‌ی رأس‌ها دیگر اجباری می‌شود.

راهنمایی

درخت همیشه دوبخشی است.

با انتخاب رنگ رأس \(1\)، رنگ تمام رأس‌ها بر اساس زوج یا فرد بودن فاصله‌شان از رأس \(1\) تعیین می‌شود.

سوال ۵ — قطر درخت

صورت سوال

قطر یک درخت \(T = (V,E)\) به صورت \(max\{\delta (u,v): u,v \in V\}\) تعریف شده است که به این معناست که بین همه کوتاه‌ترین مسیرها در درخت از همه بزرگ‌تر است. الگوریتمی با زمان اجرای \(O(n)\) برای محاسبه قطر درخت ارائه دهید و زمان اجرای آن را تحلیل کنید.

سوال ۶ — صفر و یک

صورت سوال

یک گراف به صورت \(G=(V,E)\) داده شده است که وزن هر یال فقط یکی از دو مقدار ۰ یا ۱ است، یعنی \(w(e) \in \{0,1\}\). همچنین یک رأس مبدأ \(s \in V\) داده شده است.

الگوریتمی ارائه کنید که فاصلهٔ کوتاه‌ترین مسیر از \(s\) به همهٔ رئوس را در زمان \(O(\mid V\mid + \mid E \mid)\)محاسبه کند.

سوال ۷ — اجرای الگوریتم‌های کوتاه‌ترین مسیر

صورت سوال

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

الف) الگوریتم دایکسترا را از رأس \(A\) روی گراف بدون‌جهت وزن‌دار زیر اجرا کنید. جدول مقدار فاصله‌ی موقت رأس‌ها را بعد از هر مرحله بنویسید و درخت کوتاه‌ترین مسیر نهایی را مشخص کنید.

ب) الگوریتم بلمن-فورد را از رأس \(S\) روی گراف جهت‌دار وزن‌دار زیر اجرا کنید و فاصله‌ی کوتاه‌ترین مسیر از \(S\) به همه‌ی رأس‌ها را به دست آورید.

ج) آیا با استفاده از الگوریتم دایکسترا می‌توان کوتاه‌ترین مسیر را روی هر گرافی پیدا کرد؟ به عنوان مثال آیا الگوریتم دایکسترا روی گراف بخش قبل، قابل اجراست؟ چرا؟

کوتاه‌ترین مسیرگراف

سوال ۸ — دورترین فاصله برای هر رأس درخت

صورت سوال

یک درخت با \(n\) رأس داده شده است.

برای هر رأس \(v\)، بیشترین فاصله‌ی آن تا یک رأس دیگر درخت را پیدا کنید.

مرتبه‌ی زمانی مورد انتظار: \(O(n)\)

پاسخ - سیده شقایق میرجلیلی

سوال ۹ — محدوده‌ی خدمت‌رسانی

صورت سوال

شبکه را گرافی مانند \(G=(V, E)\) در نظر بگیرید. هر گره \(v \in V\) یا یک سرویس‌دهنده (Provider) است یا یک کاربر (Client). برای هر سرویس‌دهنده \(i\)، یک بردِ مجاز \(r_i\) تعریف شده است. کاربر \(j\) تنها در صورتی می‌تواند از سرویس \(i\) استفاده کند که \(dist(i, j) \le r_i\) باشد.

الگوریتمی ارائه دهید که برای هر کاربر، نزدیک‌ترین سرویس‌دهنده‌ای که در محدودهٔ برد \(r_i\) قرار دارد را پیدا کند.

سوال ۱۰ — یال‌های موجود در یک کوتاه‌ترین مسیر

صورت سوال

یک گراف جهت‌دار وزن‌دار با \(n\) رأس و \(m\) یال داده شده است. وزن همه‌ی یال‌ها نامنفی است.

برای هر یال مشخص کنید آیا حداقل یک کوتاه‌ترین مسیر از رأس \(1\) به رأس \(n\) وجود دارد که از این یال عبور کند یا نه.

مرتبه‌ی زمانی مورد انتظار: \(O((n+m)\log n)\)

کوتاه‌ترین مسیرگراف

راهنمایی‌ها

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

برای این کار اول فاصله‌های لازم را حساب کنید:

راهنمایی

یک بار دایکسترا را از رأس \(1\) اجرا کنید تا \(dist_1[v]\) برای همه‌ی رأس‌ها به دست بیاید.

همچنین گراف را برعکس کنید و یک بار دایکسترا را از رأس \(n\) اجرا کنید.

برای اینکه ببینید چرا گراف را برعکس می‌کنیم:

راهنمایی

ما برای هر رأس \(v\) به کوتاه‌ترین فاصله از \(v\) تا \(n\) نیاز داریم.

اگر جهت همه‌ی یال‌ها را برعکس کنیم و دایکسترا را از \(n\) اجرا کنیم، دقیقاً همین مقدار برای همه‌ی رأس‌ها به دست می‌آید.

بعد شرط هر یال را جداگانه بررسی کنید:

راهنمایی

فرض کنید یال مورد نظر از \(u\) به \(v\) با وزن \(w\) باشد.

این یال روی یک کوتاه‌ترین مسیر از \(1\) به \(n\) قرار می‌گیرد اگر و فقط اگر:

\(dist_1[u] + w + dist_n[v] = dist_1[n]\)

برای حالت‌هایی که مسیر وجود ندارد هم حواستان باشد:

راهنمایی

اگر \(dist_1[n]\) بی‌نهایت باشد، یعنی اصلاً مسیری از \(1\) به \(n\) وجود ندارد.

در این حالت هیچ یالی نمی‌تواند روی کوتاه‌ترین مسیر از \(1\) به \(n\) باشد.

سوال ۱۱ — شمارش کوتاه‌ترین مسیرها

صورت سوال

گراف بدون جهت و وزن ‌داری با \(n\) راس و \(m\) یال ورودی داده شده است. الگوریتمی با پیچیدگی زمانی مرتبه‌ی \(O((n+m)\log(n+m))\) ارائه دهید که تعداد کوتاه‌ترین مسیر‌های متمایز از راس \(s\) به راس \(t\) را پیدا کند.

سوال ۱۲ — DAG

صورت سوال

یک گراف \(G=(V,E)\) داریم که یال‌های آن جهت‌دار هستند.

الف) یک الگوریتم معرفی کنید که بررسی کند در این گراف دور وجود دارد یا نه.

ب) اگر این گراف دور نداشت، یک الگویتم ارائه دهید که ترتیبی به رئوس در \(V\) بدهد به‌طوری که اگر یک یال جهت‌دار از \(u\) به \(v\) وجود داشت، رأس \(u\) قبل از \(v\) نمایش داده شده باشد.

سوال ۱۳ — جهت‌دهی قوی

صورت سوال

یک گراف بدون‌جهت همبند با \(n\) رأس و \(m\) یال داده شده است.

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

اگر چنین جهت‌دهی‌ای ممکن نیست، آن را گزارش دهید.

مرتبه‌ی زمانی مورد انتظار: \(O(n+m)\)

سوال ۱۴ — تشخیص وجود دور

صورت سوال

الگوریتمی ارائه دهید که تعیین کند آیا یک گراف بدون‌جهت داده‌شدهٔ \(G=(V, E)\) دارای دور هست یا خیر. الگوریتم شما باید در زمان \(O(V)\) و مستقل از \(|E|\) اجرا شود.

سوال ۱۵ — پیمایش لغت‌نامه‌ای درخت

صورت سوال

یک درخت با \(n\) رأس داریم که ریشه‌ی آن رأس \(1\) است.

در ابتدا فقط رأس \(1\) دیده شده است. در هر مرحله می‌توانیم یکی از رأس‌های دیده‌نشده را انتخاب کنیم که حداقل یک همسایه‌ی دیده‌شده داشته باشد، و آن را ببینیم.

این فرایند در پایان یک دنباله‌ی \(n\) تایی از ترتیب دیده‌شدن رأس‌ها می‌سازد.

کمینه‌ترین دنباله‌ی ممکن از نظر لغت‌نامه‌ای را پیدا کنید.

مرتبه‌ی زمانی مورد انتظار: \(O(n \log n)\)

راهنمایی‌ها

در هر لحظه فقط رأس‌هایی قابل انتخاب هستند که یک همسایه‌ی دیده‌شده دارند.

برای کمینه کردن دنباله، همیشه کوچک‌ترین رأس قابل انتخاب را بردارید:

راهنمایی

اگر در یک مرحله چند رأس قابل انتخاب باشند، انتخاب رأس کوچک‌تر همیشه بهتر است.

چون عنصر فعلی دنباله را کوچک‌تر می‌کند و هیچ رأس قابل انتخابی را از دست نمی‌دهیم.

برای پیاده‌سازی سریع، از یک داده‌ساختار مناسب استفاده کنید:

راهنمایی

مجموعه‌ی رأس‌های قابل انتخاب را در یک set یا priority_queue کمینه نگه دارید.

هر بار کوچک‌ترین رأس را خارج کنید و همسایه‌های دیده‌نشده‌ی آن را به مجموعه اضافه کنید.

پاسخ - محمد اسماعیلی مرندی

سوال ۱۶ — بیت‌فلیپ

صورت سوال

یک صفحه‌ی \(n \times m\) از لامپ‌ها داریم. هر لامپ یا خاموش است یا روشن.

در هر عملیات می‌توانیم دقیقاً یکی از کارهای زیر را انجام دهیم:

وضعیت همه‌ی لامپ‌های یک سطر را عوض کنیم؛ یعنی لامپ‌های روشن خاموش شوند و لامپ‌های خاموش روشن شوند.
وضعیت همه‌ی لامپ‌های یک ستون را عوض کنیم.

می‌خواهیم با کمترین تعداد عملیات، همه‌ی لامپ‌ها را روشن کنیم.

یک الگوریتم با پیچیدگی زمانی \(O(nm)\) برای محاسبه‌ی کمترین تعداد عملیات لازم ارائه دهید.

پاسخ - علی مقدسی

فایل‌های همراه

HW1.pdf

سوال ۱۷ — اسکیت روی یخ

صورت سوال

زمین اسکیت روی یخ به شکل یک جدول \(m \times m\) است و روی بعضی از خانه‌های آن، سنگ قرار دارد.
در ابتدا \(n\) سنگ داریم و سنگ \(i\)ام در خانه‌ی \((x_i, y_i)\) قرار گرفته است.

یک اسکیت‌باز می‌تواند از روی یک سنگ به سنگ دیگری برود، اگر این دو سنگ در یک سطر یا در یک ستون باشند؛ یعنی یا \(x\) آن‌ها برابر باشد یا \(y\) آن‌ها.

می‌خواهیم تعدادی سنگ جدید به زمین اضافه کنیم، طوری که بعد از آن اسکیت‌باز بتواند از هر سنگی به هر سنگ دیگر برسد.

کمترین تعداد سنگ‌هایی که باید اضافه شوند را محاسبه کنید.

یک الگوریتم با پیچیدگی زمانی \(O(n^2 + m)\) ارائه دهید.

پاسخ - کیاشا کوشانفر

سوال ۱۸ — کوتاه‌ترین مسیر زوج و فرد

صورت سوال

گراف وزن‌دار با \(n\) رأس و \(m\) یال داده می‌شود. دو رأس \(u\) و \(v\) داده می‌شود. کمترین فاصله‌ی مسیری از \(u\) به \(v\) که تعداد یال‌هایش زوج باشد و کمترین فاصله‌ای که تعداد یال‌هایش فرد باشد را بیابید. اگر چنین مسیری وجود نداشت، \(-1\) برگردانید.

اردر مورد انتظار: \(O((n + m) \log n)\)

سوال ۱۹ — یال‌های نمایی

صورت سوال

یک گراف \(G=(V,E)\) داریم که یال‌های آن وزن دارند. اما یک تفاوت این گراف با گراف‌های معمولی این است که اگر از یک رأس شروع به پیمایش کنیم، وزن یال‌های پیموده نشده در هر گام دو‌برابر می‌شود.

به طور مثال اگر یال‌های یک مسیر \(P\) به ترتیب \(\{e_1, e_2, \dots,e_k\}\) باشند، وزن این مسیر به شکل زیر محاسبه می‌شود:

\[ W(P) = e_1 + 2\times e_2 + 2^{2}\times e_3 + \dots + 2^{k-1}\times e_k \]

فرض کنید یک رأس مثل \(u\) داده شده است. الگوریتمی ارائه دهید که فاصله‌ی این رأس تا هر راس دیگر را حساب کند.

اردر مورد انتظار: \(O(|V| \cdot |E|)\)

سوال ۲۰ — تبدیل ارز

صورت سوال

فرض کنید نرخ تبدیل \(n\)‌ ارز موجود به یکدیگر را می‌دانیم. \(m\) ریال پول در اختیار داریم. می‌خواهیم بدانیم با چندین بار تبدیل پول و نهایتا تبدیل آن به ریال می‌توانیم مقدار \(m\) را افزایش دهیم. الگوریتمی با زمان اجرای چندجمله‌ای برای تشخیص چنین کاری ارائه دهید.

سوال ۲۱ — جست‌وجو در ژرف

صورت سوال

فرض کنید یک گراف ۵ راسی همبند داریم که راس‌های آن با شماره‌های ۱ تا ۵ شماره‌گذاری شده‌اند. فرض کنید از راس ۱ DFS را اجرا می‌کنیم. فرض کنید تمام حالت‌هایی که DFS‌ می‌تواند رئوس را ملاقات کند عبارتند از \(<1, 2, 4 , 3 , 5>\)، \(<1, 3, 4, 2 , 5>\) و \(<1 , 3, 5, 4, 2>\). حال اگر از راس \(5\) DFS را اجرا کنیم ترتیب ملاقات‌ها به چه شکل می‌تواند باشد. دلیل خود را بیان کنید.

سوال ۲۲ — بازسازی رشته

صورت سوال

یک رشته‌ی ناشناخته داشته‌ایم و تمام زیررشته‌های متوالیِ طول \(2\) آن را جدا کرده‌ایم.

برای مثال، اگر رشته برابر abcde باشد، تکه‌های زیر به دست می‌آیند: ab, bc, cd, de

حالا این تکه‌ها بدون ترتیب به شما داده شده‌اند.

باید تشخیص دهید آیا ممکن است رشته‌ای وجود داشته باشد که دقیقاً همین تکه‌ها از آن ساخته شده باشند یا نه.

دقت کنید هر تکه باید دقیقاً یک بار استفاده شود.

یک الگوریتم با پیچیدگی زمانی \(O(m)\) ارائه دهید که وجود یا عدم وجود چنین رشته‌ای را تشخیص دهد. در این‌جا \(m\) تعداد تکه‌های داده‌شده است.

پاسخ - علیرضا مهندسی

سوال ۲۳ — مؤلفه‌های قویاً همبند

صورت سوال

گراف جهت‌دار \(G = (V, E)\) داده شده است. یک مؤلفه‌ی قویاً همبند، زیرمجموعه‌ای ماکزیمال از رئوس است که برای هر جفت رأس آن، در هر دو جهت مسیر وجود داشته باشد.

الگوریتمی از مرتبه‌ی زمانی\(O(|V| + |E|)\) ارائه دهید که لیستی از تمامی مؤلفه‌های قویاً همبند این گراف را به‌عنوان خروجی برگرداند؛ به‌این‌صورت که برای هر مؤلفه، مجموعه‌ی رئوس متعلق به آن مشخص شده باشد.

سوال ۲۴ — رأس‌هایی که به همه‌جا می‌رسند

صورت سوال

یک گراف جهت‌دار با \(n\) رأس و \(m\) یال داده شده است.

تعداد رأس‌هایی را پیدا کنید که از آن‌ها به همه‌ی رأس‌های دیگر مسیر جهت‌دار وجود دارد.

مرتبه‌ی زمانی مورد انتظار: \(O(n+m)\)

پاسخ - Soroush Davaran

سوال ۲۵ — دزد و پلیس

صورت سوال

یک گراف بدون‌جهت با \(n\) رأس و \(m\) یال داریم. دزد در ابتدا در رأس \(1\) قرار دارد و چند پلیس نیز در رأس‌های داده‌شده قرار دارند.

در هر مرحله، هر نفر می‌تواند در رأس فعلی خود بماند یا به یکی از رأس‌های مجاور برود.

دزد زمانی فرار می‌کند که به رأس \(n\) برسد و این کار را اکیدا زودتر از همه‌ی پلیس‌ها انجام دهد. اگر در هر زمانی یک پلیس و دزد روی یک رأس باشند، دزد دستگیر می‌شود.

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

مرتبه‌ی زمانی مورد انتظار: \(O(n+m)\)

راهنمایی‌ها

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

راهنمایی

از همه‌ی رأس‌هایی که در ابتدا پلیس دارند، همزمان BFS بزنید.

همه‌ی این رأس‌ها را با فاصله‌ی \(0\) داخل صف بگذارید. مقدار به‌دست‌آمده برای هر رأس، زودترین زمان رسیدن یک پلیس به آن رأس است.

بعد فقط مسیرهایی را برای دزد بررسی کنید که ورود به همه‌ی رأس‌هایشان امن باشد:

راهنمایی

اگر دزد در زمان \(t\) به رأس \(v\) برسد، این حالت فقط وقتی امن است که:

\(t < police[v]\)

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

پاسخ - شمیم رحیمی

سوال ۲۶ — ماینکرفت

صورت سوال

پوریا، سهیل و علیرضا داخل یک مپ ماینکرفت زندگی می‌کنند.
مپ به صورت یک جدول \(n \times n\) است و بعضی از خانه‌های آن قابل عبور نیستند.

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

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

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

یک الگوریتم با پیچیدگی زمانی \(O(n^2 \log n)\) بدهید که کمترین هزینه‌ی لازم را محاسبه کند.

پاسخ - سید حسن خاتمی بیدگلی

پیشرفته

سوال ۲۷ — قرنطینه

صورت سوال

سال ۲۰۳۱. یک ویروس ناشناخته با سرعت نگران‌کننده‌ای در حال گسترش است. دولت تصمیم گرفته به عنوان آخرین راه‌حل، شهرهای آلوده را یکی یکی قرنطینه‌ی کامل کند — به این معنا که تمام جاده‌های ورودی و خروجی آن شهر برای همیشه بسته می‌شوند و آن شهر از شبکه‌ی حمل‌ونقل کشور حذف می‌گردد.

سازمان مدیریت بحران یک لیست محرمانه در اختیار شما گذاشته: ترتیب دقیق شهرهایی که قرار است قرنطینه شوند، به همراه استعلام‌هایی که در بازه‌های مختلف از شما پرسیده خواهد شد — کوتاه‌ترین مسیر بین دو شهر سالم در آن لحظه چقدر است؟

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

صورت مسئله

یک گراف وزن‌دار با \(n\) رأس و \(m\) یال داده می‌شود. دو نوع کوئری وجود دارد:

نوع ۱: رأس \(v\) و تمام یال‌های متصل به آن از گراف حذف می‌شود.
نوع ۲: کوتاه‌ترین فاصله بین رأس \(u\) و رأس \(v\) در گراف فعلی را بیابید. تضمین می‌شود هر دو رأس هنوز در گراف حضور دارند.

کوئری‌ها آفلاین هستند — یعنی تمام کوئری‌ها از ابتدا در اختیار شماست و می‌توانید آن‌ها را پردازش کرده و پاسخ‌ها را یکجا خروجی دهید.

اردر مورد انتظار: \(O(n^3 + q)\)

سوال ۲۸ — 2SAT (ارضای دودویی)

صورت سوال

در مسئله‌ی \(\text{2-SAT}\)، یک فرمول منطقی شامل تعدادی متغیر بولی به شما داده می‌شود. این فرمول در حالت استاندارد \(\text{2-CNF}\) قرار دارد؛ به این معنا که از عطف (AND) تعدادی عبارت (Clause) تشکیل شده و در هر عبارت، دقیقاً فصل (OR) دو لیترال (خود متغیر یا نقیض آن) وجود دارد.

به عنوان مثال:

\[ (x_1 \lor \neg x_2) \land (\neg x_1 \lor x_3) \land (x_2 \lor \neg x_3) \]

الگوریتمی با مرتبهٔ زمانی\(O(|X| + |C|)\) (که در آن \(X\) مجموعه‌ی متغیرها و \(C\) مجموعه‌ی عبارات است)

ارائه دهید که تعیین کند آیا می‌توان به متغیرها مقدار‌دهی بولی نسبت داد به‌گونه‌ای که کل فرمول مقدار True بگیرد یا خیر. در صورت وجود، یکی از این مقداردهی‌ها را خروجی دهید و در غیر این صورت اعلام کنید که فرمول غیرقابل ارضا (Unsatisfiable) است.

راهنمایی‌ها

برای حل این مسئله، یک گراف جهت‌دار بسازید. به ازای هر متغیر \(x\)، دو رأس مجزا برای \(x\) و نقیض آن (\(\neg x\)) در نظر بگیرید. سپس تلاش کنید هر عبارت (Clause) در فرمول را با یال‌های جهت‌دار در این گراف مدل کنید و نهایتاً سؤال را با کمک مسئله‌ی SCC حل کنید.

سوال ۲۹ — حذف تطابق

صورت سوال

گراف بدون‌جهتی به‌صورت \(G=(V,E)\) داده شده است که هر یال آن دارای یک رنگ است.

یک رنگ‌آمیزی یال‌ها را سره (proper) می‌گوییم اگر هیچ دو یال هم‌راس، رنگ یکسان نداشته باشند.

هدف، حذف مجموعه‌ای از یال‌ها است به‌طوری‌که:

یال‌های حذف‌شده یک Matching تشکیل دهند؛ یعنی هیچ دو یال حذف‌شده رأس مشترک نداشته باشند.
پس از حذف این یال‌ها، یال‌های باقی‌مانده یک رنگ‌آمیزی سره (proper) تشکیل دهند.

الگوریتمی از مرتبه‌ی زمانی \(O(|V| + |E|)\) طراحی کنید که تعیین کند آیا چنین مجموعه‌ای از یال‌ها وجود دارد یا خیر. در صورت وجود، یکی از این مجموعه‌ها را خروجی دهید.

2-satscc

راهنمایی‌ها

راهنمایی: برای حل سؤال از مسئله‌ی 2-SAT استفاده کنید.

برای هر یال \(e\)، یک متغیر بولی \(x_e\) تعریف کنید:

\(x_e = \texttt{True}\) به این معنا که یال \(e\) حذف می‌شود،
و \(x_e = \texttt{False}\) به این معنا که یال \(e\) در گراف باقی می‌ماند.

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

برای آنکه مطمئن شوید از هر رأس حداکثر یک یال حذف می‌شود، از ایده‌ی partial OR استفاده کنید.

فرض کنید یال‌های متصل به رأس \(v\) برابر

\[ e_1, e_2, \ldots, e_k \]

باشند. متغیرهای کمکی

\[ p_1, p_2, \ldots, p_k \]

را تعریف کنید، به‌طوری‌که \(p_i\) زمانی و تنها زمانی مقدار True داشته باشد که حداقل یکی از متغیرهای

\[ x_{e_1}, x_{e_2}, \ldots, x_{e_i} \]

مقدار True داشته باشد.

سپس با استفاده از Clauseهای مناسب، تضمین کنید که هیچ دو یال متصل به یک رأس به‌طور هم‌زمان حذف نشوند.

پاسخ - میلاد رستمی

سوال ۳۰ — دایجسترا با وزن‌های کوچک

صورت سوال

فرض کنید می‌خواهیم الگوریتم دایجسترا را روی گرافی اجرا کنیم که وزن یال‌های آن اعداد صحیح در بازهٔ \(\{0, 1, \dots, W\}\) هستند، که در آن \(W\) عدد نسبتاً کوچکی است.

الف) نشان دهید چگونه می‌توان الگوریتم دایجسترا را به گونه‌ای پیاده‌سازی کرد که در زمان \(O(W|V| + |E|)\) اجرا شود.

ب) یک پیاده‌سازی جایگزین نشان دهید که زمان اجرای آن برابر با \(O((|V| + |E|) \log W)\) باشد.

پاسخ - حسنا شاه حیدری

فایل‌های همراه

EE-4-.pdf

سوال ۳۱ — برعکس کردن یال‌ها

صورت سوال

یک گراف جهت‌دار با \(n\) رأس و \(m\) یال داریم. یال \(i\)ام از رأس \(u_i\) به رأس \(v_i\) می‌رود و هزینه‌ی برعکس کردن آن برابر \(w_i\) است.

می‌توانیم تعدادی از یال‌ها را برعکس کنیم. هزینه‌ی کل این کار برابر بیشترین هزینه بین یال‌هایی است که برعکس کرده‌ایم. اگر هیچ یالی را برعکس نکنیم، هزینه برابر \(0\) است.

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

یک الگوریتم با پیچیدگی زمانی \(O((n + m)\log m)\) ارائه دهید که کمترین هزینه‌ی لازم را محاسبه کند.

پاسخ - سید محمد مهدی حسینی

سوال ۳۲ — دوبینی

صورت سوال

فرض کنید یک گراف بدون‌جهت داریم که هر یال آن دارای دو وزن مثبت است. بار اولی که از یک یال عبور می‌کنیم باید به اندازه وزن بیش‌تر آن یال هزینه پرداخت کنیم و بارهای بعدی به اندازه وزن سبک‌تر هزینه پرداخت می‌کنیم. می‌خواهیم از راس \(u\) به راس \(v\) برویم و در مسیر از راس \(w\) عبور کنیم. الگوریتمی از مرتبه \(O(n\log n+m)\) ارائه دهید که مسیر با کم‌ترین وزن را پیدا کند که \(n\) و \(m\) به ترتیب تعداد رئوس و تعداد یال‌های گراف می‌باشند.

پاسخ - رادین بهارصفت

سوال ۳۳ — سیاره‌ها

صورت سوال

گوئائولد آپوفیس دوباره تیم جک اونیل را دستگیر کرده است! خود جک توانست فرار کند، اما تا آن زمان سفینه آپوفیس به فضای ابرپرش رفته بود. اما جک می‌داند آپوفیس در کدام سیاره فرود خواهد آمد. برای نجات دوستانش، جک باید مکرراً از طریق دروازه‌های ستاره‌ای (stargates) به این سیاره برود.

در مجموع، کهکشان دارای 𝑛 سیاره است که با اعداد 1 تا 𝑛 شماره‌گذاری شده‌اند. جک در سیاره‌ای با شاخص 1 قرار دارد و آپوفیس در سیاره‌ای با شاخص 𝑛 فرود خواهد آمد. جک می‌تواند از طریق دروازه‌های ستاره‌ای بین برخی از جفت‌سیاره‌ها حرکت کند (او می‌تواند در هر دو جهت حرکت کند)؛ انتقال بین جفت‌ سیاره‌های مختلف ممکن است زمان‌های مثبت و احتمالاً متفاوتی (به ثانیه) طول بکشد.

جک سفر خود را در زمان 0 آغاز می‌کند. ممکن است مسافران دیگری نیز به سیاره‌ای که جک در حال حاضر در آن است برسند. در این حالت، جک باید دقیقاً 1 ثانیه صبر کند تا بتواند از دروازه ستاره‌ای استفاده کند. یعنی اگر در زمان t مسافر دیگری به سیاره برسد، جک تنها می‌تواند در زمان t+1 از دروازه عبور کند، مگر اینکه مسافران بیشتری در زمان t+1 به همان سیاره برسند.

با دانستن اطلاعات مربوط به زمان سفر بین سیاره‌ها و زمان‌هایی که جک نمی‌تواند از دروازه ستاره‌ای در سیاره‌های خاص استفاده کند، حداقل زمانی که او می‌تواند به سیاره با شاخص n برسد را در زمان \(O((m+n)\log _{}{n}\) تعیین کنید.

کوتاه‌ترین مسیرگراف

سوال ۳۴ — بازی لحظه‌آخری

صورت سوال

گراف جهت‌دار \(n\) رأسی و \(m\) یالی داریم که مهره‌ای روی رأس شماره \(1\) آن قرار دارد. آلیس و باب به نوبت بازی می‌کنند. در هر نوبت، بازیکن باید مهره را از رأس فعلی \(v\) به یکی از رئوس همسایه خروجی آن منتقل کند. بازیکنی که در نوبت خود نتواند حرکتی انجام دهد (یعنی مهره در رأسی بدون یال خروجی قرار گرفته باشد)، بازنده است. اگر هر دو بازیکن بتوانند با بازیِ بهینه، مانع از پایان بازی شوند (بازی تا بی‌نهایت ادامه یابد)، نتیجه مساوی است. الگوریتمی با پیچیدگی \(\mathcal{O}(n+m)\) ارائه دهید که برنده بازی را مشخص کند.

پاسخ - محمد‌حسین شیرازی

سوال ۳۵ — والیبال

صورت سوال

پتیا والیبال را خیلی دوست دارد. یک روز او برای یک مسابقه والیبال دیر کرده بود. پتیا ماشین شخصی نخریده است، به همین دلیل مجبور شد تاکسی بگیرد. شهر دارای \(n\) تقاطع است که برخی از آن‌ها توسط جاده‌های دوطرفه به هم متصل شده‌اند. طول هر جاده با یک عدد صحیح مثبت بر حسب متر مشخص می‌شود؛ جاده‌ها می‌توانند طول‌های متفاوتی داشته باشند.

در ابتدا در هر تقاطع دقیقاً یک تاکسی ایستاده است. راننده تاکسی تقاطع \(i\)-ام موافقت می‌کند که پتیا را (شاید از طریق چند تقاطع میانی) به تقاطع دیگری ببرد، به شرطی که مسافت سفر بیشتر از \(t_i\) متر نباشد. همچنین، هزینه سفر به مسافت بستگی ندارد و برابر با \(c_i\) بورل (واحد پول) است. تاکسی‌ها نمی‌توانند در وسط جاده توقف کنند. از هر تاکسی حداکثر یک بار می‌توان استفاده کرد. پتیا تنها در تقاطعی می‌تواند سوار تاکسی شود که تاکسی در ابتدا در آنجا ایستاده است.

در این لحظه پتیا در تقاطع \(x\) قرار دارد و استادیوم والیبال در تقاطع \(y\) است. حداقل مقدار پولی که پتیا برای رسیدن به استادیوم باید بپردازد را تعیین کنید.

کوتاه‌ترین مسیرگراف

سوال ۳۶ — پرچم فرانسه

صورت سوال

گراف جهت‌داری مانند \(G\) را در نظر بگیرید که هر یال آن به رنگ قرمز، سفید یا آبی درآمده است. یک «پیمایش» (Walk) در \(G\) را «پیمایش پرچم فرانسه» می‌نامیم اگر دنبالهٔ رنگ یال‌های آن به صورت قرمز، سفید، آبی، قرمز، سفید، آبی و به همین ترتیب باشد. به عبارت دقیق‌تر، پیمایش \(v_0 \to v_1 \to \dots \to v_k\) یک پیمایش پرچم فرانسه است اگر برای هر عدد صحیح \(i\)، یال \(v_i \to v_{i+1}\) در صورتی که \(i \pmod 3 = 0\) قرمز، در صورتی که \(i \pmod 3 = 1\) سفید، و در صورتی که \(i \pmod 3 = 2\) آبی باشد.

الگوریتمی را توصیف کنید که تمام رئوس در \(G\) را که از یک رأس مشخص \(v\) از طریق یک پیمایش پرچم فرانسه قابل دسترسی هستند، پیدا کند.

پاسخ - محمد جعفری پور

سوال ۳۷ — مسیر متناوب

صورت سوال

یک گراف بدون جهت با \(n\) رأس و \(m\) یال به شما داده شده است. رئوس از \(1\) تا \(n\) شماره‌گذاری شده‌اند. گراف هیچ طوقه (self-loop) یا یال چندگانه‌ای ندارد.

وظیفه شما این است که با انتخاب یک جهت برای هر یال، گراف را به یک گراف جهت‌دار تبدیل کنید. پس از جهت‌دهی به یال‌ها، یک دنباله از رئوس \(v_1, v_2, \dots, v_k\) را یک مسیر متناوب (alternating path) می‌نامیم (که در آن \(k\) می‌تواند به دلخواه بزرگ باشد و هر رأس می‌تواند به هر تعداد بار تکرار شود) اگر:

یال \((v_1, v_2)\) از \(v_1\) به \(v_2\) جهت‌دهی شده باشد،
یال \((v_2, v_3)\) از \(v_3\) به \(v_2\) جهت‌دهی شده باشد،
یال \((v_3, v_4)\) از \(v_3\) به \(v_4\) جهت‌دهی شده باشد،
یال \((v_4, v_5)\) از \(v_5\) به \(v_4\) جهت‌دهی شده باشد،
و به همین ترتیب.

یک رأس \(v\) رازیبا می‌نامیم اگر تمام مسیرهایی که در گراف اولیه از رأس \(v\) شروع می‌شوند (لزوماً مسیرهای ساده نیستند)، در گراف جهت‌دارِ حاصل، متناوب باشند.

بیشترین تعداد رئوسی که می‌توانند پس از جهت‌دهی یال‌ها زیبا شوند، چقدر است؟

گراف

پاسخ - مهدی آشیانی

فایل‌های همراه

files.zip

سوال ۳۸ — کمترین عدد روی مسیر

صورت سوال

یک گراف جهت‌دار با \(n\) رأس و \(m\) یال داده شده است. روی هر یال یکی از ارقام \(0\) تا \(9\) نوشته شده است.

می‌خواهیم از رأس \(1\) به رأس \(n\) برویم. اگر ارقام یال‌های طی‌شده را به ترتیب بنویسیم، یک عدد ده‌دهی ساخته می‌شود.

کمترین عدد ممکنی را که می‌توان به این شکل ساخت، پیدا کنید.

تعداد رقم‌های جواب ممکن است زیاد باشد، پس جواب را به صورت رشته چاپ کنید. صفرهای ابتدایی در مقدار عدد اثری ندارند و نباید در خروجی بیایند، مگر اینکه جواب دقیقا \(0\) باشد.

پاسخ - سارا قضاوی

فایل‌های همراه

least_number.pdf

سوال ۳۹ — گسترش ناحیه‌ی متصل

صورت سوال

یک گراف بدون‌جهت همبند با \(n\) رأس و \(m\) یال داده شده است. رأس \(i\) مقدار مثبت \(a_i\) را دارد.

در ابتدا فقط رأس \(1\) فعال است و قدرت فعلی برابر \(a_1+x\) است، که \(x\) یک عدد صحیح نامنفی است و قبل از شروع فرایند انتخاب می‌شود.

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

کمترین مقدار \(x\) را پیدا کنید که با آن بتوان همه‌ی رأس‌ها را فعال کرد.

مرتبه‌ی زمانی مورد انتظار: \(O(m \log n)\)

پاسخ - علیرضا منصوری

فایل‌های همراه

39.pdf

سوال ۴۰ — بودن یا نبودن

صورت سوال

الگوریتمی با پیچیدگی زمانی مرتبه مکعب \(n\) ارائه دهید و ماتریس \(D\) با ابعاد \(n \times n\) را به عنوان ورودی می‌گیرد و در خروجی بیان می‌کند که آیا گراف وزن‌دار و جهت‌داری وجود دارد که در آن کوتاه‌ترین مسیر از راس \(i\) به راس \(j\) دقیقا برابر با \(D_{ij}\) باشد؟

پاسخ - محمدپارسا شاه‌محمدی

سوال ۴۱ — چک برگشتی

صورت سوال

خانم دکتر، خانم نسبتاً ولخرجی است و به خرید کردن علاقه بسیار زیادی دارد. او در کشوری با \(n\) شهر زندگی می کند که شهرهایش با \(m\) جاده دو طرفه به هم متصل هستند. هر جاده نیز طول صحیح و مثبتی دارد.

اخیراً خانم دکتر به علت خرید های زیادش بدهی بالا آورده و \(t\) چک دست طلب‌کارهایش دارد. طلب کار \(i\)-ام در شهر \(a_i\) زندگی‌ می‌کند و چک این طلب‌کار در روز \(i\)-ام برگشت می خورد. هر طلب کار بعد از برگشت خوردن چکش می خواهد خانم دکتر را پیدا کند و او را به زندان بیندازد. ولی از آن جایی که طلب‌کارها آدم های تنبلی هستند، در صورتی به دنبال خانم دکتر می روند که فاصله شهرشان تا شهر خانم دکتر کمتر از \(k\) باشد.

حال آقای مهندس، همسر مهربان خانم دکتر، در هر یک از \(t\) روز می خواهد بداند که خانم دکتر را به چند شهر می‌تواند فراری دهد که از دست طلب‌کارها در امان باشد. از آنجایی که \(k\) مقدار کمی است، الگوریتمی از \(O(k(n+m))\) دهید و به آقای مهندس کمک کنید!

کوتاه‌ترین مسیرگراف

سوال ۴۲ — اسکاتلند

صورت سوال

یک گراف بدون‌جهت همبند با \(n\) شهر و \(m\) جاده داریم. عبور از جاده‌ی بین دو شهر \(u\) و \(v\) به \(w\) لیتر بنزین نیاز دارد.

در شهر \(i\)، قیمت هر لیتر بنزین برابر \(a_i\) است. ماشین در ابتدای سفر هیچ بنزینی ندارد، ولی ظرفیت باک آن نامحدود است و در هر شهر می‌توان هر مقدار بنزین خرید.

برای هر زوج مرتب از شهرها \((s,t)\)، کمترین هزینه‌ی لازم برای سفر از \(s\) به \(t\) را پیدا کنید.

مرتبه‌ی زمانی مورد انتظار: حدود \(O(n^3)\)