Codeforces Global Round 9

A. Sign Flipping $\looparrowright$

You are given $n$ integers $a_1,a_2,\cdots,a_n$, where $n$ 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:

1. At least $\frac{n−1}{2}$ of the adjacent differences $a_{i+1}−a_i$ for $i=1,2,\cdots,n−1$ are greater than or equal to $0$.
2. At least $\frac{n−1}{2}$ of the adjacent differences $a_{i+1}−a_i$ for $i=1,2,\cdots,n−1$ are less than or equal to $0$.
   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 $t$$(1≤t≤500)$ — the number of test cases. The description of the test cases follows.
The first line of each test case contains an integer $n$ ($3≤n≤99$, $n$ is odd) — the number of integers given to you.
The second line of each test case contains $n$ integers $a_1,a_2,\cdots,a_n$ $(−10^9≤a_i≤10^9)$ — the numbers themselves.
It is guaranteed that the sum of $n$ over all test cases does not exceed $10000$.

Output

For each test case, print n integers $b_1,b_2,\cdots,b_n$, corresponding to the integers after flipping signs. $b_i$ has to be equal to either $a_i$ or $−a_i$, and of the adjacent differences $b_{i+1}−b_i$ for $i=1,\cdots,n−1$, at least $\frac{n−1}{2}$ should be non-negative and at least $\frac{n−1}{2}$ 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 $(−4)−(−2)=−2$ is non-positive, while the difference $3−(−4)=7$ is non-negative.
In the second test case, we don’t have to flip any signs. All $4$ differences are equal to $0$, which is both non-positive and non-negative.
In the third test case, $7−(−4)$ and $4−(−6)$ are non-negative, while $(−4)−(−2)$ and $(−6)−7$ are non-positive.

Idea

智商测试题。类似这样的构造问题，样例会误导选手，需要自己思考。
事实上，$n$ 个数正负交错排列，即可满足条件。

Code

#include<iostream>
#include<cmath>
#include<cstdio>
using namespace std;
int main()
{
	int _;
	for(cin>>_;_;_--)
	{
		int n;
		scanf("%d",&n);
		int i;
		for(i=1;i<=n;i++)
		{
			int x;
			scanf("%d",&x);
			//交错排列
			printf("%d ",i&1?-abs(x):abs(x));
		}
		putchar('\n');
	}
	return 0;
}

B. Neighbor Grid $\looparrowright$

You are given a grid with $n$ rows and $m$ 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 $k>0$ written on it, then exactly $k$ of its neighboring cells have a number greater than $0$ written on them. Note that if the number in the cell is $0$, there is no such restriction on neighboring cells.
You are allowed to take any number in the grid and increase it by $1$. 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 $t$ $(1≤t≤5000)$ — the number of test cases. The description of the test cases follows.
The first line of each test case contains two integers $n$ and $m$ $(2≤n,m≤300)$ — the number of rows and columns, respectively.
The following $n$ lines contain $m$ integers each, the $j$-th element in the $i$-th line $a_{i,j}$ is the number written in the $j$-th cell of the $i$-th row $(0≤a_{i,j}≤10^9)$.
It is guaranteed that the sum of $n\times m$ over all test cases does not exceed $10^5$.

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 $n$ lines each containing $m$ 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 $2$, column $3$ once. Both of the cells that contain $1$ 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 。
给定 $n,m$，可以构造形如 $EX$ 的矩阵，称该矩阵为 $base$；其四个顶点元素的值为 $2$，边界上（除四个顶点）的元素值为 $3$，其余位置元素的值为 $4$。$base$ 内各个元素的值不能更大，否则不满足形成 good gird 的条件。因此，若读入的矩阵中 $a_{i,j}>base_{i,j} $，那么就无法经过操作得到 good gird；否则，增大 $a_{i,j}$ 使得 $a_{i,j}=base_{i,j}$。

Code

#include<iostream>
#include<cstdio>
#define N 302
using namespace std;
short base[N][N];
int n,m;
int main()
{
	int _;
	for(cin>>_;_;_--)
	{
		int n;
		scanf("%d%d",&n,&m);
		int i,j;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
				//------------------------------------------------------------------------
				//顶点为2
				//边界为3
				//中部为4
				if((i==1&&j==1)||(i==1&&j==m)||(i==n&&j==1)||(i==n&&j==m)) base[i][j]=2;
				else if(i==1||i==n||j==1||j==m) base[i][j]=3;
				else base[i][j]=4;
				//------------------------------------------------------------------------
			}
		}
		bool ok=1;
		for(i=1;i<=n;i++)
		{
			for(j=1;j<=m;j++)
			{
				int x;
				scanf("%d",&x);
				if(x>base[i][j]) ok=0;
			}
		}
		if(ok)
		{
			puts("YES");
			for(i=1;i<=n;i++)
			{
				for(j=1;j<=m;j++)
				{
					printf("%hd ",base[i][j]);
				}
				putchar('\n');
			}
		}
		else puts("NO");
	}
	return 0;
}

