Algorithm Speedup
متغیر $n$ تایی $x = (x_1,x_2,\cdots,x_n)$ و متغیر $m$ تایی $y=(y_1,y_2,\cdots,y_m)$ به شما داده شده است.
میدانیم تابع $F$ به صورت زیر تعریف شده است:
$$ Boolean F(x,y):$$
$$ if W(x) \neq W(y) then return 0; $$
$$ else if |W(x)| = |W(y)| = 1 then return 1; $$
$$ else return F(p(x), p(y)) \wedge F(s(x), s(y));$$ که:
- $W(x)$ برابر است با مجموعه عناصر $x$
- $p(x)$ برابر است با بزرگترین پیشوند $x$ که $W(x) \neq W(p(x))$
- $s(x)$ برابر است با بزرگترین پسوند $x$ که $W(x) \neq W(s(x))$
- $\wedge$ علامت and منطقی است و $|Z|$ برابر تعداد عناصر $Z$ است.
به طور مثال اگر $x = (2, 3, 7, 2, 7, 4, 7, 2, 4)$ باشد ، $W(x) = \{2, 3, 4, 7\}$ ، $p(x) = (2, 3, 7, 2, 7)$ و $s(x) = (7, 2, 7, 4, 7, 2, 4)$.
به شما متغیرهای $x$ و $y$ داده شده است ، شما باید $F(x,y)$ را بهدست آورید.
ورودی
- در سطر اول ورودی $1 \leq t \leq 13$ نشاندهنده تعداد تستها آمده است.
- سطر اول هر تست دو عدد $1 \leq n,m \leq 10^5$ آمده است.
- در سطر بعدی $n$ عدد $x_1$ تا $x_n$ آمده است.
- در سطر سوم هر تست $m$ عدد $y_1$ تا $y_m$ آمده است.
- مقادیر $x_i$ ها و $y_i$ ها بین 1 و $100$ است.
خروجی
به ازای هر تست $F(x,y)$ مربوط به آن تست را چاپ کنید.
محدودیتها
- محدودیت زمان: ۲ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
ورودی و خروجی نمونه
| ورودی نمونه | خروجی نمونه |
|---|---|
| 2 4 5 3 1 2 1 1 3 1 2 1 7 7 1 1 2 1 2 1 3 1 1 2 1 3 1 3 | 0 1 |
پاسخ
میتوان نشان داد که شرط این که تابع $f$ مقدار true برگرداند برقرار بودن هر دو گزاره زیر است:
- اگر $start(x)$ برابر با لیستی از $x_i$ هایی باشد که هیچ $x_{j < i}$ برابر با $x_i$ وجود ندارد و ترتیب قرار گرفتن عناصر آن به همان ترتیب حضور عناصر در $x$ است باشد ، $start(x)$ باید با $start(y)$ برابر باشد.
- اگر $end(x)$ برابر با لیستی از $x_i$ هایی باشد که هیچ $x_{j > i}$ برابر با $x_i$ وجود ندارد و ترتیب قرار گرفتن عناصر آن به همان ترتیب حضور عناصر در $x$ است باشد ، $end(x)$ باید با $end(y)$ برابر باشد.
بدیهی است که اگر $|w(x)|$ برابر با $1$ باشد، شرط لازم و کافی برای این که تابع $f$ مقدار true برگرداند، دو شرط بالاست.
حال اگر $|w(x)| \geq 2$ باشد ، تنها در صورتی تابع $f$ مقدار true برمیگرداند که هر دو شرط برای $s(x),s(y)$ و $p(x),p(y)$ برقرار باشد که در این صورت هر دو شرط برای $x,y$ نیز برقرار است.
پس کافیست دو لیست $start$ و $end$ را برای $x$ و $y$ تولید کنیم و آنها را با هم مقایسه کنیم و در صورتی پاسخ مثبت چاپ کنیم که هر دو برابر بودند.
پیچیدگی
دو لیست $start$ و $end$ را میتوان با پیچیدگی زمانی $o(n \times \log n)$ برای $x$ و $y$ ساخت و مقایسه آنها در زمان $o(n)$ امکانپذیر است. پس پیچیدگی الگوریتم برابر است با $o(n \log n)$.
| ▸ سوال قبل | سوال بعد ◂ |