PROBLEM LINK:
Author: Krish Murarka
Tester: Abhinav Prakash
DIFFICULTY:
Medium.
PREREQUISITES:
Math.
PROBLEM:
Your task is to choose any two students standing at i and j location and interchange their
position. You can perform this operation any number of times possibly zero times .such that
after performing all operations, no three consecutive students should be having the same
number.
So, your task to tell whether it is possible to arrange the students in a row.
QUICK EXPLANATION:
Input-
5
1 2 1 2 3
Output-
YES
In the first step, we can swap the students standing at positions 3 and 5 having
values 1 and 3 respectively.
After 1st swap arrangement becomes 1 2 3 2 1
Now we can swap 4 and 5th student
And our arrangement becomes 1 2 3 1 2 and here you can see no three consecutive
students are having the same value
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#define endl "\n"
#define ll long long int
#define vi vector<int>
#define vll vector<ll>
#define vvi vector < vi >
#define pii pair<int,int>
#define pll pair<long long, long long>
#define mod 1000000007
#define inf 1000000000000000001;
#define all(c) c.begin(),c.end()
#define mp(x,y) make_pair(x,y)
#define mem(a,val) memset(a,val,sizeof(a))
#define eb emplace_back
#define f first
#define s second
#define pb push_back
using namespace std;
void solving()
{
int n;
cin>>n;
ll a[n];
ll sum=0;
map<int,int> mi;
for(int i=0;i<n;i++)
{
cin>>a[i];
//sum+=a[i];
mi[a[i]]++;
}
int maxi=ceil(n/3);
bool ok=true;
for(auto i: mi)
{
if(i.second>maxi)
{
ok=false;
break;
}
}
if(ok)
cout<<"YES\n";
else
cout<<"NO\n";
}
int main()
{
int t;
cin>>t;
while(t-->0)
{
solving();
}
return 0;
}