版权声明： 本博客所有文章除特别声明外，均采用 BY-NC-SA 许可协议。转载请注明出处！
title: "比赛记录 - CodeCraft-22 and Codeforces Round #795 (Div. 2) (A-D)" categories:
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
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$
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
2
5
2 4 3 6 8
6
3 5 9 7 1 3
1
0
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
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)
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$, $si\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$
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
2
5
1 1 1 1 1
6
3 6 8 13 15 21
5 1 2 3 4
-1
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
You are given a binary string $s$ of length $n$
Let's define $d_i$ as the number whose decimal representation is $si s{i+1}$ (possibly, with a leading zero). We define $f(s)$ to be the sum of all the valid $di$. In other words, $f(s) = \sum\limits{i=1}^{n-1} d_i$
For example, for the string $s = 1011$:
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
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$
For each test case, print the minimum value of $f(s)$ you can obtain with at most $k$ operations
3
4 0
1010
7 1
0010100
5 2
00110
21
22
12
You are given an array $a$ of $n$ integers. You are asked to find out if the inequality
$$ \max(ai, a{i + 1}, \ldots, a{j - 1}, a{j}) \geq ai + 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$
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$
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)
3
4
-1 1 -1 2
5
-1 2 -3 2 -1
3
2 3 -1
YES
YES
NO
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$
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$:
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
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$
For each test case, print a single integer $k$, the number of groups of segments
2
5
0 0 5
1 2 12
0 4 7
1 9 16
0 13 19
3
1 0 1
1 1 2
0 3 4
2
3
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}$
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$
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
Print the answer modulo $10^9 + 7$
3 2
1 2
1 3
25
7 2
1 2
2 3
2 4
1 5
4 6
4 7
849
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$