CHEFPARTY FEBRUARY COOK OFF

general
, ,
1

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:
https://www.codechef.com/viewsolution/23143243 -> Normal quick sort
https://www.codechef.com/viewsolution/23183538 -> Randomised quick sort
Please do tell me if am somewhere wrong or missing something.

2

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 :slight_smile:

1 Like
3

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 https://discuss.codechef.com/questions/145625/chefparty-editorial 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.

4

Let me try it using Quicksort. I’ll get back to you.

5

I have edited my answer. Have a look :slight_smile:

1 Like
6

Ok.Thank you for taking your time to answer my question.