Postscript

注意数据范围，读入矩阵时不能用 $\text{short}$ 类型。

C. Element Extermination $\looparrowright$

You are given an array a of length $n$, which initially is a permutation of numbers from $1$ to $n$. In one operation, you can choose an index $i$ $(1≤i<n)$ such that $a_i<a_{i+1}$, and remove either $a_i$ or $a_{i+1}$ from the array (after the removal, the remaining parts are concatenated).
For example, if you have the array $[1,3,2]$, you can choose $i=1$ (since $a_1=1<a_2=3$), then either remove $a_1$ which gives the new array $[3,2]$, or remove $a_2$ which gives the new array $[1,2]$.
Is it possible to make the length of this array equal to $1$ with these operations?

Input

The first line contains a single integer $t$ $(1≤t≤2\times 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$ $(2≤n≤3\times 10^5)$ — the length of the array.
The second line of each test case contains $n$ integers $a_1, a_2, \cdots, a_n$ ($1≤a_i≤n$, $a_i$ are pairwise distinct) — elements of the array.
It is guaranteed that the sum of $n$ over all test cases doesn’t exceed $3\times 10^5$.

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):
$[1,2,3]→[1,2]→[1]$
$[3,1,2,4]→[3,1,4]→[3,4]→[4]$
$[2,4,6,1,3,5]→[4,6,1,3,5]→[4,1,3,5]→[4,1,5]→[4,5]→[4]$.

Idea

可行的情况是 $a_1<a_n$。下面给出证明。
若 $a_1<a_n$。首先，从左向右找到距离 $a_1$ 最近的元素 $a_r$，使得 $a_r>a_1$；那么 $a_1\sim a_r$ 之间的元素都小于 $a_r$，可删除。如此一来 $a_1$ 就与 $a_r$ 相邻，可以将 $a_r$ 删除。重复上述步骤，最终 $a_1$ 就会与 $a_n$ 相邻，最后将 $a_n$ 删除留下 $a_1$。
若 $a_1\ge a_n$。注意到，若要删除 $a_1$，需要找到 $a_r>a_1$，那么序列最左端的值是递增的，因此序列最左端元素始终大于 $a_n$，不能将序列长度变为 $1$；若要删除 $a_n$，需要找到 $a_r<a_n$，那么序列最右端的值是递减的，因此序列最后端元素始终小于 $a_1$，不能将长度变为 $1$。

Code

#include<cstdio>
#include<iostream>
#define N 300002
using namespace std;
int a[N];
int n;
int main()
{
	int _;
	for(cin>>_;_;_--)
	{
		scanf("%d",&n);
		int i;
		for(i=1;i<=n;i++) scanf("%d",a+i);
		puts(a[1]<a[n]?"YES":"NO");
	}
	return 0;
}

D. Replace by MEX $\looparrowright$

You’re given an array of $n$ integers between $0$ and $n$ 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 $[0,2,2,1,4]$, you can choose the second element and replace it by the MEX of the present elements — $3$. Array will become $[0,3,2,1,4]$.
You must make the array non-decreasing, using at most $2n$ 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 $b[1\cdots n]$ is non-decreasing if and only if $b_1≤b_2≤\cdots≤b_n$.
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 $[2,2,1]$ is $0$, because $0$ does not belong to the array.
• The MEX of $[3,1,0,1]$ is $2$, because $0$ and $1$ belong to the array, but $2$ does not.
• The MEX of $[0,3,1,2]$ is $4$ because $0, 1, 2$ and $3$ belong to the array, but $4$ does not.

It’s worth mentioning that the MEX of an array of length $n$ is always between $0$ and $n$ inclusive.

Input

The first line contains a single integer $t$ $(1≤t≤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≤n≤1000)$ — length of the array.
The second line of each test case contains $n$ integers $a_1,\cdots,a_n$ $(0≤a_i≤n)$ — elements of the array. Note that they don’t have to be distinct.
It is guaranteed that the sum of $n$ over all test cases doesn’t exceed $1000$.

Output

