فرض کنید $A=\{a_1, a_2, \ldots, a_n\}$ مجموعه‌ی از $n$ عدد صحیح و متمایز باشد. $X$ را زیرمجموعه‌ای با دست کم دو عضو از $A$ در نظر بگیرید. به جفت بازه‌ی $[s_1, e_1], [s_2, e_2]$ مطلوب گوییم؛ هر گاه تمام اعداد $X$ را پوشش دهد و هم‌چنین مقدار $(e_1 - s_1) + (e_2-s_2)$ (جمع طول بازه‌ها) کمینه باشد. توجه کنید ممکن است $s_1=e_1$ یا $s_2 = e_2$ باشد.

برای مثال فرض کنید $n=5$ و $A = \{0, 1, 5, 9, 12\}$ باشد. اگر $X = \{0, 5, 9, 12\}$ باشد، جفت بازه‌ی $[0, 0], [5,12]$ مطلوب است. هم‌چنین اگر $X = \{0, 1, 5, 9 \}$ باشد، هم جفت بازه‌ی $[0, 1], [5, 9]$ و هم جفت‌ بازه‌ی $[0, 5], [9, 9]$ مطلوب هستند. هم‌چنین در این مثال جفت بازه‌ی $[0, 5], [9, 12]$ فقط در یک حالت از $X$ مطلوب است (در حالت $X = \{0, 1, 5, 9, 12\}$).

آ) فرض کنید از ورودی به شما ابتدا عدد $n$، سپس اعداد مجموعه‌ی $A$ به صورت مرتب شده و در انتها $q$ درخواست داده می‌شوند. هر درخواست به شما یک جفت بازه‌ی $[s_1, e_1], [s_2, e_2]$ می‌دهد که $s_1 < e_1 < s_2 < e_2$ باشد. شما باید در خروجی به ازای هر درخواست، تعداد زیرمجموعه‌های دست کم دو عضوی $X$ ای را بدهید که جفت بازه‌ی داده شده در آن‌ مطلوب باشد. شما باید هر خروجی را در پیمانه‌ی ۱۳۹۵ بدهید. الگوریتمی از $O(nq)$ ارائه دهید که این کار را انجام دهد.

ب) الگوریتمی از $O(n^4)$ ارائه دهید که به ازای هر ۴ عدد $s_1, e_1, s_2, e_2 \in A$ با شرط $s_1 < e_1 < s_2 < e_2$، تعداد زیرمجموعه‌هایی از $A$ را پیدا کند که زوج بازه‌ی $[s_1, e_1], [s_2, e_2]$ در آن مطلوب باشد. شما باید هر خروجی را در پیمانه‌ی ۱۳۹۵ بدهید. توجه کنید شما باید $\binom{n}{4}$ عدد در خروجی ارائه کنید.

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