SUBMEX - Editorial

Setter: Utkarsh Gupta
Tester: Manan Grover
Editorialist: Lavish Gupta

Simple

PREREQUISITES:

MEX of a set
The MEX of an array is the minimum non-negative integer that is not present in it.

PROBLEM:

Chef was on vacation when a thought struck him. Given three integers N,K, and X, he would like to make an array A of length N such that it satisfies the following conditions:

• 0 \le A_i \le N for each 1 \le i \le N
• The MEX of every contiguous subarray of length K in A is X.

Note: The MEX of an array is the minimum non-negative integer that is not present in it. For example,

• The MEX of array [0,2,5,1] is 3, because it contains 0, 1 and 2 but not 3.
• The MEX of array [1,2,5] is 0, because 0 is the smallest non-negative integer not present in the array.
• The MEX of array [0,1,2,3] is 4.

QUICK EXPLANATION:

When will the answer be -1?

If X > K, the answer will be -1. A valid array will always exist if X \leq K.

The first K elements

If X \leq K, we want first K elements to have all the values from 0 to X-1 (inclusive). There can be several ways to do this. One of the ways is to choose all the values from 0 to K (inclusive) except X.

Next elements

Start with analyzing the value of A_{K+1}. You will soon realize that one of the ways is to have A_i = A_{i-K}.

EXPLANATION:

Let us first consider the case when the answer will be -1. For a given subarray of length K, what can be the maximum value of MEX? The answer is K, when all the elements from 0 to K-1 appears in the subarray.
This means that the answer will be -1 if X > K.

We will now show that a valid array will always exist if X \leq K through construction.

Consider the first subarray of length K, i.e. the first K elements. We want the first K elements to have all the values from 0 to X-1 (inclusive). There can be several ways to do this. One of the ways is to choose all the values from 0 to K (inclusive) except X.

So now, we have fixed our \{A_1, A_2,..., A_K\}. Consider the next K elements, i.e. \{A_2, A_3, ..., A_{K+1}\}. We want the MEX of these elements to be X. Let us restate our current problem:
We know that MEX of \{A_1, A_2 \cdots A_K\} is X. We want to add one element to the set \{A_2, A_3, ... , A_K\} such that it’s MEX will become X. What should be that element? We can see that adding A_1 to this set will obviously make the MEX of the set to be X. Hence, substituting A_{K+1} = A_1 solves our current problem!

Continuing in the similar way, we can see that substituting A_i = A_{i - K} will solve our problem!

TIME COMPLEXITY:

The time complexity of the above approach will be O(N) for each test case.

SOLUTION:

Setter's Solution
//Utkarsh.25dec
#include <bits/stdc++.h>
#include <chrono>
#include <random>
#define ll long long int
#define ull unsigned long long int
#define pb push_back
#define mp make_pair
#define mod 1000000007
#define rep(i,n) for(ll i=0;i<n;i++)
#define loop(i,a,b) for(ll i=a;i<=b;i++)
#define vi vector <int>
#define vs vector <string>
#define vc vector <char>
#define vl vector <ll>
#define all(c) (c).begin(),(c).end()
#define max3(a,b,c) max(max(a,b),c)
#define min3(a,b,c) min(min(a,b),c)
#define deb(x) cerr<<#x<<' '<<'='<<' '<<x<<'\n'
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
#define ordered_set tree<int, null_type,less<int>, rb_tree_tag,tree_order_statistics_node_update>
// ordered_set s ; s.order_of_key(val)  no. of elements strictly less than val
// s.find_by_order(i)  itertor to ith element (0 indexed)
typedef vector<vector<ll>> matrix;
ll power(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll modInverse(ll a){return power(a,mod-2);}
const int N=500023;
bool vis[N];
void solve()
{
int n,k,x;
cin>>n>>k>>x;
if(k<x)
{
cout<<-1<<'\n';
return;
}
int arr[n+1]={0};
for(int i=0;i<n;i++)
{
if(i<k)
{
arr[i]=min(i,x-1);
cout<<arr[i]<<' ';
}
else
{
arr[i]=arr[i-k];
cout<<arr[i]<<' ';
}
}
cout<<'\n';
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T=1;
cin>>T;
int t=0;
while(t++<T)
{
//cout<<"Case #"<<t<<":"<<' ';
solve();
//cout<<'\n';
}
cerr << "Time : " << 1000 * ((double)clock()) / (double)CLOCKS_PER_SEC << "ms\n";
}

Tester's Solution
#include <bits/stdc++.h>
using namespace std;
int main(){
ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
int t;
cin>>t;
while(t--){
int n, k, x;
cin>>n>>k>>x;
if(k >= x){
for(int i = 0; i < n; i++){
cout<<min(i % k, x - 1)<<" ";
}
cout<<"\n";
}else{
cout<<-1<<"\n";
}
}
return 0;
}

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

const ll z = 1000000007 ;

void solve()
{
int n , k , x ;
cin >> n >> k >> x ;

if(x > k)
{
cout << -1 << endl ;
return ;
}

int curr = 0 ;
int arr[n] ;
for(int i = 0 ; i < k ; i++)
{
if(i == x)
curr++ ;
arr[i] = curr ;
curr++ ;

}

for(int i = k ; i < n ; i++)
arr[i] = arr[i-k] ;

for(int i = 0 ; i < n ; i++)
cout << arr[i] << ' ';
cout << endl ;
return ;
}

int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("inputf.txt" , "r" , stdin) ;
freopen("outputf.txt" , "w" , stdout) ;
freopen("error.txt" , "w" , stderr) ;
#endif

int t;
cin >> t ;
while(t--)
solve() ;

return 0;
}

