UVA 11902: Getting TLE

Hi All!

I’m trying to solve UVA 11902 using JAVA. This problem is a DFS related problem, where the nodes can be maximum 100 and test case is 100. I’m new in solving problem with JAVA, so I’m suspecting there may be something silly in my code. Except that, I’ve not found anything wrong in my algo. :frowning:

Any kind of help will be appreciable. Thanks in advance. :slight_smile:

Problem link: https://uva.onlinejudge.org/external/119/11902.pdf

Code link: https://ideone.com/oDiHW3

@mukit_mkbs, your solution is efficient enough to pass the time limit, but the problem lies elsewhere. The reason you are getting TLE is that you have a ton of calls to the System.out.println() function, almost one call for each character you output. System.out.println() has the behaviour of flushing to the underlying stream whenever you call it, which is inefficient and greatly increases the execution time of your program. There are two workarounds to this.

Option 1: Use your own buffer, such as a StringBuilder. Create a StringBuilder object, and use append() to append to its end whatever you want printed. Print the contents of the StringBuilder when required, usually at the end of the program. Sample program here.

Option 2: Use buffered output, such as a PrintWriter. Create a PrintWriter object on the System.out stream with autoflush disabled. Call the print functions of the PrintWriter instead of System.out. Call the flush function to flush the PrintWriter’s buffer to the output stream when required, usually at the end of the program. Sample program here.

You can adopt either of these two ways, and you should be able to get AC :slight_smile:

3 Likes

Thanks a lot for your reply. :slight_smile: I tried both ways. Got AC in both ways. :slight_smile: Anyway, would you please suggest me which way I should code in a contest? If the time limit is too strict, I think Option 2 can be the reason of TLE. Because I got Option 2 100 ms slower than Option 1 for this problem. Anything wrong in my guess? :slight_smile: