Can anyone help me with Triplets problem?

general
#1

I don’t know why am i getting TLE in 2 cases. I tried using sort function from the library and because of that i got one more testcase under TL. But I don’t get the difference between sort() function of C++ STL and heapSort() which i have implemented. I think time complexity is same for both. So, i have 2 questions to ask: (i). why there is difference in time when i use sort() from C++STL and heapsort()? (ii). Why am i getting TLE in any testcase( time complexity of the code is O(n log n) and i have seen other solutions which implemented it in just the same way)?

Problem link: https://www.codechef.com/problems/SUMQ

My Solution: https://www.codechef.com/viewsolution/14288346

#2

i) sort() function of C++ is ALWAYS NlogN , because it measures things like recursion depth etc. and switches to most optimal sorting technique. It is the quickest one, afaik. Although heap sort is also O(NlogN) in worst case, we shouldnt neglect constant factors while comparing 2 similar time complexities.

ii) Give me some comments on your technique to better get what you tried. That will help in understanding the TLE. for now, please try the fast input method.

Add follow after int main() -

ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);

use only cin and cout (no scanf and printf!!) See if it helps :slight_smile:

EDIT: Not sure, but i dont think array b needs sorting. Array a and c were enough in most the codes :confused:

1 Like
#3

Use ios_base::sync_with_stdio(0); after into main() line

#4

Use ios_base::sync_with_stdio(0); after into main() line

#5

Try using stdio operations or using std::ios::sync_with_stdio(false)

#6

Why does my code get TLE when logic is similar to yours?

Please help me debug my


[1].


  [1]: http://ideone.com/X4CODf
#7

@xerefic , @harishm , you people better be careful @admin loves to check karma histories :stuck_out_tongue:

1 Like
#8

Adding that worked very well. Time got reduced to nearly half. sorting array B was necessary. I have to figure out the sum of all elements which are less than or equal to each b[i]. For that i have sorted all the 3 arrays. As the elements in array b are sorted so i just have to add sum for b[i-1] with elements which are > b[i-1] and <= b[i]. So that we have to traverse a and c only once.

#9

This problem had large input. Time will reduce further if you replace “cout<<ans<<endl;” with “cout<<ans<<”\n";" But the effect wont be that much as input is much greater than output.

1 Like
#10

if you are using cin.tie(NULL) then use endl instead of “\n” otherwise the flow of your program will be different from what you are expecting i dont know the reason but it had happened to me