2

I stuck at a problem Minion chef and Bananas .Which is a binary search based problem

I execute the below program on following test cases; And it successfully passed all the test cases

Test case 1:

3 3

1 2 3

Output:

3

Test case 2:

3 4

1 2 3

Output:

2

Test case 3:

4 5

4 3 2 7

Output:

4

But I am when I am submitting the Below program I am getting the error as "SIGTSTP" Please help.

Here is my code:

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

int getHours(vector<int> piles,int k){
    int sum = 0;
    for(int i = 0;i<piles.size();i++){
        if(piles[i]%k==0)
            sum+=(piles[i]/k);
        else
            sum+=(1+piles[i]/k);
    }
    return sum;
}


int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        int h;
        cin>>n>>h;
        vector <int> piles;
        int tempmax = 0;

        for(int i=0;i<n;i++){
            int temp;
            cin>>temp;
            tempmax = max(temp,tempmax);
            piles.push_back(temp);
        }
        int low = 0;
        int high = tempmax;
        if(tempmax==1){
            cout<<h<<endl;
            continue;
        }

        while(low<high){
            int mid = (low + high)/2;
            int p=getHours(piles,mid);
            if(p<=h)
                high = mid;
            else
                low = mid + 1;
        }
        cout<<low<<endl;
        piles.clear();

    }


}
coders4521
  • 21
  • 1
  • 2
  • As far as I can see, `SIGTSTP` is sent to a program, when it is being killed. So, probably, your code took to much time to execute ("_Time Limit: 2 secs_"), ad was killed, which resulted in such signal. – Algirdas Preidžius Jan 17 '19 at 19:49
  • 1
    All of your test cases are fairly short, but the problem could be throwing billions of numbers at you. Ensure that when faced with extremely large `N` and `H` that the program does not take excessively long. – user4581301 Jan 17 '19 at 19:52
  • Unrelated: Consider changing `int getHours(vector piles,int k)` to `int getHours(const vector &piles,int k)` so that `piles` isn't copied every time the function is called. – user4581301 Jan 17 '19 at 20:03
  • still showing the same error @user4581301 – coders4521 Jan 17 '19 at 20:11
  • If you can find the test case that is making this fail we may be able to help, but the answer will probably still be "Your program is too slow. You will have to find a different algorithm." Sidenote: [`endl` is very expensive](https://stackoverflow.com/questions/213907/c-stdendl-vs-n). Prefer `'\n'` if all you want is a new line. – user4581301 Jan 17 '19 at 20:20
  • When i changed to `'\n' ` now it is giving as SIGFPE – coders4521 Jan 17 '19 at 20:25
  • @coders4521 [`SIGFPE`](http://www.gnu.org/software/libc/manual/html_node/Program-Error-Signals.html) may indicate a bug in your code: floating point exception. – user268396 Jan 17 '19 at 20:31
  • You can divide by zero in `getHours` if the second parameter is zero. And it can be zero if `mid=0`, which is possible when `low=0` and `high=1` (which is theoretically possible after a single iteration of the binary search, if you don't examine exact logic behind the program). – yeputons Jan 17 '19 at 20:33
  • I used `assert(k!=0)` My program terminated with error But i am not getting where i am doing mistake. – coders4521 Jan 17 '19 at 20:45
  • `assert` does nothing if the program is not compiled for debugging. If debugging is on, `assert` spits out an error message and terminates the program. Not what you want to use here. You need to PREVENT the error. – user4581301 Jan 17 '19 at 21:20
  • 1
    Sidenote: SIGFPE has been broadened over the years to cover a wider variety of mathematical errors. Do not assume it's strictly floating point. – user4581301 Jan 17 '19 at 21:21
  • `SIGTSTP` is used to *suspend* processes from the terminal (usually with `^Z`). You **can’t** *kill* a process with it! – Davis Herring Jan 18 '19 at 21:29

0 Answers0