Lena Sort
Lena Sort
+ 0 comments Why does this problem have only a score of 30? I think it's harder than that.
+ 1 comment I believe this has many solutions for a singl qeury only.
Say, for query of len of array = 5 and comparisons is 6.
The proposed array is [4,2,1,3,5]. It can also be [5,3,2,4,6] -Adding 1 to each row.
Or it may be [8,4,2,6,10].
There are many possibilities in here.
Please specify some constraints.
+ 4 comments I recommend avoiding Python when solving this problem. I couldn't solve the problem without reaching maximum recursion depth in Python. I consulted with the Editorial and the provided solution does in fact cause such an error when converted to Python.
+ 0 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:
- 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 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:- 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 secondsinput04
: seconds vs secondsinput11
: seconds vs seconds
Python3 code
#!/bin/python3 import math import os import random import re import sys sys.setrecursionlimit(100000) def get_min_arr(length, start): """ get the array with integer 0, ..., n-1 such that it requires the minimum number of comparison when applying QuickSort. """ if length == 0: return [] if length == 1: return [0] memo = [(0, length)] while len(memo) < length: new_memo = [] for m in memo: if isinstance(m, int): new_memo.append(m) else: s, l = m middle = s + (l - 1) // 2 new_memo.append(middle) s_less, l_less = s, (l - 1) // 2 s_more, l_more = middle + 1, l // 2 if l_less == 1: new_memo.append(s_less) elif l_less > 1: new_memo.append((s_less, l_less)) if l_more == 1: new_memo.append(s_more) elif l_more > 1: new_memo.append((s_more, l_more)) memo = new_memo return [start + m for m in memo] def rec(length, comparisons, first): if length == 0: return [] if length == 1: return [first] # length of increasing sequence it could tolerate prefix_length = 0 remaining = length while True: tmp = remaining - 1 if comparisons - tmp >= smallest[tmp]: prefix_length += 1 comparisons -= tmp remaining = tmp else: break prefix = [first + p for p in range(prefix_length)] if prefix_length == length: return prefix # find a feasible length for the less part length -= prefix_length comparisons -= remaining - 1 first = first + prefix_length for less in range((length + 1) // 2): more = length - 1 - less max_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) if upper >= lower: break pivot = first + less if lower == comparisons - max_more: comparisons_less = lower A = rec(less, comparisons_less, first) B = list(range(pivot + 1, pivot + 1 + more)) elif upper == comparisons - min_more: comparisons_less = upper A = rec(less, comparisons_less, first) B = get_min_arr(more, pivot + 1) else: comparisons_less = upper comparisons_more = comparisons - comparisons_less A = list(range(first, first + less)) B = rec(more, comparisons_more, pivot + 1) return prefix + [pivot] + A + B if __name__ == '__main__': sys.setrecursionlimit(100000) smallest = [0, 0] q = int(input()) for q_itr in range(q): l, c = list(map(int, input().split())) # Get the smallest number of comparison for length l for length in range(len(smallest), l + 1): if length % 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) // 2 if c < smallest[l] or c > largest: result = '-1' else: arr = rec(l, c, 1) result = ' '.join(map(str, arr)) print(result)
+ 1 comment There is an error in the base Python2 code for this challenge:
q = int(raw_input().strip()) for a0 in xrange(q): len,c = raw_input().strip().split(' ') len,c = [int(len),int(c)]
Since len is being used as a variable, if I try to use the builtin len() in my function, I get a TypeError that says 'int object is not callable'.
Sort 20 Discussions, By:
Please Login in order to post a comment