2 Likes

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

int main() {
int t;
cin>>t;
while(t)
{
int n,k,x;
cin>>n>>k>>x;
vectorv;
if(k<x)
{
cout<<"-1"<<endl;
}
else
{
for(int i=0;i<=n;i++)
{
if(i!=x)
{
v.push_back(i%k);
}
}
}
for(int i=0;i<v.size();i++)
{
if(v[i]==x)
{
v[i]=v[i]+1;
}
}
for(int i=0;i<v.size();i++)
{
cout<<v[i]<<" ";
}
cout<<endl;
t–;
}
return 0;
}
**any give me a testcase where this code fails
**

I first create string s contains [0,x-1], then I print array of required size
since k<=x, window of size k always give MEX of x (because I repeating string s)

Please correct me if I am wrong, or give me test cases where this code fails.

int n, k, x;
cin >> n >> k >> x;
if (x > k) {
cout << -1 << endl;
return;
}
string s = "";
for (int i = 0; i < x; i++) {
s += i + '0';
}

for (int i = 0; i < n / x; i++) {
for (auto t : s)cout << t << " ";
}
for (int i = 0; i < n % x; i++)cout << s[i] << " ";
cout << endl;


1
8 5 5

But s += i+‘0’ doesn’t give the expected output, when i > 9.
Try this test case
1
15 13 12

1 Like

void solve() {
int n,k,x;cin>>n>>k>>x;
vector v(n);
int i=0;
if(x>k){cout<<-1;
return ;}
while(i<n){
if(i<k){
v[i]=min(i,x-1);
}else{
v[i]=v[i-k];
}
i++;
}
for(int i=0;i<n;i++){
cout<<v[i]<<" ";
}
cout<<endl;

}

PLs tell me the mistake why it failing in two test cases

Can anyone tell me, my Output (0 1 2 3 3 3) for this input (6 4 4) is correct or not? if correct, then why is this code not acceptable?

ll n,k,x;
cin>>n>>k>>x;

if(x>k)
cout<<-1;
else {
int l=0;
for(int i=0;i<n;i++){
cout<<l<<" ";
if((l)<x-1)
l++;
}
}
cout << "\n";


MEX of all subarrays of size 4 should be 4.

\text{arr}[1, 4] \rightarrow[0, 1, 2, 3], \text{Mex} = 4
\text{arr}[2, 5] \rightarrow[1, 2, 3, 3], \text{Mex} = 0
\text{arr}[3, 6] \rightarrow[2, 3, 3, 3], \text{Mex} = 0

Hey, I am getting WA in 2nd and 3rd test case and I am not able to find out the error with my logic. Could you help?
if (x > k)
{
System.out.println("-1");
break;
}
int arr[] = new int[n];
int i, j = 0;
for (i=0;i<n;i++)
{
arr[i] = i % x;
}
for (i=0;i<n;i++)
{
System.out.print(arr[i] + " ");
}
System.out.println();

MEX of 2 3 3 3 is 1

int main()
{
int T;
scanf("%i",&T);
while(T--)
{
int N,K,X;
scanf("%i %i %i",&N,&K,&X);
if(X > K){
printf("-1\n");
continue;
}
int x = 0;
for (int i = 1; i <= N; i++,x++)
{
if(x == X)
x = 0;
printf("%i ",x);
}
printf("\n");
}
}


you shouldn’t break from while loop after printing -1,instead you should continue.

ll n,k,x;
cin>>n>>k>>x;
if(k<x) cout<<-1;
else{
ll q=0;
while(n--){
if(q!=x) cout<<q<<" ";
q++;
if(q==k) q=0;
}
}
nl
return ;


What is wrong in this?