راه حل های مسابقه شماره Quera ۲۱

سلام دوباره! اولا کمال عذر خواهی را برای تاخیر در نوشتن راه حل‌ها به جا می‌آورم! به هر حال کنکوری بودن هم معایبی دارد! امید وارم کانتست بیشتر از اندازه ی کافی جذاب بوده باشد!

• بولوف الکی!

  برای حساب کردن تعداد غلط‌ها کافی است اسپیس‌ها را کنار بگذاریم و حروف موجود در هر پرسش را با جواب آن چک کنیم(هر کدام آنها در یک خط نوشته می‌شوند). اگر مغایرت داشت جواب را یک واحد زیاد کنید. پیچیدگی زمانی $\mathcal{O}{(\sum |S_i|)}$ است.

   

  کد سی پلاس پلاس۱و کد سی پلاس پلاس ۲

• خیلی قهوه ای یا باج یا خوشخوار!

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

  حال اگر زوجیت هر سه دسته به صورت‌های بالا باشد آنگاه می‌توانیم آنقد دو تا دوتا از یک نوع بفروشیم که تعداد هر نوع دقیقا برابر اعداد بالا شوند و در هر دو حالت بدیهی است که می‌توانیم به دقیقا یکی از نوع یک برسیم.  پیچیدگی زمانی $\mathcal{O}{(1)}$ است.

  کد سی پلاس پلاس

• هر که بامش بیش درسش بیشتر!

  می‌توان هر عددی را با حداکثر دو حرکت به هر جای جایگشت رساند. ابتدا اعداد از یک تا $\frac{n}{2}$ را هر کدام حداکثر با دو حرکت سر جای خودشان می‌رسانیم. تا به حال حداکثر $n$ حرکت انجام داده ایم و $\frac{n}{2}$ تا عدد اول سر جای خودشان حضور دارند. پس اکنون کافی است حداکثر $\frac{n}{2}+1$ تای آخر را درست کنیم. چون حداکثر فاصله $\frac{n}{2}+1$ است می‌توان از $\frac{n}{2}+1$ تا$n-1$ را هر کدام حداکثر با یک حرکت به جای خودشان برد و سپس عدد $n$ ام خود به خود سر جای خودش قرار می‌گیرد. حداکثر تعداد حرکت‌ها $\frac{3\times{n}}{2}$ است. پیچیدگی زمانی جواب $\mathcal{O}{(n)}$ است.

  کد سی پلاس پلاس

• تقلب رمزی

  به طور کلی بررسی کردن هر حرف به صورت جدا انجام می‌شود و هیچ حرفی روی حرف دیگر تاثیر نمی‌گذارد. می‌خواهیم بفهمیم آیا می‌توانیم از حرف $c$ شروع کنیم یا خیر؟

  فرض می‌کنیم که می‌خواهیم بدانیم اگر با حرفی خاص مانند $c$ شروع کنیم در i عملیات اول به چه حرفی می‌رسیم. برای این منظور  $f_{c_i}$ را تعریف می‌کنیم. به سادگی معلوم است که $f_{c_i}$ می‌شود $convert( f_{c_{i - 1}}, i)$ که $convert(a, i)$ برابر حرفی است که با انجام عملیات $i$ام روی حرف $a$ بدست می‌آید.

  به همین ترتیب برای انجام برعکس عملیات‌ها $g_{c_i}$ را تعریف می‌کنیم که یعنی اگر $i$ عملیات آخر را داشته باشیم و از حرف $c$ شروع کنیم به چه حرفی می‌رسیم. بطور مشابه داریم

  $g_{c_i} = f_{convert(c,i)_{i+1}}$ 

  حال برای انجام برعکس عملیات‌ها نیز توابعی به نام $ff$ و $gg$ مانند $f$ و $g$ تعریف می‌کنیم و سپس می‌توانیم بفهمیم که آیا یک حرف خاص مثلا $c$ با حذف عملیات‌های $l$ تا $r$ یکه است یا نه. معلوم است که با حذف عملیات های $l$ تا $r$ حرف $c$ به حرف $cc = g_{{(f_{c_{(l-1)}})}_{r+1}}$ تبدیل می‌شود. اگر حرف $cc$ با انجام برعکس عملیات ها و استفاده از $ff$ و$gg$ به همان $c$ رسیدیم پس $c$ در این کوئری یکه است. 

  از طرفی چون عملیات‌ها روی یک حرف دقیقا یک خروجی دارند (حروف مستقل از هم هستند) پس کافی است تا تعداد حروف یکه را بیابیم بدین ترتیب تعداد کلمات یکه هم بدست می‌آید و جواب هر کوئری برابر $t^{ans}$ می‌شود که $ans$ تعداد حرف‌های یکه است و t طول داده شده در کوئری است. پیچیدگی زمانی $\mathcal{O}{(n+q \times K)}$ است که$K$ تعداد حروف الفباست.

  کد سی پلاس پلاس

