Codeforces Round 953 (Div. 2 ABCDEF题) 视频讲解

A. Alice and Books

Problem Statement

Alice has $n$ books. The $1$-st book contains $a_1$ pages, the $2$-nd book contains $a_2$ pages, $\dots$, the $n$-th book contains $a_n$ pages. Alice does the following:

• She divides all the books into two non-empty piles. Thus, each book ends up in exactly one of the two piles.
• Alice reads one book with the highest number in each pile.

Alice loves reading very much. Help her find the maximum total number of pages she can read by dividing the books into two piles.

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 500$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains a single integer $n$ ($2\le n\le 100$) — the number of books Alice has.

The second line of each test case contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^9$) — the number of pages in each book.

Output

For each test case, output a single integer — the maximum number of pages Alice can read.

Example

Example

input
5
2
1 1
4
2 3 3 1
5
2 2 3 2 2
2
10 3
3
1 2 3

output
2
4
5
13
5

Note

In the first test case, Alice can put book number $1$ in the first pile, and book number $2$ in the second pile. Then she will read $a_1+a_2=1+1=2$ pages.

In the second test case, Alice can put books with numbers $2$ and $3$ in the first pile, and books with numbers $1$ and $4$ in the second pile. Then she will read the book with the highest number $3$ from the first pile, and the book with the highest number $4$ from the second pile. Then she will read $a_3+a_4=3+1=4$ pages.

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 = 1e2 + 10;

int n;
int a[N];

void solve() {
	cin >> n;
	int mx = 0;
	for (int i = 1; i <= n; i ++)
		cin >> a[i];
	for (int i = 1; i < n; i ++)
		mx = max(mx, a[i]);

	cout << mx + a[n] << endl;
}

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

	int dt;
	
	cin >> dt;

	while (dt --)
		solve();

	return 0;
}

---

B. New Bakery

Problem Statement

Bob decided to open a bakery. On the opening day, he baked $n$ buns that he can sell. The usual price of a bun is $a$ coins, but to attract customers, Bob organized the following promotion:

• Bob chooses some integer $k$ ($0\le k\le \min (n,b)$).
• Bob sells the first $k$ buns at a modified price. In this case, the price of the $i$-th ($1\le i\le k$) sold bun is $(b-i+1)$ coins.
• The remaining $(n-k)$ buns are sold at $a$ coins each.

Note that $k$ can be equal to $0$. In this case, Bob will sell all the buns at $a$ coins each.

Help Bob determine the maximum profit he can obtain by selling all $n$ buns.

Input

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

The only line of each test case contains three integers $n$, $a$, and $b$ ($1\le n,a,b\le 10^9$) — the number of buns, the usual price of a bun, and the price of the first bun to be sold at a modified price.

Output

For each test case, output a single integer — the maximum profit that Bob can obtain.

Example

Example

input
7
4 4 5
5 5 9
10 10 5
5 5 11
1000000000 1000000000 1000000000
1000000000 1000000000 1
1000 1 1000

output
17
35
100
45
1000000000000000000
1000000000000000000
500500

Note

In the first test case, it is optimal for Bob to choose $k=1$. Then he will sell one bun for $5$ coins, and three buns at the usual price for $4$ coins each. Then the profit will be $5+4+4+4=17$ coins.

In the second test case, it is optimal for Bob to choose $k=5$. Then he will sell all the buns at the modified price and obtain a profit of $9+8+7+6+5=35$ coins.

In the third test case, it is optimal for Bob to choose $k=0$. Then he will sell all the buns at the usual price and obtain a profit of $10\cdot 10=100$ coins.

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, a, b;
	cin >> n >> a >> b;
	int k1 = max(min(b - a, n), 0ll), k2 = max(min(b - a + 1, n), 0ll);
	cout << max((2 * b - k1 + 1) * k1 / 2 + (n - k1) * a, (2 * b - k2 + 1) * k2 / 2 + (n - k2) * a) << endl;
}

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

	int dt;
	
	cin >> dt;

	while (dt --)
		solve();

	return 0;
}

