Discussion on Lena Sort Challenge

2 years ago+ 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 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/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)