HackerRank Lena Sort problem solution

In this HackerRank Lena Sort problem solution, You must solve Q queries where each query i consists of some len and c. For each query, construct an array of distinct elements in the inclusive range between 1 and 10 to power 9 that will be sorted by lena_sort in exactly c comparisons, then print each respective element of the unsorted array as a single line of len space-separated integers; if no such array exists, print -1 instead.

Input Format

The first line contains a single integer denoting q (the number of queries).
Each line i of the q subsequent lines contains two space-separated integers describing the respective values of leni (the length of the array) and ci (the number of comparisons) for query i.

HackerRank Lena Sort problem solution in Python.

#!/bin/python3

import math
import os
import random
import re
import sys

sys.setrecursionlimit(100000)

def get_min_arr(length, start):
    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]
    
    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
    
    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()))
        
        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)
        
        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)

Lena Sort problem solution in Java.

import java.io.*;
import java.util.*;

public class lena_sort extends PrintWriter {
    lena_sort() { super(System.out); }
    Scanner sc = new Scanner(System.in);
    public static void main(String[] $) {
        lena_sort o = new lena_sort(); o.main(); o.flush();
    }

    static final int N = 100000;
    int[] kk = new int[N + 1];
    int[] aa = new int[N];
    void init() {
        for (int n = 2; n <= N; n++) {
            int p = (n - 1) / 2, q = n - 1 - p;
            kk[n] = kk[p] + kk[q] + n - 1;
        }
    }
    void solve(int l, int r, int a, int c) {
        int n = r - l;
        if (n == 0)
            return;
        c -= n - 1;
        int lower = -1, upper = (n - 1) / 2, p, q;
        while (upper - lower > 1) {
            p = lower + upper >> 1;
            q = n - 1 - p;
            if (kk[p] + kk[q] <= c)
                upper = p;
            else
                lower = p;
        }
        p = upper;
        q = n - 1 - p;
        aa[l] = a + p;
        int cp = (int) Math.max(kk[p], c - (long) q * (q - 1) / 2), cq = c - cp;
        solve(l + 1, l + 1 + p, a, cp);
        solve(l + 1 + p, r, a + p + 1, cq);
    }
    void main() {
        init();
        int q = sc.nextInt();
        while (q-- > 0) {
            int n = sc.nextInt();
            int c = sc.nextInt();
            if (c < kk[n] || (long) n * (n - 1) / 2 < c) {
                println(-1);
                continue;
            }
            solve(0, n, 1, c);
            for (int i = 0; i < n; i++)
                print(aa[i] + " ");
            println();
        }
    }
}

Problem solution in C++.

#include <bits/stdc++.h>

using namespace std;

vector<string> split_string(string);

vector<long long int> mx;
vector<long long int> mn;

long long int mincomp(int n);
long long int maxcomp(int n);

long long int mnc (int n) {
    //cout<<"mnc "<<n<<endl;
    if (n==1||n==0) return 0;
    if (n==2) return 1;
    int one, two;
    one=(n-1)/2;
    two=n-1-one;
    return (long long int)n-1+mincomp(one)+mincomp(two);
}
long long int mxc (int n) {
    //cout<<"mxc "<<n<<endl;
    if (n==1||n==0) return 0;
    if (n==2) return 1;
    return (long long int)n-1+maxcomp(n-1);
}
long long int mincomp(int n) {
    //cout<<"mincomp "<<n<<endl;
    if (mn.size()<=n) {
        for (int i=mn.size();i<=n;i++) mn.push_back(mnc(i));
    }
    return mn[n];
}
long long int maxcomp(int n) {
    //cout<<"maxcomp "<<n<<" "<<mx.size()<<endl;
    if (mx.size()<=n) {
        //cout<<"maxcomp expanding mx"<<endl;
        for (int i=mx.size();i<=n;i++) mx.push_back(mxc(i));
    }
    //cout<<"maxcomp returning "<<endl;//<<mn[n]<<endl;
    return mx[n];
}

void reverselena(int l,int c,int add, int *arr) {
    //cout<<"rl "<<l<<" "<<c<<" "<<add<<endl;
    if (l==1) {*arr=1+add; return;}
    if (l==2) {*arr= 2+add; *(arr+1)=1+add; return;}
    if (c==maxcomp(l)) {
        //cout<<"rl max"<<endl;
        for (int i=0;i<l;i++) *(arr+i)=l-i+add;
        return;
    }
    if (c==mincomp(l)) {
        //cout<<"rl min"<<endl;
        *arr=add+(l+1)/2;
        reverselena((l-1)/2,mincomp((l-1)/2),add,arr+1);
        reverselena(l-1-(l-1)/2,mincomp(l-1-(l-1)/2),add+(l+1)/2,arr+1+(l-1)/2);
        return;
    }
    int newc=c-(l-1);
    //cout<<"rl here"<<endl;
    for (int i=0;i<l;i++){
        //cout<<"add up to "<<newc<<" "<<maxcomp(l-i-1)<<" + "<<mincomp(i)<<" or "<<maxcomp(i)<<endl;
        if (newc>=mincomp(i)+maxcomp(l-1-i)&&newc<=maxcomp(i)+maxcomp(l-1-i)){
            reverselena(i,newc-maxcomp(l-1-i),add,arr+1);
            //if (one[0]==0) break;
            reverselena(l-1-i,maxcomp(l-1-i),i+1+add,arr+1+i);
            //if (two[0]==0) break;
            *arr=i+1+add;
            return;
        }
    }
    for (int i=0;i<l;i++){
        if (newc>=mincomp(i)+mincomp(l-1-i)&&newc<=maxcomp(i)+mincomp(l-1-i)){
            reverselena(i,newc-mincomp(l-1-i),add,arr+1);
            //if (one[0]==0) break;
            reverselena(l-1-i,mincomp(l-1-i),i+1+add,arr+1+i);
            //if (two[0]==0) break;
            *arr=i+1+add;
            return;
        }
    }

    cout<<"failed for l, c, add "<<l<<" "<<c<<" "<<add<<endl;
    return;
}

