خانه توسعه‌دهنده با کوئرا | توسعه‌دهنده مسابقات و رویدادها راه‌حل‌های مسابقه الگوریتمی Newbies 2017

راه‌حل‌های مسابقه الگوریتمی Newbies 2017

۲۹ بهمن ۱۴۰۱

زمان مطالعه: 11 دقیقه

511

همون طور که می‌دونید تصمیم گرفتیم مسابقات سال‌های گذشته Newbies رو به‌صورت آنلاین در کوئرا برگزار کنیم تا فرصتی برای تمرین و رقابت باشه. هفته‌ی پیش مسابقه‌ی الگوریتمی Newbies 2017 در کوئرا برگزار شد. این مسابقه در سال ۲۰۱۷ در دانشگاه شهید بهشتی با تلاش «محمد نصیری‌فر»، «محمدرضا محسنی»، «سامان خامسیان»، «نیما شیروانیان»، «احسان فرجی‌زاده» طراحی و برگزار شده بود.

راه‌حل‌های سؤالات این مسابقه در ادامه توضیح داده شدند. در صورتی که متوجه راه‌حلی نشدید، می‌تونید در بخش نظرات، سؤالات و ابهام‌های خودتون رو مطرح کنید. اگه راه‌حل دیگه‌ای برای سؤالات دارید، خوشحال می‌شیم که راه‌حلتون رو در بخش نظرات با ما و دوستانتون به اشتراک بذارید.

فهرست مطالب

A – Hens of the Sky

اگر $m>0$ باشد، ${245}^m$ عددی با یکان $5$ ایجاد می‌کند.
اگر $n$ فرد باشد، عدد نهایی دارای یکان $5$ ، درصورتی که زوج باشد، دارای یکان $0$ خواهد شد.

اگر $m=0$ شود. ${245}^m$ عددی با یکان $1$ تولید کرده و نتیجه‌ی نهایی به یکان $n$ بستگی پیدا خواهد کرد.
لذا در این قسمت تعیین‌کننده‌ یکان نهایی، یکان $n$ می‌شود.

پیچیدگی زمانی:

\mathcal{O}(1)

#include<bits/stdc++.h>
using namespace std;

int main()
{
	int t;
	cin >> t;
	while(t--)
	{
		int n, m;
		cin >> n >> m;
		if(m > 0)
		{
			if(n & 1)
				cout << 5 << endl;
			else
				cout << 0 << endl;
			continue;
		}
		cout << (n % 10) << endl;
	}
}

B – The Breadwinner

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

از آنجایی که بحث، محاسبه‌ی کوتاه‌ترین مسیر بین تمامی گره‌ها و گره اولیه (شروع) می‌باشد بهترین راه استفاده از دایجسترا است.

در این روش آرایه‌ای به نام $dist$ درنظر می‌گیریم که $dis[i]$ بیانگر مسیر با کمترین هزینه از گره شروع تا نقطه‌ی $i$ است.

پیچیدگی زمانی:

\mathcal{O}( n + m \log n )

#include<bits/stdc++.h>
using namespace std;

int n, m, t;
int v, u, w;
long long ans;
vector<int> price, dist;
vector<vector<pair<int, int> > > graph;

#define INF 1e9

void init()
{
	ans = 0;

	dist.clear();
	dist.resize(n + 1);

	price.clear();
	price.resize(n + 1);

	graph.clear();
	graph.resize(n + 1);
}

class comparator
{
	public:

		bool operator()(pair<int, int> &a, pair<int, int> &b)
		{
			return a.second > b.second;
		}
};

long long dijkstra()
{
	for (int i = 0; i <= n; i++)
	{
		dist[i] = INF;
	}

	dist[0] = 0;

	priority_queue<pair<int, int>, vector<pair<int, int>>, comparator> pq;

	pq.push({ 0, dist[0] });

	while (!pq.empty())
	{
		u = pq.top().first;
		
		pq.pop();

		for (int i = 0; i < graph[u].size(); i++)
		{
			v = graph[u][i].first;
			w = graph[u][i].second;

			if (dist[u] + w < dist[v])
			{
				dist[v] = w + dist[u];

				pq.push({ v, dist[v] });
			}
		}
	}

	for (int i = 1; i <= n; i++)
	{
		if (dist[i] != INF && price[i] >= dist[i] * 2) ans = ans + (long long)price[i];
	}

	return ans;
}

