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

Автор phantom11, 13 лет назад, По-английски

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.

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

»
13 лет назад, # |
  Проголосовать: нравится +1 Проголосовать: не нравится

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

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

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

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

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

      • »
        »
        »
        »
        13 лет назад, # ^ |
          Проголосовать: нравится 0 Проголосовать: не нравится

        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?

        • »
          »
          »
          »
          »
          13 лет назад, # ^ |
          Rev. 2   Проголосовать: нравится 0 Проголосовать: не нравится

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

          • »
            »
            »
            »
            »
            »
            13 лет назад, # ^ |
              Проголосовать: нравится 0 Проголосовать: не нравится

            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 :(.

            • »
              »
              »
              »
              »
              »
              »
              13 лет назад, # ^ |
                Проголосовать: нравится 0 Проголосовать: не нравится

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

»
13 лет назад, # |
  Проголосовать: нравится +4 Проголосовать: не нравится

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

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится +5 Проголосовать: не нравится

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

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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.

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится +1 Проголосовать: не нравится

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

    • »
      »
      »
      13 лет назад, # ^ |
        Проголосовать: нравится 0 Проголосовать: не нравится

      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.

  • »
    »
    13 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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!

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

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