1. Here in the first step we have to genarate the max and min array define that as less and more.
2. to do that we have to first initialize the mins and max array's 1 number index as 1. and generate loop till 3 to 100001 as our maximum element's ranage is 100000.
3. to generate the element's of max we have to make addition of the previous index's element and the index of that element. to generate the mins element we have to add previous element's index and the middle element of 0 index to the (i-1)th element and the difference from the previous element's index to the middle

in the code this will be:

 mins[2]=1;
        max[2]=1;
        
        for(int i=3;i<100001;i++){
            
            mins[i]=i-1+mins[ (i-1)/2 ]+mins[ (i-1)-(i-1)/2 ];
            
            max[i]=max[i-1]+i-1;
            
        }

now our mins and max are as like as :

1. max: 0 0 1 3 6 10 15 21........
2. min: 0 0 1 2 4 6 8 10......

next step we have to check the max array's (len)th index element or the len length's max array's last element is greater than c or not and mins last element from 0 to len range. if not then we have to print -1, as this have no solution.in the code part as like as this:

if( max[len]<c || mins[len]>c ){
                
                System.out.println("-1");
                continue;
                
            }

in the main function of the solution first we have to check the best cases, that the len is 0 or not and the len is 1 or not, means this is last element or not.if this is last element then we add the last element's offset(which is initially set as 1) in the answer.in the code part:

if( len==0 ){
         
         return ans;
         
     }
     
     if( len==1 ){
         
        ans.append(offset).append(" ");
         
         return ans;
         
     }

inital pivot'e index we set as 0.and set the c as the c-=(len-1) the difference of the c and the last index of the len, th lenngth array.

now have to detect the final pivot's position.that the mins first index's to half part of the range till the middle and last index's to the middle, that the mins element is greater than c or not and max element is less than c or not to find the last position of the valid condition. in the code part as like as this is:

int pivot=0;
     
     c-=len-1;
     
     while( mins[pivot]+mins[len-pivot-1]>c || max[ pivot ]+max[len-pivot-1]<c ){
         
         pivot++;
         
     }

now we have to check the last element of max and min to comapre with the constraint c-newC. in every state the newC value will be increasing.And the initial newC value is first valid element of the mins which value is less than c.in the code part:

long newC=mins[pivot];
     
     while( mins[len-pivot-1]>c-newC || max[len-pivot-1]<c-newC ){
         
         newC++;
         
     }

then we add the summation of the pivot and the initial element of the list which we set as the offset:

ans.append( (pivot+offset)+" " );

now we make a recurssive call

1. solve(pivot,newC,offset,max,mins,ans);
2. solve(len-pivot-1,c-newC,offset+pivot+1,max,mins,ans);

in the in the first call we set the len as the pivot or first valid element's of th min or max array and set the c as the difference of initial c and the 2nd half's first non valid element's number.

and finally return the ans.

to explain more clarly if we see an example for len=5 and c or constraint as 6

first we have to set the initial max and min element array, this is:

1. max: 0 0 1 3 6 10 15 21........
2. min: 0 0 1 2 4 6 8 10......

initial len: 5 initial c: 6 initial offset: 1 ans:

and in the first state c value is: 2( 6-( 5-1 )=6-4=2 )

set the initial pivot as 0 and,

now have to visit from 0 to range 4

1. min[0]+min[len-0-1]=0+4=4, and 4>2, so pivot value is 1
2. now min[1]+min[5-1-1]=0+2 =2, and 2>2 so check the next condition for max
3. max[1]+max[5-1-1]=0+3=3 and 3<2 that is false

so in the first call our pivot value is 1

now have to detect the newC value, initially that is mins[1]=0

now mins[5-1-1]=2>2-0=2 it is false and also false for max, as max[5-1-1]=3<2 this is also false.

now our newC value is also 0.and append the summation of the pivot and offset in the ans, now the ans is: 2

now make's an another recurssive call, here the initial len: 1(pivot) initial c: 0(newC) initial offset: 1(offset) ans: 2(ans )

here the len is 1 so add 1 in the ans and return it.

now it make's the another recurrsive call here initial len: 3(len-pivot-1=5-1-1=3) initial c: 2(c-newC=2-0=2) initial offset: 3 ans: 2 1

now run till 0 to 2 the same process we done at the previous.

now pivot is: 1 and offset 3

as the same reason for the mins[len-pivot-1] and max[len-pivot-1]

newC=0

and ans: 2 1 4

and now pivot is: 1 and offset: 3, and make an another recurssive call:

now initial len: 1 initial c: 0 initial offset: 3 ans: 2 1 4

as len is 1: add 3 in the ans and return it:

now ans: 2 1 4 3

and make another recurssive call now:

initial len: 1 initial c: 0 initial offset: 5 ans: 2 1 4 3

as len==1 so answer will be 2 1 4 3 5

our final ans is: 2 1 4 3 5

this is the link of full solution:

https://github.com/AmitRoy3370/HackerRank/blob/master/Lena%20Sort

sorry for bad english and make the explanation so long

element's

5.

how can we generate the array any idea please

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)

Can anybody share their approach for this problem...Basically a hint ??

This is my code, its showing TLE, Please, somebody helps me! Thanks in advance.

import sys
from functools import lru_cache
sys.setrecursionlimit(4000)   
def lena_sort(nums):

    if len(nums) <=1 :
        return 0
    
    pivot = nums[0]
    less = []
    more = []
    for i in range(1,len(nums)):
        if nums[i] < pivot :
            less.append(nums[i])
        else :
            more.append(nums[i])
        
    sorted_less = lena_sort(less)
    sorted_more = lena_sort(more)
    ans = sorted_less + pivot + sorted_more 
    
    return ans

def combinations(tmp):
    global a
    if len(tmp)==n :
        if lena_sort(tmp) == m :
            a.append(tmp)
            return 
    else :
        for i in range(n):
            if l[i] not in tmp:
                combinations(tmp+[l[i]])
      
if __name__ == '__main__':
    for _ in range(int(input())):
        n,m = map(int,input().split())
        a = []
        l = list(range(1,n+1))
        combinations([])
        if a :
            print(*a[0])
        else:
            print("-1")