int main()
{
    int q;
    cin >> q;
    cin.ignore(numeric_limits<streamsize>::max(), 'n');

    for (int q_itr = 0; q_itr < q; q_itr++) {
        string lc_temp;
        getline(cin, lc_temp);

        vector<string> lc = split_string(lc_temp);

        int l = stoi(lc[0]);

        int c = stoi(lc[1]);

        // Write Your Code Here
        long long int maxcomparisons=maxcomp(l);
        long long int mincomparisons=mincomp(l);
        //cout<<mincomparisons<<" "<<maxcomparisons<<endl;
        if (c>maxcomparisons||c<mincomparisons) cout<<-1<<endl;
        else {
            //cout<<"here 1"<<endl;
            int* answer=new int[l];
            //cout<<"here 2"<<endl;
            reverselena(l,c,0,answer);
            if (answer[0]==0) cout<<-1<<endl;
            else {
                for (int i=0;i<l;i++) cout<<answer[i]<<" ";
                cout<<endl;
            }
            delete[] answer;
        }
        
    }

    return 0;
}

vector<string> split_string(string input_string) {
    string::iterator new_end = unique(input_string.begin(), input_string.end(), [] (const char &x, const char &y) {
        return x == y and x == ' ';
    });

    input_string.erase(new_end, input_string.end());

    while (input_string[input_string.length() - 1] == ' ') {
        input_string.pop_back();
    }

    vector<string> splits;
    char delimiter = ' ';

    size_t i = 0;
    size_t pos = input_string.find(delimiter);

    while (pos != string::npos) {
        splits.push_back(input_string.substr(i, pos - i));

        i = pos + 1;
        pos = input_string.find(delimiter, i);
    }

    splits.push_back(input_string.substr(i, min(pos, input_string.length()) - i + 1));

    return splits;
}

Problem solution in C.

#include <assert.h>
#include <ctype.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stddef.h>
#include <stdint.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_L 100000

long *g, *h;

void init() {
    g = malloc((MAX_L+1) * sizeof(long));
    h = malloc((MAX_L+1) * sizeof(long));
    
    g[0] = 0; h[0] = 0;
    for (int i=1; i<MAX_L+1; i++) {
        int l = (i - 1)/2, r = i - 1 - l;
        g[i] = i - 1 + g[l] + g[r];
        h[i] = h[i-1] + i - 1;
    }
}

int search(int n, int c) {
    int l = 1, r = (n+1)/2;
    while (l+1<r) {
        int m = (l+r) / 2;
        if (g[m-1] + g[n-m] + n - 1 > c) {
            l = m;
            continue;
        }
        if (h[m-1] + h[n-m] + n - 1 < c) {
            r = m;
            continue;
        }
        return m;
    }
    if (g[l-1] + g[n-l] + n - 1 <= c && c <= h[l-1] + h[n-l] + n - 1) return l;
    if (g[r-1] + g[n-r] + n - 1 <= c && c <= h[r-1] + h[n-r] + n - 1) return r;
    return -1;
}

int pointer;
void fill(int* arr, int n, int c, int offset) {
    if (n == 0) return;
    int m = search(n, c);
    if (m == -1) {
        return;
    }
    arr[pointer++] = m + offset;
    int c1, c2;
    if (g[m-1] + h[n-m] + n - 1 < c) {
        c2 = h[n-m];
        c1 = c - (n - 1) - c2;
    } else {
        c1 = g[m-1];
        c2 = c - (n - 1) - c1;
    }
    fill(arr, m-1, c1, offset);
    fill(arr, n-m, c2, m + offset);
}

int main()
{
    init();
    int q; scanf("%d", &q);
    for (int q_itr = 0; q_itr < q; q_itr++) {
        int l, c; scanf("%d%d", &l, &c);
        if (search(l, c) == -1) {
            printf("-1n");
        } else {
            int *arr = malloc(l * sizeof(int));
            pointer = 0;
            fill(arr, l, c, 0);
            for (int i=0; i<l-1; i++) printf("%d ", arr[i]);
            printf("%dn", arr[l-1]);
        }
    }
    return 0;
}