比赛记录 - Codeforces Round #794 (Div. 2) (A-D)

发表于 更新于 分类于 本文字数： 2.6k 阅读时长 ≈ 9 分钟

比赛链接

难度梯度好怪

A - Everything Everywhere All But One

You are given an array of \(n\) integers \(a_1, a_2, \ldots, a_n\). After you watched the amazing film "Everything Everywhere All At Once", you came up with the following operation

In one operation, you choose \(n-1\) elements of the array and replace each of them with their arithmetic mean (which doesn't have to be an integer). For example, from the array \([1, 2, 3, 1]\) we can get the array \([2, 2, 2, 1]\), if we choose the first three elements, or we can get the array \([\frac{4}{3}, \frac{4}{3}, 3, \frac{4}{3}]\), if we choose all elements except the third

Is it possible to make all elements of the array equal by performing a finite number of such operations?

Input

The first line of the input contains a single integer \(t\) (\(1 \le t \le 200\)) — the number of test cases. The description of the test cases follows

The first line of each test case contains a single integer \(n\) (\(3 \le n \le 50\)) — the number of integers

The second line of each test case contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(0 \le a_i \le 100\))

Output

For each test case, if it is possible to make all elements equal after some number of operations, output \(\texttt{YES}\). Otherwise, output \(\texttt{NO}\)

You can output \(\texttt{YES}\) and \(\texttt{NO}\) in any case (for example, strings \(\texttt{yEs}\), \(\texttt{yes}\), \(\texttt{Yes}\) will be recognized as a positive response)

Example

input

1
2
3
4
5
6
7
8
9
4
3
42 42 42
5
1 2 3 4 5
4
4 3 2 1
3
24 2 22

output

1
2
3
4
YES
YES
NO
NO

Note

In the first test case, all elements are already equal

In the second test case, you can choose all elements except the third, their average is \(\frac{1 + 2 + 4 + 5}{4} = 3\), so the array will become \([3, 3, 3, 3, 3]\)

It's possible to show that it's impossible to make all elements equal in the third and fourth test cases

代码参考

Show code

