June Long -Triplets (TLE)

general
, ,
1

Can anyone tell me why is it giving tle 1.01 although my approach is O(nlogn)
Link-https://www.codechef.com/viewsolution/14248910

2

Instead of binary search you better use upper bound.You can see my accepted solution here https://www.codechef.com/viewsolution/14007543

If you still have any doubt feel free to comment.

1 Like
3

Although your solution is O(nlgn) but it has high constant factor associated with it, for the following reasons

  1. In general floating point operations are slower than integer operations. try to change data type of vector a,b,c in your solution from double to int

  2. you can change your long long data type to integer (sum1 and sum2) ,int data types are faster , use modulo operations at every intermediate sum, and whenever there is chance of overflow use type cast operation.

  3. use call by reference for passing array and vector.

  4. Dont use Push_back() function instead allocate enough space and use [] operator for such large input. Push_back() function does a bound check everytime, which unnecessarily consumes time.

  5. And use ios::sync_with_stdio(false) for fast IO.

here is my solution: https://www.codechef.com/viewsolution/14177030
.It is similar to yours except the above points.

3 Likes
4

he used printf and scanf,then no need to use ios::sync_with_stdio(false)

5

One thing I want to mention over here is that whenever you pass any STL container (vector,set,map,etc.) into another function C++ makes a copy of that container and then pass it as value. (i.e. call by value) unlike arrays which it passes by reference.
In your code you are always creating a copy of vector while passing it into your b_search function:

int b_Search(vector<double > v,double value,int start,int end)

So every time you are calling your b_search it is taking an extra O(n) time to make a new copy of vector . O(n) space too.
Solution: pass your vector by reference

int b_Search(vector<double > &v,double value,int start,int end)

Remember : You are not manipulating the vector and only accessing it.
Happy Coding :slight_smile:

2 Likes
6

c++ cin and cout are faster than scanf and printf, when used with ios::sync_with_stdio(false)

scanf and printf does format string decoding, which takes additional time.

7

Thank you.

8

Ok . I got it .Thank you.

9

Thank you very much sneh_m.

10

you can use fast i/o
ex for reading use getchar_unlocked.its pretty fast
it doesnt lock cant be used in multithreaded environment but safe here

11

Hey can anyone help. I have solved it in java and used fast i/o. Still getting a TLE for larger test cases. Also can someone pls give me some karma as I am not allowed to ask questions.I thank you in advance. Here’s my code:

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

12

You cannot request for upvotes on this ground as there is a thread (https://discuss.codechef.com/questions/97820/i-want-to-ask-a-question-ask-them-all-here ) for you guys to ask question (and it gets upgraded to an individual/independent question if its valid/in accordance to rule)

13

In your submission i could see one thing… for every B[i] you are using linear search to find the #of values are less than or equal to B[i]…but you have sorted list… why don’t you apply binary search over Array A and C to get n1 and n2 and use cumulative sums…you solution will surely pass the testcases

14

Also, i think you used 3 nested loops, your program will take a lot of time to complete the task. Give a search to forums, the question has been discussed before.

15

@srikanth_16 I tried a new submission with bsearch still getting a TLE. Here’s the link to the new submission:

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

16

@ankush23 You can also do one thing that declare all a,b,c,sum1,sum2 vectors inside test cases. This will prevent you from clearing them again and again. I guess for clearing it takes O(n) and that can be made O(1) and as suggested by @sneh_m there is no need of double so you can remoove that too.

1 Like