WA in Minion Chef and Bananas (MINEAT)

general
, , , , ,
1

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[0];
        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.

2

@everule1 Help please.

3 
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
4

What should be the answer for your test case?

5

50

6

Can you share your logic for this problem?

7

Here, made a few changes.
https://www.codechef.com/viewsolution/30586266

1 Like
8 
#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[0]];
        for(int i=1; i<=b[0]; i++)
            possible_k[i-1] = i;
        int low = 0;
        int high = b[0]-1;
        int ans = b[0];
        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?

9

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

10

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!!!

11

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

12

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
13

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