This is August Cook Off 23/08/2020 chef and work Problem. CodeChef: Practical coding for everyone. I have run the code with sample test cases they are working fine. but when I submit the code it it showing TLE. I have tried to debug but unable to resolve it. Please help in resolving the error.
Problem Link: /* package codechef; // don't place package name! */import java.util.*;imp - Pastebin.com
1 Like
The Expected Time complexity is O(N) and your program is going O(N^2) as you are running a for loop inside a while loop for every index less than n. You have to do it in lesser time complexity.
Yeah Agree, However I have two queries,
-
If it is O(n^2) TC will be around TNN = 100 * 10^6 = 10^8 i.e < 10^9 (limit is 10^9 right)
-
I have included break statements in the inner loop and update the i value so the time complexity would be around ~ O(N)
BTW Thanks for the response.
Why would you go for a O(n^2) solution when a straight-forward O(n) is available?
I am not able to convert the logic into single loop so used two loops.
Oh i get it, see try this tc:
1
1 5
1
While going inside the loop c = 1 then you are getting f = i +1( f = i then j = f + 1 ) which is 1 then it goes in for loop it never executes because i = 1 and n = 1 too, which results in the value of i never getting incremented and hence an Infinite loop causing TLE. It’s not giving TLE when K<element and n==1 because you have a condition for that.
Here is the result of this test case: M9LVrq - Online Java Compiler & Debugging Tool - Ideone.com
1 Like
Yeah correct!!! Thanks for that I understood now why it is showing TLE.
Hi!!!
a for loop is not required inside a while loop for this problem.
I code in Python so I don’t know if you will understand my code so I am gonna explain it here and attach the link to my answer if you understand it (Python is quite an easy language to read and understand).
first we take the input-n and k
then we take the weight of boxes in a list.
then we know that chef can’t carry weight more than k so if any box weighs more than k so we can directly print -1 and continue to next case.
now if code reached this far then it means it is possible to get all boxes to start. So real thing begins!
we will need 2 variables - the no. of trips and no. of boxes currently in hand.
we will define a while loop which runs while length of list of boxes is greater than 0
then inside it we will define another while loop which runs while the weight of next box to pick is less than or equal to the weight chef can pick up more and length of list of boxes is more than 0. This won’t increase time complexity as the condition for 1st loop is being followed in second as well. If second breaks then first also breaks. First one is just to keep code working if the weight of boxes picked up becomes more than k
while the second loop is working we delete first box and add its weight to the weight of boxes picked up.
now when it breaks, it means either chef can’t pick more boxes or more boxes aren’t left so he returns means one trip is complete so we increase one trip and make weight of boxes in hand = 0.
if more boxes were left, this will happen again because of first loop or program will exit loops.
then we print the number of trips.
If you want to see the Python 3 code then here is the link → CodeChef: Practical coding for everyone
1 Like