راهنمایی سؤالات مسابقهٔ نهایی الگوریتم کدکاپ ۷

سلام

امیدوارم از مسابقه‌ی نهایی الگوریتم کدکاپ ۷ لذت برده باشید. در این بلاگ راه‌حل‌های سؤالات این مسابقه را بررسی می‌کنیم.

قبل از پرداختن به راه‌حل سؤالات، از «امیرمحمد شاهرضایی»، «علیرضا کشاورز» و «علی شاه‌علی» بابت همراهی در طراحی و آماده‌سازی سؤالات، و همچنین از «علی شفیعی» و «سعید زمانی» بابت بررسی متن‌ها و راه‌حل سؤالات تشکر می‌کنم.

خوانا برای انسان

مسئله را به سه حالت تقسیم می‌کنیم:

حالت اول. اگر m بین 1 تا 1023 باشد، «عدد» نمایش برابر m و «یکا»ی آن برابر B است.

1 \leq m \leq 1023

پس نمایش ارائه‌شده در این حالت، «خوانا برای انسان» است.

حالت دوم. اگر m بین 1024 تا 1024^2-1 باشد، «عدد» نمایش برابر \lfloor\frac{m}{1024}\rfloor و «یکا»ی آن برابر KiB است.

1024 \leq m \leq 1024^2 \quad \Rightarrow \quad
\frac{1024}{1024} \leq \frac{m}{1024} \leq \frac{1024^2-1}{1024} \quad \Rightarrow \quad
1 \leq \lfloor\frac{m}{1024}\rfloor \leq 1023

پس نمایش ارائه‌شده در این حالت، «خوانا برای انسان» است.

حالت سوم. اگر m بین 1024^2 تا 10^9 باشد، «عدد» نمایش برابر \lfloor\frac{m}{1024^2}\rfloor و «یکا»ی آن برابر MiB است.

1024^2 \leq m \leq 10^9 \quad \Rightarrow \quad
\frac{1024}{1024} \leq \frac{m}{1024} \leq \frac{10^9}{1024} \quad \Rightarrow \quad
1 \leq \lfloor\frac{m}{1024}\rfloor \leq 953 \leq 1023

پس نمایش ارائه‌شده در این حالت نیز «خوانا برای انسان» است.

راه‌حل سی‌پلاس‌پلاس

#include <iostream>

using namespace std;

void solve()
{
	int m;
	cin >> m;
	if (m < 1024)
		cout << m << "B\n";
	else if (m < 1024 * 1024)
		cout << m / 1024 << "KiB\n";
	else
		cout << m / (1024 * 1024) << "MiB\n";
}

int main()
{
	int t;
	cin >> t;
	while (t--)
		solve();

	return 0;
}

راه‌حل پایتون

