Educational Codeforces Round 165 （Rated for Div. 2 ABCDE 题）视频讲解

A. Two Friends

Problem Statement

Monocarp wants to throw a party. He has $n$ friends, and he wants to have at least $2$ of them at his party.

The $i$-th friend’s best friend is $p_i$. All $p_i$ are distinct, and for every $i\in [1,n]$, $p_i\ne i$.

Monocarp can send invitations to friends. The $i$-th friend comes to the party if both the $i$-th friend and the $p_i$-th friend receive an invitation (note that the $p_i$-th friend doesn’t have to actually come to the party). Each invitation is sent to exactly one of the friends.

For example, if $p=[3,1,2,5,4]$, and Monocarp sends invitations to the friends $[1,2,4,5]$, then the friends $[2,4,5]$ will come to the party. The friend $1$ won’t come since his best friend didn’t receive an invitation; the friend $3$ won’t come since he didn’t receive an invitation.

Calculate the minimum number of invitations Monocarp has to send so that at least $2$ friends come to the party.

Input

The first line contains one integer $t$ ($1\le t\le 5000$) — the number of test cases.

Each test case consists of two lines:

• the first line contains one integer $n$ ($2\le n\le 50$) — the number of friends;
• the second line contains $n$ integers $p_1,p_2,\dots ,p_n$ ($1\le p_i\le n$; $p_i\ne i$; all $p_i$ are distinct).

Output

Print one integer — the minimum number of invitations Monocarp has to send.

Example

Example

Note

In the first testcase, Monocarp can send invitations to friends $4$ and $5$. Both of them will come to the party since they are each other’s best friends, and both of them have invitations.

In the second testcase, Monocarp can send invitations to friends $1,2$ and $3$, for example. Then friends $1$ and $2$ will attend: friend $1$ and his best friend $2$ have invitations, friend $2$ and his best friend $3$ have invitations. Friend $3$ won’t attend since his friend $4$ doesn’t have an invitation. It’s impossible to send invitations to fewer than $3$ friends in such a way that at least $2$ come.

In the third testcase, Monocarp can send invitations to both friends $1$ and $2$, and both of them will attend.

Solution

具体见文后视频。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

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

	std::vector<int> a(n + 1);
	for (int i = 1; i <= n; i ++)
		cin >> a[i];
	for (int i = 1; i <= n; i ++)
		if (i == a[a[i]]) {
			cout << 2 << endl;
			return;
		}
	cout << 3 << endl;
}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int dt;
	
	cin >> dt;

	while (dt --)
		solve();

	return 0;
}

B. Shifts and Sorting

Problem Statement

Let’s define a cyclic shift of some string $s$ as a transformation from $s_1{s}_2\dots s_{n-1}{s}_n$ into $s_n{s}_1{s}_2\dots s_{n-1}$. In other words, you take one last character $s_n$ and place it before the first character while moving all other characters to the right.

You are given a binary string $s$ (a string consisting of only 0-s and/or 1-s).

In one operation, you can choose any substring $s_l{s}_{l+1}\dots s_r$ ($1\le l<r\le |s|$) and cyclically shift it. The cost of such operation is equal to $r-l+1$ (or the length of the chosen substring).

You can perform the given operation any number of times. What is the minimum total cost to make $s$ sorted in non-descending order?

Input

The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases.

The first and only line of each test case contains a binary string $s$ ($2\le |s|\le 2\cdot 10^5$; $s_i\in$ {0, 1}) — the string you need to sort.

Additional constraint on the input: the sum of lengths of strings over all test cases doesn’t exceed $2\cdot 10^5$.

Output

For each test case, print the single integer — the minimum total cost to make string sorted using operation above any number of times.

Example

Example

Note

In the first test case, you can choose the whole string and perform a cyclic shift: 10 $\to$ 01. The length of the substring is $2$, so the cost is $2$.

In the second test case, the string is already sorted, so you don’t need to perform any operations.

In the third test case, one of the optimal strategies is the next:

1. choose substring $[1,3]$: 11000 $\to$ 01100;
2. choose substring $[2,4]$: 01100 $\to$ 00110;
3. choose substring $[3,5]$: 00110 $\to$ 00011.

The total cost is $3+3+3=9$.

Solution

