CHEFRECP - Editorial

PROBLEM LINK:

Practice
Contest

Author: Ritesh Gupta
Tester: Raja Vardhan Reddy
Editorialist: Akash Bhalotia

DIFFICULTY:

Cakewalk

PREREQUISITES:

None

PROBLEM:

Let’s call an array good if the frequency of every integer in it is distinct, and if multiple occurrences of any integer occur only as a single contiguous subsequence in the array. Given an array of integers, find if it’s good.

EXPLANATION

show

Let’s call an array good only if both the following conditions are true:

  1. Frequency of every integer in it is distinct.
  2. Every integer only occurs as a part of a single contiguous block of numbers in the array.

Let’s check both the conditions one by one.

First we need to check if the frequency of every integer in the array is distinct. Notice that the elements can only be in range 1 \le A_i \le 1000. Thus, to find the frequency of each distinct integer in the array, we can simply iterate over all the elements an increment their frequencies in a frequency array.

//create an integer array freq of size just greater than 1000
//initialise it with 0s. Then: 

for(i=0;i<N;i++) 
	freq[a[i]]++;

Array freq will store the frequencies of every integer in the array. The elements which don’t occur in A will have 0 frequency. You can also refer to this to learn some more techniques of finding the frequencies of array elements.

For example, let the array A be: {1, 5, 2, 5, 2, 2}.
The frequency array will look like this: {0,1,3,0,0,2}.

0, 3 and 4 are not present in the array. Thus, freq[0]=freq[3]=freq[4]=0. Any integer which is not present in the array will have a frequency 0.

freq[1]=1, as 1 appears only once in the array.
freq[2]=3, as 2 appears thrice in the array, and
freq[5]=2, as 5 appears twice in A.

Now that we know the frequencies, we need to check if they are distinct. Again, the frequencies will be in a limited range, 0 \le freq_i \le N. So, we can use another array times, which will store the number of times a particular frequency occurs.

//create an integer array times of size just greater than N
//initialise it with 0s. Then: 

for(i=1;i<=1000;i++) 
	times[freq[i]]++;

times has a size just greater than N as the frequency of any integer in the array can be at most N. We iterated from 1 to 1000 because this is the range of the integers A_i.

In our array A: {1, 5, 2, 5, 2, 2},
times will store: {2, 1, 1, 1, 0, 0}.

We only considered integers \gt 0.
times[0]=2 as 3 and 4 are not present in the array, they have a frequency 0.
times[1]=1 as 1 was the only element which had a frequency 1.
times[2]=1 as 5 was the only element which had a frequency 2.
times[3]=1 as 2 was the only element which had a frequency 3.
times[4]=times[5]=0 as no element had frequencies 4 and 5.

Now, every frequency will be distinct in A only if it appears at most once, i.e., times[i] should be at most one. Again, we can check this using a simple loop.

boolean flag=true;

for(i=1;i<=N;i++)
	if(times[i]>1) 
		flag=false;

We started the loop from 1 as we are only interested in the frequencies of integers that are present in the array. We ran it till N as N is the maximum possible frequency of any element in the array.

If flag remains true, this means that the first condition is satisfied. We can now move on to check condition 2. Else, the array can’t be good, and we can print “NO”.

Now, to check the second condition, we can simply iterate over the elements in the array, and maintain an array vis to check whether or not they have occurred earlier, as a part of a different contiguous block.

//create a boolean array vis of size just greater than 1000.
//vis tells us if this integer has occurred earlier, as a part of a different block.
//initialise vis with false.
//a boolean variable flag will tell us if condition 2 is true or not.

boolean flag=true;
vis[a[0]]=true;

for(i=1;i<N;i++)
{
	//if this element is a part of the current contiguous subsequence
	//then do nothing. Check the the next element.
	if(a[i]==a[i-1]) 
		continue;
		
	//This element starts a new block.
	//If it has already occurred before, as a part of some
	//other block, then condition 2 is false.
	if(vis[a[i]]==true) 
		flag=false;
		
	//Mark the element which started the new block as visited
	vis[a[i]]=true;
}

If flag remains true after the iteration, it means that condition 2 is also true, and our array is good.

As an example, let’s look at the following array: {5,5,2,2,2,4,4,4,2}.

