Getting TLE in Round 111 Div-2

12 лет назад, # ^ |

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

→ Ответить

dalex

12 лет назад, # ^ |

Run it with -Xss256M

→ Ответить

12 лет назад, # ^ |

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

→ Ответить

12 лет назад, # ^ |

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

→ Ответить

12 лет назад, # ^ |

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

→ Ответить

12 лет назад, # ^ |

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

→ Ответить

12 лет назад, # ^ |

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?

→ Ответить

12 лет назад, # ^ |

← Rev. 2 →

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

→ Ответить

12 лет назад, # ^ |

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

→ Ответить

12 лет назад, # ^ |

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

→ Ответить

12 лет назад, # ^ |

thanks a lot! i got it.

→ Ответить

imslavko

12 лет назад, # |

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

→ Ответить

I_love_natalia

12 лет назад, # ^ |

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

→ Ответить

12 лет назад, # ^ |

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.

→ Ответить

imslavko

12 лет назад, # ^ |

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

→ Ответить

I_love_natalia

12 лет назад, # ^ |

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.

→ Ответить

12 лет назад, # ^ |

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!

→ Ответить

12 лет назад, # |

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

→ Ответить

I_love_natalia

12 лет назад, # ^ |

← Rev. 2 →

Arrays.sort is $\text{[math]}$ (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.

→ Ответить

dalex

12 лет назад, # ^ |

Actually, the generator is written by AlexanderBolshakov (his post: http://codeforces.com/blog/entry/2296)

→ Ответить