Codeforces Round 942 (Div. 2 ABCDE题) 视频讲解

A. Contest Proposal

Problem Statement

A contest contains $n$ problems and the difficulty of the $i$-th problem is expected to be at most $b_i$. There are already $n$ problem proposals and the difficulty of the $i$-th problem is $a_i$. Initially, both $a_1,a_2,\dots ,a_n$ and $b_1,b_2,\dots ,b_n$ are sorted in non-decreasing order.

Some of the problems may be more difficult than expected, so the writers must propose more problems. When a new problem with difficulty $w$ is proposed, the most difficult problem will be deleted from the contest, and the problems will be sorted in a way that the difficulties are non-decreasing.

In other words, in each operation, you choose an integer $w$, insert it into the array $a$, sort array $a$ in non-decreasing order, and remove the last element from it.

Find the minimum number of new problems to make $a_i\le b_i$ for all $i$.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 100$). The description of the test cases follows.

The first line of each test case contains only one positive integer $n$ ($1\le n\le 100$), representing the number of problems.

The second line of each test case contains an array $a$ of length $n$ ($1\le a_1\le a_2\le \cdots \le a_n\le 10^9$).

The third line of each test case contains an array $b$ of length $n$ ($1\le b_1\le b_2\le \cdots \le b_n\le 10^9$).

Output

For each test case, print an integer as your answer in a new line.

Example

Example

Note

In the first test case:

• Propose a problem with difficulty $w=800$ and $a$ becomes $[800,1000,1400,2000,2000,2200]$.
• Propose a problem with difficulty $w=1800$ and $a$ becomes $[800,1000,1400,1800,2000,2000]$.

It can be proved that it’s impossible to reach the goal by proposing fewer new problems.

In the second test case:

• Propose a problem with difficulty $w=1$ and $a$ becomes $[1,4,5,6,7,8]$.
• Propose a problem with difficulty $w=2$ and $a$ becomes $[1,2,4,5,6,7]$.
• Propose a problem with difficulty $w=3$ and $a$ becomes $[1,2,3,4,5,6]$.

It can be proved that it’s impossible to reach the goal by proposing fewer new problems.

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), b(n + 1);
	for (int i = 1; i <= n; i ++)
		cin >> a[i];
	for (int i = 1; i <= n; i ++)
		cin >> b[i];

	int res = 0;
	for (int i = 1, j = 1; i <= n; i ++) {
		while (i <= n && a[j] > b[i]) res ++, i ++;
		j ++;
	}

	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;
}

B. Coin Games

Problem Statement

There are $n$ coins on the table forming a circle, and each coin is either facing up or facing down. Alice and Bob take turns to play the following game, and Alice goes first.

In each operation, the player chooses a facing-up coin, removes the coin, and flips the two coins that are adjacent to it. If (before the operation) there are only two coins left, then one will be removed and the other won’t be flipped (as it would be flipped twice). If (before the operation) there is only one coin left, no coins will be flipped. If (before the operation) there are no facing-up coins, the player loses.

Decide who will win the game if they both play optimally. It can be proved that the game will end in a finite number of operations, and one of them will win.

Input

Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\le t\le 100$). The description of the test cases follows.

The first line of each test case contains only one positive integer $n$ ($1\le n\le 100$), representing the number of the coins.

A string $s$ of length $n$ follows on the second line of each test case, containing only “U” and “D”, representing that each coin is facing up or facing down.

Output

For each test case, print “YES” if Alice will win the game, and “NO” otherwise.

You can output the answer in any case (upper or lower). For example, the strings “yEs”, “yes”, “Yes”, and “YES” will be recognized as positive responses.

Example

Example

Note

In the first test case, the game may go as follows.

• Alice chooses the first coin and $s$ becomes “DDUU”.
• Bob chooses the last coin and $s$ becomes “UDD”.
• Alice chooses the first coin and $s$ becomes “UU”.
• Bob chooses the first coin and $s$ becomes “U”.
• Alice chooses the only coin and $s$ becomes empty.
• Bob can’t choose any coin now, and he loses the game.

It can be proved that Bob will always lose if they both play optimally.

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 flip(char &tmp) {
	if (tmp == 'U') tmp = 'D';
	else tmp = 'U';
}

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

	int cpy = n;
	for (int i = 1; i <= cpy; i ++) {
		bool flg = 1;
		for (int j = 1; j <= n; j ++)
			if (s[j] == 'U') {
				if (j == 1) flip(s[n]);
				else flip(s[j - 1]);
				if (j == n) flip(s[1]);
				else flip(s[j + 1]);
				s.erase(s.begin() + j), n --;
				flg = 0;
				break;
			}
		if (flg) {
			if (i & 1) cout << "NO" << endl;
			else cout << "YES" << endl;
			return;
		}
	}
	if (cpy & 1) cout << "YES" << endl;
	else cout << "NO" << endl;
}

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

	int dt;
	
	cin >> dt;

	while (dt --)
		solve();

	return 0;
}

C. Permutation Counting

Problem Statement

You have some cards. An integer between $1$ and $n$ is written on each card: specifically, for each $i$ from $1$ to $n$, you have $a_i$ cards which have the number $i$ written on them.