具体见文后视频。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

void solve() {
	string s;
	cin >> s;
	int n = s.size();
	s = ' ' + s;

	int tot = 0, res = 0;
	for (int i = 1; i <= n; i ++) 
		if (s[i] == '1')
			tot ++;
		else {
			if (!tot) continue;
			res += tot + 1;
		}

	cout << res << endl;
}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int dt;
	
	cin >> dt;

	while (dt --)
		solve();

	return 0;
}

C. Minimizing the Sum

Problem Statement

You are given an integer array $a$ of length $n$.

You can perform the following operation: choose an element of the array and replace it with any of its neighbor’s value.

For example, if $a=[3,1,2]$, you can get one of the arrays $[3,3,2]$, $[3,2,2]$ and $[1,1,2]$ using one operation, but not $[2,1,2$] or $[3,4,2]$.

Your task is to calculate the minimum possible total sum of the array if you can perform the aforementioned operation at most $k$ times.

Input

The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$ and $k$ ($1\le n\le 3\cdot 10^5$; $0\le k\le 10$).

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^9$).

Additional constraint on the input: the sum of $n$ over all test cases doesn’t exceed $3\cdot 10^5$.

Output

For each test case, print a single integer — the minimum possible total sum of the array if you can perform the aforementioned operation at most $k$ times.

Example

Note

In the first example, one of the possible sequences of operations is the following: $[3,1,2]\to [1,1,2$].

In the second example, you do not need to apply the operation.

In the third example, one of the possible sequences of operations is the following: $[2,2,1,3]\to [2,1,1,3]\to [2,1,1,1]$.

In the fourth example, one of the possible sequences of operations is the following: $[4,1,2,2,4,3]\to [1,1,2,2,4,3]\to [1,1,1,2,4,3]\to [1,1,1,2,2,3]$.

Solution

具体见文后视频。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 3e5 + 20;

int n, k;
int a[N], f[N][20];
int mn[N][20];

void build() {
	int m = log2(n) + 1;
	for (int j = 0; j < m; j ++)
		for (int i = 1; i <= n - (1ll << j) + 1; i ++)
			if (!j) mn[i][j] = a[i] - a[i - 1];
			else mn[i][j] = min(mn[i][j - 1], mn[i + (1ll << j - 1)][j - 1]);
}
int query(int l, int r) {
	int t = log2(r - l + 1);
	return min(mn[l][t], mn[r - (1ll << t) + 1][t]);
}

void solve() {
	cin >> n >> k;

	for (int i = 1; i <= n; i ++)
		cin >> a[i], a[i] += a[i - 1];

	for (int i = 0; i <= n; i ++)
		for (int j = 0; j <= k; j ++)
			f[i][j] = -1e16;
	build();
	f[0][k] = 0;
	for (int i = 1; i <= n; i ++)
		for (int t = 0; t <= k; t ++) {
			f[i][t] = f[i - 1][t];
			for (int j = max(1ll, i - k); j <= i; j ++) {
				if (t + (i - j) <= k)
					f[i][t] = max(f[i][t], f[j - 1][t + (i - j)] + a[i] - a[j - 1] - query(j, i) * (i - j + 1));
			}
		}

	int res = 0;
	for (int i = 0; i <= k; i ++)
		res = max(res, f[n][i]);
	cout << a[n] - res << endl;
	for (int i = 0; i <= n; i ++)
		a[i] = 0;

}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int dt;
	
	cin >> dt;

	while (dt --)
		solve();

	return 0;
}

D. Shop Game

Problem Statement

Alice and Bob are playing a game in the shop. There are $n$ items in the shop; each item has two parameters: $a_i$ (item price for Alice) and $b_i$ (item price for Bob).

Alice wants to choose a subset (possibly empty) of items and buy them. After that, Bob does the following:

• if Alice bought less than $k$ items, Bob can take all of them for free;
• otherwise, he will take $k$ items for free that Alice bought (Bob chooses which $k$ items it will be), and for the rest of the chosen items, Bob will buy them from Alice and pay $b_i$ for the $i$-th item.

Alice’s profit is equal to $\sum _{i\in S}{b}_i-\sum _{j\in T}{a}_j$, where $S$ is the set of items Bob buys from Alice, and $T$ is the set of items Alice buys from the shop. In other words, Alice’s profit is the difference between the amount Bob pays her and the amount she spends buying the items.

