Please tell why I am getting TLE for Roti Prata Problem on SPOJ?

#1

This is my code:


It is giving correct answer for the below test case but on submitting it is giving TLE.
3
10
4 1 2 3 4
8
1 1
8
8 1 1 1 1 1 1 1 1

#2

Hey @sahilkhan2312000131
There is something wrong with ur ismid function I guess
Here refer to this

bool ismid(int *arr, int c,int p,int mid) {
	int  silver=0 ; //total pratas count
	for (int i = 0; i < c; i++) {
		int x = 1;  
		while ( (x * (x + 1)*arr[i]) <= 2*mid )  //Here pratas are made in arr[i] ,2arr[i] ,3arr[i] .... summation = x*(x+1)/2*arr[i] so we are doing that here to find max x which satisfy that
			x++;
		x--;
	    silver += x ; //adding pratas by current chef to total answer
	}
	return (silver>=p);
}
#3

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.

#4

hey @KartikKhariwal
I have one doubt about this question:
What will be the value of start and end?
I think start should be the smallest rank of cook *1 and end should be if all parathas are made by the cook with the highest rank.

#5

Yes that should be it
But we can always start with end as infinty

#6

I have seen that in some questions a different value of start result in not passing of some test cases.
For eg. In Book Allocation Problem if we take start=0, the code does not pass the test cases.
Can u explain why??

#7

It actually depend on ur algo , in that also u can start from 1 with an additional condition in is check that mid is greater that all arr[i]

So u can always start from 1 and infinity

#8

In the below code for Book Allocation Problem,if I take s=a[n-1] it passes all test cases but if I take s=a[0], it does not pass any test case.
Can you please explain.

#9

Actually u have to take s=maximum(all pages) acc to ur algo

Assume this test case
1
2 2
1 3
Here ans will come 1 when u take it a[0]
Because it satisfy ur checking function ,u can start with s=1 by adding this condition in ur check function

if(a[i]>mid)return false;

1 Like
#10

Thank you so much @KartikKhariwal

1 Like
#11

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.