phantom11's blog

Getting TLE in Round 111 Div-2

By phantom11, 12 years ago, In English

I cant understand whats the problem with test case 66(n=10^5 k=1).It gives TLE. During the contest I submitted this code and it gives TLE in 66. After the contest when I saw the test case ,I put a condition of checking if k=1 for immediate passing ,just to see if it worked,and it again gave TLE(code). I used BufferedReader to check if its because of large inputs,but again TLE(code). And its not only me but many who got TLE in 66 using java(see this page). Please tell me where is it going wrong because in test case 65 also n=10^5,k=1 so it cant be a sorting issue or a input issue...But immediately after reading inputs and sorting I am displaying the result for k=1.Then why is it passing for 65 and failing for 66.

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

»
12 years ago, # |
  Vote: I like it +1 Vote: I do not like it

Try to generate the test using this program: http://pastie.org/2222386

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

    This program gives an error at line 152-stack overflow exception even when I changed the array size to 100000

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

      Run it with -Xss256M

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

        Can u please tell me how to use it.I use IntelliJ Idea.

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

        Ok .got it in the internet.Had to add a new environment variable JAVA_OPTS ..but still it gives the same error

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

    thanks a lot for the link! shouldn't the code output an array (which quicksort takes a long time to sort)?.

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

      Yes, this code outputs such an array. It is directly based on the Arrays.sort() implementation of Java 6.

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

        Thanks! I tried creating an array of 100000 integers and sorting them using the 2 methods, however, I can't see quicksort giving bad results..

        Here's what I'm getting for 100 elements: 68 1 2 3 4 5 6 7 8 63 64 69 66 74 84 13 14 15 16 17 73 19 82 21 93 23 92 25 26 27 28 78 30 31 32 81 34 35 91 37 71 39 40 41 42 80 44 45 46 70 48 49 97 51 52 79 54 55 56 57 59 60 61 96 67 89 76 9 77 18 98 29 90 88 65 85 10 86 20 43 33 53 83 72 94 11 95 22 47 36 58 87 75 99 12 0 24 50 38 62

        Could you please verify this?

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

          Is your test made against the naive implementation of quicksort? Arrays.sort() is much more complex (you can take its clean implementation from OpenJDK 6).

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

            I took the code from here.

            I guessed the int[] positions member of class AntiQuicksort holds the array. I printed this array and later tried to sort it using Arrays.sort(). Its still pretty fast :(.

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

              Why don't you read the code of the main method?! It outputs the array to a file called [number count].txt. And the positions[] array is used for the killQuicksort() method (more precisely: for restoring the original order of the scrambled array after it's sorted).

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

again for java coders: implementation of Arrays.sort is QuickSort which is hackable with special input data, causing Arrays.sort work O(N^2) time. be carefull: shuffle array before sort or use Collections.sort or self written merge sort, good luck

→ Reply
  • »
    »
    12 years ago, # ^ |
      Vote: I like it +5 Vote: I do not like it

    Also, be carefull with HashSet and HashMap in Java ;)

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

    Ok.Yes shuffeled the array and it got accepted.But this was very hard on the java programmers. Nobody had solved this problem in java during the contest.

    → Reply
    • »
      »
      »
      12 years ago, # ^ |
        Vote: I like it +1 Vote: I do not like it

      nobody shuffled the array, now you are more experienced and will shuffle it every time you sort something. Or use mergesort!

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

      You are free to select any programming language, but note that there are possible problems in all of them ;)

      By the way, I've seen solution by Petr about two months ago with random input shuffling.

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

    Could you explain how one would sort an array using Collections.sort()? And is the random shuffling easily achievable?

    I find that using Object[] arrays instead of long[] arrays forces java to use merge-sort but that's something I won't prefer doing everytime while sorting!

    And it WAS really hard on the java coders!

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

Was the Anti-Quicksort factor working because the time limit was 1sec..Could it have passed if time limit was 2 sec??

→ Reply