جشن کوزه‌گران در حال برگزاری است و ۱۰۰ کوزه‌گر از کشورهای مختلف در این جشن حضور دارند. هر یک از کوزه‌گرها فوت و فن منحصر به فرد خودش را دارد. می‌خواهیم همه‌ی کسانی که در جشن شرکت می‌کنند، همه‌ی این ۱۰۰ نوع فن کوزه‌گری را یاد بگیرند. مشکل این است که کوزه‌گرها زبان‌های مختلفی دارند و حرف همدیگر را متوجه نمی‌شوند. خوشبختانه $n$ مترجم خبره داریم که تمام زبان‌های دنیا را می‌دانند. می‌توانیم تعدادی از آن‌ها را به جشن دعوت کنیم. دعوت از مترجم $i$ ام به مقدار $c_i$ هزینه دارد. $(1 \leq i \leq n)$
هر کسی که در جشن فوت و فنی را بلد است یا یاد می‌گیرد، به تمام دوستانش آن فن را یاد می‌دهد. در ابتدا هیچ دو نفری با هم دوست نیستند و هر دو نفری حرف همدیگر را می‌فهمند مگر اینکه هر دوی آن‌ها کوزه‌گر باشند. (مترجمان حرف همه را می‌فهمند و کوزه‌گران فقط حرف مترجمان را می‌فهمند)

آ. هر کسی در جشن یک هزینه برای دوستی دارد، هزینه دوستی مترجم $i$ ام $w_i^t$ و هزینه دوستی کوزه گر $i$ ام برابر $w_i^k$ است. در هر مرحله می‌توانیم دو نفر که حرف همدیگر را می‌فهمند انتخاب کنیم و این دو را با هزینه‌ای برابر جمع $w$های متناظر این دو نفر، با هم دوست کنیم. الگوریتمی با پیچیدگی زمانی $O(n)$ ارائه کنید که به عنوان ورودی $n$، $c_1, c_2, \dots , c_n$ و مقادیر $w_1^t, w_2^t, \dots , w_n^t$ و $w_1^k, w_2^k, \dots , w^k_{100}$ را بگیرد و کمترین هزینه را برای اینکه همه افراد حاضر در جشن، تمام ۱۰۰ فوت و فن کوزه‌گری را یاد بگیرند، خروجی دهد. (۳۰ امتیاز)

ب. در هر مرحله می‌توانیم یک نفر حاضر در جشن مانند $v$ و زیرمجموعه‌ای از افراد حاضر در جشن مانند $S$ را انتخاب کنیم، به طوری که $v \notin S$ و $v$ حرف تمام اعضای $S$ را متوجه شود. سپس با هزینه $Cost(v, S)$ تمام اعضای $S$ را با $v$ دوست کنیم. می‌دانیم تابع $Cost(v, S)$ خاصیت‌های زیر را دارد:

• این تابع در زمان $O(|S|)$ قابل محاسبه است.
• ضمنا این تابع همواره نامنفی است.
• اگر $S = \emptyset$ (تهی) باشد، $Cost(v, S) = 0$
• به ازای هر $v$ و هر زیرمجموعه $S_1, S_2$ میدانیم $Cost(v, S_1 \cup S_2) \leq Cost(v, S_1) + Cost(v, S_2)$
• به ازای هر $v$ و $S_1 \subseteq S_2$ میدانیم: $Cost(v, S_1) \leq Cost(v, S_2)$

الگوریتمی با پیچیدگی زمانی چندجمله‌ای بر حسب $n$ ارائه کنید که به عنوان ورودی عدد $n$ و مقادیر $c_1, \dots , c_n$ را بگیرد و کمترین هزینه را برای اینکه همه افراد حاضر در جشن، تمام ۱۰۰ فوت و فن کوزه‌گری را یاد بگیرند، خروجی بدهد. (می‌توانید در الگوریتم خود از تابع $Cost(v, S)$ استفاده کنید، دقت کنید در این قسمت برای ایجاد دوستی میان $u$ و $v$ لازم است هم $u$ را در مجموعه $S$ مربوط به $v$ بیاورید و هم $v$ را در مجموعه $S$ مربوط به $u$) (۷۰ امتیاز)

• سوال بعد
• سوال قبل