Initially, we’ll mark vis[5] as true and then iterate till we hit the next block.
Then we encounter 2. We check if it has occurred before. We’ll mark it as visited and then similarly, we mark 4 also as visited and iterate till its block is completed.
But then, we encounter 2 again. Since 2 had already been visited as a part of a previous block, thus, the array can’t be good.

Thus, to solve the problem:

  1. Check if the frequencies of all the elements are distinct. This can be done using simple iterations and a few arrays, as explained above.
  2. Check if every distinct element occurs only as a single block of contiguous numbers. To do this, we can mark them as visited the first time we encounter them. If we encounter them again as a part of a different block, this means that this condition is not satisfied.
  3. If both the above conditions are satisfied, we print “YES”, else we print “NO”.

Note that this problem can also be solved using sets or maps , but since this is a cakewalk problem, I tried to explain it using arrays, hoping that beginners find it easier to understand.

TIME COMPLEXITY:

show

The time complexity of the above implementation is: O(N+M) per test case,
where N is number of elements in the array, and M is the largest integer that can be present in the array.

The complexity can be reduced to O(N) per test case, if we use a map (refer to the setter’s solution below).


SOLUTIONS:

Setter
#include <bits/stdc++.h>
 
#define ine long long
#define endl "\n"
 
using namespace std;
 
int a[200010];
 
