# WA in Minion Chef and Bananas (MINEAT)

Here is my code for the MINEAT problem (MINEAT Problem - CodeChef):-

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

bool comp(int a, int b)
{
return a > b;
}

int main()
{
int t;
cin >> t;
while(t--)
{
int n, h;
cin >> n >> h;
int b[n];
for(int i=0; i<n; i++)
cin >> b[i];
sort(b,b+n,comp);
int low = 0;
int high = n-1;
int ans = b;
while(low <= high)
{
int time = 0;
int k = b[(low+high)/2];
for(int i=0; i<n; i++)
time += ceil((double) b[i]/k);
if(time <= h)
{
ans = min(ans, k);
low = ((low+high)/2);
low++;
}
else
{
high = ((low+high)/2);
high--;
}
}
cout << ans << "\n";
}
return 0;
}


It gives the correct output for the sample test cases but it is giving WA on submission. Where am I going wrong? On which test cases does this fail? Please help.

1
3 6
100 100 100


Your code return 100, I don’t think that is correct. Get debugging.
Also \lceil a/b \rceil = \lfloor \frac{a-1}{b} \rfloor + 1. Always avoid floating point
calculations.
Also sorting in descending order is done by
 sort(b,b+n,greater<int>());

3 Likes

50

Can you share your logic for this problem?

https://www.codechef.com/viewsolution/30586266

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

int main()
{
int t;
cin >> t;
while(t--)
{
int n, h;
cin >> n >> h;
int b[n];
for(int i=0; i<n; i++)
cin >> b[i];
sort(b,b+n,greater<int>());
int possible_k[b];
for(int i=1; i<=b; i++)
possible_k[i-1] = i;
int low = 0;
int high = b-1;
int ans = b;
while(low <= high)
{
int time = 0;
int k = possible_k[(low+high)/2];
for(int i=0; i<n; i++)
time += ceil((double) b[i]/k);
if(time <= h)
{
ans = min(ans, k);
low = ((low+high)/2);
low++;
}
else
{
high = ((low+high)/2);
high--;
}
}
cout << ans << "\n";
}
return 0;
}


I have made some changes to the code. Can you figure out if there are any test cases for which the above code fails?

Oh right, If time<=h, then high should be decreased, and vice versa

Your solution got AC, but even my new solution gives WA. Where am I going wrong? I think I should try to figure out the changes you made and why you did that. Thanks for your help!!!

@everule1 How can I become better at implementation in code? Any suggestions?

I really don’t know. I myself struggle with implementation. The best I can say is, that you should have the code, not just the essence, planned out in your head, before starting. For longer codes, you should have each part/function planned beforehand, and try thinking in the way I have commented my code.

3 Likes

Thank you so much for your advice You are indeed very helpful, you clear all my doubts and have helped me a lot !