• درخت تقلب

  این مساله را به صورت آفلاین حل می‌کنیم
  یعنی ابتدا تمام کوئری‌هارا دریافت می‌کنیم و بعدا جواب هر یک را می‌دهیم.

  ابتدا تمام کوئری‌های نوع ۱ را دریافت می‌کنیم و راس‌ها را به درخت اضافه می‌کنیم. از راس ۱ دی اف اس میزنیم و روی هر راس زمان وارد شدن تابع $dfs$ به آن را می‌نویسیم در این صورت روی راس $u$ عدد $s_u$ نوشته خواهد شد.

  ما برای هر کوئری نوع دوم مانند $v\ d$ بیشترین ارتفاع $h$ را در درخت می‌خواهیم بطوریکه راسی در آن ارتفاع باشد که فاصله اش از $v$ کمتر یا مساوی $d$ باشد. می‌دانیم اگر $h_v\leq x-1$ باشد و راسی در ارتفاع $x$ باشد که فاصله اش از $v$ کمتر یا مساوی $d$ باشد راسی در ارتفاع $x - 1$ نیز با خاصیت مذکور وجود دارد. پس می‌توانیم با جستجوی دودویی روی ارتفاع h را پیدا کنیم.

  حال می‌خواهیم بدانیم در ارتفاع $h_v\leq x$ نزدیک ترین راس به $v$ چه راسی است. دو تا از نزدیک ترین راس‌ها به v آن دوتاییست که در ارتفاع $h$ عدد منتاظرشان در آرایه $s$  به $s_v$ نزدیک تر است. واضح است که در ارتفاع h فقط راس‌هایی را می‌بینیم که قبل از این کوئری وصل شده اند. و می‌توانیم این دو راس را با جست جوی دودویی دیگری پیدا کنیم.

  حال برای پیدا کردن فاصله دو راس در درخت جد مشترک $(lca)$ آنها را پیدا می‌کنیم به این ترتیب فاصله دو راس نیز به راحتی بدست می‌آید. پیچیدگی زمانی این جواب $\mathcal{O}{(n\times log_2{(n)} ^ 2)}$ است. همین راه پیاده سازی سریع تر هم دارد.

   

• منبع موثق

  فرض کنیم دو تابع داریم که مقادیر زیر را برای ما حساب می‌کنند :

  $f(A, d, k, x, n)=\sum_{0\leq i\leq {n-1}} \sum_{0\leq j\leq {x+i\times k}} (A+d\times j)$ $g(A, d, k, x, n)=\sum_{0\leq i\leq {n-1}} \sum_{{(i-1)}\times {(x+i\times k)}\leq j\leq i\times {(x+i\times k)}} (A+d\times j)$

  می‌دانیم که ممکن است تعدادی از سطرهای ابتدایی جدول باشند  که فقط اعداد مربوط به دنباله حسابی دوم (دنباله حسابی ستون‌ها) روی خانه‌‌های آن‌ها نوشته می‌شود. به طرز مشابه تعدادی از سطرهای آخر هستند که فقط اعداد دنباله حسابی اول روی آن‌ها نوشته می‌شود. می‌توان مجموع آن سطر‌هارا حساب کرد و جدول را بدون آنها در نظر گرفت.
  حال $p(i)$ را بدین گونه تعریف می‌کنیم : $p(i)$ برابر کوچکترین $j$ ای است که $i \times b + a < j\times d + c$ معلوم است که $p(i) + c = p(i + a)$.
  حال مجموع خانه‌های $p(i + k \times a)$ تا $m$ ام سطر $i + k\times a$ (به ازای هر $k$ ) را می‌توان با تابع $f$ حساب کرد
  همچین مجموع خانه‌های 1 تا $p(i\times k + a)$ ام سطر $i + k\times a$ (به ازای هر $k$ ) را می‌توان با تابع $g$ حساب کرد.
  پس می‌توانیم مجموع تمام سطرهایی که باقیمانده اندیسشان بر $a$ برابر است را یک جا حساب کنیم.
  بنابر این می‌توان مجموع جدول را از $\mathcal{O(a)}$ حساب کرد.
  یافتن فرمول برای دو تابع $f$ و $g$ نیز با کمی اطلاعات درباره ی دنباله‌های حسابی ساده می‌شود.

