<commit_before><div dir='rtl'>

# A - Maximum Sum II

توی این سوال، باید زیردنباله‌ای رو از توی دنباله داده‌شده پیدا کنیم که بیشترین مجموع رو بین همه زیردنباله‌ها داشته باشه.

(حواستون باشه که زیردنباله با زیرمجموعه فرق داره. اعضای زیردنباله ترتیب دارن و مثلا از عضو سوم تا عضو هشتم یه دنباله دیگه رو که پشت سرهم با همون ترتیب توی دنباله بچینیم، میشه یه دونه زیر دنباله. البته دونستن این مساله فرق خاصی توی حل این سوال برامون نداره! :دی)

### راه حل
توی صورت مساله گفته که دنباله‌ای که بهمون میده، اعضاش نامنفی هستند. یعنی صفر و بیشتر از صفر. وقتی یه سری عدد نامنفی رو با هم جمع میکنیم، به ازای هر عددی که به مجموعه‌مون اضافه میکنیم، جمع اعداد بیشتر میشه. یعنی چون عدد منفی‌ای نمیاریم توی مجموعه، پس هیچ‌وقت جمع اونها کاهش پیدا نمی‌کنه. پس هرچی تعداد بیشتری عدد بیاریم، جمع بیشتری میگیریم. پس بیاید خیلی شیک (خیلی حریصانه!) کل اعضای دنباله داده‌شده رو با هم جمع کنیم، چون بیشترین جمع رو بهمون میده!

فقط نکته اینجاست که عدد _صفر_ استثناست. یعنی هرچی صفر اضافه کنیم، جمعمون بیشتر نمیشه. چون توی صورت سوال گفته که اگه ۲ تا زیردنباله بود که جمعشون یکی بود، اونی که تعداد اعضای کمتری داره رو چاپ کن. پس به جای اینکه همه اعضای دنباله رو با هم جمع کنیم، اول صفرها رو دور میریزیم و بعد باقی‌مونده ها رو به عنوان زیردنباله موردنظر سوال، به عنوان خروجی چاپ میکنیم.


# B - <NAME>

سوال میگه که یه صفحه N در M داریم که میخوایم با دومینو های ۲ در ۱ بپوشونیمش به شرطی که هیچ ۲ دومینویی روی هم نیفتن و هیچ تکه‌ای از هیچ دومینویی بیرون از صفحه نیفته.

### راه حل
یکم که به سوال فکر کنیم میفهمیم که خیلی ساده‌تر از اونیه که فکر میکنیم! خیلی ساده (و خیلی حریصانه!) دومینوها رو از بالای صفحه سمت چپ، شروع به چیدن میکنیم به شکلی که اگر دومینو افقی جا میشد، افقی میذاریمش، اگر نمیشد، عمودی! هر دومینو رو که گذاشتیم، دیگه بعدا برنمیگردیم و جاش رو عوض کنیم یا بچرخونیمش (که این یعنی توی هر مرحله چیدن دومینوها، تصمیمشون رو حریصانه و قاطع میگریم: اگه شد، افقی، اگه نشد، عمودی! تمام!)

مساله از ما **تعداد** دومینوهای مصرفی رو میخواد. تعداد دومینوها از این هم ساده‌تر به دست میاد: مساحت صفحه تقسیم بر مساحت دومینوها (اگر اعشار داشت، بیخیال قسمت اعشاریش میشیم چون دومینوی نصفه نمیتونیم توی صفحه بذاریم).
 
# C - I Wanna Be the Guy

مساله میگه که دو نفر (X و Y) میخوان یه بازی رو مرحله به مرحله انجام بدن؛ یه سری از مراحل رو X بلده بازی کنه و یه سری رو Y. حالا ببینید که اگر این دوتا با همکاری هم بخوان بازی کنن، میتونن بازی رو تموم کنن یا نه.

### راه حل

