ScoobyDoobyDo's blog

JAVA Discussion: Collections.sort() over Arrays.sort()
By ScoobyDoobyDo, history, 4 years ago, In English

Hey Friends,

I had a fundamental query to ask which is somewhat related to the submission (I stated below), Does using set.contains() { mainly takes log(n) time } functionality take longer than 2 seconds to compute for the data as large as 2*10^5 (if we check for every input of the array that is) I am asking this because my submission to the problem 1490E - Accidental Victory (E. Accidental Victory), gave me TLE on the specified constrained. My submission -: 110974416 (look for solve() function part please)

or, Is there any other thing that I'm missing out here. Any Help regarding this will be appreciated. Thanks in advance

UPD: Solution: It was improper sorting which caused the TLE not HashSet Related functionality.

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

Comments Comments (6)
| Write comment?
»
4 years ago, # |
  Vote: I like it -7 Vote: I do not like it

The set that you are using is hash set, operations of which does not work in $$$O(\log n)$$$. Hash set has operations that in theory work in constant time, but in some testcase, they might work in linear time. The testdata might contains such test, and they often do because the problem setters oftern make anti-hash test.

For $$$O(\log n)$$$ set, you might want to use TreeSet.

→ Reply
  • »
    »
    4 years ago, # ^ |
    ← Rev. 2   Vote: I like it +8 Vote: I do not like it

    Thanks Master It turned out that the reason for TLE was not just using HashSet but also the way is was sorting the initial array ( I didn't knew that Collections.sort() works faster than Arrays.sort() in some cases like this one), The Solution worked fine after this change. (Java is quite a mysterious language afterall, lol) I really appreciate your help.

    → Reply
»
4 years ago, # |
  Vote: I like it +8 Vote: I do not like it

It's actually not the issue of the set but actually the issue of sorting. Before Java 14, Arrays.sort on primitives gives worst case quadratic time. Shuffling before sorting gives AC 110982385. On a side note I'd like to point out that Java HashSet is actually only worst case O(logn) performance on comparable elements (e.g. Integers). This is because it becomes a BBST upon getting overloaded.

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

    Thanks a lot. Regarding the same approach I had query, Does Arrays.sort() use quick Sorting to sort the array on the standard case (since the randomization of the array element will be significant when we do that right? That pivot thing).

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

      Yes. Arrays.sort() uses a somewhat complicated dual pivot quicksort which becomes insertion sort as the array becomes small enough. Unfortunately, the two pivots are chosen deterministically which makes it vulnerable to these hacks.

      → Reply
»
4 years ago, # |
← Rev. 3   Vote: I like it 0 Vote: I do not like it

I also got hacked once because of using Arrays.sort() to sort a combination of numbers.

Since then, I do the following two things interchangeably.

1. Using Collections.sort() by using data structure as ArrayList.
2. First shuffling the array and then using Arrays.sort() to nullify the chances of hitting the worst case scenario in double pivot quick sort.


My shuffle template

Credits: This comment

→ Reply