Please, try EDU on Codeforces! New educational section with videos, subtitles, texts, and problems. ×

__goku__'s blog

By __goku__, history, 6 weeks ago, In English,

My program is running in O(n) time (I hope so) but it is showing TLE in java. Can anyone please tell me what am I doing wrong here. I have used fast input with both BufferedWriter and PrintWriter but it is still showing tle. I know there is no problem with my logic because the same logic is accepted in C++. So can someone please tell me what is wrong with my java code.

Solution: Java: 82284306 CPP: 82285437

Problem: 1324D - Pair of Topics

Edit 2: The code worked after I replaced array with ArrayList. Can anyone explain to me why did this happen? Thanks in advance.

 
 
 
 
  • Vote: I like it
  • +2
  • Vote: I do not like it

»
6 weeks ago, # |
Rev. 2   Vote: I like it 0 Vote: I do not like it

try shuffling your array before sorting.

UPD: I just tried it. It works.

  • »
    »
    6 weeks ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please tell why did that work?

    • »
      »
      »
      6 weeks ago, # ^ |
      Rev. 4   Vote: I like it 0 Vote: I do not like it

      If you read the javadocs for Arrays#sort, you will see that it uses Dual Pivot Quicksort algorithm. If you studied a basic algo course before, you would know that the performance of quicksort rests mainly upon its pivoting step — If you are lucky, the chosen pivot is almost always the median. So the depth of the quicksort recursion, in this case, is $$$\mathcal{O}(\log n)$$$. Hence, quicksort's performance is worst when the pivot is (almost) always skewed towards the extreme left or right. The test data that your code failed on was designed to cause this behavior in quicksort. So the solution is to simply shuffle the array so that no one can predict which will be the chosen pivot, reducing the likelihood that quicksort will hit its worst case behavior.

      • »
        »
        »
        »
        6 weeks ago, # ^ |
        Rev. 2   Vote: I like it 0 Vote: I do not like it

        Thanks, till now I believed that sort function worked upon merge sort but I was wrong. Now the random ordering make sense.

        • »
          »
          »
          »
          »
          6 weeks ago, # ^ |
            Vote: I like it 0 Vote: I do not like it

          Well, Collections#sort does use merge sort. So you can use that as an alternative. You don't even have to shuffle the array beforehand in that case.

          • »
            »
            »
            »
            »
            »
            6 weeks ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yup that maybe the reason why ArrayList worked then.

            • »
              »
              »
              »
              »
              »
              »
              6 weeks ago, # ^ |
              Rev. 2   Vote: I like it 0 Vote: I do not like it

              Another neat little function is Arrays.parallelSort(), which works for primitive arrays.

              Otherwise you can use Arrays.sort() for object arrays like Integer, Long, etc. since Java uses merge sort for sorting array of objects.

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by __goku__ (previous revision, new revision, compare).

»
6 weeks ago, # |
  Vote: I like it 0 Vote: I do not like it

Auto comment: topic has been updated by __goku__ (previous revision, new revision, compare).