باید ببینیم که _اجتماع_ دو تا مجموعه (مجموعه مراحلی که X بلده و مجموعه مراحلی که Y بلده) میشه کل مراحل یا نه. بعضی از مراحل توی جفت مجموعه‌ها هست و نیازه که یک بار شمرده بشن. صحبت از مجموعه شد، یاد `set` افتادم! این ساختمان‌داده (همونطور که میدونید) یک مجموعه رو تداعی میکنه و عضو تکراری نداره.

پس اول مجموعه مراحلی که X بلده رو دونه‌به‌دونه میریزیم توی یه `set`. بعد همینکار رو با مراحلی که Y بلده میکنیم و در نهایت چک میکنیم که `set`مون کل مراحل ۱ تا n رو پوشونده باشه.

# D - Taxi

سوال میگه که گروه‌هایی با اندازه‌های ۱ تا ۴ داریم و میخوایم برای این‌ها تاکسی بگیریم. هر گروه باید توی یه تاکسی سوار بشه و هر تاکسی میتونه بیشتر از یک گروه رو جابه‌جا کنه. چند تا تاکسی نیاز داریم؟
 
چون این مساله ارتباط ملموسی با زندگی روزمره ما داره، راه حلش سریع به ذهن آدم میرسه! این مساله، حریصانه حل میشه! هم توی دنیای واقعی و هم توی مسابقه. میشه متوجه شد که الگوریتم‌های حریصانه، کاربرد زیادی توی زندگی روزمره ما دارن. خیلی وقت‌ها برای اینکه هزینه کمتری بدیم و سود بیشتری ببریم، مساله رو حریصانه حل میکنیم و تقریبا همه با این راه‌حل ها آشنا هستیم‌ (شاید چون انسانیم و حریص!)

راه حل‌های حریصانه لزوما همیشه به جواب درست نمیرسن اما تا حد خوبی به جواب درست نزدیک میشن. البته توی خیلی مسائل هم به جواب درست میرسن. مثل همین مساله تاکسی‌ها.

### راه حل
اول همه گروه‌هایی که ۴ نفره هستن رو براشون تاکسی میگیریم و میفرستیم برن‌ (برای هر گروه یک تاکسی). بعد سعی میکنیم گروه‌هایی که ۳ نفره هستن و گروه‌هایی که تک نفره هستند رو با هم جفت و جور کنیم. یعنی هر گروه ۳ نفره با یک گروه تک نفره میتونه سوار یک تاکسی بشه. بعد اگر گروه‌های تک نفره تموم شدن و گروه ۳ نفره‌ای باقی موند، برای هر گروه ۳ نفره باقی مونده، یه تاکسی میگیریم.

الآن فقط گروه‌های ۲ نفره و تک نفره باقی‌موندن و گروه‌های ۳ و ۴ نفره رفتن پی سرنوشتشون! دقت کنید که وقتی میگیم الگوریتم حریصانه است، یعنی اینکه الآن تکلیف گروه‌های ۳ و ۴ نفره مشخص شده و دیگه نمیریم تاکسی‌هاشون رو برگردونیم! اون‌ها رفتن و کاریش نمیشه کرد دیگه!

الآن گروه‌های ۲ نفره رو با هم جفت میکنیم. یعنی هر ۲ تا گروه ۲ نفره، یک تاکسی. اگر تعداد گروه‌های ۲ نفره فرد بوده باشه، یک گروه ۲ نفره باقی می‌مونه که سرش بی کلاه مونده. برای اون با ۲ تا از گروه‌های تک نفره یه تاکسی میگیریم.

الآن فقط گروه‌های تک نفره باقی موندن (ممکن هم هست با گروه‌های ۳ و ۲ نفره رفته باشن البته). برای هر ۴ گروه، یه تاکسی میگیریم. در نهایت اگر کمتر از ۴ تا باقی موندن، یه تاکسی هم برای اون گروه‌های باقی‌مونده‌ی تک نفره میگیریم و تمام!

 
# E - All in All

مساله میگه که توی هرخط ۲ تا رشته‌ی `s` و `t` بهت میدم، نگاه کن و ببین که آیا `s` زیردنباله‌ای از `t` هست یا نه. یعنی میشه تعدادی از کاراکترهای `t` رو حذف کرد تا `s` ساخته بشه؟