---

C. Manhattan Permutations

Problem Statement

Let’s call the Manhattan value of a permutation${}^{†}$ $p$ the value of the expression $|p_1-1|+|p_2-2|+\dots +|p_n-n|$.

For example, for the permutation $[1,2,3]$, the Manhattan value is $|1-1|+|2-2|+|3-3|=0$, and for the permutation $[3,1,2]$, the Manhattan value is $|3-1|+|1-2|+|2-3|=2+1+1=4$.

You are given integers $n$ and $k$. Find a permutation $p$ of length $n$ such that its Manhattan value is equal to $k$, or determine that no such permutation exists.

${}^{†}$A permutation of length $n$ is an array consisting of $n$ distinct integers from $1$ to $n$ in arbitrary order. For example, $[2,3,1,5,4]$ is a permutation, but $[1,2,2]$ is not a permutation ($2$ appears twice in the array), and $[1,3,4]$ is also not a permutation ($n=3$ but there is $4$ in the array).

Input

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

The only line of each test case contains two integers $n$ and $k$ ($1\le n\le 2\cdot 10^5,0\le k\le 10^{12}$) — the length of the permutation and the required Manhattan value.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

Output

For each test case, if there is no suitable permutation, output “No”. Otherwise, in the first line, output “Yes”, and in the second line, output $n$ distinct integers $p_1,p_2,\dots ,p_n$ ($1\le p_i\le n$) — a suitable permutation.

If there are multiple solutions, output any of them.

You can output the answer in any case (for example, the strings “yEs”, “yes”, “Yes”, and “YES” will be recognized as a positive answer).

Example

input
8
3 4
4 5
7 0
1 1000000000000
8 14
112 777
5 12
5 2

output
Yes
3 1 2
No
Yes
1 2 3 4 5 6 7
No
Yes
8 2 3 4 5 6 1 7
No
Yes
5 4 3 1 2
Yes
2 1 3 4 5

Note

In the first test case, the permutation $[3,1,2]$ is suitable, its Manhattan value is $|3-1|+|1-2|+|2-3|=2+1+1=4$.

In the second test case, it can be proven that there is no permutation of length $4$ with a Manhattan value of $5$.

In the third test case, the permutation $[1,2,3,4,5,6,7]$ is suitable, its Manhattan value is $|1-1|+|2-2|+|3-3|+|4-4|+|5-5|+|6-6|+|7-7|=0$.

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, k;
	cin >> n >> k;

	if (n * n / 2 < k || k & 1) {
		cout << "No" << endl;
		return;
	}
	cout << "Yes" << endl;
	std::vector<int> p(n + 1);
	int cnt = (n * n / 2 - k) / ((n + 1 >> 1) * 2), pos = ((n * n / 2 - k) % ((n + 1 >> 1) * 2)) / 2;
	for (int i = 1; i <= cnt; i ++)
		p[i] = i;
	for (int i = cnt + 1, j = n / 2 + 1; i <= cnt + (n + 1 >> 1); i ++, j ++)
		p[i] = j;
	for (int i = cnt + (n + 1 >> 1) + 1, j = cnt + 1; i <= n; i ++, j ++)
		p[i] = j;
	for (int i = cnt + (n + 1 >> 1) + 1, j = pos; j; j --, i --)
		swap(p[i], p[i - 1]);
	for (int i = 1; i <= n; i ++)
		cout << p[i] << " ";
	cout << endl;
}

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

	int dt;
	
	cin >> dt;

	while (dt --)
		solve();

	return 0;
}

---

D. Elections

Problem Statement

Elections are taking place in Berland. There are $n$ candidates participating in the elections, numbered from $1$ to $n$. The $i$-th candidate has $a_i$ fans who will vote for him. Additionally, there are $c$ people who are undecided about their favorite candidate, let’s call them undecided. Undecided people will vote for the candidate with the lowest number.

The candidate who receives the maximum number of votes wins the elections, and if multiple candidates receive the same maximum number of votes, the candidate with the lowest number among them wins.

