Codeforces Global Round 9
A. Sign Flipping
You are given integers , where is odd. You are allowed to flip the sign of some (possibly all or none) of them. You wish to perform these flips in such a way that the following conditions hold:
- At least of the adjacent differences for are greater than or equal to .
- At least of the adjacent differences for are less than or equal to .
Find any valid way to flip the signs. It can be shown that under the given constraints, there always exists at least one choice of signs to flip that satisfies the required condition. If there are several solutions, you can find any of them.
Input
The input consists of multiple test cases. The first line contains an integer — the number of test cases. The description of the test cases follows.
The first line of each test case contains an integer (, is odd) — the number of integers given to you.
The second line of each test case contains integers — the numbers themselves.
It is guaranteed that the sum of over all test cases does not exceed .
Output
For each test case, print n integers , corresponding to the integers after flipping signs. has to be equal to either or , and of the adjacent differences for , at least should be non-negative and at least should be non-positive.
It can be shown that under the given constraints, there always exists at least one choice of signs to flip that satisfies the required condition. If there are several solutions, you can find any of them.
Example
input
5
3
-2 4 3
5
1 1 1 1 1
5
-2 4 7 -6 4
9
9 7 -4 -2 1 -3 9 -4 -5
9
-4 1 9 4 8 9 5 1 -9
output
-2 -4 3
1 1 1 1 1
-2 -4 7 -6 4
-9 -7 -4 2 1 -3 -9 -4 -5
4 -1 -9 -4 -8 -9 -5 -1 9
Note
In the first test case, the difference is non-positive, while the difference is non-negative.
In the second test case, we don’t have to flip any signs. All differences are equal to , which is both non-positive and non-negative.
In the third test case, and are non-negative, while and are non-positive.
Idea
智商测试题。类似这样的构造问题,样例会误导选手,需要自己思考。
事实上, 个数正负交错排列,即可满足条件。
Code
1 |
|
B. Neighbor Grid
You are given a grid with rows and columns, where each cell has a non-negative integer written on it. We say the grid is good if for each cell the following condition holds: if it has a number written on it, then exactly of its neighboring cells have a number greater than written on them. Note that if the number in the cell is , there is no such restriction on neighboring cells.
You are allowed to take any number in the grid and increase it by . You may apply this operation as many times as you want, to any numbers you want. Perform some operations (possibly zero) to make the grid good, or say that it is impossible. If there are multiple possible answers, you may find any of them.
Two cells are considered to be neighboring if they have a common edge.
Input
The input consists of multiple test cases. The first line contains an integer — the number of test cases. The description of the test cases follows.
The first line of each test case contains two integers and — the number of rows and columns, respectively.
The following lines contain integers each, the -th element in the -th line is the number written in the -th cell of the -th row .
It is guaranteed that the sum of over all test cases does not exceed .
Output
If it is impossible to obtain a good grid, print a single line containing “NO”.
Otherwise, print a single line containing “YES”, followed by lines each containing integers, which describe the final state of the grid. This final grid should be obtainable from the initial one by applying some operations (possibly zero).
If there are multiple possible answers, you may print any of them.
Example
input
5
3 4
0 0 0 0
0 1 0 0
0 0 0 0
2 2
3 0
0 0
2 2
0 0
0 0
2 3
0 0 0
0 4 0
4 4
0 0 0 0
0 2 0 1
0 0 0 0
0 0 0 0
output
YES
0 0 0 0
0 1 1 0
0 0 0 0
NO
YES
0 0
0 0
NO
YES
0 1 0 0
1 4 2 1
0 2 0 0
1 3 1 0
Note
In the first test case, we can obtain the resulting grid by increasing the number in row , column once. Both of the cells that contain have exactly one neighbor that is greater than zero, so the grid is good. Many other solutions exist, such as the grid $\begin{pmatrix}0&1&0&0\\0&2&1&0\\0&0&0&0\end{pmatrix}$, all of them are accepted as valid answers.
In the second test case, it is impossible to make the grid good.
In the third test case, notice that no cell has a number greater than zero on it, so the grid is automatically good.
Idea
对于一个矩阵,其四个角上的元素只有两个相邻元素,边界上(除四个顶点)的元素有三个相邻元素,其余位置上的元素都有四个相邻元素。因此,形如 $EX=\begin{pmatrix}2&3&3&3&2\\3&4&4&4&3\\2&3&3&3&2\end{pmatrix}$ 的矩阵都是满足条件的 good gird 。
给定 ,可以构造形如 的矩阵,称该矩阵为 ;其四个顶点元素的值为 ,边界上(除四个顶点)的元素值为 ,其余位置元素的值为 。 内各个元素的值不能更大,否则不满足形成 good gird 的条件。因此,若读入的矩阵中 $a_{i,j}>base_{i,j} $,那么就无法经过操作得到 good gird;否则,增大 使得 。
Code
1 |
|
Postscript
注意数据范围,读入矩阵时不能用 类型。
C. Element Extermination
You are given an array a of length , which initially is a permutation of numbers from to . In one operation, you can choose an index such that , and remove either or from the array (after the removal, the remaining parts are concatenated).
For example, if you have the array , you can choose (since ), then either remove which gives the new array , or remove which gives the new array .
Is it possible to make the length of this array equal to with these operations?
Input
The first line contains a single integer — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer — the length of the array.
The second line of each test case contains integers (, are pairwise distinct) — elements of the array.
It is guaranteed that the sum of over all test cases doesn’t exceed .
Output
For each test case, output on a single line the word “YES” if it is possible to reduce the array to a single element using the aforementioned operation, or “NO” if it is impossible to do so.
Example
input
4
3
1 2 3
4
3 1 2 4
3
2 3 1
6
2 4 6 1 3 5
output
YES
YES
NO
YES
Note
For the first two test cases and the fourth test case, we can operate as follow (the bolded elements are the pair chosen for that operation):
.
Idea
可行的情况是 。下面给出证明。
若 。首先,从左向右找到距离 最近的元素 ,使得 ;那么 之间的元素都小于 ,可删除。如此一来 就与 相邻,可以将 删除。重复上述步骤,最终 就会与 相邻,最后将 删除留下 。
若 。注意到,若要删除 ,需要找到 ,那么序列最左端的值是递增的,因此序列最左端元素始终大于 ,不能将序列长度变为 ;若要删除 ,需要找到 ,那么序列最右端的值是递减的,因此序列最后端元素始终小于 ,不能将长度变为 。
Code
1 |
|
D. Replace by MEX
You’re given an array of integers between and inclusive.
In one operation, you can choose any element of the array and replace it by the MEX of the elements of the array (which may change after the operation).
For example, if the current array is , you can choose the second element and replace it by the MEX of the present elements — . Array will become .
You must make the array non-decreasing, using at most operations.
It can be proven that it is always possible. Please note that you do not have to minimize the number of operations. If there are many solutions, you can print any of them.
An array is non-decreasing if and only if .
The MEX (minimum excluded) of an array is the smallest non-negative integer that does not belong to the array. For instance:
- The MEX of is , because does not belong to the array.
- The MEX of is , because and belong to the array, but does not.
- The MEX of is because and belong to the array, but does not.
It’s worth mentioning that the MEX of an array of length is always between and inclusive.
Input
The first line contains a single integer — the number of test cases. The description of the test cases follows.
The first line of each test case contains a single integer — length of the array.
The second line of each test case contains integers — elements of the array. Note that they don’t have to be distinct.
It is guaranteed that the sum of over all test cases doesn’t exceed .
Output
For each test case, you must output two lines:
The first line must contain a single integer — the number of operations you perform.
The second line must contain integers , where is the index chosen for the -th operation.
If there are many solutions, you can find any of them. Please remember that it is not required to minimize .
Example
input
5
3
2 2 3
3
2 1 0
7
0 7 3 1 3 7 7
9
2 0 1 1 2 4 4 2 0
9
8 4 7 6 1 2 3 0 5
output
0
2
3 1
4
2 5 5 4
11
3 8 9 7 8 5 9 6 4 1 2
10
1 8 1 9 5 2 4 6 3 7
Note
In the first test case, the array is already non-decreasing .
Explanation of the second test case (the element modified by each operation is colored in red):
; the initial MEX is .
; the new MEX is .
; the new MEX is .
The final array is non-decreasing: .
Explanation of the third test case:
; the initial MEX is .
; the new MEX is .
; the new MEX is .
; the new MEX is .
; the new MEX is .
The final array is non-decreasing: .
Idea
考虑到长度为 的序列,,可以将原数组替换成 。
序列 的特征是 。若当前数组 $a $ 的 ,直接替换:。 若 ,找一个位置 ,满足 ,令 ,再求一次 ,此时 必然大于 ,直接替换 。
不满足 的位置最多有 个,要让 至多要进行两次替换,因此操作次数不会超过 次。
Code
1 |
|
E. Inversion Swap Sort
Madeline has an array of integers. A pair of integers forms an inversion in if: , .
Madeline recently found a magical paper, which allows her to write two indices and and swap the values and . Being bored, she decided to write a list of pairs with the following conditions: all the pairs in the list are distinct and form an inversion in , all the pairs that form an inversion in are in the list.
Starting from the given array, if you swap the values at indices and , then the values at indices and and so on, then after all pairs are processed, the array will be sorted in non-decreasing order.
Construct such a list or determine that no such list exists. If there are multiple possible answers, you may find any of them.
Input
The first line of the input contains a single integer — the length of the array.
Next line contains integers — elements of the array.
Output
Print if no such list exists. Otherwise in the first line you should print a single integer — number of pairs in the list.
The -th of the following lines should contain two integers .
If there are multiple possible answers, you may find any of them.
Examples
input
3
3 1 2
output
2
1 3
1 2
input
4
1 8 1 6
output
2
2 4
2 3
input
5
1 1 1 2 2
output
0
Note
In the first sample test case the array will change in this order .
In the second sample test case it will be .
In the third sample test case the array is already sorted.
Idea
首先考虑 是 全排列时的做法。
设 表示 这个数在 中出现的位置。
从边界入手,先尝试把 放到排列的最后一个位置,然后转化为规模减一的子问题。假设操作后,我们得到的排列为 ,要求 满足:;,若 ,则 ;,若 ,则 。也就是说,要保证前面的数的相对大小关系不变,这样才能转化为一个等价的子问题。我们可以依次交换索引对应的值:。举例,操作 的过程:。容易发现,这样一轮操作完成后, 被放到了最后;同时,相当于前面所有大于 的数,全部减去 ;因此,显然前面所有数的相对大小关系不变,剩下的是一个规模更小的子问题。接着以索引 的位置为末尾,将数值 放到最后。不断重复,即可得到一个标准排列。
基于以上,当 是一个全排列时,一定有解。
现在考虑 不是全排列的时候。事实上,可以设置数值为第一关键字,位置为第二关键字,强行转成一个全排列。举例,,重新赋值转换为全排列后 。发现转成全排列后,序列里的逆序对个数和原来是一样的。可以进行略证: 中 是逆序对,重新赋值后为 ,由于对于,相同数字,位置靠后的重新赋值后数值也更大,不会产生逆序对,所以逆序对个数是和原来一样的。
综上所述,对于任意的数组 ,将 经过转换后直接按全排列求解即可。对于一个全排列,总的交换次数至多为 ,满足题目限制条件。
时间复杂度 。
Postscript
智商有待提高 。
Code
1 |
|