### راه حل
بدون اینکه بخوایم به این فکر کنیم که کاراکترهای `s` کجای `t` باید قرار داشته باشن و این حرفا، کاراکترهای `s` رو به ترتیب برمیداریم و توی کاراکترهای `t` اینقدر میریم جلو تا به اون کاراکتری که برداشتیم برسیم. اینجا میگیم که «خیلی خوب! من این کاراکتر از `s` رو توی `t` پیدا کردم. میرم بقیه کاراکترهای `s` رو هم پیدا کنم!».

پس ۲ تا اشاره‌گر داریم: یکی که به کاراکترهای `s` و یکی که به کاراکترهای `t` اشاره میکنه. اشاره‌گر `t` رو اینقدر می‌بریم جلو تا به کاراکتری برسیم که مثل کاراکتریه که زیر اشاره‌گر `s` ه. بعد اشاره‌گر `s` رو یکی میبریم جلو (که یعنی کاراکتر قبلیه رو پیدا کردیم، بریم بعدی رو پیدا کنیم). اگر اشاره‌گر `s` به آخر `s` رسید، یعنی همه کاراکترهای `s` رو توی `t` پیدا کردیم و اگر نرسید و به آخر `t` رسیدیم، یعنی پیدا نکردیم.

# F - Foreign Exchange

سوال میگه که یک سری جفت عدد داریم (که عدد اول مبدا و عدد دوم مقصد حرکت یک آدمه). باید به ازای هر آدم که مثلا از A میخواد بره به B، یک نفر باشه که بخواد از B بیاد به A (یعنی این ۲ تا آدم بتونن جاشون رو با هم عوض کنن). اگر این شرایط برقرار بود باید `YES` به عنوان خروجی چاپ بشه و اگر نبود، `NO`.

### راه حل اول (که Time Limit Exceeded میخوره)
یه راه اینه که بیایم و برای هرکسی، یه جفت پیدا کنیم. یعنی مثلا کسی که از ۱ میخواد بره به ۲، یه نفر پیدا کنیم که از ۲ بخواد بره به ۱. پس یه حلقه (`for`) داریم که روی لیست آدمها حرکت میکنه و به ازای هرکسی، یه حلقه دیگه داریم که میگرده دنبال جفت اون آدم. شبه کدش میشه این:

<div dir='ltr'>
```
for c in candidates:
  for p in candidates:
    if c and p can be paired and non of them have been paired yet:
      pair(c, p)
      break
```
</div>

پیچیدگی زمانی این مساله از مرتبه تعداد آدمها به توان ۲ ه (
<div dir='ltr'>
`O(n^2)‍`
</div>
در حقیقت). از اونجایی که تعداد آدمها میتونه تا ۵۰۰۰۰۰ تا هم بالا بره، تعداد عملیاتی که ممکنه لازم باشه که انجام بشه، میتونه به `500000 * 500000` برسه یعنی `250000000000` یا `2.5E11`. (احتمالا میدونید که) هر کامپیوتر معمولی، حدود
<div dir='ltr'>
`10^8‍`
</div>
عملیات رو میتونه توی یه ثانیه انجام بده و این مساله (با یه حساب سرانگشتی) حدود ۲۵۰۰ ثانیه (یا ۴۱:۴۰ دقیقه) طول میکشه که منجر به **Time Limit Exceeded Error** میشه.

### راه حل دوم (که Accept میشه)
یکم که بیشتر فکر کنیم، میبینیم که اگر ۲ تا لیست داشته باشیم، یکی که مبداهای حرکت آدم‌ها رو تو خودش نگه میداره و یکی که مقصدها رو نگه میداره، این ۲ تا لیست باید یکی باشن. چون مبدا حرکت هر نفر باید مقصد حرکت یه نفر دیگه باشه و همچنین برعکس.