• چمران

  $t$ را در نظر بگیریم کمترین زمانی که می‌توان چنین گشتی را طی کرد. اگر چنین عددی وجود نداشته باشد جواب $"NO"$ و گرنه $"YES"$ است. می‌خواهیم کوتاه ترین گشت ممکن را بررسی کنیم. برای سادگی راه حل فرض می‌کنیم شروع مسیر در جواب به سمت خانه‌ی $n$ بوده است(یک بار هم فرض می‌کنیم به سمت خانه‌ی 0 بوده است) و سوال را حل می‌کنیم.

  دنباله‌ی $Sl$ و $Sr$ را در نظر بگیرید. $Sl$ دنباله‌ای از اعداد ۱ تا $n$ است که تمام جاهایی است که در طول مسیر فرد مورد نظر به سمت خانه‌ی $n$ درحال حرکت بوده و در خانه‌ی $Sl_i$  به سمت خانه‌ی صفر دور می‌زند( تغییر جهت می‌دهد). دورها به ترتیب زمان در $Sl$ ظاهر می‌شوند به این معنا که اگر دوری زودتر از دور دیگری انجام شود در دنباله در خانه‌ای با اندیس کمتر ظاهر می‌شود.$Sr$ هم مانند $Sl$ است با این تفاوت که دور‌ها از سمت خانه‌ی صفر به سمت خانه‌ی $n$ است.  اولین خانه ی مسیر را هم به $Sl$ می‌افزاییم چرا که به سمت خانه‌ی $n$ است. مقصد نیز به آن طرفی می‌افزاییم که به سمت آن تمام می‌شود.

  ابتدا ثابت می‌کنیم اگر $t$ مینیموم باشد $Sl$ دنباله ای اکیدا نزولی و $Sr$ اکیدا صعودی است. بدون از دست دادن کلیت روی $Sl$ بحث می‌کنیم (برای $Sr$ به قرینه ثابت می‌شود). فرض کنید $Sl$ نزولی اکید نباشد. شماره اولین دوری این ترتیب را به هم زده است را i در نظر بگیرید.  پس اکنون $Sl_i \leq Sl_{i+1}$. قسمتی از مسیر به این صورت است:

  $Sl_{i-1}$ ا—> $Sr_i$ ا—->  $Sl_i$ ا—> $Sr_{i+1}$ ا—> $Sl_{i+1}$.

  که جایگزین مناسب تر آن این مسیر است:  

  $Sl_{i-1}$ ا—> $\min(Sr_i,Sr_{i+1})$ ا—> $Sl_{i+1}$

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

  چون $t$ کوتاه ترین گشت بود پس $Sl$ نزولی اکید و $Sr$ صعودی اکید است.$t$ حداکثر بیشترین عدد آرایه $a$ است. چون اولین خانه را فقط یک بار و در همان شروع می‌بینیم. می‌خواهیم ثابت کنیم اندازه‌ی $Sl$ حداکثر برابر $\sqrt{maxai}\times 2$ است.

  این نامساوی را در نظر بگیرید:

  $\sum_{0\leq i\leq p} (|Sl_i - Sr_i|) < t$

  چون $Sl$ نزولی و $Sr$ صعودی است پس هیچ کدام از $|Sl_i - Sr_i|$ها با هم برابر نیست پس اگر بخواهیم $p$ حداکثر باشد باید جمله‌های این جمع را حداقل کنیم:

  $\sum_{0\leq i\leq 2\times \sqrt{t}} i \simeq t$

  پس$p \leq \sqrt{maxai}$ یعنی تعداد دورها حداکثر $\sqrt{maxai} \times 4$ است.

  حال کافی است دنباله‌های $Sl$ و  $Sr$ را تعیین کنیم. ابتدا برای خانه‌ی $i$ام $b_i$ را در نظر می‌گیریم برابر آخرین زمانی که تا الآن دیده شده است.

  سپس $t$ را فیکس می‌کنیم.  فرض می‌کنیم این کوتاه ترین زمانی است که می‌توان این گشت را طی کرد. همه ی درایه‌های $b$ منفی بینهایت است(به این معنا که تا به حال دیده نشده است). همانطور که از ابتدای راه حل اشاره کردیم از خانه‌ی $n$ شروع می‌کنیم.

  هر بار که می‌خواهیم تا جایی برویم و دور بزنیم محل دور را نزدیک ترین جایی که می‌توانیم انتخاب می‌کنیم.

  نزدیک ترین جایی را انتخاب می‌کنیم که خانه‌های از آن به بعد(از آن تا 0 یا از آن تا $n$) تا آخر $t$ ثانیه خواب باشند یا به عبارت دیگر اینکه به ازای همه iهایی که از محل دور به بعد وجود دارد: $t-b_i \leq a_i$

  و لازم به ذکر است که حتما باید تا آنجا برویم و این بهترین گشت برای کوتاه ترین زمان ممکن است.

  $t \leq maxai$ و تعداد دورها حداکثر $\sqrt{maxai} \times 4$ است و می‌توانیم بهترین مکان هر دور را با جست و جوی دو دویی پیدا کنیم. پس اردر زمانی مساله $\mathcal{O}{(maxai \times \sqrt{maxai} \times \log_2 (n))}$ است.

بازم سوالی بود بپرسید! ان‌شاءالله جواب میدیم.

التماس دعا!

خداحافظتون 🙂