PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Ritul Kumar Singh
Testers: Nishank Suresh, Satyam
Editorialist: Nishank Suresh
DIFFICULTY:
1648
PREREQUISITES:
None
PROBLEM:
You have an array A. In one move you can choose two integers i \lt j such that A_i = A_j and set A_k = A_i for each i \lt k \lt j.
Can you perform operations such that A has at most two distinct elements in the end?
EXPLANATION:
First, if A_1 = A_N, the answer is clearly “Yes”: just make the entire array equal.
Otherwise, notice that the operation cannot change A_1 or A_N, so our only hope is to have the two distinct elements in the array be these two.
So, the only reasonable moves to make are those starting at i = 1 or those ending at j = N.
This immediately means the answer is “Yes” if and only if there exists an index i such that A_i = A_1 and A_{i+1} = A_N.
This can be checked easily with a simple for
loop.
TIME COMPLEXITY
\mathcal{O}(N) per test case.
CODE:
Setter's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define sp << ' ' <<
#define nl << '\n'
signed main() {
cin.tie(0)->sync_with_stdio(0);
int T; cin >> T;
while(T--) {
int N; cin >> N;
int A[N];
for(int &i : A) cin >> i;
bool ok = A[0] == A[N-1];
for(int i = 1; i < N; ++i)
if(A[i] == A[N-1] && A[i-1] == A[0]) ok = 1;
cout << (ok ? "YES" : "NO") nl;
}
}
Tester's code (C++)
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
#define ll long long
const ll INF_MUL=1e13;
const ll INF_ADD=1e18;
#define pb push_back
#define mp make_pair
#define nline "\n"
#define f first
#define s second
#define pll pair<ll,ll>
#define all(x) x.begin(),x.end()
#define vl vector<ll>
#define vvl vector<vector<ll>>
#define vvvl vector<vector<vector<ll>>>
#ifndef ONLINE_JUDGE
#define debug(x) cerr<<#x<<" "; _print(x); cerr<<nline;
#else
#define debug(x);
#endif
void _print(ll x){cerr<<x;}
void _print(char x){cerr<<x;}
void _print(string x){cerr<<x;}
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
template<class T,class V> void _print(pair<T,V> p) {cerr<<"{"; _print(p.first);cerr<<","; _print(p.second);cerr<<"}";}
template<class T>void _print(vector<T> v) {cerr<<" [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T>void _print(set<T> v) {cerr<<" [ "; for (T i:v){_print(i); cerr<<" ";}cerr<<"]";}
template<class T>void _print(multiset<T> v) {cerr<< " [ "; for (T i:v){_print(i);cerr<<" ";}cerr<<"]";}
template<class T,class V>void _print(map<T, V> v) {cerr<<" [ "; for(auto i:v) {_print(i);cerr<<" ";} cerr<<"]";}
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
typedef tree<ll, null_type, less_equal<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_multiset;
typedef tree<pair<ll,ll>, null_type, less<pair<ll,ll>>, rb_tree_tag, tree_order_statistics_node_update> ordered_pset;
//--------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
const ll MOD=1e9+7;
const ll MAX=1000100;
void solve(){
ll n; cin>>n;
vector<ll> a(n+5);
for(ll i=1;i<=n;i++){
cin>>a[i];
}
if(a[1]==a[n]){
cout<<"YES\n";
return;
}
for(ll i=1;i<n;i++){
if((a[i]==a[1]) and (a[i+1]==a[n])){
cout<<"YES\n";
return;
}
}
cout<<"NO\n";
return;
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
freopen("error.txt", "w", stderr);
#endif
ll test_cases=1;
cin>>test_cases;
while(test_cases--){
solve();
}
cout<<fixed<<setprecision(10);
cerr<<"Time:"<<1000*((double)clock())/(double)CLOCKS_PER_SEC<<"ms\n";
}
Editorialist's code (Python)
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
if a[0] == a[-1]:
print('Yes')
else:
ans = 'No'
for i in range(n-1):
if a[i] == a[0] and a[i+1] == a[-1]:
ans = 'Yes'
print(ans)