int main()
{
	cin >> t;

	while (t--)
	{
		cin >> n >> m;

		init();

		for (int i = 1; i <= n; i++)
		{
			cin >> price[i];
		}

		for (int i = 0; i < m; i++)
		{
			cin >> v >> u >> w;

			graph[u].push_back({ v, w });
			graph[v].push_back({ u, w });
		}

		cout << dijkstra() << endl;
	}
}

C – Expensive Spray

اگر تمامی مکعب‌ها را به‌صورت عمودی روی هم قرار دهیم، به‌گونه‌ای که تنها یک ستون ایجاد کنند، میزان استفاده از اسپری کمترین مقدار خواهد شد.

هر مکعبی که به ستون اضافه می‌شود با معکب زیرین خود تماس داشته و نیازی به محاسبه‌ی رنگ برای وجه پایینی نیست.

اولین معکب هم با زمین درتماس است که بازهم نیازی به رنگ آن وجه تماس پیدا کرده با زمین نخواهد داشت.

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

sum += (max\times max)

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

sum += (d\times d \times 4)

پیچیدگی زمانی:

\mathcal{O}(n)

#include<bits/stdc++.h>

using namespace std;

int main()
{
    int t;
    cin >> t;

    while(t--)
    {
        long long max = 0;
        long long sum = 0;
        long long n;
        cin >> n;
        while(n--)
        {
            long long d;
            cin >> d;
            if (d > max)
                max = d;
            sum += d * d * 4;
        }

        sum += max * max;
        cout << sum << "\n";
    }
    return 0;
}

D – Restoring a Tree

طبق گفته‌ی سؤال فرزندان یک گره در بین آن قرار می‌گیرند. بنابراین می‌توان نتیجه گرفت اگر دو گره پشت سرهم تکرار شوند، به این معناست که گره انتهایی هستند و فرزندی ندارند. لذا برای حل، مقادیر آرایه را در یک استک می‌ریزیم و یک آرایه با نام $Hight$ برای ذخیره ارتفاع یک گره درنظر می‌گیریم.

اگر گره‌ای که می‌خواهیم در استک قرار بدهیم با عضو بالای استک یکسان است، گره بالای استک را از آن بیرون می‌آوریم.
در غیراینصورت این گره فرزندی برای گره‌ای که بالای استک قرار دارد محسوب می‌شود. پس یکی به ارتفاع آن اضافه می‌کنیم.

در نهایت مقدار بیشینه ارتفاع را به‌عنوان خروجی چاپ می‌کنیم.

پیچیدگی زمانی:

\mathcal{O}(n)

#include <bits/stdc++.h>
using namespace std;

int Hight[200005];
stack <int> s;

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        memset(Hight, 0, sizeof Hight);
        int n;
        cin >> n;
        int temp;
        cin >> temp;
        s.push(temp);
        
        for(int i=1;i<2*n;i++)
        {
            cin >> temp;
            if(s.top() == temp)
                s.pop();
            else
            {
                Hight[s.top()]++;
                s.push(temp);
            }
        }
        for(int i=2;i<n+1;i++)
            Hight[i]++;
        cout << *max_element(Hight + 1, Hight + n + 1) << endl;
    }
}

E – Dormitory Nights

می‌توان از ساختمان داده‌ی map برای ذخیره‌سازی مقدار پولی که هرنفر باید پرداخت کند یا بگیرد، متناسب با نامش استفاده کنیم. (یک مپ از اسم به پول هر فرد).

برای این‌کار پس از دریافت هر خط detail در هر تست‌کیس، پول فرد اول که آن شب پرداخت کرده (buyer) را به مقدار cost تومان اضافه می‌کنیم.

money[buyer] += cost_total

مقدار پول پرداختی در آن شب را به تعداد افراد تقسیم کرده و از حساب هرکدام از افراد که با نام temp در کد نشان‌داده شده‌اند، کم می‌کنیم.

cost = cost_total / n
money[temp] -= cost

در نهایت کسانی که مقدار پولشان منفی شده است، بدهکار (Debtors) و کسانی که مقدار پولشان مثبت است، بستانکار(Creditors) محسوب شده و مقدار پولشان همراه با اسم‌شان چاپ خواهد شد.