You found these elections too boring and predictable, so you decided to exclude some candidates from them. If you do not allow candidate number $i$ to participate in the elections, all $a_i$ of his fans will become undecided, and will vote for the candidate with the lowest number.

You are curious to find, for each $i$ from $1$ to $n$, the minimum number of candidates that need to be excluded from the elections for candidate number $i$ to win the elections.

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 2\cdot 10^4$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$ and $c$ ($1\le n\le 2\cdot 10^5$, $0\le c\le 10^9$) — the number of candidates in the elections and the number of undecided people.

The second line of each test case contains $n$ integers $a_1,a_2,\dots ,a_n$ ($0\le a_i\le 10^9$) — the number of fans for each candidate.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$.

Output

For each test case, output $n$ integers, the $i$-th of which should be equal to the minimum number of candidates that need to be excluded from the elections for candidate number $i$ to win.

Example

Example

input
5
3 1
2 0 3
2 3
0 10
5 3
5 4 3 2 1
4 5
3 10 7 1
6 0
2 2 2 3 3 3

output
0 1 2
1 0
0 1 2 3 4
1 0 2 3
1 1 2 0 4 5

Note

In the first test case:

• If all candidates are allowed, candidate number $1$ will receive $3$ votes ($1$ undecided person will vote for him), candidate number $2$ will receive $0$ votes, and candidate number $3$ will receive $3$ votes. Therefore, candidate number $1$ wins (he received the same number of votes as candidate $3$, but his number is lower), so the answer for him is $0$.
• If candidate number $1$ is not allowed, his $2$ fans will become undecided. Then candidate number $2$ will receive $3$ votes ($3$ undecided people will vote for him) and candidate number $3$ will receive $3$ votes. Therefore, candidate number $2$ wins (he received the same number of votes as candidate $3$, but his number is lower), so the answer for him is $1$.
• If candidates with numbers $1$ and $2$ are not allowed, candidate number $3$ wins, so the answer for him is $2$.

In the second test case, candidate number $1$ will win if candidate number $2$ is not allowed to participate.

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, c;
	cin >> n >> c;
	std::vector<int> a(n);
	int mx = 0, p;
	for (int i = 0; i < n; i ++) {
		cin >> a[i];
		if (a[i] > mx) mx = a[i], p = i;
	}

	int sum = 0;
	for (int i = 0; i < n; i ++) {
		if (p == 0 && i == 0 || i == p && a[0] + c < a[i]) cout << 0 << " ";
		else if (sum + c + a[i] >= mx) cout << i << " ";
		else cout << i + 1 << " ";
		sum += a[i];
	}
	cout << endl;
}

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

	int dt;
	
	cin >> dt;

	while (dt --)
		solve();

	return 0;
}

---

E. Computing Machine

Problem Statement

Sasha has two binary strings $s$ and $t$ of the same length $n$, consisting of the characters 0 and 1.

There is also a computing machine that can perform two types of operations on binary strings $a$ and $b$ of the same length $k$:

1. If $a_i=a_{i+2}=$ 0, then you can assign $b_{i+1}:=$ 1 ($1\le i\le k-2$).
2. If $b_i=b_{i+2}=$ 1, then you can assign $a_{i+1}:=$ 1 ($1\le i\le k-2$).

Sasha became interested in the following: if we consider the string $a=s_l{s}_{l+1}\dots s_r$ and the string $b=t_l{t}_{l+1}\dots t_r$, what is the maximum number of 1 characters in the string $a$ that can be obtained using the computing machine. Since Sasha is very curious but lazy, it is up to you to answer this question for several pairs $(l_i,r_i)$ that interest him.

Input

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

The first line of each test case contains a single integer $n$ ($1\le n\le 2\cdot 10^5$) — the length of the strings $s$ and $t$.

The second line of each test case contains a binary string $s$ of length $n$, consisting of the characters 0 and 1.

The third line of each test case contains a binary string $t$ of length $n$, consisting of the characters 0 and 1.

The fourth line of each test case contains a single integer $q$ ($1\le q\le 2\cdot 10^5$) — the number of queries.

