pranp_24's blog

Hacked and Confused
By pranp_24, history, 21 month(s) ago, In English

So, I just got hacked on this problem from the recent Div4 contest for problem G1 and I still don't know why. I got TLE but there is nothing in my code that could've caused it. Can someone please help?

Submission Link: https://mirror.codeforces.com/contest/1791/submission/192492521 Problem Link: https://mirror.codeforces.com/contest/1791/problem/G1

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

Comments Comments (10)
| Write comment?
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Array.sort() in java has worst case time complexity of O(n^2), that's why your code gave tle.

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +7 Vote: I do not like it

cause you use java

→ Reply
»
21 month(s) ago, # |
  Vote: I like it 0 Vote: I do not like it

Instead of using array and Arrays.sort() , use ArrayList and Collections.sort().

I've been hacked twice due to this :(

192512576 <--- You can check out this, i've just modified your code.

→ Reply
  • »
    »
    21 month(s) ago, # ^ |
    ← Rev. 2   Vote: I like it 0 Vote: I do not like it

    I just use an array of Integer instead of int. Since it’s an object instead of an primitive type, Arrays.sort becomes nlogn with merge.

    → Reply
    • »
      »
      »
      21 month(s) ago, # ^ |
      ← Rev. 2   Vote: I like it 0 Vote: I do not like it

      Be careful when using == with object data types, you have to use .equals.

      → Reply
»
21 month(s) ago, # |
  Vote: I like it +19 Vote: I do not like it

You should use C++ even Java uses C++ !

→ Reply
»
21 month(s) ago, # |
  Vote: I like it +1 Vote: I do not like it

In Java, calling Arrays.sort() on an array of primitives uses the quicksort algorithm (hence it is possible to create adversarial cases that exhibit $$$\mathcal{O}(n^2)$$$ behavior) -- note the same is not true for arrays of reference types.

To remedy this, one solution is to first randomly shuffle your array before sorting it, or to use a different sorting algorithm (Collections.sort() for example).

→ Reply