int32_t main()
{
	int t;
	cin >> t;
 
	while(t--)
	{
		int n;
		cin >> n;
 
		for(int i=0;i<n;i++)
			cin >> a[i];
 
		a[n] = -1;
 
		map <int,int> m1,m2;
		int cnt = 1;
		bool flag = true;
 
		for(int i=0;i<n;i++)
		{
			if(a[i] == a[i+1])
				cnt++;
			else
			{
				m1[a[i]]++;
				m2[cnt]++;
				cnt = 1;
			}
		}
 
		for(auto i:m1)
		{
			if(i.second != 1)
			{
				flag = false;
				break;
			}
		}
 
		for(auto i:m2)
		{
			if(i.second != 1)
			{
				flag = false;
				break;
			}
		}
 
		if(flag)
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
 
	return 0;
} 
Tester
//raja1999
 
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC optimize("Ofast")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,avx,avx2")
 
#include <bits/stdc++.h>
#include <vector>
#include <set>
#include <map>
#include <string> 
#include <cstdio>
#include <cstdlib>
#include <climits>
#include <utility>
#include <algorithm>
#include <cmath>
#include <queue>
#include <stack>
#include <iomanip> 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp> 
//setbase - cout << setbase (16)a; cout << 100 << endl; Prints 64
//setfill -   cout << setfill ('x') << setw (5); cout << 77 <<endl;prints xxx77
//setprecision - cout << setprecision (14) << f << endl; Prints x.xxxx
//cout.precision(x)  cout<<fixed<<val;  // prints x digits after decimal in val
 
using namespace std;
using namespace __gnu_pbds;
#define f(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) f(i,0,n)
#define fd(i,a,b) for(i=a;i>=b;i--)
#define pb push_back
#define mp make_pair
#define vi vector< int >
#define vl vector< ll >
#define ss second
#define ff first
#define ll long long
#define pii pair< int,int >
#define pll pair< ll,ll >
#define sz(a) a.size()
#define inf (1000*1000*1000+5)
#define all(a) a.begin(),a.end()
#define tri pair<int,pii>
#define vii vector<pii>
#define vll vector<pll>
#define viii vector<tri>
#define mod (1000*1000*1000+7)
#define pqueue priority_queue< int >
#define pdqueue priority_queue< int,vi ,greater< int > >
#define int ll
 
typedef tree<
int,
null_type,
less<int>,
rb_tree_tag,
tree_order_statistics_node_update>
ordered_set;
 
 
//std::ios::sync_with_stdio(false);
int a[200005],vis[200005],cnt[200005];
map<int,int>mapi;
map<int,int>::iterator it;
main(){
	std::ios::sync_with_stdio(false); cin.tie(NULL);
	int t;
	cin>>t;
	while(t--){
		int n,i,c,fl=0;
		cin>>n;
		mapi.clear();
		rep(i,n){
			cin>>a[i];
			mapi[a[i]]=1;
			vis[i+1]=0;
		}
		c=0;
		for(it=mapi.begin();it!=mapi.end();it++){
			cnt[c]=0;
			it->ss=c++;
		}
		rep(i,n){
			a[i]=mapi[a[i]];
		}
		cnt[a[0]]++;
		f(i,1,n){
			if(a[i]!=a[i-1] && cnt[a[i]]!=0){
				fl=1;
			}
			cnt[a[i]]++;
		}
		rep(i,c){
			if(vis[cnt[i]]){
				fl=1;
			}
			vis[cnt[i]]=1;
		}
		if(fl){
			cout<<"NO"<<endl;
		}
		else{
			cout<<"YES"<<endl;
		}
 
	}
	return 0;
} 
Editorialist
//created by Whiplash99
import java.io.*;

class A
{
	//checks if every element has a distinct frequency
	private static boolean distinctFreq(int a[], int N)
	{
	    //stores frequency of an integer in the array
	    int freq[]=new int[1005];
	    for(int i=0;i<N;i++) freq[a[i]]++;

	    //stores the number of times a particular frequency
	    //occurs in the array
	    int times[]=new int[N+5];
	    for(int i=1;i<=1000;i++) times[freq[i]]++;

	    //checks whether every frequency occurs at most once
	    for(int i=1;i<=N;i++) if(times[i]>1) return false;
	    return true;
	}

	//checks if multiple occurrences of an integer occur
	//only as a part of a single contiguous block in the array
	private static boolean contiguousBlock(int a[], int N)
	{
	    boolean vis[]=new boolean[1005]; int i;

	    //vis tells us if this integer has occurred earlier
	    //as a part of some other block
	    vis[a[0]]=true;
	    for(i=1;i<N;i++)
	    {
	        if(a[i]==a[i-1]) continue;
	        if(vis[a[i]]) break;
	        vis[a[i]]=true;
	    }
	    return i==N;
	}
	public static void main(String[] args) throws IOException
	{
	    BufferedReader br=new BufferedReader(new InputStreamReader(System.in));

	    int i,N;

	    int T=Integer.parseInt(br.readLine().trim());
	    StringBuilder sb=new StringBuilder();

	    while(T-->0)
	    {
	        N=Integer.parseInt(br.readLine().trim());

	        int a[]=new int[N];
	        String[] s=br.readLine().trim().split(" ");
	        for(i=0;i<N;i++) a[i]=Integer.parseInt(s[i]);

	        boolean condition1= distinctFreq(a,N);
	        boolean condition2=contiguousBlock(a,N);

	        if(condition1&&condition2) sb.append("YES\n");
	        else sb.append("NO\n");
	    }
	    System.out.println(sb);
	}
}

Feel free to share your approach if it differs. You can ask your doubts below. Please let me know if something’s unclear. I would LOVE to hear suggestions :slight_smile:

9 Likes

https://ide.geeksforgeeks.org/v2WAk0uL1e

//please tell me what is wrong with my code

Can anyone help in making this faster?
I got AC on it still i want optimization.
And what will be time complexity of my code?
I guess O(N)

from collections import Counter
def main(N,l):
    a=max(l)
    c=[0]*(a+1)
    c[l[0]]+=1
    for i in range(1,N,1):
        if c[l[i]]==0:
            c[l[i]]+=1
        elif c[l[i]]!=0 and l[i-1]==l[i]:
            c[l[i]]+=1
        elif c[l[i]]!=0 and l[i-1]!=l[i]:
            return 'NO'
    d=Counter(c)
    for i in d:
        if i!=0 and d[i]>1:
            return 'NO'
    return 'YES'
t=int(input())
for _ in range(t):
    N=int(input())
    l=list(map(int,input().split()))
    print(main(N,l))

Here is mine but I dont get it where I am wrong.

from itertools import groupby
for i in range(int(input())):
    n = int(input())
    c = 0
    a = list(map(int, input().split()))
    g = sorted(a)
    b = [len(list(group)) for key, group in groupby(a)]
    h = [len(list(group)) for key, group in groupby(g)]
    b = sorted(b)
    h = sorted(h)
    #print(b)
    #print(h)
    if(b == h):
    #print(b)
        #b = sorted(b)
        d = [len(list(group)) for key, group in groupby(b)]
        #for i in range(len(b)-1):
     #       if(b[i] == b[i+1]):
      #          c = 0
           # else:
        #     c = 1
        for i in d:
            if(i > 1):
                c = 1
        #print(c)
        if(c == 1):
            print("NO")
        else:
            print("YES")
    else:
        print("NO")

https://www.codechef.com/viewsolution/33319218

I don’t understand why this approach isn’t working.

why i am getting wrong answer???
somebody please help

#include<bits/stdc++.h>
using namespace std;
#define ll long long int
#define vi vector
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
ll t{};
cin>>t;
while(t–)
{

ll n{},i{},j{},x{},y{},c{1};
cin>>n;
vi v3;
vi v1(n+2,0);
vi v2(n+2,0);
for(i=1;i<=n;++i)
cin>>v1.at(i);
for(i=1;i<=n;++i){
for(j=0;j<n+2;++j)
{
if(v1.at(i)==v1.at(j))
v2.at(i)++;
}
}

for(i=1;i<=n;++i){
for(j=0;j<n+2;++j)
{
if(v1.at(i)==v1.at(j))
{
if(v1.at(j-1)!=v1.at(i)&&v1.at(j+1)!=v1.at(i)&&v2.at(i)!=1)
{
x=1;
break;
}}
}
}

for(i=1;i<=n;++i)
{ 
    if(v1.at(i)==v1.at(i+1))
    c++;
    else
    { 
        v3.push_back(c);
        c=1;
    }
}

/for(i=0;i<v3.size();++i)
cout<<v3.at(i)<<" ";
cout<<endl;
/
sort(v3.begin(),v3.end());
for(i=0;i<v3.size()-1;++i)
{
if(v3.at(i)==v3.at(i+1))
{
y=1;
break;
}
}
//cout<<x<<" "<<y<<endl;
if(x+y==0)
cout<<“YES”<<endl;
else
cout<<“NO”<<endl;
}
}

