RANGEASSIGN - Editorial

editorial
,
1

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)
1 Like
2

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

1 Like
3 
1
6
1 3 2 1 3 2
2 Likes
4

Sir What about my solution ??
Link

5

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

6

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;
}
8

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

9

Your code also fails on the testcase I provided above.

1 Like
10

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.

11

#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

12

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

13

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

15

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";
	}
}