# PROBLEM LINK:

Author: Ritul Kumar Singh
Testers: Nishank Suresh, Satyam
Editorialist: Nishank Suresh

1648

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)

1 Like

https://www.codechef.com/viewsolution/79484178
please suggest a testcase where the solution is failing

1 Like
1
6
1 3 2 1 3 2

2 Likes

Sir What about my solution ??
Link

What are the test cases that my Code is failing. I think I did pretty much right.

I submitted this but it passed only 3 out of 5 test cases. Please tell me what am I missing here. Thanks

#include <iostream>
using namespace std;

bool helper(int n, int arr[]){
int start = arr[0];
int end = arr[n-1];
if(start==end) return true;

int lastStartIdx = 0, firstEndIdx = n-1;
for(int i=0;i<n;i++){
if(arr[i]==start) lastStartIdx = i;
}
for(int i=n-1;i>=0;i--){
if(arr[i]==end) firstEndIdx = i;
}
if(firstEndIdx<lastStartIdx || lastStartIdx+1==firstEndIdx) return true;
return false;
}

int main() {
int t;cin>>t;
while(t--){
int n;cin>>n;
int arr[n];
for(int i=0;i<n;i++){
cin>>arr[i];
}
if(helper(n,arr)) cout<<"Yes"<<endl;
else cout<<"No"<<endl;
}
// your code goes here
return 0;
}


thank you i just misinterpreted the question
Thank you have a great day

Your code also fails on the testcase I provided above.

1 Like

oh yeah, Iâ€™ve been thinking that if the 2 distinct numbers have overlapping area, then also the answer would be â€śYesâ€ť.
Shouldâ€™ve dry ran during the contest.

if(firstEndIdx<lastStartIdx || lastStartIdx+1==firstEndIdx) return true;
return false;


The first condition shouldnâ€™t be there.
Thank you.

#include
#include<bits/stdc++.h>
#define ll long long
using namespace std;

int main()
{
#ifndef ONLINE_JUDGE
freopen(â€śinput.txtâ€ť , â€śrâ€ť ,stdin);
freopen(â€śoutput.txtâ€ť , â€śwâ€ť ,stdout);
#endif
int t;
cin>>t;
while(tâ€“){
long long n;
cin>>n;
if(n<=2){
cout<<â€śyesâ€ť<<endl;
continue;
}

vector a(n);
map<long long , pair<long long, long long>> m;
for(long long i=0 ; i<n ;i++){
cin>>a[i];
if(m.find(a[i])!=m.end()){
m[a[i]].second=i;
continue;
}
m[a[i]]={i, i};
}
vector<pair<long long , long long>> v;
for(auto x : m){
v.push_back({x.second.first , x.second.second});
}
sort(v.begin() , v.end());
long long l=v[0].first,r=v[0].second;
long long ct=1;
for(long long i=0 ; i<v.size() ; i++){
if(v[i].first>l && v[i].first<r){
r=max(r , v[i].second);
continue;
}
else{
if(v[i].first!=v[i].second){
ct=ct+v[i].first-r-1;
l=v[i].first , r=v[i].second;
}
}
}
ct=ct+n-1-r;
if(ct>2){
cout<<â€śnoâ€ť<<endl;
}
if(ct<=2)
cout<<â€śyesâ€ť<<endl;

}
return 0;


}
hello sir , can you please tell me whats wrong with my approach

same bro , i tried all i can. but couldnt pass starting two testcases

What test cases are failing for my Code? Please help!

#include <bits/stdc++.h>
using namespace std;

int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int t;
cin >> t;
while(t--) {
int n;
cin >> n;
int *a = new int[n];
unordered_map<int, int> firstIndex, lastIndex;
for(int i = 0; i < n; ++i) {
cin >> a[i];
lastIndex[a[i]] = i;
if(firstIndex.count(a[i]) < 1) {
firstIndex[a[i]] = i;
}
}

bool ans1, ans2;
int pointer1 = lastIndex[a[0]];
int pointer2 = pointer1+1;

if(pointer1 == n-1) {
ans1 = true;
} else if(lastIndex[a[pointer2]] == n-1) {
ans1 = true;
} else {
ans1 = false;
}

pointer1 = n-1;
pointer2 = firstIndex[a[pointer1]]-1;

if(pointer1 == 0) {
ans2 = true;
} else if(firstIndex[a[pointer2]] == 0) {
ans2 = true;
} else {
ans2 = false;
}

ans1 || ans2 ? cout << "YES\n" : cout << "NO\n";
}
return 0;
}



I found the corner caseâ€¦
1
8
1 3 2 1 2 1 4 2

Can anyone tell me my mistakes or testcases where this code fails, this solution fails only for the first 2 testcases.

CODE:

void solve(){
int n;
cin >> n;
vl v(n);

for(int i=0;i<n; ++i) cin >> v[i];
vector<ll> vis(v.begin(), v.end());

umap<ll, vector<ll>> ind;

for(int i=0; i<n; ++i) ind[v[i]].pb(i);

for(auto k: ind){
if(k.second.size() >= 2){
vector<ll> arr = k.second;
int len = arr.size();
for(int i=arr[0]+1; i<arr[len-1]; ++i){
vis[i] = v[arr[0]];
}
}
}

uset<ll> set(vis.begin(), vis.end());

if(set.size() <= 2){
cout <<"YES\n";
}
else{
cout <<"NO\n";
}
}