CodeForces_1686Aview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define _for(i, l, r, vals...) \
  for (decltype(l + r) i = (l), i##end = (r), ##vals; i <= i##end; ++i)
template <class T>
bool chkmin(T &a, T b) {
  return b < a ? a = b, true : false;
}
template <class T>
bool chkmax(T &a, T b) {
  return a < b ? a = b, true : false;
}
const uint32_t OFFSET = 5;
const uint32_t N = 1e5 + OFFSET, M = 2e5 + OFFSET, K = 21;
int a[N];
auto solve() -> void {
  int n;
  cin >> n;
  i64 sum = 0;
  _for(i, 1, n) {
    cin >> a[i];
    sum += a[i];
  }
  cout << (sum % n == 0 && any_of(a + 1,
                                  a + n + 1,
                                  [sum, n](int x) { return x == sum / n; }) ?
             "YES" :
             "NO")
       << '\n';
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int _t;
  cin >> _t;
  while (_t--) solve();
  return 0;
}

B - Odd Subarrays

For an array \([b_1, b_2, \ldots, b_m]\) define its number of inversions as the number of pairs \((i, j)\) of integers such that \(1 \le i < j \le m\) and \(b_i>b_j\). Let's call array \(b\) odd if its number of inversions is odd

For example, array \([4, 2, 7]\) is odd, as its number of inversions is \(1\), while array \([2, 1, 4, 3]\) isn't, as its number of inversions is \(2\)

You are given a permutation \([p_1, p_2, \ldots, p_n]\) of integers from \(1\) to \(n\) (each of them appears exactly once in the permutation). You want to split it into several consecutive subarrays (maybe just one), so that the number of the odd subarrays among them is as large as possible

What largest number of these subarrays may be odd?

Input

The first line of the input 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 a single integer \(n\) (\(1 \le n \le 10^5\)) — the size of the permutation

The second line of each test case contains \(n\) integers \(p_1, p_2, \ldots, p_n\) (\(1 \le p_i \le n\), all \(p_i\) are distinct) — the elements of the permutation

The sum of \(n\) over all test cases doesn't exceed \(2\cdot 10^5\)

Output

For each test case output a single integer — the largest possible number of odd subarrays that you can get after splitting the permutation into several consecutive subarrays

Example

input

1
2
3
4
5
6
7
8
9
10
11
5
3
1 2 3
4
4 3 2 1
2
1 2
2
2 1
6
4 5 6 1 2 3

output

1
2
3
4
5
0
2
0
1
1

Note

In the first and third test cases, no matter how we split our permutation, there won't be any odd subarrays

In the second test case, we can split our permutation into subarrays \([4, 3], [2, 1]\), both of which are odd since their numbers of inversions are \(1\)

In the fourth test case, we can split our permutation into a single subarray \([2, 1]\), which is odd

In the fifth test case, we can split our permutation into subarrays \([4, 5], [6, 1, 2, 3]\). The first subarray has \(0\) inversions, and the second has \(3\), so it is odd

代码参考

Show code

CodeForces_1686Bview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define _for(i, l, r, vals...) \
  for (decltype(l + r) i = (l), i##end = (r), ##vals; i <= i##end; ++i)
template <class T>
bool chkmin(T &a, T b) {
  return b < a ? a = b, true : false;
}
template <class T>
bool chkmax(T &a, T b) {
  return a < b ? a = b, true : false;
}
const uint32_t OFFSET = 5;
const uint32_t N = 1e5 + OFFSET, M = 2e5 + OFFSET, K = 21;
int a[N];
auto solve() -> void {
  int n;
  cin >> n;
  i64 sum = 0;
  _for(i, 1, n) cin >> a[i];
  int ans = 0;
  _for(i, 2, n)
    if (a[i] < a[i - 1]) {
      ++ans;
      ++i;
    }
  cout << ans << '\n';
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int _t;
  cin >> _t;
  while (_t--) solve();
  return 0;
}

C - Circular Local MiniMax

You are given \(n\) integers \(a_1, a_2, \ldots, a_n\). Is it possible to arrange them on a circle so that each number is strictly greater than both its neighbors or strictly smaller than both its neighbors?

In other words, check if there exists a rearrangement \(b_1, b_2, \ldots, b_n\) of the integers \(a_1, a_2, \ldots, a_n\) such that for each \(i\) from \(1\) to \(n\) at least one of the following conditions holds:

\(b_{i-1} < b_i > b_{i+1}\) \(b_{i-1} > b_i < b_{i+1}\) To make sense of the previous formulas for \(i=1\) and \(i=n\), one shall define \(b_0=b_n\) and \(b_{n+1}=b_1\)

Input

The first line of the input contains a single integer \(t\) (\(1 \le t \le 3\cdot 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\) (\(3 \le n \le 10^5\)) — the number of integers

The second line of each test case contains \(n\) integers \(a_1, a_2, \ldots, a_n\) (\(0 \le a_i \le 10^9\))

The sum of \(n\) over all test cases doesn't exceed \(2\cdot 10^5\)

Output

For each test case, if it is not possible to arrange the numbers on the circle satisfying the conditions from the statement, output \(\texttt{NO}\). You can output each letter in any case

Otherwise, output \(\texttt{YES}\). In the second line, output \(n\) integers \(b_1, b_2, \ldots, b_n\), which are a rearrangement of \(a_1, a_2, \ldots, a_n\) and satisfy the conditions from the statement. If there are multiple valid ways to arrange the numbers, you can output any of them

Example

input

1
2
3
4
5
6
7
8
9
4
3
1 1 2
4
1 9 8 4
4
2 0 2 2
6
1 1 1 11 111 1111

output

1
2
3
4
5
6
NO
YES
1 8 4 9
NO
YES
1 11 1 111 1 1111

Note

It can be shown that there are no valid arrangements for the first and the third test cases

In the second test case, the arrangement \([1, 8, 4, 9]\) works. In this arrangement, \(1\) and \(4\) are both smaller than their neighbors, and \(8, 9\) are larger

In the fourth test case, the arrangement \([1, 11, 1, 111, 1, 1111]\) works. In this arrangement, the three elements equal to \(1\) are smaller than their neighbors, while all other elements are larger than their neighbors

代码参考

Show code

CodeForces_1686Cview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
using i64 = int64_t;
#define _for(i, l, r, vals...) \
  for (decltype(l + r) i = (l), i##end = (r), ##vals; i <= i##end; ++i)
template <class T>
bool chkmin(T &a, T b) {
  return b < a ? a = b, true : false;
}
template <class T>
bool chkmax(T &a, T b) {
  return a < b ? a = b, true : false;
}
const uint32_t OFFSET = 5;
const uint32_t N = 1e5 + OFFSET, M = 2e5 + OFFSET, K = 21;
int a[N];
int ans[N];
auto solve() -> void {
  int n;
  cin >> n;
  i64 sum = 0;
  _for(i, 1, n) cin >> a[i];
  sort(a + 1, a + n + 1);
  _for(i, 1, (n + 1) / 2) ans[i * 2 - 1] = a[i];
  _for(i, 1, n - (n + 1) / 2) ans[i * 2] = a[i + (n + 1) / 2];
  ans[0] = ans[n];
  ans[n + 1] = ans[1];
  bool f = 0;
  _for(i, 1, n)
    if (!(ans[i - 1] < ans[i] && ans[i + 1] < ans[i]) &&
        !(ans[i - 1] > ans[i] && ans[i + 1] > ans[i])) {
      f = 1;
      break;
    }
  cout << (f ? "NO" : "YES") << '\n';
  if (f) return;
  _for(i, 1, n) cout << ans[i] << " \n"[i == n];
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int _t;
  cin >> _t;
  while (_t--) solve();
  return 0;
}

D - Linguistics

Alina has discovered a weird language, which contains only \(4\) words: \(\texttt{A}\), \(\texttt{B}\), \(\texttt{AB}\), \(\texttt{BA}\). It also turned out that there are no spaces in this language: a sentence is written by just concatenating its words into a single string

Alina has found one such sentence \(s\) and she is curious: is it possible that it consists of precisely \(a\) words \(\texttt{A}\), \(b\) words \(\texttt{B}\), \(c\) words \(\texttt{AB}\), and \(d\) words \(\texttt{BA}\)?

In other words, determine, if it's possible to concatenate these \(a+b+c+d\) words in some order so that the resulting string is \(s\). Each of the \(a+b+c+d\) words must be used exactly once in the concatenation, but you can choose the order in which they are concatenated

Input

The first line of the input 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 four integers \(a\), \(b\), \(c\), \(d\) (\(0\le a,b,c,d\le 2\cdot 10^5\)) — the number of times that words \(\texttt{A}\), \(\texttt{B}\), \(\texttt{AB}\), \(\texttt{BA}\) respectively must be used in the sentence

The second line contains the string \(s\) (\(s\) consists only of the characters \(\texttt{A}\) and \(\texttt{B}\), \(1\le |s| \le 2\cdot 10^5\), \(|s|=a+b+2c+2d\)) — the sentence. Notice that the condition \(|s|=a+b+2c+2d\) (here \(|s|\) denotes the length of the string \(s\)) is equivalent to the fact that \(s\) is as long as the concatenation of the \(a+b+c+d\) words

The sum of the lengths of \(s\) over all test cases doesn't exceed \(2\cdot 10^5\)

Output

For each test case output \(\texttt{YES}\) if it is possible that the sentence \(s\) consists of precisely \(a\) words \(\texttt{A}\), \(b\) words \(\texttt{B}\), \(c\) words \(\texttt{AB}\), and \(d\) words \(\texttt{BA}\), and \(\texttt{NO}\) otherwise. You can output each letter in any case

Example

input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
8
1 0 0 0
B
0 0 1 0
AB
1 1 0 1
ABAB
1 0 1 1
ABAAB
1 1 2 2
BAABBABBAA
1 1 2 3
ABABABBAABAB
2 3 5 4
AABAABBABAAABABBABBBABB
1 3 3 10
BBABABABABBBABABABABABABAABABA

output

1
2
3
4
5
6
7
8
NO
YES
YES
YES
YES
YES
NO
YES

Note

In the first test case, the sentence \(s\) is \(\texttt{B}\). Clearly, it can't consist of a single word \(\texttt{A}\), so the answer is \(\texttt{NO}\)

In the second test case, the sentence \(s\) is \(\texttt{AB}\), and it's possible that it consists of a single word \(\texttt{AB}\), so the answer is \(\texttt{YES}\)

In the third test case, the sentence \(s\) is \(\texttt{ABAB}\), and it's possible that it consists of one word \(\texttt{A}\), one word \(\texttt{B}\), and one word \(\texttt{BA}\), as \(\texttt{A} + \texttt{BA} + \texttt{B} = \texttt{ABAB}\)

In the fourth test case, the sentence \(s\) is \(\texttt{ABAAB}\), and it's possible that it consists of one word \(\texttt{A}\), one word \(\texttt{AB}\), and one word \(\texttt{BA}\), as \(\texttt{A} + \texttt{BA} + \texttt{AB} = \texttt{ABAAB}\)

In the fifth test case, the sentence \(s\) is \(\texttt{BAABBABBAA}\), and it's possible that it consists of one word \(\texttt{A}\), one word \(\texttt{B}\), two words \(\texttt{AB}\), and two words \(\texttt{BA}\), as \(\texttt{BA} + \texttt{AB} + \texttt{B} + \texttt{AB} + \texttt{BA} + \texttt{A}= \texttt{BAABBABBAA}\)

代码参考

Show code

CodeForces_1686Dview raw
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
/*
 * @Author: Tifa
 * @Description: From <https://github.com/Tiphereth-A/CP-archives>
 * !!! ATTENEION: All the context below is licensed under a 
 *  GNU Affero General Public License, Version 3.
 *  See <https://www.gnu.org/licenses/agpl-3.0.txt>.
 */
#include <bits/stdc++.h>
using namespace std;
#define _for(i, l, r, vals...) \
  for (decltype(l + r) i = (l), i##end = (r), ##vals; i <= i##end; ++i)
#define _all(a) (a).begin(), (a).end()
#define _run_return_void(expressions) \
  {                                   \
    expressions;                      \
    return;                           \
  }
template <class T>
bool chkmin(T &a, T b) {
  return b < a ? a = b, true : false;
}
template <class T>
bool chkmax(T &a, T b) {
  return a < b ? a = b, true : false;
}
const uint32_t OFFSET = 5;
const uint32_t N = 2e5 + OFFSET, M = 2e5 + OFFSET, K = 21;
int base[N];
bool startswith_A[N];
int f[N];
auto solve() -> void {
  int a, b, ab, ba;
  cin >> a >> b >> ab >> ba;
  string s;
  cin >> s;
  int _a = count_if(_all(s), [](char ch) { return ch == 'A'; });
  if (_a != a + ab + ba) _run_return_void(cout << "NO\n");
  int cnt = 0;
  bool head = 1;
  char pre = s.front();
  for (size_t i = 1; i < s.size(); ++i) {
    char &now = s[i];
    if (pre == now) {
      head = 1;
      continue;
    }
    if (head) {
      startswith_A[++cnt] = pre == 'A';
      base[cnt] = 1;
      head = 0;
    }
    ++base[cnt];
    pre = now;
  }
  vector<pair<int, bool>> data_odd, data_even;
  data_even.reserve(cnt);
  data_odd.reserve(cnt);
  _for(i, 1, cnt)
    (base[i] & 1 ? data_odd : data_even).emplace_back(base[i], startswith_A[i]);
  sort(_all(data_odd));
  sort(_all(data_even));
  for (auto [i, b] : data_even) {
    if (!(i & 1) && b) {
      if (ab >= i / 2) {
        ab -= i / 2;
        continue;
      }
      if (ab) i -= ab * 2 + 2;
      if ((ba -= i / 2 - !ab) <= (ab = 0)) break;
      continue;
    }
    if (ba >= i / 2) {
      ba -= i / 2;
      continue;
    }
    if (ba) i -= ba * 2 + 2;
    if ((ab -= i / 2 - !ba) <= (ba = 0)) break;
  }
  if (ab > 0 || ba > 0)
    for (auto [i, b] : data_odd) {
      if (ba >= i / 2) {
        ba -= i / 2;
        continue;
      }
      if (ba) i -= ba * 2 + 1;
      if ((ab -= i / 2) <= (ba = 0)) break;
    }
  cout << (ab <= 0 && ba <= 0 ? "YES\n" : "NO\n");
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int _t;
  cin >> _t;
  while (_t--) solve();
  return 0;
}

E - Bring Balance

Alina has a bracket sequence \(s\) of length \(2n\), consisting of \(n\) opening brackets '(' and \(n\) closing brackets ')'. As she likes balance, she wants to turn this bracket sequence into a balanced bracket sequence

In one operation, she can reverse any substring of \(s\)

What's the smallest number of operations that she needs to turn \(s\) into a balanced bracket sequence? It can be shown that it's always possible in at most \(n\) operations

As a reminder, a sequence of brackets is called balanced if one can turn it into a valid math expression by adding characters + and 1. For example, sequences (())(), (), and (()(())) are balanced, while )(, ((), and (()))( are not

Input

The first line of the input 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 a single integer \(n\) (\(1 \le n \le 10^5\))

The second line of each test case contains a string \(s\) of length \(2n\), consisting of \(n\) opening and \(n\) closing brackets

The sum of \(n\) over all test cases doesn't exceed \(2\cdot 10^5\)

Output

For each test case, in the first line output a single integer \(k\) \((0 \le k \le n)\) — the smallest number of operations required

The \(i\)-th of the next \(k\) lines should contain two integers \(l_i, r_i\) (\(1 \le l_i \le r_i \le 2n\)), indicating that in the \(i\)-th operation, Alina will reverse the substring \(s*ls*{l+1} \ldots s\_{r-1}s_r\). Here the numeration starts from \(1\)

If there are multiple sequences of operations with the smallest length which transform the sequence into a balanced one, you can output any of them

Example

input

1
2
3
4
5
6
7
3
2
(())
5
())((()))(
6
())((()))(()

output

1
2
3
4
5
6
0
2
3 4
9 10
1
2 11

Note

In the first test case, the string is already balanced

In the second test case, the string will be transformed as follows: ())((()))( \(\to\) ()()(()))( \(\to\) ()()(())(), where the last string is balanced

In the third test case, the string will be transformed to ((()))((())), which is balanced

代码参考

Show code

F - Permutation Weight (Easy Version)

This is an easy version of the problem. The difference between the easy and hard versions is that in this version, you can output any permutation with the smallest weight

You are given a permutation \(p_1, p_2, \ldots, p_n\) of integers from \(1\) to \(n\)

Let's define the weight of the permutation \(q_1, q_2, \ldots, q_n\) of integers from \(1\) to \(n\) as

\[ |q_1 - p_{q_{2}}| + |q_2 - p_{q_{3}}| + \ldots + |q_{n-1} - p_{q_{n}}| + |q_n - p_{q_{1}}| \]

You want your permutation to be as lightweight as possible. Find any permutation \(q\) with the smallest possible weight

Input

The first line of the input contains a single integer \(t\) (\(1 \le t \le 100\)) — 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 200\)) — the size of the permutation

The second line of each test case contains \(n\) integers \(p_1, p_2, \ldots, p_n\) (\(1 \le p_i \le n\), all \(p_i\) are distinct) — the elements of the permutation

The sum of \(n\) over all test cases doesn't exceed \(400\)

Output

For each test case, output \(n\) integers \(q_1, q_2, \ldots, q_n\) (\(1 \le q_i \le n\), all \(q_i\) are distinct) — one of the permutations with the smallest weight

Example

input

1
2
3
4
5
6
7
3
2
2 1
4
2 3 1 4
5
5 4 3 2 1

output

1
2
3
1 2
1 3 4 2
1 4 2 3 5

Note

In the first test case, there are two permutations of length \(2\): \((1, 2)\) and \((2, 1)\). Permutation \((1, 2)\) has weight \(|1 - p_2| + |2 - p_1| = 0\), and permutation \((2, 1)\) has the same weight: \(|2 - p_1| + |1 - p_2| = 0\). You can output any of these permutations in this version

In the second test case, the weight of the permutation \((1, 3, 4, 2)\) is \(|1 - p_3| + |3 - p_4| + |4 - p_2| + |2 - p_1| = |1 - 1| + |3 - 4| + |4 - 3| + |2 - 2| = 2\). There are no permutations with smaller weights

In the third test case, the weight of the permutation \((1, 4, 2, 3, 5)\) is \(|1 - p_4| + |4 - p_2| + |2 - p_3| + |3 - p_5| + |5 - p_1| = |1 - 2| + |4 - 4| + |2 - 3| + |3 - 1| + |5 - 5| = 4\). There are no permutations with smaller weights

代码参考

Show code