__goku__'s blog

By __goku__, history, 4 years 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

| Write comment?
»
4 years 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.

  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Can you please tell why did that work?

    • »
      »
      »
      4 years 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.

      • »
        »
        »
        »
        4 years 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.

        • »
          »
          »
          »
          »
          4 years 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.

          • »
            »
            »
            »
            »
            »
            4 years ago, # ^ |
              Vote: I like it 0 Vote: I do not like it

            Yup that maybe the reason why ArrayList worked then.

            • »
              »
              »
              »
              »
              »
              »
              4 years 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.