Why TLE in Triplets ( SUMQ ) ?

I got 30 points in the problem Triplets ( SUMQ ) from the contest JUNE17.

My solution in c++

My solution in java

How can I optimize my code more than this?

One more thing, I noticed that I got TLE in only one test case in c++ solution and got TLE in two test cases in java solution.
Why is this so as I used the same approach in both of my solutions?

Can anyone tell me how can I optimize my java solution?

instead of cin use scanf for taking input.

1 Like

Follow this thread:
https://discuss.codechef.com/questions/101196/can-anyone-help-me-with-sumq-from-june17

Using scanf instead of cin or typing iosbase:syncwith_stdio (false) just after the int main() line will solve your problem

2 Likes

I have calculated prefix sums of each of the three arrays and then just use them to derive the final result. The prefix sums helped me to get rid of every redundant calculation.

My solution: CodeChef: Practical coding for everyone

1 Like

ios_base::syn_with_stdio(flase);

Thing totally works thanks man!

Can someone throw some light on when to use it?

@manjrekarmon29 . Follow this thread on Stack Overflow.

Use scanf instead of cin for taking input and Printf instead of cout your solution will be accepted.
If you have any doubt you can check this solution CodeChef: Practical coding for everyone

As it is already told that you need Fast I/O to solve this problem, I’ll just add the solution for Java.

Refer - http://www.geeksforgeeks.org/fast-io-in-java-in-competitive-programming/
https://www.hackerearth.com/practice/notes/inputoutput-in-javascanner-bufferedreader-self-made-fast-io/

Scanner is one of the slowest methods to take input.

2 Likes

Can someone help me here? I was using this java code (sumq - Pastebin.com ) to solve this problem and I got NZEC. But when I removed the prefix sum thing first task was running fine and tle in second task (as expected), but I dont know why I was getting NZEC after applying prefix sum.
Finally I converted the same code to c++ and got AC.
Thanks.

There is no need to sort array q. You can arrive at the solution by sorting the p and r arrays , calculating the prefix sums, then doing upper bound search for each of the element of q in both p and r arrays. There is a bit of calculation involved in the last part. But removing the sorting of q array should get you an AC(I did).

That alone wont solve the problem if you apply brute-force

if u are including <bits/stdc++.h> then don’t include any other header,
as you also included in your c++ code

@sharan_omkar Thanks!!

It really worked!!!

What will you say about my java solution?

How can I optimize that?

1 Like

Thanks!

ios_base::sync_with_stdio(false);

After using above line, it worked!!

Can you help me in optimizing my java solution?

Thank you.

Got 100 points after using BufferedReader class instead of Scanner class for taking input.

Invalid link. Wait, lemme fix it.