CHEFEZQ - Editorial

PROBLEM LINK:

Division 1
Division 2

Author: Jatin Nagpal
Tester: Srikkanth
Editorialist: Srikkanth

DIFFICULTY:

Cakewalk

PROBLEM:

For first n days, you get a number of queries, however you can answer maximum k queries per day.
Find the first day you get to have a break, i.e. you answer strictly less than k queries.

EXPLANATION:

We can simulate the process for each day from 1 to n.
If we didn’t get a break in the first n days, we keep answering k queries for \lfloor\frac{q_r}{k}\rfloor days.
So answer in this case is \lfloor\frac{q_r}{k}\rfloor + 1 where q_r is total number of queries.

TIME COMPLEXITY:

TIME: \mathcal{O}(n)
SPACE: \mathcal{O}(1)

SOLUTIONS:

Setter's Solution
#include<bits/stdc++.h>
 
using namespace std;
 
#define LL long long int
#define FASTIO ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
const int oo = 1e9 + 5;
const LL ooll = (LL)1e18 + 5;
const int MOD = 1e9 + 7;
// const int MOD = 998244353;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define rand(l, r) uniform_int_distribution<int>(l, r)(rng)

clock_t start = clock();

const int N = 1e5 + 5;
int v[N], sumn = 0;

void subtask() {
    int n, k;
    cin >> n >> k;
    sumn += n;
    assert(1 <= n && n <= 100000);
    assert(1 <= k && k <= 100000000);
    LL sumv = 0;
    for (int i=0;i<n;++i) {
        cin >> v[i];
        assert(0 <= v[i] && v[i] <= 100000);
        sumv += v[i];
    }
    assert(1 <= sumv && sumv <= 100000);
    int days = 1, answer_me = v[0];
    while(answer_me > 0) {
        int answer = min(answer_me, k);
        if (answer < k) break;
        ++days;
        answer_me -= k;
        if (days <= n) answer_me += v[days-1];
    }
    cout << days << '\n';
}

void solve() {
    int n, k;
    cin >> n >> k;
    sumn += n;
    assert(1 <= n && n <= 100000);
    assert(1 <= k && k <= 100000000);
    for (int i=0;i<n;++i) {
        cin >> v[i];
        assert(0 <= v[i] && v[i] <= 100000000);
    }
    LL sum = 0;
    for (int i=0;i<n;++i) {
        sum += v[i];
        if (sum < (i+1) * 1LL * k) {
            cout << i+1 << '\n';
            return;
        }
    }
    cout << sum / k + 1 << '\n';
}

int main() {
    FASTIO;
    int T = 1;
    cin >> T;
    assert(1 <= T && T <= 100000);
    for (int t=1;t<=T;++t) {
        solve();
        // subtask();
    }
    assert(sumn >= T && sumn <= 100000);
    cerr << fixed << setprecision(10);
    cerr << "Time: " << (clock() - start) / (CLOCKS_PER_SEC) << " secs\n"; 
    return 0;
} 
7 Likes

CHEF AND QUERIES: Full Explanation - Link

5 Likes
2 Likes

chef and easy queries video solution

#include<bits/stdc++.h>
using namespace std;
int main()
{
int64_t t;
cin>>t;
while(t>0)
{
int64_t n,k,noOfQ,quesLeft=0,ctr=0;
cin>>n>>k;
if(n==1)
{
cin>>noOfQ;
cout<<(noOfQ/k)+1<<endl;
}
else
{
while(n>0)
{
ctr++;
cin>>noOfQ;
quesLeft+=noOfQ;
n–;
if(quesLeft < k)
{
cout<<ctr<<"\n";
break;
}
else
{
quesLeft-=k;
}
}
if(n==0 && quesLeft>=k)
{
cout<<ctr+1+(quesLeft/k)<<"\n";
}
if(quesLeft==0)
{
cout<<ctr<<endl;
}
}
t–;
}
return 0;
}

Can someone tell me if there’s anything that Im not covering in this code? I was only able to pass Subtask 2 for this one, and getting SIGFPE for Subtask 1… I checked about SIGFPE, but I wasn’t able to find any scenario where divide by zero was encountered.

Have I misunderstood a part of the problem?

#include<bits/stdc++.h>

#define ll long long int
#define vi vector<int>
#define pb push_back


using namespace std;

int solve(int arr[],int n,int k){
    ll buffer = 0;
//    int days = 1;
    for(int i = 0;i<n;i++){
        if(arr[i]+buffer<k) return i+1;
        else if(arr[i]>=k) buffer += arr[i]-k;
        else if(arr[i] < k) buffer -= k-arr[i];
//        days++;
    }
    //days += buffer/k + 1;
    return n + buffer/k + 1;

}

int main() {
    int t;
    cin>>t;
    while(t--){
        int n,k;
        cin>>n>>k;
        int arr[n];
        for(int i = 0;i<n;i++) cin>>arr[i];
        cout<<solve(arr,n,k)<<"\n";
        }
    return 0;
}

I am failing testcase 2. Can someone explain where I am going wrong

You need to consider long long for variable arr array and days.

1 Like

Why my code is wrong.

