OneClickAC's blog

Can aybody help me with TLE..?? :(
By OneClickAC, history, 7 years ago, In English

Hi Reader,

I just wrote the solution for this problem (710-B) in Java and I just don`t know that why i am getting a TLE verdict.. Problem link -> http://codeforces.com/contest/710/problem/B The real reason to worry is that my code is passing one of the tests (where value of n is 300000) but is getting a verdict of TLE where (n is equal to 299999) .. How can this be posssible ?? I have used basic inbuilt sorting algorithm in Java and then one more step of O(n) complexity . So if n is larger , time will also be larger. As it will be directly proportional to O(n) or O(nlogn).. What is the reason behing this , that time is larger in latter case?? Infact , I then solved the problem in C++ where no such unexpected activity is happening and i passed all tests ..

Please help me out with this !! This is my code -> http://pastebin.com/DfYg30zj This is my submission link -> http://codeforces.com/contest/710/submission/23467650

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

»
7 years ago, # |
  Vote: I like it +10 Vote: I do not like it

I guess it's anti-quick sort testcase.

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

    Well , I guess not .. Because , as I said , I have also submitted the same code in c++ also and there are no such discrepancies .. As you can also see in my submissions , for c++ -> http://codeforces.com/contest/710/submission/23467676 for java -> http://codeforces.com/contest/710/submission/23467650 in c++ code , everything is normal.(test-24 and test-9 to 15).. Problem is in java version..

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

      Accepted code

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

        I believe our codes are same , only that you have used (Integer) to define the array and i have used long keyword.. Can you please tell me now (the reason) , why my code is getting a TLE verdict and your`s not..??

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

          In java primitive datatype arrays (long , int , etc..) are sorted using a variant of quicksort . Since the worst case complexity of quicksort is O(N2) you are getting a TLE . On the contrary java uses merge sort for sorting reference data types (Integer , Long , etc...) . If you want to use a primitive data type array then just shuffle the array before sorting .

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

            Well i had no idea about this sorting thing in java Thanks for telling about this bhishma .. :)

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

      In C++ std::sort is using introspection sorting. For anti-quicksort test cases it would switch to heapsort.

      → Reply