Блог пользователя pranp_24

Hacked and Confused
Автор pranp_24, история, 22 месяца назад, По-английски

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.net/contest/1791/submission/192492521 Problem Link: https://codeforces.net/contest/1791/problem/G1

  • Проголосовать: нравится
  • +1
  • Проголосовать: не нравится

»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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

→ Ответить
»
22 месяца назад, # |
  Проголосовать: нравится +7 Проголосовать: не нравится

cause you use java

→ Ответить
»
22 месяца назад, # |
  Проголосовать: нравится 0 Проголосовать: не нравится

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.

→ Ответить
  • »
    »
    22 месяца назад, # ^ |
    ← Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    → Ответить
»
22 месяца назад, # |
  Проголосовать: нравится +19 Проголосовать: не нравится

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

→ Ответить
»
22 месяца назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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).

→ Ответить