The $i$-th of the following lines contains two integers $l_i$ and $r_i$ ($1\le l_i\le r_i\le n$) — the boundaries of the $i$-th pair of substrings that interest Sasha.

It is guaranteed that the sum of $n$ over all test cases does not exceed $2\cdot 10^5$ and the sum of $q$ over all test cases does not exceed $2\cdot 10^5$.

Output

For each test case, output $q$ integers — the answers to all queries.

Example

input
3
4
1111
0000
2
1 2
2 4
4
1010
1101
2
1 3
1 4
6
010101
011010
5
2 3
1 6
2 5
4 4
3 6

output
2
3
2
3
1
4
3
1
2

Note

In the first test case:

• In the first query, $a=$ 11, so the maximum number of 1 characters is $2$.
• In the second query, $a=$ 111, so the maximum number of 1 characters is $3$.

In the second test case:

• In the first query, $a=$ 101 and $b=$ 110. No operations can be performed, so the maximum number of 1 characters is $2$.
• In the second query, $a=$ 1010 and $b=$ 1101. Since $a_2=a_4=$ 0, we can assign $b_3:=$ 1. Now $b_1=b_3=$ 1, so we can assign $a_2:=$ 1. The string $a$ becomes 1110, so the maximum number of 1 characters is $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 = 2e5 + 10;

int n, q, cnt;
string a, b, c, d;
int tot[N];

int work(int l, int r) {
	string s = b, t = a;
	for (int i = l; i <= r - 2; i ++)
		if (a[i] == a[i + 2] && a[i] == '0') s[i + 1] = '1';
	for (int i = l; i <= r - 2; i ++)
		if (s[i] == s[i + 2] && s[i] == '1') t[i + 1] = '1';
	int res = 0;
	for (int i = l; i <= r; i ++)
		res += t[i] == '1';
	return res;
}

void solve() {
	cin >> n >> a >> b >> q;
	a = ' ' + a, b = ' ' + b, c = a, d = b;

	for (int i = 1; i <= n - 2; i ++)
		if (c[i] == c[i + 2] && c[i] == '0') d[i + 1] = '1';
	for (int i = 1; i <= n - 2; i ++)
		if (d[i] == d[i + 2] && d[i] == '1') c[i + 1] = '1';
	for (int i = 1; i <= n; i ++)
		tot[i] = tot[i - 1] + (c[i] == '1');

	while (q -- ) {
		int l, r;
		cin >> l >> r, cnt ++;

		if (r - l + 1 <= 4) {
			cout << work(l, r) << endl;
			continue;
		}
		int res = tot[r] - tot[l - 1];
		if (d[l - 1] == d[l + 1] && d[l - 1] == '1' && a[l] == '0') res --;
		if (l + 1 <= n && a[l - 1] == '0' && a[l + 1] == '0' && b[l] == '0') {
			if (l + 2 <= n && d[l + 2] == '1') res --;
		}
		if (r + 1 <= n && d[r - 1] == d[r + 1] && d[r + 1] == '1' && a[r] == '0') res --;
		if (r + 1 <= n && a[r - 1] == '0' && a[r + 1] == '0' && b[r] == '0') {
			if (r - 2 >= 1 && d[r - 2] == '1') res --;
		}
		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;
}

---

F. Large Graph

Problem Statement

Given an array $a$ of length $n$. Let’s construct a square matrix $b$ of size $n\times n$, in which the $i$-th row contains the array $a$ cyclically shifted to the right by $(i-1)$. For example, for the array $a=[3,4,5]$, the obtained matrix is

$$b=\left[\begin{array}{ccc}3& 4& 5\\ 5& 3& 4\\ 4& 5& 3\end{array}\right]$$

Let’s construct the following graph:

• The graph contains $n^2$ vertices, each of which corresponds to one of the elements of the matrix. Let’s denote the vertex corresponding to the element $b_{i,j}$ as $(i,j)$.
• We will draw an edge between vertices $(i_1,j_1)$ and $(i_2,j_2)$ if $|i_1-i_2|+|j_1-j_2|\le k$ and $\gcd (b_{i_1,j_1},b_{i_2,j_2})>1$, where $\gcd (x,y)$ denotes the greatest common divisor of integers $x$ and $y$.

Your task is to calculate the number of connected components${}^{†}$ in the obtained graph.

${}^{†}$A connected component of a graph is a set of vertices in which any vertex is reachable from any other via edges, and adding any other vertex to the set violates this rule.

Input

Each test consists of multiple test cases. The first line contains a single integer $t$ ($1\le t\le 10^5$) — the number of test cases. The description of the test cases follows.

The first line of each test case contains two integers $n$ and $k$ ($2\le n\le 10^6$, $2\le k\le 2\cdot 10^6$) — the length of the array and the parameter $k$.

The second line of each test case contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^6$) — the elements of the array $a$.

