[Solution] Distinct Neighbours CodeChef Solution

Problem

You are given an array $A$ of length $2\cdot N$.

You also have an empty array $B$. You are asked to do the following operation exactly $N$ times.

• Choose two distinct indices $x$ and $y$ $(1\le x,y \le |A|)$;
• Append $(A_x - A_y)$ to the end of array $B$;
• Delete the $x^{th}$ and $y^{th}$ elements from $A$ and concatenate remaining elements without changing the order.

Find whether there exists a set of operations to get array $B$ such that $B_i \neq B_{(i+1)}$ $(1 \leq i \lt N)$.

Input Format

• The first line of input contains a single integer $T$, denoting the number of test cases.
• Each test case consists of two lines of input.
  • The first line of each test case contains an integer $N$.
  • The second line of each test case contains $2\cdot N$ space-separated integers $A_1,A_2,\ldots,A_{2\cdot N}$ representing the array $A$.

Output Format

For each test case, print on a new line the answer: YES if it is possible to obtain valid $B$, and NO otherwise.

Each character of the output may be printed in either uppercase or lowercase, i.e, the strings Yes, YES, yes, yEs` will all be treated as identical.

Explanation:

Test case $1$: No matter how we perform the operations, $B=[0,0]$.

Test case $2$:

• In first operation, we can take $x=2$ and $y=3$. Now we append $A_x-A_y=1-2=-1$ at the back of $B$, and delete $A_2$ and $A_3$ from $A$. Now $A=[1,2,3,3]$.
• In second operation, we can take $x=2$ and $y=1$; append $A_x - A_y = 2-1 = 1$ at the back of $B$ and delete $A_2$ and $A_1$. Thus, $A = [3, 3]$ and $B = [-1, 1]$.
• In the third operation, we take $x=1$ and $y=2$; append $A_x - A_y = 3-3 = 0$ at the back of $B$ and delete $A_1$ and $A_2$. Thus, $A = []$ and $B = [-1, 1,0]$.

Thus, finally $B=[-1,1,0]$. There are no two consecutive elements in $B$ that are equal.

Test case $3$:

• In first operation, we can take $x=2$ and $y=3$. Now we append $A_x-A_y=1-2=-1$ at the back of $B$, and delete $A_2$ and $A_3$ from $A$. Now $A=[1,2]$.
• In second operation, we can take $x=2$ and $y=1$; append $A_x - A_y = 2-1 = 1$ at the back of $B$ and delete $A_2$ and $A_1$. Thus, $A = []$ and $B = [-1, 1]$.

Thus, finally $B=[-1,1]$. There are no two consecutive elements in $B$ that are equal.