BOWLERS - Editorial

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

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 :sweat_smile:

3 Likes

can someone please tell me what’s wrong with my code _

[code] (https://www.codechef.com/viewsolution/38071271)

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

@rahuldugar please help

My submission

Can someone help me with this solution. I didn’t understand why is this failing.
thanks in advance :slight_smile:
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();

Click here for submission link.

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
	{
		// your code goes here
		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

@ayukismis `

your code with a small change and it worked

`

@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