For each test case, you must output two lines:
The first line must contain a single integer $k$ $(0≤k≤2n)$ — the number of operations you perform.
The second line must contain $k$ integers $x_1,\cdots,x_k$ $(1≤x_i≤n)$, where $x_i$ is the index chosen for the $i$-th operation.
If there are many solutions, you can find any of them. Please remember that it is not required to minimize $k$.

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 $(2≤2≤3)$.
Explanation of the second test case (the element modified by each operation is colored in red):
$a=[2,1,0]$ ; the initial MEX is $3$.
$a=[2,1,{\color {red} 3}]$ ; the new MEX is $0$.
$a = [{\color{red}{0}}, 1, 3]$ ; the new MEX is $2$.
The final array is non-decreasing: $0≤1≤3$.
Explanation of the third test case:
$a=[0,7,3,1,3,7,7]$ ; the initial MEX is $2$.
$a=[0,{\color{red}2},3,1,3,7,7]$ ; the new MEX is $4$.
$a=[0,2,3,1,{\color{red}4},7,7]$ ; the new MEX is $5$.
$a=[0,2,3,1,{\color{red}{5}},7,7]$ ; the new MEX is $4$.
$a=[0,2,3,{\color{red}{4}},5,7,7]$ ; the new MEX is $1$.
The final array is non-decreasing: $0≤2≤3≤4≤5≤7≤7$.

Idea

考虑到长度为 $n$ 的序列，$0\le \mathrm {mex}\le n$，可以将原数组替换成 $[1,2,\cdots,n]$。
序列 $[1,2,\cdots,n]$ 的特征是 $a_i=i$。若当前数组 $a $ 的 $\mathrm{mex}>0$，直接替换：$a_{\mathrm{mex}}=\mathrm{mex}$。 若 $\mathrm{mex}=0$，找一个位置 $i$，满足 $a_i\ne i$，令 $a_i=0$，再求一次 $\mathrm{mex}$，此时 $\mathrm{mex}$ 必然大于 $0$，直接替换 $a_{\mathrm{mex}}=\mathrm{mex}$。
不满足 $a_i=i$ 的位置最多有 $n$ 个，要让 $a_{\mathrm{mex}}=\mathrm{mex}$ 至多要进行两次替换，因此操作次数不会超过 $n$ 次。

Code

#include<cstdio>
#include<vector>
#include<cstring>
#include<iostream>
#define N 1003
using namespace std;
int a[N];
int n;
vector<int>ans;
bool vis[N];
int cal_mex()
{
	//计算mex
	memset(vis,0,sizeof(vis));
	int i;
	for(i=1;i<=n;i++) vis[a[i]]=1;
	for(i=0;i<=n;i++) if(!vis[i]) return i;
}
int main()
{
	int _;
	for(cin>>_;_;_--)
	{
		scanf("%d",&n);
		int i;
		ans.clear();
		for(i=1;i<=n;i++) scanf("%d",a+i);
		while(true)
		{
			bool ok=1;
			for(i=1;i<=n;i++)
			{
				if(a[i]!=i)
				{
					ok=0;
					break;
				}
			}
			if(ok) break;
			int mex=cal_mex();
			if(!mex)//mex=0,算两次
			{
				for(i=1;i<=n;i++)
				{
					if(a[i]!=i) 
					{
						a[i]=0;
						ans.push_back(i);
						break;
					}
				}
				mex=cal_mex();
				a[mex]=mex;
				ans.push_back(mex);
			}
			else//mex>0直接替换
			{
				a[mex]=mex;
				ans.push_back(mex);
			}
		}
		printf("%d\n",ans.size());
		for(auto v:ans) printf("%d ",v);
		putchar('\n');
	}
	return 0;
}

E. Inversion Swap Sort $\looparrowright$

Madeline has an array $a$ of $n$ integers. A pair $(u,v)$ of integers forms an inversion in $a$ if: $1≤u<v≤n$, $a_u>a_v$.
Madeline recently found a magical paper, which allows her to write two indices $u$ and $v$ and swap the values $a_u$ and $a_v$. Being bored, she decided to write a list of pairs $(u_i,v_i)$ with the following conditions: all the pairs in the list are distinct and form an inversion in $a$, all the pairs that form an inversion in $a$ are in the list.
Starting from the given array, if you swap the values at indices $u_1$ and $v_1$, then the values at indices $u_2$ and $v_2$ and so on, then after all pairs are processed, the array $a$ 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 $n$ $(1≤n≤1000)$ — the length of the array.
Next line contains $n$ integers $a_1,a_2,\cdots,a_n$ $(1≤a_i≤10^9)$ — elements of the array.

Output

Print $-1$ if no such list exists. Otherwise in the first line you should print a single integer $m$ $\left(0≤m≤\frac{n(n−1)}{2}\right)$ — number of pairs in the list.
The $i$-th of the following $m$ lines should contain two integers $u_i,v_i$ $(1≤u_i<v_i≤n)$.
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 $[3,1,2]$$→$$[2,1,3]$$→$$[1,2,3]$.
In the second sample test case it will be $[1,8,1,6]→[1,6,1,8]→[1,1,6,8]$.
In the third sample test case the array is already sorted.

Idea

