# BOWLERS - Editorial

Author: Naman Jain
Tester: Rahul Dugar
Editorialist: Ritesh Gupta

CakeWalk

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: 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 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){
}
long long readIntLn(long long l,long long r){
}
}
}

void solve() {
int n,k,l;
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;
//	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;
}
}
}
``````

## Video Editorial

6 Likes

If any one wants video editorial in hindi -Link

BTW-Nice Contest

Can anyone tell me whatâ€™s wrong in my code I am getting an error?
https://www.codechef.com/viewsolution/38069631

It is wrong for this test case

1
5 1 5

Correct Output -> -1
Your Output -> 1 1 1 1 1

1 Like

Thanks @its_abhijeet. But Could you tell me why I am getting this error?

1 Like

WHY IS MY CODE NOT WORKING PLEASE TELL
#include<bits/stdc++.h>

using namespace std;

int main()

{

``````int t;

cin>>t;

while(t--)

{

ios_base::sync_with_stdio(false);

cin.tie(NULL);

long int n,k,l;

cin>>n>>k>>l;

if(k*l<n || (k==1 && n>1))

cout<<-1<<"\n";

else

{ int x=1;

for(int i=1;i<=n;i++)

{

if(x%k!=1 || x==1){

cout<<x<<" ";x++;}

else

{

x=x-k;

cout<<x<<" ";x++;

}   }

cout<<"\n";

}
``````

}

}

You included the condition n<=k*l which is true in this test case , but the answer is wrong because same bowler should not bowl in 2 consecutive overs.

This condition is causing trouble somehow, I made it x<=k and solution got accepted.

all those who have faced problem in this check one important corner case:
if(k==1 && n!=1)cout<<-1<<endl;
for this test case ,I was receiving WA for first 2 hours

3 Likes

can someone please tell me whatâ€™s wrong with my code _

Simple C++ solution
short and clear video:

what is the problem in my code

#include<bits/stdc++.h>
using namespace std;
int main()
{
int t; cin>>t;
while(tâ€“)
{
int n,k,l; cin>>n>>k>>l; int ans; ans=-1;
if(k==1&&l!=1&&n!=1)
{
cout<<ans<<endl;
break;
}
int arr[k+1];int i;
for(int i=1;i<k+1;i++)
arr[i]=l;
if(n>k*l)
cout<<ans<<endl;
else
{
i=1;
while(nâ€“)
{
cout<<i<<" ";
i++;
if(i>k)
i=1;
}
cout<<endl;
}
}
return 0;
}

My submission

Can someone help me with this solution. I didnâ€™t understand why is this failing.
I didnâ€™t kept an order, just kept track of who did the last over and find any bowler who has thrown overs less than L and is not the previous bowler and print it.
Why is this approach wrong

``````Scanner scan = new Scanner(System.in);
int testCases = scan.nextInt();
int n, k, l;
while (testCases > 0) {
n = scan.nextInt();
k = scan.nextInt();
l = scan.nextInt();
if (n > k * l || (k == 1 && n < 1)) {
System.out.println(-1);
} else {
for (int i = 0; i < n; i++) {
System.out.print((i % k) + 1+" ");
}
System.out.println();
}
testCases--;
}
scan.close();
``````

I am actually new to codechef contests. I did participate in September cook off contest and for the bowlerâ€™s problem I gave this solution. I got it to be wrong. I knew that I have tried the edge case, but still I got it wrong. I didnâ€™t feel myself to try again with another question, and went to sleep.

And yesterday my rating before the contest was 0 and now it is 1452. I got it to be wrong and also got some ratings.

Can someone tell me what is wrong with my solution and how does ratings work?

In my original solution I was using a function that returned a StringBuffer variable as a result and wasnâ€™t checking for the boundary case when K == 1 and N > 1. After going through the editorial, Iâ€™ve tried testing the solution as itâ€™s explained and the code still fails. Could anyone please tell me why?

Thanks!

``````class Codechef
{
public static void main (String[] args) throws java.lang.Exception
{
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
sc.nextLine();
while (T-- > 0) {
String[] parts = sc.nextLine().split(" ");
int N = Integer.parseInt(parts[0]);
int K = Integer.parseInt(parts[1]);
int L = Integer.parseInt(parts[2]);

if(K*L < N) {
System.out.println(-1);
} else if(K==1&&N>1) {
System.out.println(-1);
} else {
int rep = 0;
for(int i=0; i<N; i++) {
if(i == K) rep = 0;
System.out.print(++rep + " ");
}
System.out.println();
}
}
}
}
``````

Can you please tell for which possible test case it wonâ€™t work ??

@krishna_kc itâ€™s still not working

@krishna_kc thanks bro I got it why it wasnâ€™t working bcoz I had put ios_base::sync_with_stdio(false); cin.tie(NULL); inside my test case loop.

1 Like