در تمامی این مراحل درستی اسم‌ هر فرد و نحوه‌ی چاپ آن با استفاده از توابع make-valid و printName بررسی و چاپ می‌شوند.

پیچیدگی زمانی:

\mathcal{O}(T \times L \times n+ T \times n)

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define L(s) (int)((s).size())

void printName(const string & name) {
    cout << char(toupper(name[0]));
    for (int i = 1; i < L(name); i++)
        cout << name[i];
}

void make_valid(string & name) {
    for (int i = 0; i < L(name); i++)
        if (isalpha(name[i]) && isupper(name[i]))
            name[i] = tolower(name[i]);
}
map<string, int> money;
void end_testcase() {
    static int tc = 0;
    cout << "Case #" << ++tc << ":" << endl;
    
    vector<pair<string, int> > dept, cred;

    for (map<string,int>::iterator it = money.begin(); it != money.end(); it++){
        if (it->second > 0)
            cred.push_back(*it);
        else if (it->second < 0)
            dept.push_back(*it);
    }
    
    cout << "Debtors:" << endl;
    for (int i = 0; i < L(dept); i++) {
        printName(dept[i].first);
        cout << " owes " << -dept[i].second << " Tomans." << endl;
    }
    
    cout << "Creditors:" << endl;
    for (int i = 0; i < L(cred); i++) {
        printName(cred[i].first);
        cout << " paid " << cred[i].second << " Tomans." << endl;
    }
    money.clear();
}

int main () {
    int Tc, l;
    cin >> Tc;
    while (Tc-- && cin >> l) {
        while (l--) {
            string buyer, temp;
            int cost, n;
            cin >> buyer >> cost >> n;
            make_valid(buyer);
            money[buyer] += cost;
            cost /= n;
            
            while (n-- && cin >> temp) {
                make_valid(temp);
                money[temp] -= cost;
            }
        }
        end_testcase();
    }
    return 0;

}

F – Khaltoor

برای اینکه بتوانیم بیشترین تعداد آهنگ را در CD جا بدهیم، کافیست آهنگ‌هایی را انتخاب کنیم که کوچک‌ترین زمان ممکن را دارند. لذا برای حل این سؤال کافیست آهنگ‌ها را بر حسب زمان از کوچک به بزرگ مرتب کرده و تا جایی که فضای CD اجازه می‌دهد، از ابتدا آهنگ‌های مرتب‌شده آن‌ها را انتخاب نماییم.

پیچیدگی زمانی:

\mathcal{O}(n\log n)

#include <bits/stdc++.h>
using namespace std;

int main()
{
	int n, m, t, test = 1;
	cin >> t;
	while (t--){
		int ans = 0;
		cin >> n >> m;

		long long sum = 0;
		vector<long long> music(n);

		for (int i = 0; i < n; i++){
			cin >> music[i];
		}

		sort(music.begin(), music.end());

		for (int i = 0; i < n; i++){
			if (sum + music[i] <= m){
				sum += music[i];
				ans++;
			}
		}
		
		cout << ans << endl;
	}
}

G – Grid Filter

هر مثلث سه ارتفاع دارد، هر ارتفاع اندازه کوچکتری نسب به اضلاعی که برای آن وتر مسحوب می‌شود دارد. به عبارتی به جز ضلعی که ارتفاع بر آن فرود می‌آید، طبق فیثاغورس می‌توان نتیجه گرفت که دو ضلع دیگر از ارتفاع بزرگ‌تر هستند. (توان دوم ارتفاع به علاوه توان دوم قسمتی از ضلعی که ارتفاع برآن عمود می‌آید برابر با توان دوم وتر می‌کند که این حاکی از بزرگتر بودن این مقدار از ارتفاع است).

پس لازم است علاوه بر اضلاع، ارتفاع‌ها را نیز پیدا کرده و کوچکترین آن‌ها را به‌عنوان معیاری برای رد شدن بیسکویت از توری درنظر بگیریم. (یعنی اگر با این ارتفاع رد نشود با هیچ شکل ورود دیگری نمی‌تواند از توری عبور کند).