Alice wants to maximize her profit, Bob wants to minimize Alice’s profit. Your task is to calculate Alice’s profit if both Alice and Bob act optimally.

Input

The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases.

The first line of each test case contains two integers $n$ and $k$ ($1\le n\le 2\cdot 10^5$; $0\le k\le n$).

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^9$).

The third line contains $n$ integers $b_1,b_2,\dots ,b_n$ ($1\le b_i\le 10^9$).

Additional constraint on the input: the sum of $n$ over all test cases doesn’t exceed $2\cdot 10^5$.

Output

For each test case, print a single integer — Alice’s profit if both Alice and Bob act optimally.

Example

Example

Note

In the first test case, Alice should buy the $2$-nd item and sell it to Bob, so her profit is $2-1=1$.

In the second test case, Alice should buy the $1$-st, the $2$-nd and the $3$-rd item; then Bob takes the $1$-st item for free and pays for the $2$-nd and the $3$-rd item. Alice’s profit is $(3+2)-(1+2+1)=1$. Bob could take $2$-nd item for free instead; this does not change Alice’s profit. Bob won’t take the $3$-rd item for free, since this would lead to a profit of $2$.

Solution

具体见文后视频。

Code

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 2e5 + 10;

int n, k;
PII item[N], cpy[N];

void solve() {
	cin >> n >> k;

	for (int i = 1; i <= n; i ++)
		cin >> item[i].fi;
	for (int i = 1; i <= n; i ++)
		cin >> item[i].se, cpy[i] = item[i];

	if (!k) {
		int res = 0;
		for (int i = 1; i <= n; i ++)
			res += max(0ll, item[i].se - item[i].fi);
		cout << res << endl;
		return;
	}

	sort(item + 1, item + 1 + n, [&](PII a, PII b) {
		if (a.se == b.se) return a.fi > b.fi;
		return a.se < b.se;
	});
	
	int tot = 0, res = 0, sum = 0;
	for (int i = 1; i <= n; i ++)
		sum += max(0ll, item[i].se - item[i].fi);

	multiset<int> s;
	for (int i = n; i >= n - k + 1; i --) {
		s.insert(item[i].fi), tot += item[i].fi;
		sum -= max(0ll, item[i].se - item[i].fi);
	}
	
	for (int i = n - k; i >= 0; i --) {
		// cout << item[i].se << ":" << sum << " " << tot << "->" << sum - tot << endl;
		res = max(res, sum - tot);
		auto it = s.end();
		it --;
		if (*it > item[i].fi) {
			tot -= *it, s.erase(it), s.insert(item[i].fi), tot += item[i].fi;
		}
		sum -= max(0ll, item[i].se - item[i].fi);
	}

	cout << res << endl;
}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int dt;
	
	cin >> dt;

	while (dt --)
		solve();

	return 0;
}

E. Unique Array

Problem Statement

You are given an integer array $a$ of length $n$. A subarray of $a$ is one of its contiguous subsequences (i. e. an array $[a_l,a_{l+1},\dots ,a_r]$ for some integers $l$ and $r$ such that $1\le l<r\le n$). Let’s call a subarray unique if there is an integer that occurs exactly once in the subarray.

You can perform the following operation any number of times (possibly zero): choose an element of the array and replace it with any integer.

Your task is to calculate the minimum number of aforementioned operation in order for all the subarrays of the array $a$ to be unique.

Input

The first line contains a single integer $t$ ($1\le t\le 10^4$) — the number of test cases.

The first line of each test case contains a single integer $n$ ($1\le n\le 3\cdot 10^5$).

The second line contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le n$).

Additional constraint on the input: the sum of $n$ over all test cases doesn’t exceed $3\cdot 10^5$.

Output

For each test case, print a single integer — the minimum number of aforementioned operation in order for all the subarrays of the array $a$ to be unique.

Example

Note

In the second test case, you can replace the $1$-st and the $3$-rd element, for example, like this: $[3,4,1,4]$.

In the third test case, you can replace the $4$-th element, for example, like this: $[3,1,2,3,2]$.

Solution

具体见文后视频。

Code

