I’ve just checked a successful Java solution. I noticed the programmer used a custom fast I/O, so I modified my own solution with this fast I/O and got AC. So even using Java buffered streams is not fast enough and it is neccessary to use custom I/O. I think this should be included in the FAQ. Don’t you use Scanner, don’t you use BufferedReader, use custom I/O. It is a huge difference !!! I measured execution of 100 test cases (all of them being the example test case). When using BufferedReader + Scanner it took 0.646 seconds, when using custom I/O it just took 0.026 seconds.
I used the same dfs approach, but was getting the TLE. And I even tried using fast IO, but it did not work. Finally is modified my code to if(m == n*(n-1)/2) return 0 ,as for complete graph there are no cut nodes and it got AC. My code was in java. I still don’t understand how many milliseconds did it save!
@milhaus : Thanks for your help but @anunay_arunav is right. Removing those test cases do save a TLE even without using fast I/O.
This is sometimes really dissapointing on part of Codechef that the time limit they set is too much strict, even after getting the algorithm correct, one has to waste time on over-optimizing.The dfs approach was already optimized.
@Tester: It is my attempt for this problem - CodeChef: Practical coding for everyone .
can anyone please look at it and tell me why it getting WA (can I know the test cases for which it getting WA)
I tried to solve the prob using Articulation Point concept but , am getting TLE. CodeChef: Practical coding for everyone :->Here is my solution.
Please debug my code
me 2… Took a lot of time to find it, at first I thought it was mostly a had hoc problem because a lot of people were solving it and good tutorials on this were hard to find…
Such solution has complexity O(N * M). In this problem N could be up to 3000 and M could be up to 4500000. So N * M is very large number. It depends on test data whether such solution could be fit into TL using some tricks.
@betlista >> Because before went to depth I wanted to first try out from things that I already know but … rather I am thankful that I learned new things.
In java, you cant really say anything. The TL is set basically using C/C++ because tester and setter both use these most of the times. You did well, congratulations and all the best for future contests.
rather I am thankful that I learned new things.