برای اینکار، ۲ تا لیست (`vector` توی سی‌پلاس‌پلاس) میگیریم و مبداها رو توی یکی و مقاصد رو توی دیگری نگه میداریم. در نهایت ۲ تا لیست هم اندازه داریم. برای اینکه چک کنیم که این ۲ تا عین هم هستن یا نه، ساده‌ترین راه حل اینه که جفتشون رو مرتب (`sort`) کنیم و بینشون `==` بذاریم. ۲ تا لیست (یا وکتور) زمانی با همدیگه برابرن که اعضاشون نظیر به نظیر با هم برابر باشن.

پیچیدگی زمانی این راه حل از `O(nlogn)` ه. چون کاری که بیشترین زمان رو توی الگوریتم میگیره، مرتب کردنه که با همین پیچیدگی زمانی انجام میشه و وقتی الگوریتم از جمع چند تا کار انجام شده باشه، پیچیدگی زمانیش میشه پیچیدگی زمانی کاری که بیشتر از همه طول میکشه.

# G - Shell Sort
سوال در مورد ۲ تا استک (پشته یا `stack`)ه. استک اولی، استکیه که اول کار داریم و استک دوم، اونیه که میخوایم بهش برسیم. اما حق انجام یک نوع عملیات رو داریم فقط: میتونیم یکی از اعضای استک رو از میانه‌ی استک بیرون بکشیم و روی استک بذاریم. هرچندباری که بخوایم، میتونیم این‌کار رو بکنیم. حالا باید با کمترین تعداد ممکن از این نوع عملیات، استک اول رو تبدیل به استک دوم کنیم. چیزی که سوال میخواد، اون اعضایی که این عملیات‌ها رو روشون انجام می‌دیمه (به ترتیب انجام عملیات‌ها).

مثلا استک اول اینه:
```
2
1
3
```<commit_msg>Fix ltr<commit_after><div dir="rtl">

# A - Maximum Sum II

توی این سوال، باید زیردنباله‌ای رو از توی دنباله داده‌شده پیدا کنیم که بیشترین مجموع رو بین همه زیردنباله‌ها داشته باشه.

(حواستون باشه که زیردنباله با زیرمجموعه فرق داره. اعضای زیردنباله ترتیب دارن و مثلا از عضو سوم تا عضو هشتم یه دنباله دیگه رو که پشت سرهم با همون ترتیب توی دنباله بچینیم، میشه یه دونه زیر دنباله. البته دونستن این مساله فرق خاصی توی حل این سوال برامون نداره! :دی)

### راه حل
توی صورت مساله گفته که دنباله‌ای که بهمون میده، اعضاش نامنفی هستند. یعنی صفر و بیشتر از صفر. وقتی یه سری عدد نامنفی رو با هم جمع میکنیم، به ازای هر عددی که به مجموعه‌مون اضافه میکنیم، جمع اعداد بیشتر میشه. یعنی چون عدد منفی‌ای نمیاریم توی مجموعه، پس هیچ‌وقت جمع اونها کاهش پیدا نمی‌کنه. پس هرچی تعداد بیشتری عدد بیاریم، جمع بیشتری میگیریم. پس بیاید خیلی شیک (خیلی حریصانه!) کل اعضای دنباله داده‌شده رو با هم جمع کنیم، چون بیشترین جمع رو بهمون میده!

فقط نکته اینجاست که عدد _صفر_ استثناست. یعنی هرچی صفر اضافه کنیم، جمعمون بیشتر نمیشه. چون توی صورت سوال گفته که اگه ۲ تا زیردنباله بود که جمعشون یکی بود، اونی که تعداد اعضای کمتری داره رو چاپ کن. پس به جای اینکه همه اعضای دنباله رو با هم جمع کنیم، اول صفرها رو دور میریزیم و بعد باقی‌مونده ها رو به عنوان زیردنباله موردنظر سوال، به عنوان خروجی چاپ میکنیم.


# B - Domino Pilling

