SUBMEX - Editorial

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3

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

DIFFICULTY:

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.

Please help Chef in finding such an array. If there are multiple answers, you can output any configuration; and if there is no possible answer, output -1.

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];
vector <int> adj[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

Your idea is correct.
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?