در ورودی اضلاع هر مثلث به ما داده می‌شود با استفاده از قضیه هرون مساحت را محاسبه کرده و تمامی ارتفاع‌ها را به نام‌های $h_c, h_b, h_a$ محاسبه می‌کنیم.

قضیه هرون:
با داشتن سه ضلع با نا‌م‌های $c, b, a$ خواهیم داشت:

p=\frac {a+b+c}{2} \\ \\ S= \sqrt{p\times (p-a) \times (p-b) \times (p-c)}

با این روش مساحت را محاسبه کرده و با داشتن ضلعی که ارتفاع برا آن فرود می‌آید, $h_c, h_b, h_a$ را محاسبه می‌کنیم. مینیمم مقدار آن را در آرایه‌ای با نام minH می‌ریزیم، در نهایت یکی از این ارتفاع‌ها معیاری برای توری ما درنظر گرفته خواهد شد.

چگونه بفهمیم کدام مقدار minH معیار ما باشد؟

طبق خواسته سؤال باید $P-E$ یا $P+E$ درصد بیسکویت‌ها اجازه عبور داشته باشند. مشخص است که اگر ارتفاع‌ها را از کوچک به بزرگ مرتب کنیم و برای مثال minH[k] را به‌عنوان معیار توری انتخاب کنیم، $k-1$ تای دیگر هم از این توری عبور خواهد کرد.

یعنی درصد عبوری توری به عبارت زیر خواهد بود:

percentage=\frac {k}{n}

هر بار بررسی می‌کنیم، اگر این درصد با محدوده‌ی سؤال مطابقت داشت، minH[k] به‌عنوان معیار معرفی خواهد شد.
اگر تا $n$ پیش رفتیم ولی مقدار موردنظر در محدوده قرار نگرفت، بدین معناست که توری با هیچ معیاری بیسکویت با درصد خواسته شده سؤال را نگه نمی‌دارد، بنابراین IMPOSSIBLE را چاپ خواهیم کرد.

نکته‌ای درباره تابع cmp :
برای مقایسه دو ورودی از EPS که مقدار کوچکی‌است استفاده شده، دلیل استفاده متغیر double است که اعداد با اعشار را تا دقت مشخصی ذخیره می‌کند.

به‌طور فرضی در نظر بگیرید یک متغیر سه رقم اعشار را ذخیره می‌کند، پس دو عدد $3.21456$ و $3.21487$ را برابر درنظر می‌گیرید. برای جلوگیری از چنین اتفاقی درحالی که دو عدد یکسان نیستند، از یک مقدار کوچک EPS برای نمایان‌تر شدن اختلاف استفاده می‌کنیم.

پیچیدگی زمانی:

\mathcal{O}(T \times n)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

#define _ << " - " <<

#define MAX 100010

#define EPS 1e-9
#define INF 1e10

int n, p, e;

double minH[MAX];


int cmp(double a, double b) {
    if (a < b - EPS) return -1;
    if (a > b + EPS) return +1;
    return 0;
}

double area(double a, double b, double c) {
    double s = (a + b + c) / 2;

    return sqrt(s * (s - a) * (s - b) * (s - c));
}

int main() {
    ios_base::sync_with_stdio(0);cin.tie(0);

    int tc; cin >> tc;

    while (tc-- && cin >> n >> p >> e) {
        for (int i = 0; i < n; i++) {
            double a, b, c;
            cin >> a >> b >> c;
            double s = area(a, b, c);
            double ha = s / a * 2.0;
            double hb = s / b * 2.0;
            double hc = s / c * 2.0;
            minH[i] = min(ha, min(hb, hc));
        }

        sort(minH, minH + n);
        reverse(minH, minH + n);

        double minP = (p - e) / 100.0;
        double maxP = (p + e) / 100.0;

        double ans = INF;

        for (int i = 0; i < n; i++) {
            double per = double(i + 1) / double(n);

            if (cmp(per, minP) >= 0 && cmp(per, maxP) <= 0) {
                if (i == n-1) {
                    ans = 0;
                }
                else if (cmp(minH[i], minH[i+1]) != 0) {
                    ans = minH[i+1];
                }
            }
        }

        if (ans == INF)
            cout << "IMPOSSIBLE" << endl;
        else
            cout << fixed << setprecision(2) << ans << endl;
    }
    return 0;
}