def solve():
	m = int(input())
	if m < 1024:
		print(str(m) + 'B')
	elif m < 1024 * 1024:
		print(str(m // 1024) + 'KiB')
	else:
		print(str(m // (1024 * 1024)) + 'MiB')

t = int(input())
for i in range(t):
	solve()

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

به‌ازای هر تست پاسخ سؤال از \mathcal{O}(1) محاسبه شد.

نقشه گز

مختصات تقاطع‌ها در «گز» به فرم (0, y) یا (x, 0) هستند. (x و y اعدادی صحیح‌‌اند.)

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

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

راه‌حل سی‌پلاس‌پلاس

#include <iostream>
#include <cmath>

using namespace std;

void solve()
{
    int x_1, y_1, x_2, y_2;
    cin >> x_1 >> y_1 >> x_2 >> y_2;

    long double ans;

    if (x_1 == x_2)
        ans = abs(y_1 - y_2);
    else if (y_1 == y_2)
        ans = abs(x_1 - x_2);
    else 
    {
        int r_1 = abs(x_1) + abs(y_1);
        int r_2 = abs(x_2) + abs(y_2);
        ans = 0.5 * M_PI * min(r_1, r_2) + abs(r_1 - r_2);
    }

    cout << fixed << ans << '\n';
}

int main()
{

    cout.precision(6);

    int t;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

راه‌حل پایتون

import math

def solve():
    x_1, y_1, x_2, y_2 = map(int, input().split())

    ans = 0.0
    if x_1 == x_2:
        ans = abs(y_1 - y_2)
    elif y_1 == y_2:
        ans = abs(x_1 - x_2)
    else:
        r_1 = abs(x_1) + abs(y_1);
        r_2 = abs(x_2) + abs(y_2);
        ans = 0.5 * math.pi * min(r_1, r_2) + abs(r_1 - r_2);

    print(f'{ans:.6f}')

t = int(input())
for i in range(t):
	solve()

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

به ازای هر تست پاسخ سؤال از \mathcal{O}(1) محاسبه شد.

رشته‌های باینری

فرض کنید یکی از رشته‌های دودویی به فرم s_1, s_2, \dots, s_m\, باشد که s_i \in {0, 1} است. از روی این رشته، رشته‌ی دودویی دیگر به نام t را به این صورت می‌سازیم:

t_i = \left\{
\begin{array}{lr}
s_i \oplus s_{i + 1} & i \lt m\\ 
s_i & i = m
\end{array}
\right.

می‌توان نشان داد دو رشته مثل s و s' با هم برابرند اگر و تنها اگر t و t' معادل آن‌ها برابر باشد.

هر عملیات، یعنی برعکس کردن یک پیشوند s، معادل تغییر برعکس کردن یک کاراکتر در t متناظر با آن است.

بنابراین مسئله به این صورت قابل تبدیل است: n رشته از 0 و 1 داریم و در هر عملیات می‌توانیم یک حرف از یکی از این رشته‌ها را تغییر دهیم. کمترین عملیات لازم برای اینکه همه‌ی این رشته‌ها را برابر کنیم چقدر است؟

برای حل مسئله‌ی بالا کافی است هر ستون را به‌صورت مستقل حل کنیم. یعنی برای هر ستون باتوجه به اینکه تعداد 0 و 1 چقدر است، تصمیم بگیریم کاراکتری که کمتر آمده کدام است و آن را به دیگری تبدیل کنیم.

راه‌حل سی‌پلاس‌پلاس

#include <iostream>

using namespace std;

const int maxn = 5e5;
int col[maxn];

void solve()
{
    int n, m;
    cin >> n >> m;

    for (int j = 0; j < m; j++)
        col[j] = 0;

    for (int i = 0; i < n; i++)
    {
        string s;
        cin >> s;

        for (int j = 0; j < m - 1; j++)
            if (s[j] != s[j + 1])
                col[j]++;

        if (s[m - 1] == '1')
            col[m - 1]++;
    }

    int ans = 0;
    for (int j = 0; j < m; j++)
        ans += min(col[j], n - col[j]);

    cout << ans << '\n';
}

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

    int t;
    cin >> t;
    while (t--)
        solve();

    return 0;
}

راه‌حل پایتون

def solve():
    n, m = map(int, input().split())
    col = [0 for j in range(m)]

    for i in range(n):
        s = input()

        for j in range(m - 1):
            if s[j] != s[j + 1]:
                col[j] += 1

        if s[m - 1] == '1':
            col[m - 1] += 1

    print(sum([min(col[j], n - col[j]) for j in range(m)]))

t = int(input())
for i in range(t):
	solve()

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

به ازای هر تست پاسخ سؤال از \mathcal{O}(nm) محاسبه شد.

هیتلر مخفی

می‌خواهیم مسئله را برای هر رأس به‌صورت جداگانه حل کنیم. می‌توانیم فرض کنیم که همواره هیتلر با تمام قدرت برای فتح ضعیف‌ترین کشور همسایه با مجموعه‌ی کشورهای فتح‌شده اقدام می‌کند و اگر نتواند ضعیف‌ترین کشور را فتح کند باید به قدرتش اضافه کند.

فرض کنید هیتلر زیرمجموعه‌ی S از کشورها را تا این لحظه فتح کرده و قدرت ارتش فعلی او برابر p است و به‌اندازه‌ی e مجبور به افزایش نیرو شده است. برای شروع می‌توانیم S = {v} و e = 0 و p = a_v در نظر بگیریم.

اگر کشورهای همسایه‌ی S (به‌جز خود اعضای S) را با N(S) نشان‌دهیم، در هر مرحله ضعیف‌ترین (ارتش) کشور عضو N(S) را به S اضافه می‌کنیم. فرض کنید توانایی این ارتش m باشد.

• اگر m از p + e کمتر بود، صرفاً مقدار p را به اندازه‌ی m افزایش می‌دهیم.
• اگر m بیشتر یا مساوی p + e بود، مقدار e را به‌اندازه‌ی m - (p + e) + 1 افزایش می‌دهیم (این کمترین نیروی لازم برای فتح این کشور است) و سپس مقدار p را به‌اندازه‌ی m افزایش می‌دهیم.

به این‌ترتیب اگر همواره N(S) را در یک داده‌ساختاری مثل set یا heap نگه‌داریم، می‌توانیم در هر مرحله از O(\log{n}) کشور مناسب را انتخاب و حذف کنیم و بعد از n - 1 مرحله کل دنیا را فتح کنیم. (با توجه به همبندی گراف این کار ممکن است.)

راه‌حل سی‌پلاس‌پلاس

#include <bits/stdc++.h>

using namespace std;

const int maxn = 1933;
vector <int> adj[maxn];
bool mark[maxn];
int a[maxn];


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

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

        adj[v].push_back(u);
        adj[u].push_back(v);
    }

    for (int v = 0; v < n; v++)
    {
        long long int p = a[v], e = 0;

        for (int i = 0; i < n; i++)
            mark[i] = false;
        mark[v] = true;

        set <pair <int,int> > ns;
        for (int u : adj[v])
            if (!mark[u])
                ns.insert(make_pair(a[u], u));

        for (int i = 0; i < n - 1; i++)
        {
            int u = (*ns.begin()).second;
            ns.erase(ns.begin());

            mark[u] = true;
            for (int w : adj[u])
                if (!mark[w])
                    ns.insert(make_pair(a[w], w));

            if (a[u] < p + e)
                p += a[u];
            else
            {
                e += a[u] - (p + e) + 1;
                p += a[u];
            }

        }

        cout << e << " \n"[v == n - 1];
    }

    return 0;
}

راه‌حل پایتون

import heapq


n, m = map(int, input().split())
a = list(map(int, input().split()))

adj = [list() for i in range(n)]
for i in range(m):
    u, v = map(int, input().split())
    adj[v - 1].append(u - 1)
    adj[u - 1].append(v - 1)


for v in range(n):
    p, e = a[v], 0;

    mark = [False for i in range(n)]
    mark[v] = True

    seen = [False for i in range(n)]
    seen[v] = True

    ns = list()
    for u in adj[v]:
        if (not mark[u]) and (not seen[u]):
            heapq.heappush(ns, (a[u], u))
            seen[u] = True

    for i in range(n - 1):
        u = heapq.heappop(ns)[1]

        mark[u] = True
        for w in adj[u]:
            if (not mark[w]) and (not seen[w]):
                heapq.heappush(ns, (a[w], w))
                seen[w] = True

        if a[u] < p + e:
            p += a[u]
        else:
            e += a[u] - (p + e) + 1
            p += a[u]

    if v == n - 1:
        print(e)
    else:
        print(e, end=' ')

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

مسئله برای هر رأس مثل v از مرتبه‌ی \mathcal{O}((n + m)\log{n}) حل شد. بنابراین مرتبه‌ی زمانی از \mathcal{O}(n(n + m)\log{n}) است.

حذف نابه‌جایی

فرض کنید dp[l][r] یعنی با عملیات تعریف‌شده در سؤال، به چند طریق می‌توان زیردنباله‌ی a_l, a_{l + 1}, \dots, a_r \, را کاملاً خالی کرد. (اگر نمی‌توان چنین کاری انجام داد تعداد حالات صفر است.)

برای به‌روزرسانی حذف‌شدن a_l و a_k در یک عملیات، به ازای kهای مختلف، حالت‌بندی می‌کنیم. مقدار این رابطه‌ی بازگشتی را از رابطه‌ی زیر محاسبه می‌کنیم:

dp[l][r] = \sum_{k = l + 1, a_k \lt a_l }^{r} \binom{\frac{r - l + 1}{2}}{\frac{k-l+1}{2}} \times dp[l + 1][k - 1] \times dp[k + 1][r]

پاسخ مسئله در dp[1][n] است.

راه‌حل سی‌پلاس‌پلاس

#include <iostream>

using namespace std;

const int maxn = 510, mod = 1000000007;
int a[maxn], c[maxn][maxn], dp[maxn][maxn];

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

	for (int i = 0; i < maxn; i++)
		c[i][0] = 1, c[i][i] = 1;

	for (int i = 0; i < maxn; i++)
		for (int j = 1; j < i; j++)
			c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod;
	
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) 
		cin >> a[i];
	
	for (int i = 1; i <= n + 1; i++) 
		dp[i][i - 1] = 1;

	for (int r = 1; r <= n; r++)
		for (int l = r - 1; l >= 1; l -= 2)
			for (int i = l + 1; i <= r; i += 2) 
				if (a[l - 1] > a[i - 1])
					dp[l][r] = (dp[l][r] + 1LL * ((1LL * dp[l + 1][i - 1] * dp[i + 1][r]) % mod) * c[(r - l + 1) / 2][(i - l + 1) / 2]) % mod;

	cout << dp[1][n] << endl;
	return 0;
}

راه‌حل پایتون

maxn = 510
mod = 1000000007

c = [[0] * maxn for i in range(maxn)]
dp = [[0] * maxn for i in range(maxn)]


for i in range(maxn):
	c[i][0] = 1
	c[i][i] = 1

for i in range(maxn):
	for j in range(1, i):
		c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % mod

n = int(input())
a = list(map(int, input().split()))

for i in range(1, n + 2):
	dp[i][i - 1] = 1;
	
for r in range(1, n + 1):
	for l in range(r - 1, 0, -2):
		for i in range(l + 1, r + 1, 2):
			if a[l - 1] > a[i - 1]:
				dp[l][r] = (dp[l][r] + dp[l + 1][i - 1] * dp[i + 1][r] * c[(r - l + 1) // 2][(i - l + 1) // 2]) % mod

print(dp[1][n])

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

برای محاسبه‌ی dp[l][r] نیاز به یک حلقه از \mathcal{O}(n) داریم. پس پیچیدگی زمانی کل راه‌حل از \mathcal{O}(n^3) است.

چهل و دو

ابتدا همه‌ی اعضای آرایه‌ی ورودی را منهای 42 می‌کنیم، سپس مسئله را به مسئله‌ی زیر تناظر می‌دهیم.

به دنباله‌ی a می‌گوییم «مولایی» اگر بتوان آن را با جمع‌کردن یک دنباله‌ی نزولی و یک دنباله‌ی صعودی با اعضای نامنفی ساخت.

یعنی دو دنباله‌ی D و I داشته باشیم به طوری که:

• D_i, I_i \geq 0
• D_{i - 1} \geq D_i (i > 1)
• I_{i - 1} \leq I_i (i > 1)
• a_i = D_i + I_i

اگر چنین دو دنباله‌ای موجود باشند، حتماً می‌توان آن‌ها را طوری ساخت که I_1 = 0 و D_n=0.

a_i - a_{i -1} = (I_i - I_{i - 1}) - (D_{i - 1} - D_i)

هر دو پرانتز در معادله‌ی بالا مقدار نامنفی دارند. داریم:

\sum_{i>1}{max(0, a_i - a_{i-1}) } \leq I_n - I_1

در نتیجه

\sum_{i>1}{max(0, a_i - a_{i-1}) } \leq a_n 

شرط بالا، شرط لازم و کافی برای «مولایی» بودن دنباله است.

کافی است I و D را طوری تعیین کنیم که:

• I_1=0, D_1 = a_1
• I_i = I_{i - 1} + max(0, a_i - a_{i - 1})
• D_i = D_{i - 1} + max(0, a_{i - 1} - a_i)

حالا باید بزرگ‌ترین زیرمجموعه را پیدا کنیم که یک دنباله‌ی «مولایی» تشکیل دهد.

حالا dp[i][j] را به این صورت تعریف می‌کنیم: کمترین مقداری که سیگما می‌تواند داشته باشد در صورتی که از بین i عضو اول آرایه j عضو را انتخاب کرده باشیم و عضو i هم انتخاب شده باشه.

dp[i][j] = \min_{k < i}{dp[k][j - 1] + max(0, a_i - a_k)}

اگر a_kهای بزرگ‌تر از a_i را جدا کنیم داریم.

dp[i][j] = min(a_i + \min_{k < i, a_k < a_i}{dp[k][j - 1] - a_k}, \min_{k < i, a_k \geq a_i}{dp[k][j - 1]})

کافی است بزرگترین j را پیدا کنیم که dp[i][j] \leq a_i

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

با استفاده از سگمنت‌تری یا فنویک می‌توانیم dp را در \mathcal{O}(n^2\log n) آپدیت کنیم.

سلف سرویس

گراف n + 2رأسیِ G را به روش زیر می‌سازیم و ادعا می‌کنیم بیشترین شارش از رأسِ «چشمه» (source) به رأسِ «چاه» (sink)، جواب مسئله خواهد بود.

رأس شماره‌ی 0 را به‌عنوان «چشمه» در نظر می‌گیریم. این رأس را با ظرفیت (capacity) بی‌نهایت و هزینه‌ی (cost) ۱ به رأس‌های 1 تا n + 1 وصل می‌کنیم.

به‌ازای رأس شماره‌ی i (از 1 تا n) یک یال با ظرفیت a_i و هزینه‌ی ۰ به رأس i + 1 وصل می‌کنیم.

همچنین به ازای هر رأس از 1 تا n + 1 یک یال به رأس شماره‌ی n + 2 با ظرفیت بی‌نهایت و هزینه‌ی ۰ می‌کشیم.

حال یک شارش از رأس 0 به رأس n + 2 با هزینه‌ی k، برابر پاسخ مسئله به ازای k بازه است. پس برای بیشینه‌کردن مجموع باید به دنبال بیشینه‌کردن شارش باشیم.

اگر برای این کار از الگوریتم‌های mincost-maxflow استفاده کنیم، با خطای محدودیت زمانی مواجه می‌شویم. اما می‌توانیم روند این الگوریتم را به‌صورت زیر معادل کنیم:

به ازای k = 1 پاسخ مسئله همان پیداکردن زیربازه با بیشترین مجموع است.

برای محاسبه‌ی جواب از حالت k به حالتk + 1 پاسخ مرحله‌ی قبل را در -1 ضرب می‌کنیم و مجدداً بازه با بیشترین جمع را پیدا کرده و اضافه می‌کنیم.

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

ممکن است بازه‌هایی که در روش بالا انتخاب می‌کنیم به طول تهی باشند. اگر تعداد اعداد نامنفی آرایه برابر p باشد، به ازای k \leq p پاسخ مسئله به‌درستی محاسبه می‌شود و بازه‌ها ناتهی انتخاب می‌شوند. اما برای k \gt p باید همه‌ی اعداد مثبت و بزرگ‌ترین اعداد منفی را به‌عنوان یک بازه انتخاب کنیم.

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

کل راه‌حل از مرتبه‌ی \mathcal{O}(n\log{n}) خواهد بود.