When submitting a solution in C++, please select either C++14 (GCC 6-32) or C++17 (GCC 7-32) as your compiler. ×

pranp_24's blog

By pranp_24, history, 13 months 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://codeforces.com/contest/1791/submission/192492521 Problem Link: https://codeforces.com/contest/1791/problem/G1

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

| Write comment?
»
13 months 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.

»
13 months ago, # |
  Vote: I like it +7 Vote: I do not like it

cause you use java

»
13 months 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.

  • »
    »
    13 months 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.

    • »
      »
      »
      13 months 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.

»
13 months ago, # |
  Vote: I like it +19 Vote: I do not like it

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

»
13 months 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).