#include <bits/stdc++.h>
#define fi first
#define se second

using namespace std;

typedef pair<int, int> PII;
typedef long long LL;

const int N = 3e5 + 10;

int n;
int a[N], l[N], r[N], p[N];
struct Segment {
	int l, r;
	int mn, len, lazy;
}tr[N << 2];
int q[N], hh, tt, f[N];

void pushup(int u) {
	tr[u].mn = min(tr[u << 1].mn, tr[u << 1 | 1].mn), tr[u].len = 0;
	if (tr[u << 1].mn == tr[u].mn) tr[u].len += tr[u << 1].len;
	if (tr[u << 1 | 1].mn == tr[u].mn) tr[u].len += tr[u << 1 | 1].len;
}

void pushdown(int u) {
	if (tr[u].lazy) {
		tr[u << 1].mn += tr[u].lazy, tr[u << 1].lazy += tr[u].lazy;
		tr[u << 1 | 1].mn += tr[u].lazy, tr[u << 1 | 1].lazy += tr[u].lazy;
		tr[u].lazy = 0;
	}
}

void build(int u, int l, int r) {
	tr[u] = {l, r}, tr[u].len = r - l + 1;
	if (l == r) return;
	int mid = l + r >> 1;
	build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}

void modify(int u, int l, int r, int d) {
	if (tr[u].l >= l && tr[u].r <= r) {
		tr[u].mn += d, tr[u].lazy += d;
		return;
	}
	pushdown(u);
	int mid = tr[u].l + tr[u].r >> 1;
	if (mid >= l) modify(u << 1, l, r, d);
	if (mid < r) modify(u << 1 | 1, l, r, d);
	pushup(u);
}

int query(int u, int l, int r) {
	if (tr[u].l >= l && tr[u].r <= r) {
		if (tr[u].mn > 0) return tr[u].r - tr[u].l + 1;
		return tr[u].r - tr[u].l + 1 - tr[u].len;
	}

	pushdown(u);
	int mid = tr[u].l + tr[u].r >> 1, res = 0;
	if (mid >= l) res += query(u << 1, l, r);
	if (mid < r) res += query(u << 1 | 1, l, r);
	return res;
}

void solve() {
	cin >> n;

	for (int i = 1; i <= n; i ++) p[i] = 0;
	for (int i = 1; i <= n; i ++)
		cin >> a[i], l[i] = p[a[i]] + 1, p[a[i]] = i;
	for (int i = 1; i <= n; i ++) p[i] = n + 1;
	for (int i = n; i >= 1; i --)
		r[i] = p[a[i]] - 1, p[a[i]] = i;
	// (l[i], i) -> (i, r[i])
	std::vector<array<int, 4>> opr;
	for (int i = 1; i <= n; i ++) {
		opr.push_back({i, l[i], i, 1});
		opr.push_back({r[i] + 1, l[i], i, -1});
	}
	sort(opr.begin(), opr.end());
	build(1, 1, n);

	q[0] = 0, q[ ++ tt] = 1, hh = 0, tt = 0, f[1] = 1;
	int lim = 0;
	for (int i = 1, j = 0; i <= n; i ++) {
		while (j < opr.size() && opr[j][0] == i) {
			modify(1, opr[j][1], opr[j][2], opr[j][3]);
			j ++;
		}
		int l = 1, r = i;
		while (l < r) {
			int mid = l + r + 1 >> 1;
			if (query(1, mid, i) == i - mid + 1) r = mid - 1;
			else l = mid;
		}
		if (query(1, 1, i) == i) p[i] = 0;
		else p[i] = l;
		lim = max(lim, p[i]);
		while (hh <= tt && q[hh] < lim) hh ++;
		f[i + 1] = f[q[hh]] + 1;
		while (hh <= tt && f[q[tt]] > f[i + 1]) tt --;
		q[ ++ tt] = i + 1;
	}
	
	int res = 2e9;
	for (int i = lim; i <= n; i ++)
		res = min(res, f[i]);
	cout << res << endl;
}

signed main() {
	cin.tie(0);
	cout.tie(0);
	ios::sync_with_stdio(0);

	int dt;
	
	cin >> dt;

	while (dt --)
		solve();

	return 0;
}

视频讲解

最后祝大家早日