April Long Two 2022 Division 4 (Rated)

 

Geometric Mean Inequality

You are given an array A$A$ of length N$N$ containing the elements −1$-1$ and 1$1$ only. Determine if it is possible to rearrange the array A$A$ in such a way that Ai$A_i$ is not the geometric mean of Ai−1$A_{i-1}$ and Ai+1$A_{i+1}$, for all i$i$ such that 2≤i≤N−1$2\le i\le N-1$.

Y$Y$ is said to be the geometric mean of X$X$ and Z$Z$ if Y2=X⋅Z$Y^2=X\cdot Z$.

Input Format

• The first line contains a single integer T$T$ - the number of test cases. Then the test cases follow.
• The first line of each test case contains an integer N$N$ - the size of the array A$A$.
• The second line of each test case contains N$N$ space-separated integers A1,A2,…,AN$A_1,A_2,\dots ,A_N$ denoting the array A$A$.

Output Format

For each test case, output Yes if it is possible to rearrange A$A$ in such a way that Ai$A_i$ is not the geometric mean of Ai−1$A_{i-1}$ and Ai+1$A_{i+1}$, where 2≤i≤N−1$2\le i\le N-1$. Otherwise output No.

You may print each character of Yes and No in uppercase or lowercase (for example, yes, yEs, YES will be considered identical).

Constraints

• 1≤T≤200$1\le T\le 200$
• 3≤N≤1000$3\le N\le 1000$
• Ai∈{−1,1}$A_i\in \{-1,1\}$

Sample Input 1 

3
5
1 1 1 -1 -1
3
1 1 1
6
1 -1 -1 -1 -1 1

Sample Output 1 

Yes
No
Yes

Explanation

Test case 1: We can rearrange the array A$A$ to [1,1,−1,−1,1]$[1,1,-1,-1,1]$. One can see that Ai2≠Ai−1⋅Ai+1${A_i}^2\ne A_{i-1}\cdot A_{i+1}$, for any 2≤i≤N−1$2\le i\le N-1$.

Test case 2: None of the rearrangements of A$A$ satisy the given condition.

Solution :

#include <iostream>

using namespace std;

int yes(){

    cout<<"YES"<<endl;

    return 0;

}

int no(){

    cout<<"NO"<<endl;

    return 0;

}

int main() {

    int t; cin>>t;

    int n;

    while(t--){

        cin>>n;

        int a[n];

        int b=0,c=0;

        for(int i=0; i<n;i++){

            cin>>a[i]; 

            if(a[i]==-1) b++; else c++;

        }

        int r=abs(b-c);

        if(r<2) yes();

        else if(r==2) {

            if(b%2) no();

            else yes();

        }

        else no();

    }

return 0;

}