Lena Sort
Lena Sort
+ 0 comments  Here in the first step we have to genarate the max and min array define that as less and more.
 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.
 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 (i1)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]=i1+mins[ (i1)/2 ]+mins[ (i1)(i1)/2 ]; max[i]=max[i1]+i1; }
now our mins and max are as like as :
 max: 0 0 1 3 6 10 15 21........
 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=(len1) 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=len1; while( mins[pivot]+mins[lenpivot1]>c  max[ pivot ]+max[lenpivot1]<c ){ pivot++; }
now we have to check the last element of max and min to comapre with the constraint cnewC. 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[lenpivot1]>cnewC  max[lenpivot1]<cnewC ){ 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
 solve(pivot,newC,offset,max,mins,ans);
 solve(lenpivot1,cnewC,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:
 max: 0 0 1 3 6 10 15 21........
 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( 51 )=64=2 )
set the initial pivot as 0 and,
now have to visit from 0 to range 4
 min[0]+min[len01]=0+4=4, and 4>2, so pivot value is 1
 now min[1]+min[511]=0+2 =2, and 2>2 so check the next condition for max
 max[1]+max[511]=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[511]=2>20=2 it is false and also false for max, as max[511]=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(lenpivot1=511=3) initial c: 2(cnewC=20=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[lenpivot1] and max[lenpivot1]
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.
+ 0 comments how can we generate the array any idea please
+ 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 divideandconquer 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 divideandconquer 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 divideandconquer with a length0 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 nonrecursive function (
get_min_arr
). The recursive solution is also kind of straightforward but we can turn it into a nonrecursive 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, ..., n1 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)
+ 0 comments Can anybody share their approach for this problem...Basically a hint ??
+ 0 comments 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")
Sort 20 Discussions, By:
Please Login in order to post a comment