首先考虑 $a$ 是 $1\sim n$ 全排列时的做法。
设 $pos_x$ 表示 $x$ 这个数在 $a$ 中出现的位置。
从边界入手，先尝试把 $n$ 放到排列的最后一个位置，然后转化为规模减一的子问题。假设操作后，我们得到的排列为 $b$，要求 $b$ 满足：$b_n=n$；$∀\ 1≤i,j<n$，若 $a_i<a_j$，则 $b_i<b_j$；$∀ 1≤i,j<n$，若 $a_i>a_j$，则 $b_i>b_j$。也就是说，要保证前面的数的相对大小关系不变，这样才能转化为一个等价的子问题。我们可以依次交换索引对应的值：$(pos_{a_n+1},n)$$,$$(pos_{a_n+2},n)$$,$$(pos_{a_n+3},n)$$,$$\cdots$$,$$(pos_n,n)$。举例，操作 $[1,5,3,4,2]$ 的过程：$[1,5,3,4,2]$$\rightarrow$$[1,5,2,4,3]$$\rightarrow$$[1,5,2,3,4]$$\rightarrow$$[1,4,2,3,5]$。容易发现，这样一轮操作完成后，$n$ 被放到了最后；同时，相当于前面所有大于 $a_n$的数，全部减去 $1$；因此，显然前面所有数的相对大小关系不变，剩下的是一个规模更小的子问题。接着以索引 $n-1$ 的位置为末尾，将数值 $n-1$ 放到最后。不断重复，即可得到一个标准排列。
基于以上，当 $a$ 是一个全排列时，一定有解。
现在考虑 $a$ 不是全排列的时候。事实上，可以设置数值为第一关键字，位置为第二关键字，强行转成一个全排列。举例，$a=[1,4,3,5,3,1]$，重新赋值转换为全排列后 $a=[1,5,3,6,4,2]$。发现转成全排列后，序列里的逆序对个数和原来是一样的。可以进行略证：$a,a,c$ 中$(1,3)$ 是逆序对，重新赋值后为 $2,3,1$，由于对于，相同数字，位置靠后的重新赋值后数值也更大，不会产生逆序对，所以逆序对个数是和原来一样的。
综上所述，对于任意的数组 $a$，将 $a$ 经过转换后直接按全排列求解即可。对于一个全排列，总的交换次数至多为 $(n-1)+(n-2)+\cdots+1=\frac{n(n-1)}{2}$，满足题目限制条件。
时间复杂度 $O(n^2)$。

Postscript

智商有待提高 $\mathrm{Orz}$。

Code

#include<map>
#include<utility>
#include<iostream>
#include<vector>
#include<algorithm>
#include<cstdio>
#define N 1003
using namespace std;
pair<int,int>a[N];//按照（位置，数值）排序
map<pair<int,int>,int>temp;//记录排序后(位置，数值)的序号
int num[N];//初始数组
int permutation[N];//重新赋值得到的全排列
int n;
vector<pair<int,int>>ans;//记录答案
int pos[N];//存数值的位置
int main()
{
	cin>>n;
	int i,j; 
	for(i=1;i<=n;i++) scanf("%d",num+i);
	//----------------------------------------------------------------
	//数值为第一关键字
	//位置为第二关键字
	for(i=1;i<=n;i++)
	{
		a[i].second=num[i];
		a[i].first=i;
	}
	//first 位置
	//second 数值
	//排序
	sort(a+1,a+1+n,[](const pair<int,int>& x,const pair<int,int>& y){
		if(x.second==y.second) return x.first<y.first;
		else return x.second<y.second;});
	//-----------------------------------------------------------------
	//-----------------------------------------------------------------
	//得到（位置，数值）排序后的序号
	for(i=1;i<=n;i++) temp[make_pair(a[i].first,a[i].second)]=i;
	//初始序列中位置为i，数值为num[i]
	//重新赋值，形成全排列
	for(i=1;i<=n;i++) permutation[i]=temp[make_pair(i,num[i])];
	//-----------------------------------------------------------------
	//-----------------------------------------------------------------
	for(i=n;i>=1;i--)
	{
		//记录[1,i]各个数值的位置
		for(j=1;j<=i;j++) pos[permutation[j]]=j;
		//swap(permutation[pos[permutation[i]+1]],permutation[i])
		//swap(permutation[pos[permutation[i]+2]],permutation[i])
		//...........
		//swap(permutation[pos[i]],permutation[i])
		for(j=permutation[i]+1;j<=i;j++) 
		{
			swap(permutation[i],permutation[pos[j]]);
			ans.push_back(make_pair(pos[j],i));//记录答案
		}
	}
	//-----------------------------------------------------------------
	cout<<ans.size()<<endl;
	for(auto v:ans) printf("%d %d\n",v.first,v.second);
	return 0;
}