Блог пользователя Distructed_Cat

Автор Distructed_Cat, история, 5 лет назад, По-английски

While solving a problem I get TLE by submitting it as JAVA 11. But same code while submitted as JAVA 8 it got Accepted. Can any one describe why this happen. And please provide me the template of fastest I/O in JAVA for competitive programming. Thanks in advanced.

  • Проголосовать: нравится
  • -3
  • Проголосовать: не нравится

»
5 лет назад, # |
  Проголосовать: нравится +16 Проголосовать: не нравится

The solution that got accepted in java 8 was 2 milliseconds away from TLEing; my guess is you just got lucky (or got unlucky the first time). That said, most ICPC regionals use java 8, so that's what most competative programmers who code in java use. There isn't really anything in java 11 that you need in competative programming.

As a side note, the reason your code was so slow is because you are using Scanner and System.out.println(). Scanner has a really tiny buffer, which makes it slow when you read more than 1000 integers in input. You can use a BufferedReader and a StringTokenizer instead, combined with Integer.parseInt(). If you look at my submissions, I will wrap this in a class I call FastScanner which works the same way as Scanner but is way faster.

Then for output, if you are outputting more than a few integers, or if the problem is multitestcase, you need to use a PrintWriter. That code looks like this:

  //top of program
  PrintWriter out=new PrintWriter(System.out);

  //figure out your answer

  //end of program
  out.println(answer);
  out.close();

Fast input and PrintWriter for output are the big two causes of Java TLE's. The third one (which is pretty CF specific) is that calling Arrays.sort() on an array of primitives is $$$O(n^2)$$$, not $$$O(n*log(n))$$$ like you would expect. It uses dual-pivot-quicksort internally, and it is possible to create worst case for the sort by reverse-engineering how it works. The solution is to either shuffle you array before sorting it, or to use Collections.sort() which uses mergesort and is always $$$O(n*log(n))$$$.