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.
Try to generate the test using this program: http://pastie.org/2222386
This program gives an error at line 152-stack overflow exception even when I changed the array size to 100000
Run it with -Xss256M
Can u please tell me how to use it.I use IntelliJ Idea.
Ok .got it in the internet.Had to add a new environment variable JAVA_OPTS ..but still it gives the same error
thanks a lot for the link! shouldn't the code output an array (which quicksort takes a long time to sort)?.
Yes, this code outputs such an array. It is directly based on the Arrays.sort() implementation of Java 6.
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?
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).
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 :(.
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).
thanks a lot! i got 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
Also, be carefull with HashSet and HashMap in Java ;)
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.
nobody shuffled the array, now you are more experienced and will shuffle it every time you sort something. Or use mergesort!
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.
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!
Was the Anti-Quicksort factor working because the time limit was 1sec..Could it have passed if time limit was 2 sec??
Arrays.sort is
(worst-case) method with a good constant. Actually, you can run your solution with dalex's test and see the execution time. I think, it is about 3-4 seconds.
Actually, the generator is written by AlexanderBolshakov (his post: http://codeforces.me/blog/entry/2296)
When I send a PM to MikeMirzayanov, he just ignores it. But now my generator is used exactly for what I've written about in my PM. I hate such behaviour...
Anyway, thank him for giving me a reason for publishing my code. At least, many people have become aware of anti-java-quicksort.