#include <bits/stdc++.h>
#include <string>
#include <sstream> 
#include <iostream> 
#define rep(i,a,n) for(int i=int (a);i<int (n);i++)
#define OUT  freopen("output.txt", "w", stdout)
#define IN  freopen("input.txt", "r", stdin)
#define mem(a,b) memset((a),(b),sizeof(a))
#define NumofDigits(n) ((int)log10(n)+1)
#define NumofBits(n) ((int)log2(n)+1)
#define PI 3.14159265358979323846264
#define vii vector<pair<int,int>>
#define all(x) x.begin(),x.end()
#define pii pair<int,int>
#define pll pair<ll,ll>
#define vi  vector<int>
#define vc  vector<char>
#define vl  vector<long>
#define nl  cout<<"\n"
#define pb  push_back
#define mp  make_pair
#define ll  long long
#define ss  second 
#define ff  first
#define endl "\n"
#define sp  " "
using namespace std;

int main(){
    ll t;
    cin>>t;
    while(t--){
    	ll n,k;
    	cin>>n>>k;
    	vi a(n);
    	for(int i = 0; i < n; i++){
    		cin>>a[i];
    	}
    	ll b=0;
    	int c=-1;
    	for(int i = 0; i < n; i++){
    		b += a[i];
    		b = b-k;
    		if(b < 0){
    			c = i+1;
    			break;
    		}
    	}
    	if(c == -1){
    		c = n+b/k+1;
    	}
    	cout<<c<<endl;
    }
}

Any testcase please

It worked. Thanks a lot!

In depth explanation with fun : https://www.youtube.com/watch?v=gRZNTCkxlXM


In depth explanation, with key observations and caveats for testcase 2

Have a look here

#include <bits/stdc++.h>
using namespace std;
#define inf (long)1e7 + 6
#define ll long long
#define FASTIO ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);

void solve(){
ll n, k, x, sum = 0, ans = inf;
cin >> n >> k;
for(ll i = 0; i < n; ++i){
cin >> x;
sum += x;
if((sum / k) <= i)
ans = min(ans, i + 1);
}
ans = min(ans, (sum / k) + 1);
cout << ans << “\n”;
}

int main(){
FASTIO
int t=1;
cin >> t;
while(t–) solve();
return 0;
}

Someone, help me with the code i can’t understand where my code went wrong .It’s giving only partially correct

 # include <bits/stdc++.h>
using namespace std;
#define ll long long 

int main()
{
    ll  k,temp;
    ll T,n;
    
 

    cin>>T;
    
    while(T--)
    {
        ll index=0,sum=0;
        cin>>n;
        cin>>k;
        vector<int> arr;
        for(int i=0;i<n;i++)
        {
            int temp;
            cin>>temp;
            arr.push_back(temp);
        
        }
        for(int i=0;i<n;i++)
        {  
           sum+=arr[i]-k;
           if(sum<0)
            {
               index=i;
               break;
            }
        }
        if(index!=0){
            cout<<index+1<<endl;
        }
        else{
            cout<<n+(sum/k)+1<<endl;
        }

            
            

        


    }
}

can someone tell me why my code is not passing the 1st tescase

I also did similar thing and still not able to pass subtask-1, did you got what mistake is there?.
I tried applying Floor (don’t know why) and naturally it didn’t work.

Please provide any testcase.

If it is the day 1 then ur index becomes 0 and then final answer will change (i.e n +( sum / k) + 1)

I am failing Subtask 1 with the error: RE (SIGFPE). What is wrong in my code?

#include <bits/stdc++.h>
using namespace std;

int main() {
long long int num_test;
long long int days,k;
long long int queries,i,day;

scanf("%lld",&num_test);
for(i=0;i<num_test;i++){
	queries =0;
	scanf("%lld %lld",&days,&k);
	
	long long int test;
	for (day=1;day<=days;day++){
		scanf("%lld",&test);
		if(queries < k -test){
			printf("%lld\n",day);
			// printf("here");
			break;
		}
		queries = queries - k + test;
	}
	if (day>days){
		long long int out = (queries/k)+1+days;
		printf("%lld\n",out);
		
	}
}
return 0;

}

#include<bits/stdc++.h>

using namespace std;

int main() {
// your code goes here
int total_testcases;
cin>>total_testcases;

int testcases=0;
//long long int sumn=0;
//long long int sumq=0;


while(testcases<total_testcases){
    int n;
    long long int k;
    cin>>n;
    cin>>k;
    //assert(n>=1 && n<=100000);
    //sumn+=n;
    long long int available_questions=0,days=1,carried=0,answered=0,new_questions=0;
    int i;
    //assert(k>=1&&k<=100000000);
    for(i=0;i<n;i++){
        cin>>new_questions;
        available_questions=carried+new_questions;
        if(available_questions<k){
            break;
        }
        else{
            answered=k;
            carried=available_questions-answered;
            days++;
        }
        
    }
    
    if(i==n){
        days+=(carried/k);
    }
    
    //assert(1<=sumq&&sumq<=100000);
    cout<<days<<endl;
    testcases++;
    
}
//assert(total_testcases<=sumn&&sumn<=100000);
return 0;

}

Can someone help me with debugging my code ? I am getting a SIGFPE error. I cannot find any instance where i am dividing with 0. Also, i used long long data type for all the variables.

1 Like

#include
using namespace std;
int main() {
// your code goes here
int t,n,k;
cin>>t;
while(t>0)
{
cin>>n>>k;
int a[n],days,que=0,i;
for(int i=0;i<n;i++)
{
int b;
cin>>b;
a[i]=b;
}
for( i=0;i<n;i++)
{
if(a[i]>=k)
{
que=a[i]-k;
a[i+1]=a[i+1]+que;
}
else
{
if(a[i]<k)
{
cout<<i+1;
}
}}
if(que>0)
{
days=que/k;
days=days+i+1;
cout<<days;

            }
            t--;
}
return 0;

}
can someone will please tell me why its not running on codechef ide but correctly runs on code blocks?