比赛记录 - CodeCraft-22 and Codeforces Round #795 (Div. 2) (A-D)

发表于 2022-06-01 更新于 2024-06-25 分类于算法竞赛本文字数： 2.1k 阅读时长 ≈ 8 分钟

A - Beat The Odds

Given a sequence \(a_1, a_2, \ldots, a_n\), find the minimum number of elements to remove from the sequence such that after the removal, the sum of every \(2\) consecutive elements is even

Input

Each test contains multiple test cases. The first line contains a single integer \(t\) (\(1 \le t \le 100\)) — the number of test cases. 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 second line of each test case contains \(n\) integers \(a_1, a_2,\dots,a_n\) (\(1\leq a_i\leq10^9\)) — elements of the sequence

It is guaranteed that the sum of \(n\) over all test cases does not exceed \(10^5\)

Output

For each test case, print a single integer — the minimum number of elements to remove from the sequence such that the sum of every \(2\) consecutive elements is even

Example

input

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

output

1
2

1
0

Note

In the first test case, after removing \(3\), the sequence becomes \([2,4,6,8]\). The pairs of consecutive elements are \(\{[2, 4], [4, 6], [6, 8]\}\). Each consecutive pair has an even sum now. Hence, we only need to remove \(1\) element to satisfy the condition asked

In the second test case, each consecutive pair already has an even sum so we need not remove any element

代码参考

Show code

CodeForces_1691Aview raw