It is guaranteed that the sum of $n$ over all test cases does not exceed $10^6$.

Output

For each test case, output a single integer — the number of connected components in the obtained graph.

Example

input
6
3 3
3 4 5
3 3
3 4 9
3 2
3 4 9
2 2
2 8
5 3
8 27 5 4 3
4 10
2 2 2 2

output
3
2
3
1
4
1

Note

In the first test case, the matrix $b$ is given in the statement. The first connected component contains the vertices $(1,1)$, $(2,2)$, and $(3,3)$. The second connected component contains the vertices $(1,2)$, $(2,3)$, and $(3,1)$. The third connected component contains the vertices $(1,3)$, $(2,1)$, and $(3,2)$. Thus, the graph has $3$ connected components.

In the second test case, the following matrix is obtained:

$$b=\left[\begin{array}{ccc}3& 4& 9\\ 9& 3& 4\\ 4& 9& 3\end{array}\right]$$

The first connected component contains all vertices corresponding to elements with values $3$ and $9$. The second connected component contains all vertices corresponding to elements with the value $4$.

In the fourth test case, all vertices are in one connected component.

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 = 2e6 + 10;

int n, m, k;
int a[N], b[N], p[N];
int st[N], prime[N], idx;
std::vector<int> fact[N], pos[N];

int find(int x) {
	if (p[x] != x) p[x] = find(p[x]);
	return p[x];
}
void Euler(int lim) {
	st[1] = 1;
	for (int i = 2; i <= lim; i ++) {
		if (!st[i]) prime[ ++ idx] = i;
		for (int j = 1; prime[j] * i <= lim; j ++) {
			st[prime[j] * i] = 1;
			if (i % prime[j] == 0) break;
		}
	}
}
void solve() {
	cin >> n >> k;
	for (int i = 1; i <= n; i ++)
		cin >> a[i];
	m = 0;
	for (int i = 2; i <= n; i ++) b[ ++ m] = a[i];
	b[ ++ m] = a[1];
	for (int i = 2; i <= n; i ++) b[ ++ m] = a[i];

	int res = m;
	set<int> avl;
	for (int i = 1; i <= m; i ++) {
		p[i] = i, res += (b[i] == 1) * ((m + 1 >> 1) - abs(i - (m + 1 >> 1)) - 1);
		for (auto v : fact[b[i]])
			if (!st[v])
				pos[v].push_back(i), avl.insert(v);
	}

	for (auto i : avl)
		for (int j = 1; j < pos[i].size(); j ++) {
			if (pos[i][j] - pos[i][j - 1] <= k) {
				int pa = find(pos[i][j]), pb = find(pos[i][j - 1]);
				if (pa != pb) {
					p[pa] = pb;
					res --;
				}
			}
		}

	cout << res << endl;
	for (int i = 1; i <= m; i ++)
		for (auto v : fact[b[i]])
			pos[v].clear();
}

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

	for (int i = 1; i < (N >> 1); i ++)
		for (int j = i; j < (N >> 1); j += i)
			fact[j].push_back(i);
	Euler(N >> 1);

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

	return 0;
}

---

视频讲解

---

最后祝大家早日