سوال میگه که یه صفحه N در M داریم که میخوایم با دومینو های ۲ در ۱ بپوشونیمش به شرطی که هیچ ۲ دومینویی روی هم نیفتن و هیچ تکه‌ای از هیچ دومینویی بیرون از صفحه نیفته.

### راه حل
یکم که به سوال فکر کنیم میفهمیم که خیلی ساده‌تر از اونیه که فکر میکنیم! خیلی ساده (و خیلی حریصانه!) دومینوها رو از بالای صفحه سمت چپ، شروع به چیدن میکنیم به شکلی که اگر دومینو افقی جا میشد، افقی میذاریمش، اگر نمیشد، عمودی! هر دومینو رو که گذاشتیم، دیگه بعدا برنمیگردیم و جاش رو عوض کنیم یا بچرخونیمش (که این یعنی توی هر مرحله چیدن دومینوها، تصمیمشون رو حریصانه و قاطع میگریم: اگه شد، افقی، اگه نشد، عمودی! تمام!)

مساله از ما **تعداد** دومینوهای مصرفی رو میخواد. تعداد دومینوها از این هم ساده‌تر به دست میاد: مساحت صفحه تقسیم بر مساحت دومینوها (اگر اعشار داشت، بیخیال قسمت اعشاریش میشیم چون دومینوی نصفه نمیتونیم توی صفحه بذاریم).
 
# C - I Wanna Be the Guy

مساله میگه که دو نفر (X و Y) میخوان یه بازی رو مرحله به مرحله انجام بدن؛ یه سری از مراحل رو X بلده بازی کنه و یه سری رو Y. حالا ببینید که اگر این دوتا با همکاری هم بخوان بازی کنن، میتونن بازی رو تموم کنن یا نه.

### راه حل

باید ببینیم که _اجتماع_ دو تا مجموعه (مجموعه مراحلی که X بلده و مجموعه مراحلی که Y بلده) میشه کل مراحل یا نه. بعضی از مراحل توی جفت مجموعه‌ها هست و نیازه که یک بار شمرده بشن. صحبت از مجموعه شد، یاد `set` افتادم! این ساختمان‌داده (همونطور که میدونید) یک مجموعه رو تداعی میکنه و عضو تکراری نداره.

پس اول مجموعه مراحلی که X بلده رو دونه‌به‌دونه میریزیم توی یه `set`. بعد همینکار رو با مراحلی که Y بلده میکنیم و در نهایت چک میکنیم که `set`مون کل مراحل ۱ تا n رو پوشونده باشه.

# D - Taxi

سوال میگه که گروه‌هایی با اندازه‌های ۱ تا ۴ داریم و میخوایم برای این‌ها تاکسی بگیریم. هر گروه باید توی یه تاکسی سوار بشه و هر تاکسی میتونه بیشتر از یک گروه رو جابه‌جا کنه. چند تا تاکسی نیاز داریم؟
 
چون این مساله ارتباط ملموسی با زندگی روزمره ما داره، راه حلش سریع به ذهن آدم میرسه! این مساله، حریصانه حل میشه! هم توی دنیای واقعی و هم توی مسابقه. میشه متوجه شد که الگوریتم‌های حریصانه، کاربرد زیادی توی زندگی روزمره ما دارن. خیلی وقت‌ها برای اینکه هزینه کمتری بدیم و سود بیشتری ببریم، مساله رو حریصانه حل میکنیم و تقریبا همه با این راه‌حل ها آشنا هستیم‌ (شاید چون انسانیم و حریص!)

راه حل‌های حریصانه لزوما همیشه به جواب درست نمیرسن اما تا حد خوبی به جواب درست نزدیک میشن. البته توی خیلی مسائل هم به جواب درست میرسن. مثل همین مساله تاکسی‌ها.

### راه حل
اول همه گروه‌هایی که ۴ نفره هستن رو براشون تاکسی میگیریم و میفرستیم برن‌ (برای هر گروه یک تاکسی). بعد سعی میکنیم گروه‌هایی که ۳ نفره هستن و گروه‌هایی که تک نفره هستند رو با هم جفت و جور کنیم. یعنی هر گروه ۳ نفره با یک گروه تک نفره میتونه سوار یک تاکسی بشه. بعد اگر گروه‌های تک نفره تموم شدن و گروه ۳ نفره‌ای باقی موند، برای هر گروه ۳ نفره باقی مونده، یه تاکسی میگیریم.

