PROBLEM LINK:
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:
- Frequency of every integer in it is distinct.
- 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:
- Check if the frequencies of all the elements are distinct. This can be done using simple iterations and a few arrays, as explained above.
- 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.
- 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