H – Revenge of the Roosters

این سؤال شباهتی به سؤال معروف کوله‌پشتی در مسائل dp دارد.

در این سؤال ابتدا یک آرایه دوبعدی dp درنظرمی‌گیریم که بعد اول آن rem که بیانگر میزان مجاز اضافه کردن نمره‌ است و بعد دوم بیانگر تعداد نمراتی که وجود دارند.

لازم به ذکر است بعد دوم بیانگر تعداد افراد انتخابی برای اضافه کردن نمره نیست، مثلاً dp[16][8] به معنای این نیست که به $8$ نفر نمره اضافه شده است، بلکه تعداد تمامی اعضای احتمالی را نشان‌ می‌دهد.

به‌طور کلی dp[rem][idx] بیانگر بیشترین میزان شادی بدست آمده از افراد انتخابی از بین idx نفر برای پاس شدن، با سقف مجاز اضافه کردن نمره به اندازه‌ی rem است.

با توضیحات ذکر شده بدیهی است که جواب نهایی ما در dp[k][n] قرار دارد.

برای حل این سؤال ابتدا نمراتی که زیر $10$ هستند را به همراه میزان happiness آن‌ها ذخیره می‌کنیم.

سپس از انتها شروع می‌کنیم $idx=n$ ، بعد از برخورد به هر نمره‌ای $grades[idx]$ دو حالت انتخاب خواهیم داشت:

نمره را به $10$ برسانیم، در اینصورت به میزان خوشحالی happiness[idx] اضافه شده و میزان مجاز $k$ به اندازه‌ی $10-grades[idx]$ کم می‌شود.
تصمیم بگیریم این تغییر نمره را اعمال نکنیم، در اینصورت به میزان خوشحالی چیزی اضافه نخواهد شد و از مقدار $k$ نیز عددی کم نخواهد شد.

پس از هریکی از تصمیات بعدی سراغ $grades[idx-1]$ می‌رویم و بازهم با دو انتخاب بالا مواجه می‌شویم. تا زمانی این‌کار را ادامه می‌دهیم که یکی از این دوحالت رخ دهد:

به انتهای اعضا برسیم $idx=1$ .
مقدار $k$ به انتها برسد.

پیچیدگی زمانی:

\mathcal{O}(n \times k)

#include <bits/stdc++.h>

typedef long long ll;
using namespace std;
#define L(a) (int)((a).size())
const int INF32 = (int)1e9;

vector<int> grades, happiness;
int a[105];
int h[105];
int dp[2005][105];

void init()
{
    grades.clear();
    happiness.clear();
    memset(dp, -1, sizeof dp);
}

int solve(int rem, int idx)
{
    if(rem < 0)
        return -INF32;
    if(idx < 0)
        return 0;
    if(dp[rem][idx] != -1)
        return dp[rem][idx];
    return dp[rem][idx] = max(solve(rem, idx - 1), solve(rem - (10 - grades[idx]), idx - 1) + happiness[idx]);
}

int main()
{
    int t;
    cin >> t;
    while(t--)
    {
        init();
        int n, k;
        cin >> n >> k;
        for(int i=0;i<n;i++)
            cin >> a[i];
        for(int i=0;i<n;i++)
            cin >> h[i];
        for(int i=0;i<n;i++)
        {
            if(a[i] < 10)
            {
                grades.push_back(a[i]);
                happiness.push_back(h[i]);
            }
        }
        k = min(k, 20 * L(grades)); // worst case, all grades are 0 and we change the to 20
        cout << solve(k, L(grades) - 1) << endl;
    }
}

I – Lightning Strike

خواسته‌های سؤال را می‌توانیم با ساختمان داده‌ی segment tree به‌صورت زیر پیاده‌سازی کنیم. در هر رأس از درخت، ضرب اعداد زیربازه‌ی مورد نظر را نگه‌داری می‌کنیم.

پیچیدگی زمانی:

\mathcal{O}((n + m.\log{n})\log{k})

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1e6 + 100, mod = 1e9 + 7;
int n, a[maxn], seg[4 * maxn], lzy[maxn];

