PROBLEM LINK:
Division 1
Division 2
Video Editorial
Author: Naman Jain
Tester: Rahul Dugar
Editorialist: Ritesh Gupta
DIFFICULTY:
CakeWalk
PREREQUISITES:
Greedy
PROBLEM:
You are given three integers N, K and L. You have to find a sequence of size N where
- Each number is from range 1 to K.
- No two adjacent numbers are the same.
- Each number should appear at most L times.
Find any such valid sequence or -1 if it is not possible.
QUICK EXPLANATION:
- Simply assign i-th over to (i\%k+1)^{th} bowler so as to distribute N overs among K bowlers uniformly
- After assignment, check if the given conditions are satisfied.
EXPLANATION:
For uniform distribution of overs, we must make sure that any bowler is assigned his next over only after all the remaining bowlers have been assigned their overs.
Why this greedy works: As we are having a constraint that the numbers of overs that a bowler can have is L.
Once it is assigned, we can check if the assignment is valid or not based on conditions given in the question.
TIME COMPLEXITY:
TIME: O(N)
SPACE: O(N)
SOLUTIONS:
Setter's Solution
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
using namespace std;
template<class T> ostream& operator<<(ostream &os, vector<T> V) {
os << "[ "; for(auto v : V) os << v << " "; return os << "]";}
template<class L, class R> ostream& operator<<(ostream &os, pair<L,R> P) {
return os << "(" << P.first << "," << P.second << ")";}
#define TRACE
#ifdef TRACE
#define trace(...) __f(#__VA_ARGS__, __VA_ARGS__)
template <typename Arg1>
void __f(const char* name, Arg1&& arg1){
cout << name << " : " << arg1 << std::endl;
}
template <typename Arg1, typename... Args>
void __f(const char* names, Arg1&& arg1, Args&&... args){
const char* comma = strchr(names + 1, ',');cout.write(names, comma - names) << " : " << arg1<<" | ";__f(comma+1, args...);
}
#else
#define trace(...) 1
#endif
#define vi vector<int>
#define pii pair<int, int>
#define vpii vector< pii >
#define I insert
#define pb push_back
#define F first
#define S second
#define ll long long
#define ld long double
#define vll vector<ll>
#define pll pair<ll,ll>
#define vpll vector<pll>
#define endl "\n"
int main(){
ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);cout<<setprecision(25);
int T; cin>>T;
while(T--){
int N, K, L;
cin>>N>>K>>L;
if(K*1ll*L < N) {cout<<"-1\n"; continue;}
if(K==1 && N>1) {cout<<"-1\n"; continue;}
for(int i=0;i<N;i++){
cout<<(i%K)+1<<" ";
}
cout<<"\n";
}
}
Tester's Solution
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/rope>
using namespace __gnu_pbds;
using namespace __gnu_cxx;
#ifndef rd
#define trace(...)
#define endl '\n'
#endif
#define pb push_back
#define fi first
#define se second
//#define int long long
typedef long long ll;
typedef long double f80;
#define double long double
#define pii pair<int,int>
#define pll pair<ll,ll>
#define sz(x) ((long long)x.size())
#define fr(a,b,c) for(int a=b; a<=c; a++)
#define rep(a,b,c) for(int a=b; a<c; a++)
#define trav(a,x) for(auto &a:x)
#define all(con) con.begin(),con.end()
const ll infl=0x3f3f3f3f3f3f3f3fLL;
const int infi=0x3f3f3f3f;
//const int mod=998244353;
const int mod=1000000007;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef tree<pii, null_type, less<pii>, rb_tree_tag, tree_order_statistics_node_update> oset;
auto clk=clock();
mt19937_64 rang(chrono::high_resolution_clock::now().time_since_epoch().count());
int rng(int lim) {
uniform_int_distribution<int> uid(0,lim-1);
return uid(rang);
}
int powm(int a, int b) {
int res=1;
while(b) {
if(b&1)
res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res;
}
long long readInt(long long l,long long r,char endd){
long long x=0;
int cnt=0;
int fi=-1;
bool is_neg=false;
while(true){
char g=getchar();
if(g=='-'){
assert(fi==-1);
is_neg=true;
continue;
}
if('0'<=g && g<='9'){
x*=10;
x+=g-'0';
if(cnt==0){
fi=g-'0';
}
cnt++;
assert(fi!=0 || cnt==1);
assert(fi!=0 || is_neg==false);
assert(!(cnt>19 || ( cnt==19 && fi>1) ));
} else if(g==endd){
if(is_neg){
x= -x;
}
assert(l<=x && x<=r);
return x;
} else {
assert(false);
}
}
}
string readString(int l,int r,char endd){
string ret="";
int cnt=0;
while(true){
char g=getchar();
assert(g!=-1);
if(g==endd){
break;
}
cnt++;
ret+=g;
}
assert(l<=cnt && cnt<=r);
return ret;
}
long long readIntSp(long long l,long long r){
return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
return readString(l,r,'\n');
}
string readStringSp(int l,int r){
return readString(l,r,' ');
}
void solve() {
int n,k,l;
n=readIntSp(1,10000);
k=readIntSp(1,10000);
l=readIntLn(1,10000);
if(k*l<n||(k==1&&n>1))
cout<<-1<<endl;
else {
fr(i,1,n)
cout<<i%k+1<<" ";
cout<<endl;
}
}
signed main() {
ios_base::sync_with_stdio(0),cin.tie(0);
srand(chrono::high_resolution_clock::now().time_since_epoch().count());
cout<<fixed<<setprecision(8);
int t=readIntLn(1,30);
// int t;
// cin>>t;
fr(i,1,t)
solve();
assert(getchar()==EOF);
return 0;
}
Editorialist's Solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int t;
cin >> t;
while(t--) {
int n,k,l;
cin >> n >> k >> l;
if(k == 1 && n > 1){
cout << -1 << endl;
continue;
}
vector <int> ans;
while(l--) {
int temp = k;
while(temp--)
ans.push_back(temp+1);
}
if(ans.size() < n) {
cout << -1 << endl;
}
else {
for(int i=0;i<n;i++)
cout << ans[i] << " ";
cout << endl;
}
}
}