/*
 * @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)
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;
}
auto solve() -> void {
  int n;
  cin >> n;
  int cnt0 = 0, cnt1 = 0;
  _for(i, 1, n, x) {
    cin >> x;
    (x & 1 ? cnt1 : cnt0)++;
  }
  cout << min(cnt0, cnt1) << '\n';
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int _t;
  cin >> _t;
  while (_t--) solve();
  return 0;
}

B - Shoe Shuffling

A class of students got bored wearing the same pair of shoes every day, so they decided to shuffle their shoes among themselves. In this problem, a pair of shoes is inseparable and is considered as a single object

There are \(n\) students in the class, and you are given an array \(s\) in non-decreasing order, where \(s_i\) is the shoe size of the \(i\)-th student. A shuffling of shoes is valid only if no student gets their own shoes and if every student gets shoes of size greater than or equal to their size

You have to output a permutation \(p\) of \(\{1,2,\ldots,n\}\) denoting a valid shuffling of shoes, where the \(i\)-th student gets the shoes of the \(p_i\)-th student (\(p_i \ne i\)). And output \(-1\) if a valid shuffling does not exist

A permutation 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 contains multiple test cases. The first line contains a single integer \(t\) (\(1 \le t \le 1000\)) — the number of test cases. Description of the test cases follows

The first line of each test case contains a single integer \(n\) (\(1\leq n\leq10^5\)) — the number of students

The second line of each test case contains \(n\) integers \(s_1, s_2,\ldots,s_n\) (\(1\leq s_i\leq10^9\), and for all \(1\le i<n\), \(s_i\le s_{i+1}\)) — the shoe sizes of the students

It is guaranteed that the sum of \(n\) over all test cases does not exceed \(10^5\)

Output

For each test case, print the answer in a single line using the following format

If a valid shuffling does not exist, print the number \(-1\) as the answer

If a valid shuffling exists, print \(n\) space-separated integers — a permutation \(p\) of \(1,2,\ldots,n\) denoting a valid shuffling of shoes where the \(i\)-th student gets the shoes of the \(p_i\)-th student. If there are multiple answers, then print any of them

Example

input

2
5
1 1 1 1 1
6
3 6 8 13 15 21

output

1 2	5 1 2 3 4 -1

Note

In the first test case, any permutation \(p\) of \(1,\ldots,n\) where \(p_i\ne i\) would represent a valid shuffling since all students have equal shoe sizes, and thus anyone can wear anyone's shoes

In the second test case, it can be shown that no valid shuffling is possible

代码参考

Show code

CodeForces_1691Bview raw

/*
 * @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)
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;
}
auto solve() -> void {
  int n;
  cin >> n;
  int pre, cnt = 1;
  cin >> pre;
  bool f = 0;
  vector<int> ans;
  ans.reserve(n);
  _for(i, 2, n, x) {
    cin >> x;
    if (f) continue;
    if (x == pre) {
      ++cnt;
      continue;
    }
    if (f |= cnt < 2) continue;
    ans.push_back(i - 1);
    _for(j, i - cnt, i - 2) ans.push_back(j);
    pre = x;
    cnt = 1;
  }
  if (cnt < 2 || f) {
    cout << "-1\n";
    return;
  }
  ans.push_back(n);
  _for(j, n - cnt + 1, n - 1) ans.push_back(j);
  for (int i : ans) cout << i << ' ';
  cout << '\n';
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  cout.tie(nullptr);
  int _t;
  cin >> _t;
  while (_t--) solve();
  return 0;
}

C - Sum of Substrings

You are given a binary string \(s\) of length \(n\)

Let's define \(d_i\) as the number whose decimal representation is \(s_i s_{i+1}\) (possibly, with a leading zero). We define \(f(s)\) to be the sum of all the valid \(d_i\). In other words, \(f(s) = \sum\limits_{i=1}^{n-1} d_i\)

For example, for the string \(s = 1011\):

\(d_1 = 10\) (ten);
\(d_2 = 01\) (one)
\(d_3 = 11\) (eleven);
\(f(s) = 10 + 01 + 11 = 22\)

In one operation you can swap any two adjacent elements of the string. Find the minimum value of \(f(s)\) that can be achieved if at most \(k\) operations are allowed

Input

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

First line of each test case contains two integers \(n\) and \(k\) (\(2 \le n \le 10^5\), \(0 \le k \le 10^9\)) — the length of the string and the maximum number of operations allowed

The second line of each test case contains the binary string \(s\) of length \(n\), consisting of only zeros and ones

It is also given that sum of \(n\) over all the test cases doesn't exceed \(10^5\)

Output

For each test case, print the minimum value of \(f(s)\) you can obtain with at most \(k\) operations

Example

input

output

1
2
3

21
22
12

Note

For the first example, you can't do any operation so the optimal string is \(s\) itself. \(f(s) = f(1010) = 10 + 01 + 10 = 21\)
For the second example, one of the optimal strings you can obtain is "0011000". The string has an \(f\) value of \(22\)
For the third example, one of the optimal strings you can obtain is "00011". The string has an \(f\) value of \(12\)

代码参考

Show code

CodeForces_1691Cview raw

/*
 * @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 _all(a) (a).begin(), (a).end()
#define _run_return_void(expressions) \
  {                                   \
    expressions;                      \
    return;                           \
  }
#define _run_break(expressions) \
  {                             \
    expressions;                \
    break;                      \
  }
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;
i64 sum[N];
auto solve() -> void {
  int n, k;
  cin >> n >> k;
  string s;
  cin >> s;
  auto tot1 = count_if(_all(s), [](const char ch) { return ch & 1; });
  if (tot1 == 0) _run_return_void(cout << "0\n");
  int cnt = 0;
  auto ends = s.rbegin();
  for (auto it = s.rbegin(); it != s.rend(); ++it) {
    if (*it & 1) _run_break(ends = it);
    ++cnt;
  }
  int cnt2 = 0;
  auto ends2 = s.begin();
  for (auto it = s.begin(); it != s.end(); ++it) {
    if (*it & 1) _run_break(ends2 = it);
    ++cnt2;
  }
  if (tot1 == 1) {
    if (k >= cnt) _run_return_void(cout << "1\n");
    if (k >= cnt2) _run_return_void(cout << "10\n");
    _run_return_void(cout << "11\n");
  }
  i64 ans = 11 * tot1;
  if (k >= cnt) {
    k -= cnt;
    ans -= 10;
  }
  if (k >= cnt2) {
    k -= cnt2;
    --ans;
  }
  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;
}

D - Max GEQ Sum

You are given an array \(a\) of \(n\) integers. You are asked to find out if the inequality

\[ \max(a_i, a_{i + 1}, \ldots, a_{j - 1}, a_{j}) \geq a_i + a_{i + 1} + \dots + a_{j - 1} + a_{j} \]

holds for all pairs of indices \((i, j)\), where \(1 \leq i \leq j \leq n\)

Input

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

The first line of each test case contains a single integer \(n\) (\(1 \leq n \leq 2 \cdot 10^5\)) — the size of the array

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

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

Output

For each test case, on a new line output "YES" if the condition is satisfied for the given array, and "NO" otherwise. You can print each letter in any case (upper or lower)

Example

input

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

output

1
2
3

YES
YES
NO

Note

In test cases \(1\) and \(2\), the given condition is satisfied for all \((i, j)\) pairs

In test case \(3\), the condition isn't satisfied for the pair \((1, 2)\) as \(\max(2, 3) < 2 + 3\)

代码参考

Show code

CodeForces_1691Dview raw

/*
 * @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 = 2e5 + OFFSET, M = 2e5 + OFFSET, K = 21;
template <size_t N,
          typename data_t,
          typename init_func = std::function<data_t(size_t)>,
          typename query_func =
            std::function<data_t(const data_t &, const data_t &)>>
class RMQ_ST {
protected:
  init_func ifunc;
  query_func qfunc;
  data_t f[(size_t)log2(N) + 1][N];
  size_t log_table[N];

public:
  RMQ_ST(init_func ifunc, query_func qfunc): ifunc(ifunc), qfunc(qfunc) {}
  void init(size_t n) {
    for (size_t i = 0; i <= n; ++i) f[0][i] = ifunc(i);
    for (size_t i = 1; i <= std::log2(n); ++i)
      for (size_t j = 0; j + (1 << i) - 1 <= n; ++j)
        f[i][j] = qfunc(f[i - 1][j], f[i - 1][j + (1 << (i - 1))]);
  }
  data_t query(size_t l, size_t r) const {
    size_t _ = std::log2(r - l + 1);
    return qfunc(f[_][l], f[_][r - (1 << _) + 1]);
  }
};
int a[N];
i64 sum[N];
RMQ_ST<N, int> max_a([](const size_t i) { return i; },
                     [](const int l, const int r) {
                       return a[l] < a[r] ? r : l;
                     });
RMQ_ST<N, i64> min_sum([](const size_t i) { return sum[i]; },
                       [](const i64 l, const i64 r) { return min(l, r); });
RMQ_ST<N, i64> max_sum([](const size_t i) { return sum[i]; },
                       [](const i64 l, const i64 r) { return max(l, r); });
bool dfs(int l, int r) {
  if (l >= r) return true;
  int now = max_a.query(l, r);
  i64 mins = min_sum.query(l - 1, now - 1), maxs = max_sum.query(now, r);
  if (a[now] < maxs - mins) return false;
  return dfs(l, now - 1) && dfs(now + 1, r);
}
auto solve() -> void {
  int n;
  cin >> n;
  _for(i, 1, n) cin >> a[i];
  _for(i, 1, n) sum[i] = sum[i - 1] + a[i];
  max_a.init(n);
  max_sum.init(n);
  min_sum.init(n);
  cout << (dfs(1, n) ? "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 - Number of Groups

You are given \(n\) colored segments on the number line. Each segment is either colored red or blue. The \(i\)-th segment can be represented by a tuple \((c_i, l_i, r_i)\). The segment contains all the points in the range \([l_i, r_i]\), inclusive, and its color denoted by \(c_i\):

if \(c_i = 0\), it is a red segment;
if \(c_i = 1\), it is a blue segment

We say that two segments of different colors are connected, if they share at least one common point. Two segments belong to the same group, if they are either connected directly, or through a sequence of directly connected segments. Find the number of groups of segments

Input

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

The first line of each test case contains a single integer \(n\) (\(1 \leq n \leq 10^5\)) — the number of segments

Each of the next \(n\) lines contains three integers \(c_i, l_i, r_i\) (\(0 \leq c_i \leq 1, 0 \leq l_i \leq r_i \leq 10^9\)), describing the \(i\)-th segment

It is guaranteed that the sum of \(n\) over all test cases does not exceed \(10^5\)

Output

For each test case, print a single integer \(k\), the number of groups of segments

Example

input

output

1
2

2
3

Note

In the first example there are \(5\) segments. The segments \(1\) and \(2\) are connected, because they are of different colors and share a point. Also, the segments \(2\) and \(3\) are connected, and so are segments \(4\) and \(5\). Thus, there are two groups: one containing segments \(\{1, 2, 3\}\), and the other one containing segments \(\{4, 5\}\)

代码参考

Show code

F - K-Set Tree

You are given a tree \(G\) with \(n\) vertices and an integer \(k\). The vertices of the tree are numbered from \(1\) to \(n\)

For a vertex \(r\) and a subset \(S\) of vertices of \(G\), such that \(|S| = k\), we define \(f(r, S)\) as the size of the smallest rooted subtree containing all vertices in \(S\) when the tree is rooted at \(r\). A set of vertices \(T\) is called a rooted subtree, if all the vertices in \(T\) are connected, and for each vertex in \(T\), all its descendants belong to \(T\)

You need to calculate the sum of \(f(r, S)\) over all possible distinct combinations of vertices \(r\) and subsets \(S\), where \(|S| = k\). Formally, compute the following:

\[ \sum_{r \in V} \sum_{S \subseteq V, |S| = k} f(r, S), \]

where \(V\) is the set of vertices in \(G\)

Output the answer modulo \(10^9 + 7\)

Input

The first line contains two integers \(n\) and \(k\) (\(3 \le n \le 2 \cdot 10^5\), \(1 \le k \le n\))

Each of the following \(n - 1\) lines contains two integers \(x\) and \(y\) (\(1 \le x, y \le n\)), denoting an edge between vertex \(x\) and \(y\)

It is guaranteed that the given edges form a tree

Output

Print the answer modulo \(10^9 + 7\)

Examples

input

1
2
3

3 2
1 2
1 3

output

input

output

Note

The tree in the second example is given below:

We have \(21\) subsets of size \(2\) in the given tree. Hence,

\[ S \in \left\{\{1, 2\}, \{1, 3\}, \{1, 4\}, \{1, 5\}, \{1, 6\}, \{1, 7\}, \{2, 3\}, \{2, 4\}, \{2, 5\}, \{2, 6\}, \{2, 7\}, \{3, 4\}, \{3, 5\}, \{3, 6\}, \{3, 7\}, \{4, 5\}, \{4, 6\}, \{4, 7\}, \{5, 6\}, \{5, 7\}, \{6, 7\} \right\}. \]

And since we have \(7\) vertices, \(1 \le r \le 7\). We need to find the sum of \(f(r, S)\) over all possible pairs of \(r\) and \(S\)

Below we have listed the value of \(f(r, S)\) for some combinations of \(r\) and \(S\)

\(r = 1\), \(S = \{3, 7\}\). The value of \(f(r, S)\) is \(5\) and the corresponding subtree is \(\{2, 3, 4, 6, 7\}\)
\(r = 1\), \(S = \{5, 4\}\). The value of \(f(r, S)\) is \(7\) and the corresponding subtree is \(\{1, 2, 3, 4, 5, 6, 7\}\)
\(r = 1\), \(S = \{4, 6\}\). The value of \(f(r, S)\) is \(3\) and the corresponding subtree is \(\{4, 6, 7\}\)

代码参考

Show code