We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
Here is a solution I came up with. I will first discuss the idea in word and post the complete code at the end.
This is a rather hard problem for me and I worked on it for 3 days straight to get a python solution that will run fast enough to be accepted.
My solution is definitely not perfect and it is also very verbose. I will work on optimizing it continuously.
Two key observations:
The maximum number of comparisons for an array of length n is . This happens when the array is already sorted in either increasing or descreasing order.
The minimum number of comparisons as a function array length can be calculated using dynamic programming (the list smallest in the code below. The recursive formula is smallest[n] = smallest[(n - 1) // 2] + smallest[n // 2] + n - 1. That is to say, we can sort the array with the minimum number of comparisons if the pivots (arr[0]) are always the middle largest.
I know that the validity of the number of comparisons can be determined during the divide-and-conquer step (the recursion function rec) but I decided to test the validity before running recursion since that helps me think clearly (as I am sure that the recursion would be success without me coding for bounary cases).
How to avoid large stack height
The divide-and-conquer solution using recursion is kind of straightforward, but we may can run into the problem stack overflow especially when the array is partially sorted. I added sys.setrecursionlimit(100000) to increase the recursion limit but I doubt whether it is still needed in my solution. I will look into the matter later and please try remove the line and see whether it works.
The rec function has two parts:
finding the longest increasing sequence the number of comparisons could tolerate. Without this step, we may run too many divide-and-conquer with a length-0 array as the first half when the array is partial sorted.
When we can no longer have monotonically increasing sequence as prefix, we find the a feasible length for the less part.
Some other things that may decrease the total number of recursion needed
When we have to sort an array with the minimum number of comparisons, the array can be formed using non-recursive function (get_min_arr). The recursive solution is also kind of straightforward but we can turn it into a non-recursive solution using something similar to the BFS. I have tested on input 03, 04, and 11 and it does speed the calculation up by a lot:
input03: seconds vs seconds
input04: seconds vs seconds
input11: seconds vs seconds
Python3 code
#!/bin/python3importmathimportosimportrandomimportreimportsyssys.setrecursionlimit(100000)defget_min_arr(length,start):"""getthearraywithinteger0,...,n-1suchthatitrequirestheminimumnumberofcomparisonwhenapplyingQuickSort."""iflength==0:return[]iflength==1:return[0]memo=[(0,length)]whilelen(memo)<length:new_memo=[]forminmemo:ifisinstance(m,int):new_memo.append(m)else:s,l=mmiddle=s+(l-1)// 2new_memo.append(middle)s_less,l_less=s,(l-1)// 2s_more,l_more=middle+1,l// 2ifl_less==1:new_memo.append(s_less)elifl_less>1:new_memo.append((s_less,l_less))ifl_more==1:new_memo.append(s_more)elifl_more>1:new_memo.append((s_more,l_more))memo=new_memoreturn[start+mforminmemo]defrec(length,comparisons,first):iflength==0:return[]iflength==1:return[first]# length of increasing sequence it could tolerateprefix_length=0remaining=lengthwhileTrue:tmp=remaining-1ifcomparisons-tmp>=smallest[tmp]:prefix_length+=1comparisons-=tmpremaining=tmpelse:breakprefix=[first+pforpinrange(prefix_length)]ifprefix_length==length:returnprefix# find a feasible length for the less partlength-=prefix_lengthcomparisons-=remaining-1first=first+prefix_lengthforlessinrange((length+1)// 2):more=length-1-lessmax_more,min_more=more*(more-1)// 2, smallest[more]max_less,min_less=less*(less-1)// 2, smallest[less]lower=max(min_less,comparisons-max_more)upper=min(max_less,comparisons-min_more)ifupper>=lower:breakpivot=first+lessiflower==comparisons-max_more:comparisons_less=lowerA=rec(less,comparisons_less,first)B=list(range(pivot+1,pivot+1+more))elifupper==comparisons-min_more:comparisons_less=upperA=rec(less,comparisons_less,first)B=get_min_arr(more,pivot+1)else:comparisons_less=uppercomparisons_more=comparisons-comparisons_lessA=list(range(first,first+less))B=rec(more,comparisons_more,pivot+1)returnprefix+[pivot]+A+Bif__name__=='__main__':sys.setrecursionlimit(100000)smallest=[0,0]q=int(input())forq_itrinrange(q):l,c=list(map(int,input().split()))# Get the smallest number of comparison for length l forlengthinrange(len(smallest),l+1):iflength%2==0:s=smallest[length// 2 - 1] + smallest[length // 2]else:s=2*smallest[length// 2]smallest.append(s+length-1)# If the number of comparisons c is not within the range = [smallest, largest],# there is no array will sort with c comparisons.largest=l*(l-1)// 2ifc<smallest[l]orc>largest:result='-1'else:arr=rec(l,c,1)result=' '.join(map(str,arr))print(result)
Cookie support is required to access HackerRank
Seems like cookies are disabled on this browser, please enable them to open this website
Lena Sort
You are viewing a single comment's thread. Return to all comments →
Here is a solution I came up with. I will first discuss the idea in word and post the complete code at the end.
This is a rather hard problem for me and I worked on it for 3 days straight to get a python solution that will run fast enough to be accepted.
My solution is definitely not perfect and it is also very verbose. I will work on optimizing it continuously.
Two key observations:
smallest
in the code below. The recursive formula issmallest[n] = smallest[(n - 1) // 2] + smallest[n // 2] + n - 1
. That is to say, we can sort the array with the minimum number of comparisons if the pivots (arr[0]
) are always the middle largest.I know that the validity of the number of comparisons can be determined during the divide-and-conquer step (the recursion function
rec
) but I decided to test the validity before running recursion since that helps me think clearly (as I am sure that the recursion would be success without me coding for bounary cases).How to avoid large stack height
The divide-and-conquer solution using recursion is kind of straightforward, but we may can run into the problem stack overflow especially when the array is partially sorted. I added
sys.setrecursionlimit(100000)
to increase the recursion limit but I doubt whether it is still needed in my solution. I will look into the matter later and please try remove the line and see whether it works.The
rec
function has two parts:Some other things that may decrease the total number of recursion needed
When we have to sort an array with the minimum number of comparisons, the array can be formed using non-recursive function (
get_min_arr
). The recursive solution is also kind of straightforward but we can turn it into a non-recursive solution using something similar to the BFS. I have tested on input 03, 04, and 11 and it does speed the calculation up by a lot:input03
: seconds vs secondsinput04
: seconds vs secondsinput11
: seconds vs secondsPython3 code