int power(int bas, int exp)
{
    if (exp == 0)
        return 1;
    int res = power(bas, exp >> 1);
    res = (1LL * res * res) % mod;
    if (exp & 1)
        res = (1LL * res * bas) % mod;
    return res;
}

void relax(int id)
{
    lzy[id * 2 + 0] = (1LL * lzy[id * 2 + 0] * lzy[id]) % (mod - 1);
    lzy[id * 2 + 1] = (1LL * lzy[id * 2 + 1] * lzy[id]) % (mod - 1);
    seg[id * 2 + 0] = power(seg[id * 2 + 0], lzy[id]);
    seg[id * 2 + 1] = power(seg[id * 2 + 1], lzy[id]);
    lzy[id] = 1;
}

void build(int L = 0, int R = n, int id = 1)
{
    if (L == R - 1)
    {
        seg[id] = a[L];
        lzy[id] = 1;
        return;
    }

    int mid = (L + R) >> 1;
    
    build(L, mid, id * 2 + 0);
    build(mid, R, id * 2 + 1);

    seg[id] = (1LL * seg[id * 2 + 0] * seg[id * 2 + 1]) % mod;
    lzy[id] = 1;
}

void modify(int l, int r, int k, int L = 0, int R = n, int id = 1)
{
    if (l == L && r == R)
    {
        seg[id] = power(seg[id], k);
        lzy[id] = (1LL * lzy[id] * k) % (mod - 1);
        return;
    }
    
    if (lzy[id] > 1)
        relax(id);

    int mid = (L + R) >> 1;
    if (l < mid)
        modify(l, min(mid, r), k, L, mid, id * 2 + 0);
    if (r > mid)
        modify(max(l, mid), r, k, mid, R, id * 2 + 1);

    seg[id] = (1LL * seg[id * 2 + 0] * seg[id * 2 + 1]) % mod;
}

int ask(int l, int r, int L = 0, int R = n, int id = 1)
{
    if (l == L && r == R)
        return seg[id];

    if (lzy[id] > 1)
        relax(id);
    
    int mid = (L + R) >> 1, res = 1;
    if (l < mid)
        res = (1LL * res * ask(l, min(mid, r), L, mid, id * 2 + 0)) % mod;
    if (r > mid)
        res = (1LL * res * ask(max(l, mid), r, mid, R, id * 2 + 1)) % mod;

    return res;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(0);
    
    int m;
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> a[i];

    build();

    for (int i = 0; i < m; i++)
    {
        int t;
        cin >> t;
        if (t == 1)
        {
            int l, r, k;
            cin >> l >> r >> k;
            l--;
            modify(l, r, k);
        }
        else
        {
            int l, r;
            cin >> l >> r;
            l--;
            cout << ask(l, r) << '\n';
        }
    }
    return 0;
}

J – Game of Permutations

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

برای مثال در دو آرایه‌ی $3,4,2,1,6,5$ و $1,4,3,2,5,6$ ، این دنباله برابر با $4,2,5$ می‌باشد.

برای حل آن از الگوریتم LIS یا Longest Increasing Subsequence استفاده می‌کنیم. برای خواندن بیشتر در رابطه با این الگوریتم می‌توانید به این لینک مراجعه بفرمایید.

پیچیدگی زمانی:

\mathcal{O}(T \times N \times \log{N})

#include <bits/stdc++.h>

typedef long long ll;
const int mx =100005;

using namespace std;

int a[mx], b[mx], reva[mx], tail[mx], d[mx];

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int t;
    cin >> t;
    while(t--)
    {
        int n;
        cin >> n;
        for(int i=0;i<n;i++)
        {
            cin >> a[i];
            reva[--a[i]] = i;
        }
        for(int i=0;i<n;i++)
        {
            cin >> b[i];
            b[i]--;
        }
        for(int i=0;i<n;i++)
            d[i] = reva[b[i]];
        tail[0] = d[0];
        int len = 1;
        for(int i=0;i<n;i++)
        {
            if(d[i] > tail[len - 1])
                tail[len++] = d[i];
            else if(d[i] < tail[0])
                tail[0] = d[i];
            else
                tail[lower_bound(tail, tail + len, d[i]) - tail] = d[i];
        }
        cout << 2 * n - 2 * len << endl;
    }
}

آموزش برنامه نویسی با کوئرا کالج