There is also a shop which contains unlimited cards of each type. You have $k$ coins, so you can buy $k$ new cards in total, and the cards you buy can contain any integer between $1$ and $n$.

After buying the new cards, you rearrange all your cards in a line. The score of a rearrangement is the number of (contiguous) subarrays of length $n$ which are a permutation of $[1,2,\dots ,n]$. What’s the maximum score you can get?

Input

Each test contains multiple test cases. The first line contains the number of test cases $t(1\le t\le 100)$. The description of the test cases follows.

The first line of each test case contains two integers $n$, $k$ ($1\le n\le 2\cdot 10^5$, $0\le k\le 10^{12}$) — the number of distinct types of cards and the number of coins.

The second line of each test case contains $n$ integers $a_1,a_2,\dots ,a_n$ ($1\le a_i\le 10^{12}$) — the number of cards of type $i$ you have at the beginning.

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

Output

For each test case, output a single line containing an integer: the maximum score you can get.

Example

Note

In the first test case, the final (and only) array we can get is $[1,1,1,1,1,1,1,1,1,1,1]$ (including $11$ single $1$s), which contains $11$ subarrays consisting of a permutation of $[1]$.

In the second test case, we can buy $0$ cards of type $1$ and $4$ cards of type $2$, and then we rearrange the cards as following: $[1,2,1,2,1,2,1,2,1,2,1,2,1,2,1,2]$. There are $8$ subarrays equal to $[1,2]$ and $7$ subarrays equal to $[2,1]$, which make a total of $15$ subarrays which are a permutation of $[1,2]$. It can also be proved that this is the maximum score we can get.

In the third test case, one of the possible optimal rearrangements is $[3,3,1,2,3,1,2,3,1,2,3,1,2,3,1,2,3,1,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, k;
int a[N], b[N];
unordered_map<int, int> cnt;

void solve() {
	cnt.clear();
	cin >> n >> k;

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

	sort(a + 1, a + 1 + n);
	int m = unique(a + 1, a + 1 + n) - a - 1;
	int need = 0, sub = 0, res = 0;
	for (int i = 1; i <= m; i ++) {
		if (k < need * (a[i] - sub)) {
			res += k / need * n, k = k % need;
			break;
		}
		res += (a[i] - sub) * n, k -= need * (a[i] - sub);
		need += cnt[a[i]], sub = a[i];
	}

	if (k < need) {
		for (int i = 1; i <= n; i ++)
			if (b[i] - sub > 0)
				res ++;
	}
	res += k;
	cout << res - n + 1 << endl;
}

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

	int dt;
	
	cin >> dt;

	while (dt --)
		solve();

	return 0;
}

D1. Reverse Card (Easy Version)

Problem Statement

The two versions are different problems. You may want to read both versions. You can make hacks only if both versions are solved.

You are given two positive integers $n$, $m$.

Calculate the number of ordered pairs $(a,b)$ satisfying the following conditions:

• $1\le a\le n$, $1\le b\le m$;
• $a+b$ is a multiple of $b\cdot \gcd (a,b)$.

Input

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

The first line of each test case contains two integers $n$, $m$ ($1\le n,m\le 2\cdot 10^6$).

It is guaranteed that neither the sum of $n$ nor the sum of $m$ over all test cases exceeds $2\cdot 10^6$.

Output

For each test case, print a single integer: the number of valid pairs.

Example

Example

Note

In the first test case, only $(1,1)$ satisfies the conditions.

In the fourth test case, $(1,1),(2,1),(2,2),(3,1),(4,1),(5,1),(6,1),(6,2),(6,3),(7,1),(8,1),(9,1),(10,1),(10,2)$ satisfy the conditions.

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

	int res = 0;
	for (int i = 1; i <= m; i ++) {
		res += (n + i) / (i * i);
	}

	cout << res - 1 << endl;
}

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

	int dt;
	
	cin >> dt;

	while (dt --)
		solve();

	return 0;
}

D2. Reverse Card (Hard Version)

Problem Statement

The two versions are different problems. You may want to read both versions. You can make hacks only if both versions are solved.

You are given two positive integers $n$, $m$.

Calculate the number of ordered pairs $(a,b)$ satisfying the following conditions:

• $1\le a\le n$, $1\le b\le m$;
• $b\cdot \gcd (a,b)$ is a multiple of $a+b$.

Input

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

The first line of each test case contains two integers $n$, $m$ ($1\le n,m\le 2\cdot 10^6$).

It is guaranteed that neither the sum of $n$ nor the sum of $m$ over all test cases exceeds $2\cdot 10^6$.

Output

For each test case, print a single integer: the number of valid pairs.

Example

Example

Note

In the first test case, no pair satisfies the conditions.

In the fourth test case, $(2,2),(3,6),(4,4),(6,3),(6,6),(8,8)$ satisfy the conditions.

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

	int res = 0;
	for (int p = 1; p <= n / p; p ++)
		for (int q = 1; q <= m / q; q ++)
			if (__gcd(p, q) == 1)
				res += min(n / p, m / q) / (p + q);

	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. Fenwick Tree

Problem Statement

