المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:آزمون های اینترنتی ۸۹ تا ۹۱:سوال ۷۱

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)$‎.


ابزار صفحه