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.
  • Hackerrank Home
  • Prepare
    NEW
  • Certify
  • Compete
  • Career Fair
  • Hiring developers?
  1. Prepare
  2. Algorithms
  3. Constructive Algorithms
  4. Lena Sort
  5. Discussions

Lena Sort

Problem
Submissions
Leaderboard
Discussions
Editorial

Sort 20 Discussions, By:

votes

Please Login in order to post a comment

  • jstimpfle
    4 years ago+ 0 comments

    Why does this problem have only a score of 30? I think it's harder than that.

    14|
    Permalink
  • prateekkol2103
    5 years ago+ 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.

    8|
    Permalink
  • KamBre
    5 years ago+ 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.

    4|
    Permalink
    View more Comments..
  • pphuangyi
    1 year 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)
    
    3|
    Permalink
  • mmweber2
    5 years ago+ 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'.

    2|
    Permalink
Load more conversations

Need Help?


View editorial
View top submissions
  • Blog
  • Scoring
  • Environment
  • FAQ
  • About Us
  • Support
  • Careers
  • Terms Of Service
  • Privacy Policy
  • Request a Feature