Let $\mathrm{lowbit}(x)$ denote the value of the lowest binary bit of $x$, e.g. $\mathrm{lowbit}(12)=4$, $\mathrm{lowbit}(8)=8$.

For an array $a$ of length $n$, if an array $s$ of length $n$ satisfies $s_k=\left(\sum _{i=k-\mathrm{lowbit}(k)+1}^k{a}_i\right)\mathrm{mod}998244353$ for all $k$, then $s$ is called the Fenwick Tree of $a$. Let’s denote it as $s=f(a)$.

For a positive integer $k$ and an array $a$, $f^k(a)$ is defined as follows:

$$f^k(a)=\{\begin{array}{ll}f(a)& \text{if }k=1\\ f(f^{k-1}(a))& \text{otherwise.}\end{array}$$

You are given an array $b$ of length $n$ and a positive integer $k$. Find an array $a$ that satisfies $0\le a_i<998244353$ and $f^k(a)=b$. It can be proved that an answer always exists. If there are multiple possible answers, you may print any of them.

Input

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

The first line of each test case contains two positive integers $n$ ($1\le n\le 2\cdot 10^5$) and $k$ ($1\le k\le 10^9$), representing the length of the array and the number of times the function $f$ is performed.

The second line of each test case contains an array $b_1,b_2,\dots ,b_n$ ($0\le b_i<998244353$).

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

Output

For each test case, print a single line, containing a valid array $a$ of length $n$.

Example

Note

In the first test case, it can be seen that $f^1([1,1,1,1,1,1,1,1])=[1,2,1,4,1,2,1,8]$.

In the second test case, it can be seen that $f^2([1,2,3,4,5,6])=f^1([1,3,3,10,5,11])=[1,4,3,17,5,16]$.

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 exgcd(int a, int b, int &x, int &y) {
	if (!b) { x = 1, y = 0; return; }
	exgcd(b, a % b, y, x);
	y -= a / b * x;
}
template <int mod>
struct modint {
	int v;
	int norm(const int &x) { return x < 0 ? x + mod : x; }
	int get_mod() { return mod; }
	modint() : v(0) {}
	modint(int x) : v(norm(x % mod)) {}
	modint operator-() const {
		modint res;
		return res.v = -v;
	}
	bool operator== (const modint &x) { return v == x.v; }
	bool operator< (const modint &x) { return v < x.v; }
	bool operator> (const modint &x) { return v > x.v; }
	modint operator+= (const modint &x) { return v = (v + x.v) % mod; }
	modint operator-= (const modint &x) { return v = norm(v - x.v); }
	modint operator*= (const modint &x) { return v = v * x.v % mod; }
	modint operator/= (const modint &x) {
		int a, b;
		exgcd(x.v, mod, a, b);
		return v = v * norm(a % mod) % mod;
	}
	modint operator+ (const modint &x) { return (v + x.v) % mod; }
	modint operator- (const modint &x) { return norm(v - x.v); }
	modint operator* (const modint &x) { return v * x.v % mod; }
	modint operator/ (const modint &x) {
		int a, b;
		exgcd(x.v, mod, a, b);
		return v * norm(a % mod) % mod;
	}
	modint operator+= (const int &x) { return v = (v + x) % mod; }
	modint operator-= (const int &x) { return v = norm(v - x); }
	modint operator*= (const int &x) { return v = v * x % mod; }
	modint operator/= (const int &x) {
		int a, b;
		exgcd(x, mod, a, b);
		return v = v * norm(a % mod) % mod;
	}
	modint operator^= (int x) {
		int res = 1, a = v;
		while (x) {
			if (x & 1) res = res * a % mod;
			a = a * a % mod;
			x >>= 1;
		}
		return res;
	}
	modint operator+ (const int &x) { return (v + x) % mod; }
	modint operator- (const int &x) { return norm(v - x); }
	modint operator* (const int &x) { return v * x % mod; }
	modint operator/ (const int &x) {
		int a, b;
		exgcd(x, mod, a, b);
		return v * norm(a % mod) % mod;
	}
	modint operator^ (int x) {
		int res = 1, a = v;
		while (x) {
			if (x & 1) res = res * a % mod;
			a = a * a % mod;
			x >>= 1;
		}
		return res;
	}
	friend istream& operator>> (istream &in, modint &x) {
		in >> x.v;
		return in;
	}
	friend ostream& operator<< (ostream &out, modint &x) {
		out << x.v;
		return out;
	}
};
using Mint = modint<998244353>;
Mint to_Mint(int x) {
	Mint res(x);
	return res;
}

const int N = 2e5 + 10;

int n, k;
Mint a[N], b[N];

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

	for (int i = 1; i <= n; i ++)
		cin >> b[i];

	for (int i = 1; i <= n; i ++) {
		a[i] = b[i];
		Mint mul = 1;
		for (int j = i + (i & -i), l = 1; j <= n; j += (j & -j), l ++) {
			mul *= to_Mint(k + l - 1) / l;
			b[j] -= mul * a[i];
		}
	}
	for (int i = 1; i <= n; i ++)
		cout << 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;
}

视频讲解

最后祝大家早日