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