You are not supposed to sort the inputs, that’s where you are wrong

please tell my mistake

Why am I getting a WA? Can you give me a test case for which this fails?
https://www.codechef.com/viewsolution/33301484

https://www.codechef.com/viewsolution/33316760
I was getting WA, I want to know where I went wrong I mean on which test case condition.

“arri” stores the ingredient sequence.

“temp” is used to check if current element is already visited or not

“dic” is counting occurrence of each element…

“dic2” is storing count of each element from dic.

https://www.codechef.com/viewsolution/33297287

Anyone please let me know where this solution fails… you can provide me testcase or point out my mistake.

for(int i=1;i<1001;i++)
{
hash[i]=0;
}
*for this you can simply use * hash[1001] = { } ;
It will automatically initialise your array to 0.

**** For you second logic just sort the hash array and check if hash[i]==hash[i+1];
This will check for distinct element…

your soln is failing simple testcases.
1
1 1 7 8 9

output must be NO bc frequency of 7 8 9 are 1

from collections import Counter
for _ in range(int(input())):
n=int(input())
a=list(map(int,input().split()))
s=set()
counter=0
for i in range(n):
if a[i] not in s:
s.add(a[i])

    else:
        if a[i]==a[i-1]:
            counter=0
        else:
            print("NO")
            counter=1
            break
if counter==0:
    l=list(Counter(a).values())
    l.sort()
    m=0
    for i in range(len(l)):
        if l[i]==m:
            print("NO")
            counter=1
            break
        else:
            m=l[i]
            counter=0
    if counter==0:
        print("YES")

1
5
1 1 7 8 9
ouput:NO

can someone give me the test casesusedfor checking??

please help
https://www.codechef.com/viewsolution/33302473
it passes all inputs that i give

I am getting correct in testcase. Can you provide some test cases

I just check it with its sorted list, about the occurrence of same ingredient

Since I am new to coding Please tell why I got WA.Anyone so that I can improve
Here is my solution
https://www.codechef.com/viewsolution/33312715

`int m1[10];``
m1[a[i]]++; plzz explain anyone what does this line exactly do just explain how m1 array effects m1[a[i]];