الآن فقط گروه‌های ۲ نفره و تک نفره باقی‌موندن و گروه‌های ۳ و ۴ نفره رفتن پی سرنوشتشون! دقت کنید که وقتی میگیم الگوریتم حریصانه است، یعنی اینکه الآن تکلیف گروه‌های ۳ و ۴ نفره مشخص شده و دیگه نمیریم تاکسی‌هاشون رو برگردونیم! اون‌ها رفتن و کاریش نمیشه کرد دیگه!

الآن گروه‌های ۲ نفره رو با هم جفت میکنیم. یعنی هر ۲ تا گروه ۲ نفره، یک تاکسی. اگر تعداد گروه‌های ۲ نفره فرد بوده باشه، یک گروه ۲ نفره باقی می‌مونه که سرش بی کلاه مونده. برای اون با ۲ تا از گروه‌های تک نفره یه تاکسی میگیریم.

الآن فقط گروه‌های تک نفره باقی موندن (ممکن هم هست با گروه‌های ۳ و ۲ نفره رفته باشن البته). برای هر ۴ گروه، یه تاکسی میگیریم. در نهایت اگر کمتر از ۴ تا باقی موندن، یه تاکسی هم برای اون گروه‌های باقی‌مونده‌ی تک نفره میگیریم و تمام!

 
# E - All in All

مساله میگه که توی هرخط ۲ تا رشته‌ی `s` و `t` بهت میدم، نگاه کن و ببین که آیا `s` زیردنباله‌ای از `t` هست یا نه. یعنی میشه تعدادی از کاراکترهای `t` رو حذف کرد تا `s` ساخته بشه؟

### راه حل
بدون اینکه بخوایم به این فکر کنیم که کاراکترهای `s` کجای `t` باید قرار داشته باشن و این حرفا، کاراکترهای `s` رو به ترتیب برمیداریم و توی کاراکترهای `t` اینقدر میریم جلو تا به اون کاراکتری که برداشتیم برسیم. اینجا میگیم که «خیلی خوب! من این کاراکتر از `s` رو توی `t` پیدا کردم. میرم بقیه کاراکترهای `s` رو هم پیدا کنم!».

پس ۲ تا اشاره‌گر داریم: یکی که به کاراکترهای `s` و یکی که به کاراکترهای `t` اشاره میکنه. اشاره‌گر `t` رو اینقدر می‌بریم جلو تا به کاراکتری برسیم که مثل کاراکتریه که زیر اشاره‌گر `s` ه. بعد اشاره‌گر `s` رو یکی میبریم جلو (که یعنی کاراکتر قبلیه رو پیدا کردیم، بریم بعدی رو پیدا کنیم). اگر اشاره‌گر `s` به آخر `s` رسید، یعنی همه کاراکترهای `s` رو توی `t` پیدا کردیم و اگر نرسید و به آخر `t` رسیدیم، یعنی پیدا نکردیم.

# F - Foreign Exchange

سوال میگه که یک سری جفت عدد داریم (که عدد اول مبدا و عدد دوم مقصد حرکت یک آدمه). باید به ازای هر آدم که مثلا از A میخواد بره به B، یک نفر باشه که بخواد از B بیاد به A (یعنی این ۲ تا آدم بتونن جاشون رو با هم عوض کنن). اگر این شرایط برقرار بود باید `YES` به عنوان خروجی چاپ بشه و اگر نبود، `NO`.

### راه حل اول (که Time Limit Exceeded میخوره)
یه راه اینه که بیایم و برای هرکسی، یه جفت پیدا کنیم. یعنی مثلا کسی که از ۱ میخواد بره به ۲، یه نفر پیدا کنیم که از ۲ بخواد بره به ۱. پس یه حلقه (`for`) داریم که روی لیست آدمها حرکت میکنه و به ازای هرکسی، یه حلقه دیگه داریم که میگرده دنبال جفت اون آدم. شبه کدش میشه این:

