This question is from February COOK OFF DIV B.I want to know if this question is solvable using quick sort.Even after using randomised quick sort i get time limit exceeded.If anyone has solved it using only quick sort,please do share the link to your code.
Here are mine links of TLE:
CodeChef: Practical coding for everyone β Normal quick sort
CodeChef: Practical coding for everyone β Randomised quick sort
Please do tell me if am somewhere wrong or missing something.
Here. I have modified your code so that it gives AC. It seems that the testers made anti-quicksort cases so that it runs in O(N^2) in worst case. All I did was replace your Quicksort with std::sort.
EDIT:
It does pass quicksort. See this. I have used in-built quicksort of C++. Maybe your implementation of quicksort failed to pass some cases.
Generally, it is always advisable to use in-built functions if they are available, as they have been thoroughly tried and tested.
Hope this helps
Thank you for replying.Actually I know it works with std::sort() as well as it works with merge sort.I asked this because I wanted to make sure that it is not solvable using quick sort only.In this CHEFPARTY - Editorial - editorial - CodeChef Discuss editorial of CHEF PARTY,they should have mentioned that itβs not solvable using quick sort.Instead they have mentioned itβs solvable using quick sort.
Let me try it using Quicksort. Iβll get back to you.
I have edited my answer. Have a look
Ok.Thank you for taking your time to answer my question.