<div dir="ltr">
```
for c in candidates:
  for p in candidates:
    if c and p can be paired and non of them have been paired yet:
      pair(c, p)
      break
```
</div>

پیچیدگی زمانی این مساله از مرتبه تعداد آدمها به توان ۲ ه (
<div dir="ltr">
`O(n^2)‍`
</div>
در حقیقت). از اونجایی که تعداد آدمها میتونه تا ۵۰۰۰۰۰ تا هم بالا بره، تعداد عملیاتی که ممکنه لازم باشه که انجام بشه، میتونه به `500000 * 500000` برسه یعنی `250000000000` یا `2.5E11`. (احتمالا میدونید که) هر کامپیوتر معمولی، حدود
<div dir="ltr">
`10^8‍`
</div>
عملیات رو میتونه توی یه ثانیه انجام بده و این مساله (با یه حساب سرانگشتی) حدود ۲۵۰۰ ثانیه (یا ۴۱:۴۰ دقیقه) طول میکشه که منجر به **Time Limit Exceeded Error** میشه.

### راه حل دوم (که Accept میشه)
یکم که بیشتر فکر کنیم، میبینیم که اگر ۲ تا لیست داشته باشیم، یکی که مبداهای حرکت آدم‌ها رو تو خودش نگه میداره و یکی که مقصدها رو نگه میداره، این ۲ تا لیست باید یکی باشن. چون مبدا حرکت هر نفر باید مقصد حرکت یه نفر دیگه باشه و همچنین برعکس.

برای اینکار، ۲ تا لیست (`vector` توی سی‌پلاس‌پلاس) میگیریم و مبداها رو توی یکی و مقاصد رو توی دیگری نگه میداریم. در نهایت ۲ تا لیست هم اندازه داریم. برای اینکه چک کنیم که این ۲ تا عین هم هستن یا نه، ساده‌ترین راه حل اینه که جفتشون رو مرتب (`sort`) کنیم و بینشون `==` بذاریم. ۲ تا لیست (یا وکتور) زمانی با همدیگه برابرن که اعضاشون نظیر به نظیر با هم برابر باشن.

پیچیدگی زمانی این راه حل از `O(nlogn)` ه. چون کاری که بیشترین زمان رو توی الگوریتم میگیره، مرتب کردنه که با همین پیچیدگی زمانی انجام میشه و وقتی الگوریتم از جمع چند تا کار انجام شده باشه، پیچیدگی زمانیش میشه پیچیدگی زمانی کاری که بیشتر از همه طول میکشه.

# G - Shell Sort
سوال در مورد ۲ تا استک (پشته یا `stack`)ه. استک اولی، استکیه که اول کار داریم و استک دوم، اونیه که میخوایم بهش برسیم. اما حق انجام یک نوع عملیات رو داریم فقط: میتونیم یکی از اعضای استک رو از میانه‌ی استک بیرون بکشیم و روی استک بذاریم. هرچندباری که بخوایم، میتونیم این‌کار رو بکنیم. حالا باید با کمترین تعداد ممکن از این نوع عملیات، استک اول رو تبدیل به استک دوم کنیم. چیزی که سوال میخواد، اون اعضایی که این عملیات‌ها رو روشون انجام می‌دیمه (به ترتیب انجام عملیات‌ها).

مثلا استک اول اینه:
```
2
1
3
```
{'fraction_non_alphanumeric': 0.05533596837944664, 'fraction_numerical': 0.010899508923224338, 'mean_word_length': 3.5914215012372837, 'pattern_counts': {'":': 0, '<': 18, '<?xml version=': 0, '>': 18, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 2, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'dir': 'git-commits-cleaned', 'id': '5412912', 'n_tokens_mistral': 15546, 'n_tokens_neox': 12669, 'n_words': 3308}